MIT课程原文链接：https://pdos.csail.mit.edu/6.824/labs/lab-mr.html
中文视频课程链接：https://www.bilibili.com/video/av91748150?p=3&spm_id_from=pageDriver
MapReduce论文英文原版： https://pdos.csail.mit.edu/6.824/papers/mapreduce.pdf
看本文前最好先自己做一遍

任务理解

这是论文中讲解MapReduce的流程图
输入数据以文件进入系统，先使用所有的Worker运行Map任务，拆分原任务然后产生了一些中间数据（intermediate），然后再使用Worker运行Reduce任务，利用中间体产生最终输出，Master进程用于分配任务，调度各个Worker。Reduce任务要在map任务都完成以后才开始执行，Reduce传入中间体中某个key的所有value，一般只返回一个字符串或很少的数据。
输入数据能产生中间体，说明原来的任务是可以拆分的（类似快排的分而治之思想），也就才有写成分布式的可能性。如果原问题不能拆，MapReduce就无从谈起，当然也可以拆分多次，比如一些需要迭代的算法，通过多次迭代最终结果来提高精度。
中间体由Master均匀地分配给各个Reduce任务，每个Reduce都要整合这些中间体中每个Key相同的内容，令中间体的个数减少，直到整合出最终结果。
对于输入数据以什么形式进入系统，原任务如何拆分，中间体如何保存和传输，Master和Worker之间如何调度和通信，中间体入伙转化为最终输出，这些都是设计层面的考虑，没有正确答案。

任务总览和说明

Lab1要求我们实现一个和MapReduce论文类似的机制，也就是数单词个数WordCount（MR代码已给出在src/mrapps/wc.go）
用于输入的文件是src/main/pg-*.txt文件，每个文件都是一本电子书，非常长。我们的任务是统计出出现过的所有单词和出现次数。

单机实现

如果不写成分布式，这个任务非常简单，一个实现在src/main/mrsequential.go中。
将所有的文章中的单词分出，存到一个KV数组中。然后对他们排序，从而相同单词在数组中连续的出现在一起。便利这个数组，统计单词个数就很简单了。

我们的任务

测试时，会启动一个master和多个worker，也就是运行一次mrcoordinator.go,多次mrworker.go.
master进程会启动一个rpc服务器，每个worker进程通过rpc机制向master要任务，任务分为Map、Reduce、Exit等类型，具体如何分配取决于master的实现。
每个单词的和它的出现次数以Key-Value键值对形式出现，Map进程将每个单词的出现次数分离出来，并且每次都标位1次。很多单词在电子书中（pg-*）多次出现，也就产生了很多相同的键值对。想通的单词应由Reduce进程处理，处理方式和mrsequential.go中类似，对KV组按Key排序，令单词处于数组的相邻位置，再统计单词个数。最终，每个reduce进程都有一个输出，合并这些输出就是WordCount结果。
这类需要注意一下，一开始传入的nReduce就是reduce任务的数量，每个map任务结束后拆分成nReduce个中间文件如mr-map任务id-reduceid，这样如果我们要处理3个文件，就会有3*nReduce个文件，reduce任务则处理reduceid相同的文件，这里需要注意一下reduce任务处理完直接输出mr-out-reduceID就可以了，不需要像mrsequential里一样把所有的输出合起来排序再放到一个文件中，test-mr.sh里会用sort命令对out文件的内容进行排序，只要你的结果是正确的就可以通过。

交换信息

Master和Worker之间通过rpc交换信息，可有如下结构体

type FuckArgs struct {
        // Worker自己的id
    WorkerID int
}

type FuckReply struct {
    // 任务类型:[1] Map任务, [2] Reduce任务
    TaskType int
    // Reduce任务数量
    ReduceCount int
    // Map任务文件名
    MapName string
    // Map任务ID
    MapID int
    // Reduce任务ID
    ReduceID int
    // Reduce任务用的,map任务数量
    MapTaskCount int
    // 是否退出Worker
    Exit bool
}

大致上的设计可能差不多，在我的设计里Worker一开始要执行一个register，在Master中登记后拿到一个自己的ID，如果Worker挂了（某个任务超时）就可以直接删除此Worker

定义Map任务

一个Map任务就是把一个文件拆分成KV键值对，并且将这些键值对分配给特定的Reduce任务，会有多个Map任务同时进行，Master要给Worker分配一个Map任务，就要将任务设为Working，避免重发，然后另外一个协程用来检查任务超时，超时的话就当Worker挂了。

// Map任务结构
type mapTask struct {
    id       int
    name     string
    working  bool
    done     bool
    workerID int
}