Google MapReduce

Execution Overview

overview

Map调用将输入数据划分成了M splits,可以并行处理;Reduce调用将中间结果分区成了R pieces,分区函数类似于hash(key) mod R。分区个数R和分区函数可以由用户指定。

如上图所示,整体执行流程如下:

  1. 用户程序里的MapReduce库首先将输入文件划分成M个(16MB-64MB),然后在一个集群里启动其他进程。
  2. 其中有一个进程是特殊的角色:master;其他的worker由master指定工作,共有M个map任务和R个reduce任务。
  3. 进行map任务的worker从文件中读取对应的split,解析KV数据并传递给用户定义的Map函数,产生的中间KV结果缓存在内存里。
  4. 中间结果数据按照分区函数被分成R个区域,周期性地写到磁盘上。他们的位置被回传给master,master负责把这些位置转发给reduce任务。
  5. 当reduce worker收到master传来的这些数据位置时,使用RPC读取这些数据。读到后,首先做一次排序(不同的key也可能分区到同一个reduce任务)。如果中间结果数据太多,会使用外排。
  6. reduce worker遍历排好序的数据,把每一个唯一的中间结果key和它对应的中间结果值(可能有多个)传给用户定义的Reduce函数,Reduce函数的输出被追加到最后的输出文件里。
  7. 当所有的map任务和reduce任务都完成了之后,master会唤醒用户程序。这时候MapReduce调用返回到用户代码。

成功执行之后,会产生R个输出文件,每个reduce任务一个。通常情况下,用户不需要合并它们,而是把它们作为下一个MapReduce调用的输入;或者让另外一个程序,处理这些分区过的文件。

flacro

Read more posts by this author.