CS6.8540 lab1 - MapReduce

MapReduce is a programming model and an associated implementation for processing and generating big data sets with a paradel and distributed algorithm on a cluster.

A MapReduce framework is usually composed of three operations:

1. Map: each worker node applies the map function to the local data, and writes the output to a temporary storage. A master node ensures that only one copy of the redundant input data is processed.
2. Shuffle: worker nodes redistribute data based on the output keys (produced by the map function), such that all data belonging to one key is located on the same worker node.
3. Reduce: worker nodes now process each group of output data, per key, in parallel.

Another way to look at MapReduce is as a 5-step parallel and distributed computation:

1. Prepare the Map() input – the "MapReduce system" designates Map processors, assigns the input key K1 that each processor would work on, and provides that processor with all the input data associated with that key.
2. Run the user-provided Map() code – Map() is run exactly once for each K1 key, generating output organized by key K2.
3. "Shuffle" the Map output to the Reduce processors – the MapReduce system designates Reduce processors, assigns the K2 key each processor should work on, and provides that processor with all the Map-generated data associated with that key.
4. Run the user-provided Reduce() code – Reduce() is run exactly once for each K2key produced by the Map step.
5. Produce the final output – the MapReduce system collects all the Reduce output, and sorts it by K2 to produce the final outcome.

Input and Output types of a MapReduce job:

Dataflow:

Logical view：

Example：

LAB：

In this lab you'll build a MapReduce system. You'll implement a worker process that calls application Map and Reduce functions and handles reading and writing files, and a coordinator process that hands out tasks to workers and copes with failed workers. You'll be building something similar to the MapReduce paper. (Note: this lab uses "coordinator" instead of the paper's "master".)

已有的函数：

需要关注的几个点：

• 如何将原文件转换成键值对
• 如何将键值对进行再次转换？
• 如何确定某个阶段任务完成？
• 结构体如何定义？
• 任务队列如何定义
• 中间输出如何定义
• worker 如何将自己注册给coordinator
• coordinator 如何管理 task？
• 并行性如何保证

Woker.go

下边是我对 worker 的理解：

所以对于 worker向 coordinator 发送的struct 可以这么定义：

go
type struct MessSend {
	MsgType MsgType
	TaskID int
}

go
type struct MessReply {
	MsgType MsgType
	TaskID int
	TaskFileName string
	NReduce int
}

消息的类型如下：

go
const (
		AskForTask    MsgType=itoa // worker 请求任务
		ApplyForMap
		ApplyForReduce
		MapSucess  
		MapFail
		ReduceSucess
		ReduceFail
		Shutdown
		Wait
)

woker 通过两个函数和coordinator 通信：

• 请求任务CallForTask() -> *MessReply
• 报告任务完成情况CallForReportStatus(succesType MsgType, taskID int) -> error