背景
为了解MapReduce的原理,回头读了一遍了google的论文《MapReduce: Simplied Data Processing on Large Clusters》
<strong >问题</strong>
在2000年以后,网页数量急剧增加,由于google平时要编写很多程序和框架来处理大量的row data:爬到的文件、网页请求日志;要计算不同的数据:图、网页。。。通常数据都很大,需要利用分布式的方式去完成计算,开始考虑如何进行并行计算,分配数据和处理失败。
<strong>思路</strong>
针对这些复杂问题,决定设计抽象框架来提供简单的计算能力,并隐藏并发、容错、数据分布和负载均衡等细节。
受到Lisp和其他语言map、reduce的思想的启发,作者意识到大多数计算任务涉及对每个逻辑“记录”执行map操作,得到一批中间key/value对,然后利用reduce操作合并那些key指相同的k-v对。这种模型能很容易实现大规模并行计算,并且可以用re-execution作为容错机制。
编程模型
计算过程接受一组key/value对为输入,产生一组key/value的输出对。该过程可描述为两个功能:map和reduce。
Map取一组输入对,产生一组中间k/v对,MapReduce程序将一样的键分为一组,将他们传给Reduce程序。
Reduce程序收到一个键I,和其对应的一组value,将这些值归并。
实现
Map调用分布在多台机器上,自动将输入数据分为M份,多台机器并行处理这些数据片。Reduce程序由中间产生的数据分为R个,个数由用户来指定。
- 首先将输入文件分为M个16MB到64MB之间文件块,然后启动集群的多个程序。
- 一个主要程序是master,其余是由master给分配任务的workers。总共有M个map任务和R个reduce任务,master将一个map任务和一个reduce任务分配给闲置的workers。
- 分到map任务的worker读取输入片的数据,将输入片解析为key/value对,然后将这些键值对扔给用户定义的Map函数,然后将Map函数处理完的中间结果缓存在内存中。
- 隔一段时间,这些中间结果被写到磁盘,由分区程序分割为R个区域。键值对在本地磁盘的地址被写回master,master负责将这些地址信息传递给执行reduce的worker们。
- 如果master通知一个reduce worker的中间结果的地址信息,该worker调用远程程序去读取本地磁盘的中间结果,然后根据中间结果的键进行排序,这样相同key的数据就排列到一起。
- reduce worker不断重复对中间结果进行排序,然后将唯一键和其可能的一组值扔给用户编写的Reduce函数。对于该reduce分区,Reduce函数执行的结果会附加到一个最终的输出文件中。
7.当所有的map任务和reduce任务完成,master唤醒用户的程序。这时MapReduce调用用户程序返回到其他代码中。
容错
因为mapreduce利用成千上万的机器来处理海量数据,所以必须得应对机器失效。
<strong>Worker失效</strong>
master每隔一段时间就会ping每个worker,如果有worker长时间没有回复,master就将它标记为失效。该worker执行完的所有map任务将会重新启动,调度程序会将它们分配给其他worker,该worker正在执行所有map和reduce任务也会重启,分配给其他worker。
完成的map任务被重新执行是因为中间结果存储在该节点的本地磁盘,它如果失效的话,就无法获取。而完成的reduce任务不需要重启,因为结果存储在全局存储中。
当一个map任务首先由A执行,然后又分给了B(因为A失效),程序会通知执行reduce任务的worker,去worker B上读取数据。
<strong> Master失效</strong>
认为master的单点失效不大可能
网友评论