mapreduce

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


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，也就是“云”。

参考文献：

[1]MapReduce: Simplied Data Processing on Large Clusters, Jeffrey Dean,Sanjay Ghemawat OSDI