image.png

Map：拆解的过程
Reduce：组合的过程

image.png

image.png

Worker和Master是同等级的，Worker有负责Map的，也有负责Reduce的；
Master主要负责任务的分配

image.png

执行过程概述：

1.MapReduce库将输入文件拆分为M个分片。典型大小为16MB to 64 MB

2.Master分配工作，将M个map任务和R个reduce任务进行分配。选择闲置的workers分给每一个worker一个map或reduce任务

3.被分配map任务的worker将key/value处理，然后生成中间值的key/value

4.不时地将中间值key/value写入本地磁盘，根据分区函数(mod R)写R份。并把文件位置返回给Master，让其好通知分配reduce任务

5.当一个woker被通知分配了一个reduce任务，就使用RPC来读本地磁盘的数据，并根据key来将key/value排序

6.reduce worker遍历排序后的中间值，然后对每个unique intermediate key计数。最后生成R个output文件。（一般不需要合并，因为后续步骤可能需要做数据处理之类的）

7.当map和reduce任务都完成后，master唤醒用户程序，回到用户的代码。

文献：

Dean, Jeffrey, and Sanjay Ghemawat. "MapReduce: simplified data processing on large clusters." Communications of the ACM 51.1 (2008): 107-113.