MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算,应用于大规模的演算法图形处理和文字处理。Google上,超过一万个不同的项目已经采用MapReduce来实现,这些项目往往都需要输入大量的数据,MapReduce的作用就是运用定义好的框架合并衍生数据。

举个例子,更直观的认识MapReduce的优点。

查找过去十年的有关大数据的论文中出现的高频辞汇,有什么办法?

方法一:将所有论文按顺序遍历(先不论机器的内存,需要开多大的数组),统计每个辞汇出现的频率,最后比较一下大小。这种方法最为直观和简单,但花费的时间最多。

方法二:设置一个多线程,同时遍历多篇论文。时间上比方法一要快很多,但这种方法是在一台PC机上实现,同步共享数据,需要考虑重复统计文件这些问题。

方法三:将这些数据分成N份,在一个大的PC机集群上遍历,最后将数据汇总。这种方法所需的时间更少,遍历这种操作写个小程序就可以实现,但将数据分到每个机器上和最后的整合要略为麻烦。

方法四:MapReduce在方法三的基础上进行优化,它的框架已经定义了如何拆分数据集、数据传输和最后的整合,我们所需要做的定义用户程序。

Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages.

该句选自Google上的MapReduce的论文,提到了MapReduce的思想来源,翻译过来就是:我们的灵感来自Lisp和其他函数编程语言中的古老的映射和化简操作。MapReduce中将映射和化简实现为map函数和reduce函数,这两个函数需要用户自己定义。

map函数:对输入数据进行处理,输入一对key/value,通过map函数生成输出中间值key/value对,MapReduce将有著相同key和value的中间对组合,输给reduce函数。

map(String input_key,String input_value){
//input_key:文档名
//input_value:文档内容
for eachword w input_value:
EmitIntermediate(w,"1");
//每个单词出现一次,输出1
}

reduce函数:接受一个键以及相关的一组值,将这组值进行合并产生一组规模更小的值(通常为一个或零个)。

reduce(String output_key,Iterator output_values){
//output_key:单词
//output_values:计数值列表
int result = 0;
for each v in output_values:
result+= ParseInt(v);
Emit(AsString(result));
//合并相加单词output_key的输出次数
}

这些单词的出现次数会被写到用户定义的位置,存储在底层的分散式存储系统(GFS或HDFS)。

下面是执行过程:

1.MapReduce库先将输入文件划分为M份(M为用户定义),每一份通常为16MB~64MB,如上图所示分为split0~4;然后使用fork将用户进程拷贝到集群内其他机器上

2.user program副本中master(只有一个)负责调度,为空闲的worker分配map或者reduce工作

3.被分配了map作业的worker,开始读取对应分片上的输入数据,抽取出键值对,调用map函数,输出的中间对缓存在内存中

4.缓存的中间键值对会被定期写入本地磁碟,而且被分为R个区(大小为用户定义),将来每个区都会对应一个Reduce作业,中间键值对的位置由master转给Reduce worker

5.master通知分配了Reduce作业的worker它负责的分区在什么位置(可能在R中的不同分区),worker读取它所负责的键值对,进行排序,使相同键的键值对的聚集在一起。

6.reduce worker遍历排序后的键值对,对每一个唯一的键,都将键与关联的值传给reduce函数,函数的输出添加到分区的输出文件中

7.所有的map和reduce作业完成后,master唤醒正版的user program,MapReduce函数调用返回user program的代码

举例:

MapReduce是基于大型PC机集群上的,难免会发生机器错误。在运行过程中,机器被分为一个master,其余称之为worker。

当worker发生机器错误时,该节点被标记为失败,其所做的map作业将被master分配给其他机器重做(因为发生机器错误时,其存储在本机磁碟上的中间键值对无法查找),而已完成的reduce作业不需要重做(因为reduce作业的输出在全球性文件上),未完成的由其他机器继续完成。

当master发生机器错误时,可采用定时建立恢复点,如果发生错误,可在上一个恢复点建立新的程序副本。

在运行过程中可能会导致MapReduce操作时间过长,往往是因为其中的某个worker在操作map或reduce作业时花费时间过长,造成这种状况的原因有许多,例如磁碟发生异常,读取速度变慢。

MapReduce在其运行接近尾声时,在一部分worker执行剩余任务时,将这一部分任务调度给其他机器备份执行。原任务和备份任务中但凡有一个完成,该任务即标记为已完成。

我们将map阶段分成M份,reduce阶段分成R份,总数据量为D,机器数为P,M和R应比P大很多,其大小比较为D>M>R>P。

MapReduce的一个经典实例是Hadoop,用于处理大型分散式资料库。其框架最核心的设计就是HDFS和MapReduce。

Hadoop技术社区-CSDN.NET


用最简洁的话概括MapReduce(摘自网上):

我们要一起数图书馆中的所有书。你数1号书架,我数2号书架。这就是map,人越多越快。

现在我们到一起,把所有人的数据统计到一起,这就是reduce。


推荐阅读:
相关文章