Mapreduce小结

读完mapreduce论文小结一下。

1.MapReduce是一个编程模型，封装了并行计算、容错、数据分布、负载均衡等细节问题。输入是一个key-value对的集合，中间输出也是key-value对的集合，用户使用两个函数：Map和Reduce。

Map函数接受一个输入的key-value对，然后产生一个中间key-value 对的集合。MapReduce库把所有具有相同中间key值I的中间value值集合在一起后传递给reduce函数。

Reduce函数接受一个中间key的值I和相关的value值的集合，合并这些value值，形成一个较小的value值的集合。

对输入的key-value的理解：这里的key-value是概念上的，很泛型的，比如key是一个文件名，value是其内容。而map产生的key-value对不同于其输入的key-value类型。

2.工作流程

程序调用mapreduce后，mapreduce库会将输入文件分成m个数据片段。由master将m个map任务和r个reduce任务分配给空闲的worker机器。被分配了map任务的worker程序读取相关的数据片段，从中解析出key-value对，然后传递给map函数，由map函数生成中间的key-value对，缓存在内存中。缓存的key-value对周期性地写入到本地磁盘上，并按划分规则分到r个区域中。缓存的key-value对在本地磁盘的存储位置发给master，master再把它发给reduce worker。reduce worker接收到master发来的位置信息后，使用rpc从map worker所在机器的磁盘上读取这些缓存数据，当读取了所有的中间数据后，通过对key排序使得具有相同key值的数据聚合在一起。然后遍历排序后的数据，对于每一个中间key值，reduce worker将该key与之相关的value值集合传递给reduce函数，reduce函数的输出追加到本reduce分区的输出文件中。所有map和reduce任务完成之后，master唤醒用户程序。输出的结果存在r个文件中。

问题：input file在GFS文件系统上，可能分布于多个chunk上，mapreduce将其分成m片，一片（16M-64M），一个chunkblock（64M）。mapreduce的这种划分与GFS的chunk大小是否存在关系？

一个worker可以同时兼备map和reduce任务吗？

Map或reduce任务完成后，是worker report to master还是master主动检测？

3.容错机制

master主动检测worker的状态，周期性地ping每个worker，一定时间内如果没有收到worker返回的信息（返回什么有用信息？），master将其标记为失效。所有由该失效的worker负责的任务（包括map和reduce）重设为初始的idle状态，等待重新调度。

worker故障时，即便已经完成的map任务也要重新执行，而完成的reduce任务就不需要重新执行，因为它的结果直接写入了全局的文件系统上（GFS，因为有其他副本？）。

map任务重新执行时，master要向所有的reduce worker通告。

master容易出现单点故障，周期性地保存检查点以便恢复，或者故障时终止mapreduce，报错给用户程序。

4.存储位置

mapreduce在分配map任务时会考虑GFS的文件副本位置。尽量将一个map任务分配在包含相关输入数据副本的机器上执行；不能如此也要尽可能在存有数据副本的机器附近的机器上执行。

5.当一个mapreduce操作接近完成的时候，master调度backup任务进程来执行剩下的in-progress状态的任务。不管是最初的执行进程还是backup任务进程完成了任务，就把这个任务标记为已完成。这种机制有助于减少大任务的处理时间。

问题：计算每个任务的时候为何不采用并行执行而只是后期并行呢？

Backup任务进程与原来的初始执行进程是属于同一woker，还是由master重新分配一个？我认为是后者

6.分区函数

默认是使用hash方法在中间key上把数据划分到R个区域。用户可以根据需要自己提供分区函数。

7. Combiner函数

Combiner函数在每台执行Map任务的机器上都会被执行一次，将本地记录合并一次再发给reduce worker。其效用类似于reduce函数。

mapreduce库的使用：

用户编写代码实现map和reduce函数，然后使用输入和输出文件的名字、可选的调节参数来创建一个符合MapReduce模型规范的对象，然后调用MapReduce 函数，并把这个规范对象传递给它。

作者: 绿豆芽33 发表于 2011-08-31 23:13 原文链接

评论: 2　查看评论　发表评论

最新新闻：
· 马云：阿里巴巴要做21世纪数据分享平台(2011-09-10 17:48)
· Facebook聘用OpenAppMkt创始人 负责斯巴达项目(2011-09-10 17:44)
· 首个计算机Bug的由来(2011-09-10 14:32)
· 亚马逊应当收购Hulu的六大原因(2011-09-10 14:32)
· Groupon数百员工集体诉讼索要3年加班费(2011-09-10 14:31)

编辑推荐：从微博的改版谈网页重构

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库