作者：刘旭晖 Raymond 转载请注明出处

Email：colorant at 163.com

BLOG：http://blog.csdn.net/colorant/

更多论文阅读笔记 http://blog.csdn.net/colorant/article/details/8256145

关键字

MapReduce分布式计算

==目标问题 ==

大规模数据的生成，运算，处理框架

==核心思想 ==

MapReduce提出了一个功能受限的分布式计算编程模型，以此编程模型为基础，实现一个大规模分布式的可容错的分布式计算框架。在MapReduce的编程模型中，主要的运算逻辑被分为Map和Reduce两个阶段，处理和传输<key，Value>形式的数据。用户提供Map/Reduce方法的运算逻辑，MapReduce框架负责在集群上调度多个Map和Reduce方法实例的运行

 基本流程看下图就可以解释清楚：

1. 用户程序发起一个Job，在集群上启动一个Master，多个Map和Reduce任务进程
2. Master进程负责调度，分配Map和Reduce任务
3. 每个Map实例从输入文件中获取对应的数据（MapReduce框架会根据特定的算法将数据划分成分区，每个分区的数据以<Key,Value>对的形式传给一个Map实例），处理并生成中间结果<K,V>对
4. 这些中间结果排序后以特定的算法（通常是Hash(key)）分组写入本地文件中
5. 每个Reduce实例从各个节点的Map实例生成的数据中读取属于自己的分组数据，合并排序后将相同Key对应的Value以<key, list<value>>的形式交给用户提供的Reduce函数处理
6. Reduce实例生成最终结果并输出（比如写入GFS文件系统）
7. 用户程序结束返回

论文中举例了各种可以套用这种编程模型实现的案例，例如统计文本中单词出现频率，每个Map任务读入一段文本，对每个单词输出<key,1>的中间结果，Reduce任务汇总每个Key的Value，统计和累加个数，完成任务

==实现 ==

实现中需要考虑的一些细节：

容错和灾难恢复

master定期和worker进程通讯，如果发现worker失效，将重新调度对应的任务到另一个worker上执行。master方面，理论上可以Log相关调度信息，崩溃后根据Log信息恢复现场，不过基于master是单点的，任务期间崩溃可能性较小，灾难恢复机制简化为由用户程序自己重启Job

数据本地性

由于网络带宽资源的相对稀缺性，为了减少网络通讯，尽量分配Map任务到对应数据所在节点的worker上，以保证每个Map任务尽量读取本地数据。在具体的数据大小的划分上，也结合考虑底层GFS的文件块大小(64MB)，默认16M为单位划分

备份并发任务

当个别节点由于各种原因运行缓慢时，某些Map/Reduce任务可能会完成得很慢，大大超过平均任务时间。为了减少这种情况发生时对整体Job完成时间造成的影响，Master会将滞后的任务在其它worker上重复调度，任何一份任务完成都算这个任务完成，系统的关键是控制这种备份调度的时机。

灵活的框架

如果仅仅提供Map/Reduce函数入口，毕竟不够灵活，MapReduce同时提供了定制Partition分区算法，定制输入输出读写函数，提供Map阶段Combiner（在每个Map任务的输出阶段，在本地先做一次类Reduce的聚合运算，减少网络数据传输）等功能来拓展和优化应用

此外，某些情况下，任务的失败可能是由于特定记录造成的固定失败（比如算法bug，特定数据无法处理等），在个别记录的丢失不影响整体结果的情况下，MapReduce框架允许自动检测多次相同的失败，进而跳过失败记录。

提供了Counter用于统计各种运行时参数，如读取的记录数等等，由各个任务定期汇报给Master，汇总输出，便于监控和分析Job

==相关研究，项目等 ==

功能实现依赖于GFS和Google内部的一个集群任务调度框架

Hadoop项目中的MapReduce框架基本上是本论文的一个开源Java版本实现，不过其任务调度框架是内置实现的。