MapReduce之原理、工作流程

【导读：数据是二十一世纪的石油，蕴含巨大价值，这是·情报通·大数据技术系列第[10]篇文章，欢迎阅读和收藏】

1基本概念

MapReduce是一个分布式运算程序的编程框架，是用户开发 “ 基于 hadoop 的数据分析 应用 ” 的核心框架。MapReduce 核心功能是将用户编写的业务逻辑代码和自带默认组件整合成一个完整的 分布式运算程序，并发运行在一个 hadoop 集群上。在程序由单机版扩成分布式版时，会引入大量的复杂工作。为了提高开发效率，可以将分布式程序中的公共功能封装成框架，让开发人员可以将精力集中于业务逻辑。Hadoop 当中的 MapReduce 就是这样的一个分布式程序运算框架，它把大量分布式程序都会涉及的到的内容都封装进了，让用户只用专注自己的业务逻辑代码的开发。

2术语解释

映射（ Map ）：

简单说来，一个映射函数就是对一些独立元素组成的概念上的列表的每一个元素进行指定的操作。每个元素都是被独立操作的，而原始列表没有被更改，因为这里创建了一个新的列表来保存新的答案。这就是说， Map 操作是可以高度并行的，这对高性能要求的应用以及并行计算领域的需求非常有用。

化简（ Reduce ）：

对一个列表的元素进行适当的合并，虽然它不如映射函数那么并行，但是因为化简总是有一个简单的答案，大规模的运算相对独立，所以化简函数在高度并行环境下也很有用。

3详细说明

3.1MapReduce原理

Hadoop中的 MapReduce 是一个使用简单的软件框架，基于它写出来的应用程序能够运行在由上千个机器组成的大型集群上，并以一种可靠容错并行处理 TB 级别的数据集。Hadoop MapReduce 源于 Google 在 2004 年 12 月份发表的 MapReduce 论文。Hadoop MapReduce 其实就是 Google MapReduce 的一个克隆版本。

MapReduce主要有以下几个特点：

1、 MapReduce 易于编程：它简单的实现一些接口，就可以完成一个分布式程序，这个分布式程序可以分布到大量廉价的 PC 机器运行。也就是说你写一个分布式程序，跟写一个简单的串行程序是一模一样的。就是因为这个特点使得 MapReduce 编程变得非常流行。

2、良好的扩展性：当你的计算资源不能得到满足的时候，你可以通过简单的增加机器来扩展它的计算能力。

4、适合 PB 级以上海量数据的离线处理：它适合离线处理而不适合在线处理。比如像毫秒级别的返回一个结果， MapReduce 很难做到。

MapReduce框架的核心步骤主要分两部分：Map 和 Reduce ，当你向 MapReduce 提交一个计算作业时，它会首先把计算作业拆分成若干个 Map 任务，然后分配到不同的节点上去执行，每一个 Map 任务处理输入数据中的一部分，当 Map 任务完成后，会生产一些中间文件，这些中间文件将会作为 Reduce 任务的输入数据， Reduce 的任务主要目标就是把前面若干个 Map 的输出汇总到一起并输出，从高层抽象来看， MapReduce 的数据流图如下图所示：

Map过程：

2.在写入磁盘之前，线程首先会根据 reduce 任务的数目划分相同数目的分区，也就是一个 reduce 任务对应一个分区的数据。这样做就是为了避免有些 reduce 任务分配到大量数据，而有些 reduce 分配到很小的数据，甚至没有数据。其实分区就是对数据进行 hash 的过程，然后对每个分区中的数据进行排序，如果此时设置了 combiner ，将排序后的结果进行 Combia 操作，这样做的目的是让尽可能少的数据写入到磁盘；

3.当 Map 任务输出到最后一个记录时，可能会有很多的溢出文件，这时需要将这些文件合并，合并的过程中会不断进行排序和 combia 操作，目的有两个：

