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。


推荐阅读：
相关文章