MapReduce 的基本原理

  MapReduce正式发表是在2004年，是在超大集群上进行高性能分布式计算的经典算法。

      MapReduce是工作在分布式的环境下的一种扩展灵活的算法，搜索引擎的公司经常会处理大量的网页，计算网页的权值，比如统计一个网页的单词数量，都是在分布式计算环境下做的。

Map指的是对原始的文档进行按照自定义的map规则进行处理，输出中间结果，reduce按照自定义的reduce规则对中间结果合并。

    比如：I am a nice boy and I work hard every day.

      Map 处理的结果：{I,1},{am,1},{a,1},{nice,1},{boy,1},{and,1},{I,1},{work,1},{every,1},{day,1}

    当然用户可以自己定义map函数来实现不同的处理。

        Reduce的结果：{I,2},{am,1},{a,1}….

    同样，用户可以自己定义reduce函数。

MapReduce的分布式计算环境中，有一台主机作为Master，其它的都是worker，就是老板和一群员工的关系。这里的worker是真正做事情的，有map worker，reduce worker，但是不一定是每台worker要么是map worker，要么是reduce worker，而是可能同时担任两个角色。

 

Map Reduce 执行过程：

1.Master 把输入文件分成M 份，通常16M – 64M每份

2.Master选择处于Idle状态的worker，assign一份给他，此时worker的角色是map worker，assign的过程很简单，就

是把这个task piece传输到worker上

3.Map worker拿到任务后读取task的内容，解析出key/value pairs，这些中间结果开始是存在worker的内存里面，周

期性的写到map worker的本地磁盘上。但是map worker产生的中间结果不是写在一个文件里，而是由partition

function分割成R个中间文件，尽量把相同的keykey/value对写在一个中间文件里。

4.当map完成task以后，会把这些partition文件在本地磁盘中的位置通知master。（只是通知位置，而不是传输文件

到master，仔细想想为什么）

5.Master接到任务完成的消息后，寻找idle状态的worker，通知他去reduce，此时的worker就是reduce worker（值得

注意的是刚刚完成任务的 map worker可能会担当reduce worker的角色），reduce worker通过RPC读取map worker

磁盘上的中间文件到本地磁盘，读完之后，reduce worker对其进行排序,如果中间文件太大，就要用外部排序。

Master并不是随便找一个worker来做reduce的，尽量让一个reduce worker做包含同样key的partition文件。

比如：map work1 包含R个partition文件，key为K1，K2.。。。。。KR，master会把所有map works产生的partition文件含有K1的尽量交给同一个reduce worker，当然这里面也有个负载平衡的问题。

6.Reduce work把合并后的结果写入一个文件，因为一个reduce worker尽量处理同一个key的partition文件，所以当

reduce worker合并完成之后，所有包含这个key的结果都在这个文件里了

7.Reduce work把合并的结果传回master

8.当所有的reduce workers都完成之后，master得到了R个结果文件（每个reduce worker一个），唤醒用户进程，

把R个结果文件交给客户程序。

优化：

1.合并函数

Map往往会产生大量的key/value对，比如1万个{a,1}，这些都要被reduce来合并，可以在reduce工作之前有合并函数对map中的key/value对进行合并。看起来，合并函数和reduce函数一样，其实还是不同的，合并函数所合并的是map本地的key/value对，产生的结果写入map的本地buffer；reduce函数合并的是来自不同map的partition文件，产生的结果传回master。

2.容错处理

Cluster的庞大集群，机器出现故障是必然的，所以master要进行容错处理。在master上会记录所有集群内或者子群内worker的状态，定期的ping 正在工作的worker，如果不通，说明这个worker死掉了，那么会把这个worker标记为down，把他上面执行的任务重新分配给另外的worker。但是如果master死掉了怎么办？因为集群内只有一个master，此时只好通知客户程序－计算失败。

3.集群内备份

如果map worker完成了工作之后，reduce处理之前，map worker死掉了，那么reduce就拿不到结果了，难道要map重新执行一遍吗？不是的，map完成之后，要把他的结果向集群内备份.

小结：分布式计算重点不是计算，而是分布式。云计算（Cloud Computing）归根结底还是分布式计算，在客户端看来，他们只需一个简单的PC，能上网即可。但是在云服务提供商，为了存储客户的数据，执行客户的计算，显然是一个分布式的Cluster，也就是“云”。

转自：http://hi.baidu.com/azuryy/blog/item/09c12bd35b94f0d9a9ec9abc.html