论文笔记：MapReduce

简介

Google在2004年发表了一篇论文：MapReduce: Simplified Data Processing on Large Clusters，介绍了他们内部如何实现和使用MapReduce。

简单地说，MapReduce是一个受限的分布式并行编程模型，可用于处理和输出很大的数据集。而编写MapReduce任务的用户只需要实现两个函数：

• Map函数：输入一个key/value数据，输出一个key/value形式的中间数据集。
• Reduce函数：输入是一个中间数据的key和一个与这个key对应的value集合。它负责将这些值按照一定的规则进行“合并”。

例子——WordCount

伪代码来自Google的原始论文：

map (String key, String value) :
    // key: document name
    // value: ducument content
    for each word w in value :
        EmitIntermediate(w, "1");
        
reduce (String key, Interator values) :
    // key: a word
    // value: a list of counts
    int result = 0;
    for each v in values :
        result += ParseInt(v);
    Emit(AsString(result));

执行过程简析

MapReduce全程概览

1. MapReduce框架对输入的文件数据分成M片，每份数据的大小为16~64MB（可由用户配置）。
2. 在多台机器上开始运行User Program：包括一个master、多个map worker和多个reduce worker。
3. master主要负责map worker和reduce worker的状态管理和任务分发。
4. map worker从GFS读取分配到的文件数据，并进行相应的处理。MapReduce框架的调度会尽量使map worker运行的机器与数据靠近，以提高数据传输的效率。所以，数据传输可以是本地，也可能是网络。
5. map worker的输出缓存在内存中，并定期刷到本地磁盘上。这些中间数据的位置信息会通过心跳信息告诉master，master记下这些信息后，通知reduce worker。数据存储在本地。
6. reduce worker通过RPC从map worker读取需要的中间数据。数据通过网络传输。
7. reduce worker对中间数据进行“合并”处理后，输出结果。

容错

• map worker
  • map任务执行完成后宕机：因为中间数据存储在本地磁盘，需要重新执行。
  • map任务执行完成前宕机：需要重新执行。
• reduce worker
  • reduce任务执行完成后宕机：因为数据存储在GFS，不需要重新执行。
  • reduce任务执行完成前宕机：需要重新执行，输出文件可以覆盖原来的（文件名一样）。
• master宕机，任务失败。（master是个单点）

优化

• 局部性：MapReduce用于大数据集的处理，其主要瓶颈是网络带宽。通过优化调度，可以让执行MapReduce任务的机器尽可能靠近机器。（同一机器==>同一机架==>同一机房...）
• 任务粒度：执行MapReduce任务的过程其实就是M个Map任务+R个Reduce任务。M和R必须比机器数大很多才会有利于负载均衡。
• 备份任务：当MapReduce任务即将执行完成时，MapReduce框架会针对那些还在执行的任务，启动一个对应的备份任务。之后，只要主任务或备份任务执行完成，MapReduce任务就完成了。这样可以有效避免整个MapReduce任务被少部分比较慢的机器拖死。

参考文献

• MapReduce: Simplified Data Processing on Large Clusters