大数据之 – MapReduce介绍

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

这篇文章主要依据《MapReduce:Simplified Data Processing on Large Clusters》论文介绍MapReduce的要点。

MapReduce是Google提出的一个大数据处理的编程模型。它使用map函数处理key/value健值对生成临时的key/value健值对,然后使用reduce函数将临时的key/value中相同的key对应的值合并得到最终的结果。

使用MapReduce的程序能够在一个普通机器组成的大型集群上做并行计算。

典型的计算流程

计算流程

图1 展示了一个典型的MapReduce计算流程:

大数据之 - MapReduce介绍

图1 MapReduce 计算流程

总的来说,分为Map阶段和Reduce阶段,文件包括输入文件,临时文件,输出文件。

具体步骤如下:

  1. 用户程序的MapReduce库首先将输入文件分成M块,每块大小大概在16Mbytes到64Mbytes间(可通过用户配置大小)。然后在集群中启动一批程序的副本,同时运行。
  2. 其中一个程序的角色为master,其余的程序角色为worker,由master将工作任务分配给worker。map 任务的数量为M,reduce任务的数量为R。Master挑选出空闲的worker,然后分配给他们map任务或者reduce任务。
  3. 分配到map任务的worker从相应的输入分片里读出数据,解出key/value健值对,传递key/value健值对到用户定义的map函数,由map函数产生的临时key/value健值对缓存在内存中。
  4. 缓存的key/value健值对会周期性地写入磁盘,被分区成R块。这些缓存的键值对的位置会被传递给master,master负责后续将这些位置转发给reduce worker。
  5. 当master告知reduce worker数据分片的位置后,reduce worker使用远程方法调用(RPC)读取buffer中的数据。当reduce worker读取了所有的临时数据,它会计算同一个key的发生次数。
  6. reduce worker对排好序的临时数据做递归,然后将key和临时的value发送到用户reduce函数,reduce函数的输出最终追加到该reduce分区的输出文件上。
  7. 当所有的map&reduce任务完成,master唤醒用户程序。

在成功完成后,输出文件是R个文件(每个reduce任务对应一个输出文件)。一般来说,用户没必要将这些文件整合成1个,更多的时候这些文件作为另外一个MapReduce的输入文件,或者使用其它能够处理被多个文件的输入的分布式系统。

Master数据结构

master保存了每个map任务和reduce任务的状态(idle, in-progress, completed),以及其所在的worker机器。

master也是临时文件从map任务传送到reduce任务的渠道。master保存了map任务产生的临时文件的位置和R大小,当map任务完成的时候这些数据会更新。这些信息也会增量推送给in-progress的reduce任务。

容错能力

MapReduce是为了在大量机器组成的集群中做大数据计算设计的,所以必须要考虑容错性。

  • Worker出错

master会周期性地ping worker,如果在一定时间内没有回应,master会将worker标记成failed。任何由这个worker已经完成的map任务会被重置为idle状态,任务被重新调度到别的worker做计算(已完成的map任务被重置是因为计算结果保存在出错的机器本地无法获取;已完成的reduce任务不需要被重置是因为计算结果存储在全局的文件系统中可以获取);同样的,任何在出错的worker上的in-progress状态的map或者reduce任务也会被重置成idle状态,重新被调度到别的worker做计算。

  • Master出错

master可以周期性地保存master存储的数据结构(checkpoints),如果master任务死掉,可以从保存的状态重新开始。另外,也可以不周期性存储状态,而简单地将MapReduce任务终止,重新开始计算。

  • 任务切分粒度(Task Granularity)

可以把map阶段切成M块,reduce阶段切成R块。理想情况下,M和R的个数要比worker机器的数量多很多,以便与充分利用集群的计算能力。

每个map任务会产生R个临时文件,供reduce任务计算。所以master需要存储o(M*R)个状态在内存中,master需要调度o(M+R)个任务。

下面是一组在实际过程中经常使用的数据:M=200000,R=5000,worker机器数为2000。

  • 备份任务(Backup Tasks)

在大数据计算中一个常见的问题就是‘straggler’,指的是计算显著慢于其它任务的‘拖后腿’任务。这种情况经常发生,例如某一个worker所在的机器CPU利用率特别高,磁盘问题导致读写速度特别慢,内存不足等。由于MapReduce计算的是最终结果,straggler任务会显著拖慢整个计算所用时间。

一个解决办法是,当某个MapReduce计算快结束的时候,master调度备份任务执行剩下的还没完成的任务(in-progress)。不管是主任务还是备份任务完成,这个任务都被mark成已经完成。通过多个节点同时计算,显著地提高了整个集群的吞吐量。

原文始发于:大数据之 - MapReduce介绍