分布式数据处理——MapReduce

为什么会有 MapReduce 的出现呢？

Jeffery Dean 想设计一个新的抽象模型，封装并行处理、容错处理、本地化计算、负载均衡的细节，还提供了一个简单而强大的接口。然后就出现了 MapReduce。

MapReduce这种并行编程模式思想最早是在1995 年提出的。

与传统的分布式程序设计相比，MapReduce封装了并行处理、容错处理、本地化计算、负载均衡等细节，还提供了一个简单而强大的接口。

MapReduce把对数据集的大规模操作，分发给一个主节点管理下的各分节点共同完成，通过这种方式实现任务的可靠执行与容错机制。

编程模型

从图中，可以很清晰的看出来 Map 函数是对原始数据进行指定操作

Reduce 函数是将每个 Map所产生的一部分结果进行合并操作

Map: (in_key, in_value) -> {(key j , value j ) | j = 1…k}
Reduce: (key, [value 1 ,…,value m ]) -> (key, final_value)

Map输入参数：in_key和 in_value，它指明了Map需要处理的原始数据

Map输出结果：一组 < key,value >对，这是经过Map操作后所产生的中间结果

Reduce输入参数：（key,[value 1 ,…,value m ]）

Reduce工作：对这些对应相同key的value值进行归并处理

Reduce输出结果：（key, final_value），所有Reduce的结果并在一起就是最终结果

实现机制

1. MapReduce函数首先把输入文件分成M块
2. 分派的执行程序中有一个主控程序Master
3. 一个被分配了Map任务的Worker读取并处理相关的输入块
4. 这些缓冲到内存的中间结果将被定时写到本地硬盘，这些数据通过分区函数分成R个区
5. 当Master通知执行Reduce的Worker关于中间< key,value >对的位置时， 它调用远程过程，从Map Worker的本地硬盘上读取缓冲的中间数据
6. Reduce Worker根据每一个唯一中间key来遍历所有的排序后的中间数据，并且把key和相关的中间结果值集合传递给用户定义的Reduce函数
7. 当所有的Map任务和Reduce任务都完成的时候，Master激活用户程序

由于MapReduce在成百上千台机器上处理海量数据，所以容错机制是不可或缺的。总的来说，MapReduce通过重新执行失效的地方来实现容错。

Master失效

Master会周期性地设置检查点（checkpoint），并导出Master的数据。一旦某个任务失效，系统就从最近的一个检查点恢复并重新执行。由于只有一个Master在运行，如果Master失效了，则只能终止整个MapReduce程序的运行并重新开始。

Worker失效

Master会周期性地给Worker发送ping命令，如果没有Worker的应答，则Master认为Worker失效，终止对这个Worker的任务调度，把失效Worker的任务调度到其他Worker上重新执行。

案例分析: 怎样通过MapReduce完成排序工作，使其有序（字典序）呢？

1. 第一个步骤: 对原始的数据进行分割（Split），得到N个不同的数据分块 。

2. 第二个步骤：对每一个数据分块都启动一个Map进行处理。采用桶排序的方法，每个Map中按照首字母将字符串分配到26个不同的桶中。

3. 第三个步骤：对于Map之后得到的中间结果，启动26个Reduce。按照首字母将Map中不同桶中的字符串集合放置到相应的Reduce中进行处理。