分布式数据处理MapReduce

  MapReduce是google提出的一个软件架构，是一种处理海量数据的并行编程模式，用于大规模数据集（通常大于1TB）的并行运算。

MapReduce封装了并行处理，容错处理，本地化计算，负载均衡等细节，还提供了一个简单而强大的接口。

MapReduce把对数据集的大规模操作，分发给一个节点管理下的哥哥节点共同完成，通过这种方式实现任务的可靠执行与容错机制。在每个时间周期，主节点都会对分节点的工作状态进行标记，一旦分节点状态标为死亡状态，则这个节点的所有任务都会分配给其他节点重新执行。

1.MapReduce的编程模型

简单的说，Map函数就是对一部分原始数据进行指定的操作。Map之间是并行化的。Reduce操作就是对每个Map所产生的一部分中间结果进行合并操作，每个Reduce所处理的Map中间结果是不交叉的，所有Reduce产生的中间结果经过简单链接就形成了完成的结果集，因此Reduce也可以在并行环境下执行。

两个主要函数

Map:(in_key,in_value) –>>{(key_j,value_j)|j=1…k}

Reduce:(key,[value_1,value_2,…value_m])->>(key,final_value)

2.MapReduce实现机制

用户程序条用MapReduce函数后，会引起下面的操作过程

MapReduce函数首先把输入文件分成M块，每块大概在16-64MB（可以通过参数决定），接着在集群的机器上执行分派处理程序

 

这些分派的执行程序中有一个程序比较特别，它是主控程序Master。剩下的执行程序都是作为Master分派工作的Worker（工作机）。总共有M个Map任务和R个Reduce任务需要分派，Master选择空闲的Worker来分配这些Map或Reduce任务。

 

一个被分配了Map任务的Worker读取并处理相关的输入块。它处理输入的数据，并且将分析出<key,value>对传递给用户定义的Map函数。Map函数产生的中间结果<key，value>对暂时缓冲到内存中

 

这些缓存到内存的中间结果将定时写到本地硬盘，这些数据通过分区函数分成R个区。中间结果在本地硬盘的位置信息将发送回Master，然后Master负责把这些位置信息传送给Reduce Worker。

 

当 Master通知执行Reduce的Worker关于中间<key，value>对的位置信息时，它条用远程过程，从Map Worker的本地硬盘上读取缓冲的中间数据。当Reduce Worker读到所有的中间数据，它就使用中间key进行排序，这样可使相同的key的值都在一起。因为有许多不用的key的Map都对用相同的 Reduce任务，所以排序是必须的。如果中间结果集过于庞大，那么就需要使用外排序。

 

Reduce Worker根据每一个唯一中间的key来遍历所有排序后的中间数据，并且把key和相关的中间结果值集合传递给用户定义的Reduce函数。Reduce函数的结果写到最终的一个输出文件。

 

当所有的Map任务和Reduce任务都完成的时候，Master激活用户程序。此时MapReduce返回用户程序的调用点。

注：MapReduce通过重新执行失效的地方来实现容错。