这篇文章主要介绍 mit6.824 lab1 的实现思路，在开始动手写 lab1 之前，建议先看看课程视频、论文，实验文档还有熟悉一下 go 的基本语法。所有资料都在文末的参考资料中了。也可以看看我的上一篇文章，是一些总结 juejin.cn/post/728260…
如果你已经对 MapReduce 有一定的理解了，并且会 go的基本语法，那就和我一起食用 lab1 吧！
执行流程
在 lab1 中，整个程序的执行流程大概如下：
下面我们来对各个 part 进行详细解释
协调器（coordinator）
在 MapReduce 模型中， master 节点主要负责
具体到 lab1 的代码实现，我们对 coordinator.go（也就是上面提到的 master 节点）所需要做的东西其实就只有（这里暂时不讨论 crash test）
func MakeCoordinator(files []string, nReduce int) *Coordinator
func (c *Coordinator) PollTask(args *TaskArgs, reply *Task) error
工作节点（worker）
在 MapReduce 模型中，任务的执行可以用一个成语概括 —— ”分而治之“。因此，worker 节点分为两种，map 节点负责”分“，reduce 节点负责”治“。
- 在 word count 这个场景下，一个输入文件对应了一个 map 节点，那么 map 节点需要做的事情就是将输入的文件切分成一个一个的 KV 结构，例如 input.txt 中有内容 “ hello world hello MapReduce ” ,那么 map 节点从文件中读取到数据之后，把这些数据给到用户定义的 map 函数，map 函数将它们分成 “ “。然后 map 节点再把这些缓存数据分成R块（对应 R 个 reduce 节点），并写入本地磁盘中。（map 函数由用户定义后会加载到 map 节点中，由 map 节点自行调用）
- 在 word count 这个场景下，reduce 节点需要读取 ，map 节点产生的中间数据，通过
shuffle()函数将 key 相同的键值对排在一起，并转化成 的格式，调用用户定义的 reduce 函数，reduce 函数产生的数据将写入最终的 out 文件中。 - 例如，map 节点产生的数据为 “ “，通过
shuffle()会排序成 “ ”，再转化成 “ ” ，调用 reduce 函数，reduce 函数完成 word count 的操作，输出 “ ”，写入输出文件。
具体到 lab1 的代码实现，我们对 worker.go 所需要做的工作有：
完成func Worker(mapf func(string, string) []KeyValue,reducef func(string, []string) string) 函数，不断从 master 节点获取任务并执行，直到 master 通知任务已经完成
为各种任务编写 doTask 方法，例如 func DoMapTask(mapf func(string, string) []KeyValue, response *Task)
编写callDone() 方法，通知主节点，当前分配的任务已经完成。
各个节点的数据结构
在了解了各个节点的工作之后，我们可以根据这些需求来编写 master 节点和 task 的结构
coordinator
- 为了识别各个节点，我们需要在 coordinator 中创建一个自增 id，在每个任务被分配的时候，将这个 id 分配给任务，这样就能赋予每个任务唯一的 id；
- map 节点和 reduce 节点的输入都是 master 节点分配的，因此需要一个
files []string来存储输入 - 为了让 master 知道各个节点的工作状态，需要一个
TaskMap map[int]*Task来存储所有任务 - 为了表示任务的执行阶段（map/reduce/done），我们要定义一个枚举
Phase Phase - 为了知道初始化 reduce 节点的数量，还需要一个属性
ReducerNum int来接收用户的配置 - 为了将任务分配给节点，需要两个 chan 来实现 master 和 worker 之间的通信
TaskChannelReduce chan *Task // Reduce 任务
TaskChannelMap chan *Task // Map 任务
Task
- 任务的唯一标识 taskId，由 master 分配
TaskType TaskType，任务的类型FileSlice []string，输入的文件ReducerNum int，map 节点的输出需要根据 reduce 节点的数量决定输出到几个文件中State TaskState,该任务的状态（工作中/已经完成/等待分配）StartTime time.Time，为了 crash 做准备，这里先不讲。
Crash 测试
经过上面的一顿操作，我们已经跑通了 MapReduce 的大部分流程，这时候执行 test-mr.sh 去测试，你会发现大部分 test 可以通过，但还有一个 crash test，这又是什么玩意？我们去看看lab的文档
The coordinator can't reliably distinguish between crashed workers, workers that are alive but have stalled for some reason, and workers that are executing but too slowly to be useful. The best you can do is have the coordinator wait for some amount of time, and then give up and re-issue the task to a different worker. For this lab, have the coordinator wait for ten seconds; after that the coordinator should assume the worker has died (of course, it might not have).
说人话就是，一个任务的执行时间可能会出现异常（时间过长），但 coordinator 没有办法准确的识别出是因为该 worker 节点崩溃了还是只是因为一些别的原因导致 task 完成需要的时间变长了，因此在这个 lab 中我们可以让 coordinator 每隔一段时间去判断任务有没有完成，如果没有完成就任务改节点崩溃了，回收这个任务，为这个任务重新分配一个 worker。
这个时候， Task 结构中的 StartTime 就有用武之地了，我们可以在初始化 coordinator 的时候同步开启一个crash探测协程，将超过10s的任务都回收，放回 chan中，等待 worker 重新请求这个任务。
PASS TEST
-
至此，lab1 的内容就全部做完啦！如果不出意外的话，执行
test-mr.sh进行测试，你就可以看到下面的输出啦！（虽然一般都会出意外，比如我就因为判断条件写错导致 map 任务还没有执行完就开启了 reduce 任务，最后统计出来的单词数量全都变少了）
-
在这里我没有给出具体的代码实现，读者如果需要可以去参考github仓库（地址在文末）。希望大家都早日看到 PASSED ALL TEST ! ! !
参考资料
-
实验文档：pdos.csail.mit.edu/6.824/labs/…
-
论文
- 原文：pdos.csail.mit.edu/6.824/paper…
- 翻译：www.cnblogs.com/fuzhe1989/p…
-
课程视频：
- 英文：www.youtube.com/watch?si=ij…
- 中翻：www.bilibili.com/video/BV1x7…
-
大佬博客：blog.csdn.net/weixin_4593…
-
go 教程：
- 视频教程：www.bilibili.com/video/BV1tP…
- Go 语言圣经：docs.hacknode.org/gopl-zh/ind…
- the-way-to-go：github.com/unknwon/the…
-
仓库地址： github.com/warr99/mit6… （欢迎 star）