4.将分区中的数据拷贝给相对应的 reduce 任务，有人可能会问：分区中的数据怎么知道它对应的 reduce 呢？其实 Map 任务一直和其父 TaskTracker 保持联系，而 TaskTracker 又一直和 JobTracker 保持心跳，所以 JobTracker 中保存了整个集群中的宏观信息，只要 reduce 任务向 JobTracker 获取对应的 Map 输出位置就可以了。

Reduce过程：

2.随着溢写文件的增多，后台线程会将他们合并成一个更大的有序文件，这样做是为了给后面的合并节省时间，其实不管在 map 端还是 reduce 端， MapReduce 都是反复地执行排序，合并操作；

3.合并的过程中会产生许多的中间文件（写入磁盘了），但 MapReduce 会让写入磁盘的数据尽可能地少，并且最后一次合并的结果并没有写入磁盘，而是直接输入到 reduce 函数。

3.2MapReduce工作流程

一个 MapReducer 作业经过了 input ， map ， combine ， reduce ， output 五个阶段，其中 combine 阶段并不一定发生， map 输出的中间结果被分到 reduce 的过程成为 shuffle （数据清洗）。流程图如下：

一切都是从最上方的 user program 开始的， user program 链接了 MapReduce 库，实现了最基本的 Map 函数和 Reduce 函数。

1.MapReduce库先把 user program 的输入文件划分为 M 份（ M 为用户定义），每一份通常有 16MB 到 64MB ，如图左方所示分成了 split0~4 ；然后使用 fork 将用户进程拷贝到集群内其它机器上。

2.user program的副本中有一个称为 master ，其余称为 worker ， master 是负责调度的，为空闲 worker 分配作业（ Map 作业或者 Reduce 作业）， worker 的数量也是可以由用户指定的。

3.被分配了 Map 作业的 worker ，开始读取对应分片的输入数据， Map 作业数量是由 M 决定的，和 split 一一对应；Map 作业从输入数据中抽取出键值对，每一个键值对都作为参数传递给 map 函数， map 函数产生的中间键值对被缓存在内存中。

4.缓存的中间键值对会被定期写入本地磁盘，而且被分为 R 个区， R 的大小是由用户定义的，将来每个区会对应一个 Reduce 作业；这些中间键值对的位置会被通报给 master ， master 负责将信息转发给 Reduce worker 。

5.master通知分配了 Reduce 作业的 worker 它负责的分区在什么位置（肯定不止一个地方，每个 Map 作业产生的中间键值对都可能映射到所有 R 个不同分区），当 Reduce worker 把所有它负责的中间键值对都读过来后，先对它们进行排序，使得相同键的键值对聚集在一起。因为不同的键可能会映射到同一个分区也就是同一个 Reduce 作业（谁让分区少呢），所以排序是必须的。

6.reduce worker遍历排序后的中间键值对，对于每个唯一的键，都将键与关联的值传递给 reduce 函数， reduce 函数产生的输出会添加到这个分区的输出文件中。

7.当所有的 Map 和 Reduce 作业都完成了， master 唤醒正版的 user program ， MapReduce 函数调用返回 user program 的代码。

所有执行完毕后， MapReduce 输出放在了 R 个分区的输出文件中（分别对应一个 Reduce 作业）。用户通常并不需要合并这 R 个文件，而是将其作为输入交给另一个 MapReduce 程序处理。整个过程中，输入数据是来自底层分布式文件系统（ GFS ）的，中间数据是放在本地文件系统的，最终输出数据是写入底层分布式文件系统（ GFS ）的。而且我们要注意 Map/Reduce 作业和 map/reduce 函数的区别：Map 作业处理一个输入数据的分片，可能需要调用多次 map 函数来处理每个输入键值对；Reduce 作业处理一个分区的中间键值对，期间要对每个不同的键调用一次 reduce 函数， Reduce 作业最终也对应一个输出文件。