带码农看论文：MapReduce: Simplefied Data Processing on Large Clusters
导语
本次看的论文是<MapReduce: Simplefied Data Processing on Large Clusters>, 这篇论文描述了Google“三驾马车”之一的MapReduce。MapReduce 是一个为了简化海量数据处理而提出的编程模型与对应框架实现，Hadoop为其开源实现，是整个大数剧处理的基础。
摘要
MapReduce 是一个用来处理和生成海量数据的编程模型以及一个对应实现。用户指定Map和Reduce函数：Map 处理一个 Key/Value 对，生成内部的 Key/Value 对集合,Reduce 合并所有相关Key的Key/Vaule对集合。
按照这种函数式风格编写的程序会被自动并行化，调度在大规模的由普通机器组成的集群上执行。运行时系统负责内部的具体逻辑：如何将输入数据分区；如何调度程序；处理机器故障；管理必须的机器之间的通信。这可以让没有并行编程和分布式编程经验的程序员很容易的利用大规模分布式系统的资源。
MapReduce的实现运行在由普通机器组成的大规模集群，而且是高可拓展性的：一个典型的MapReduce在成百上千的机器上计算处理TB级别的数据。编程者会发现这个系统很容易去使用：成百上千个MapReduce程序已经被实现，上千个任务每天在Google的集群上执行。
编程模型
MapReduce 的编程模型很简单，计算任务接收key/value对集合，产生一个key/value对集合，用户关心的只是如何实现两个无副作用的函数：Map和Reduce。
Map，用户编写的函数，接收一个输入Key/Value对，产生一个内部的Key/
Value对集合。MapReduce库会把内部Key/Values对按照Key来聚合，然后传递给Reduce函数。
Reduce，也由用户编写，接收一个内部Key和这个Key对应的Value集合，它合并那些value来构建一个更小的Value集合。一般每个Reduce只会有0个或者1个输出。内部Values集合一般通过迭代器提供给用户的Reduce函数，这可以让用户处理超过内存限制的Values集合。
举个例子
接着，论文举了一个精典的例子Words Count：给定文档集合，输出每个单词的个数。
在MapReduce中，Map 弹出每个单词和该单词的出现次数，Reduce对一个特定的单词，计算总数。
类型
MapReduce 程序的类型如下描述：
Map (k1, v1) -> list(k2, v2)
Reduce (k2, list(v2)) -> list(v2)
在google的C++实现中，只传递字符串，由用户的程序来解析。
接着，论文介绍了几个更复杂的例子：
1. Distributed Grep
2. Count of URL Access Frequency
3. Reverse Web-Link Graph
4. Term-Vector per Host
5. Inverted Index
6. Distributed Sort
实现
文章第三章主要讲述了MapReduce如何实现，包括：执行流程，master的数据结构，以及如何容灾，本地性，任务粒度，备份任务。
Map 被分布在多个机器上，通过自动的对输入数据分区为M片，输入分片可以被不同的机器并行处理。Reduce通过对内部Key空间使用一个分区函数（例如,hash(key) % R）分区为R片来分布式。R由用户指定。
Figure 1展示了MapReduce的操作流程，当用户程序调用 MapReduce时，执行如下动作：
用户程序中的MapReduce库切割输入文件为M份，一般为16~64MB每份，然后在机器上启动多个程序副本。
副本之一成为master，其它为worker，被分配任务。master选择一个空闲worker，为其分配一个map/reduce任务。
分配了map task的worker读取对应输入文件的分片。它解析输入文件的Key/Value对，传递给用户定义的Map函数，Map产生的内部Key/Value对缓存在内存（内存放不下怎么办？）。
缓存的key/value对周期的写入到本地磁盘，分区到R个区。这些缓存的key/value对在本地磁盘的位置都传回给master，master负责转发这些位置给reduce worker。
当一个 reduce worker 被master通知这些位置时，它使用RPC去读取map worker的磁盘上的key/value对。当reduce worker读完所有内部key/value，它根据内部key来排序，所有相同的key的都聚合在一起。如果内部数据过大，就使用外部排序。
Reduce worker迭代排序的内部数据，对于每一个不同的内部key，它传递key和对应的values集合到用户的Reduce函数。Reduce函数的输出添加到该分区的最终输出文件。
当所有map 任务和reduce 任务都完成，master调起用户程序，重新返回到用户代码。
对于每个map task和reduce task，master 保存它们的状态（idle，in-process 或者 completed），以及每个worker机器的标识。
容灾
MapReduce 如何容灾是其最重要的部分，对于故障我们可以分为 worker故障和master故障，worker故障又可以分为 map worker和reduce worker。
Worker 故障
Master 通过心跳的机制来检测worker故障，如果超过一定时间没有回应，master就认为worker故障，worker上的处于 completed 状态的map task都重新标记为最初的idle状态，让其可以重新调度到其它机器 。Worker 上的处于 in-progress 状态的map/reduce task也被重置为idle。
已经完成的map task被重新执行的原因是因为它的输出文件写在本地磁盘（为什么不写到gfs）。已经完成的reduce task不用重新执行，因为它将结果写到gfs。
所以，对于worker故障，MapReduce的处理方式就是重新执行，足够简单高效。
Master 故障
论文中介绍，当前实现(2006年时）是中止MapReduce计算任务，Client可以检查执行情况，并决定是否重试。论文也提到，可以简单的通过周期写快照的方式来处理master故障。
为了应对长尾现象（一个特别慢的子任务拖慢整个任务），MapReduce提供了 Backup Task的机制：当一个MapReduce接近结束时，master 对还处理 in-progress状态的task额外的调度备份执行，当primary和backup中一个执行成功就标记成功。
后记
1。 Mapreduce 论文是将map的结果写到本地，为什么不直接写到gfs？hadoop的对应实现是怎样的？
2。 “任务序列化”是如何实现的？
2。 文章致谢里面提到“感谢xx开发集群管理系统”，论文没有透露关于这方面的信息。
。