MapReduce是Google开发的C++编程工具,用于大规模数据集(大于lTB)的并行运算。由于计算分布在成百上千的机器上,尽管输入的是海量数据,计算还是可以在一个合理的时间内结束。分割分配输入数据,在机器群中调度执行并行计算、处理错误、负载平衡是MapReduce的代码的重点。MapReduce最初是Google公司为了处理不断增长的文档和Web需求日志而设计的并行编程模型。同时它还可以进行很多衍生计算,例如,倒排索引、Web文档的图结构表示、每个主机的页数汇总和指定日的最频繁查寻等。
Map:将每对输入数据的逻辑记录计算转为一组中间键/值对集合。MapReduce库将相同中间键的中间值集合在一起,传递给Reduce函数。
Reduce:合并所有具有相同的中间键的中间值。例如,Reduce函数接受一个中间键,和具有这个键的一组值。将这组值合并形成一个可能更小的值集合。
MapReduce的执行过程如图1.16所示,具体如下。
(1)用户程序中的MapReduce库首先将输入文件分割成M块(由用户通过参数控制,一般每份16~64MB),然后集群中的机器拥有程序的多个备份。
(2)程序的一个备份是特殊的——主机(master),其他是由主机分配工作的从机(worker)。一共有M个Map任务,JR个Reduce任务需要分配。主机选取空闲从机并且给它们一个Map或者Reduce任务。
……
展开