MapReduce过程详解

MapReduce是一种云计算的核心计算模式，是一种分布式运算技术，也是简化的 分布式并行 编程模式，主要用于大规模并行程序并行问题。

MapReduce的主要思想：

自动将一个大的计算（程序）拆分成Map（映射）和Reduce（化简）的方式。

流程图如下：

数据被分割后通过Map函数将数据映射成不同的区块，分配给计算集群进行处理，以达到分布运算的效果，再通过Reduce函数将结果进行汇整，从而输出开发者所需要的结果。

MapReduce借鉴了函数式程序设计语言的思想，其软件实现是指定一个Map函数，把键值对（Key/Value）映射成一个新的键值对（Key/Value），形成一系列中间结果形式的（Key/Value），然后把它们传递给Reduce函数，把具有相同中间形式Key的Value合并在一起。Map函数和Reduce函数具有一定的关联性。

接下来从Shuffler来详细描述Map和Reduce的细节

Shuffler就是reduce从map拉取数据的过程。(说的形象一点就是：将数据重新打乱汇聚到不同节点的过程，当然相同key需要汇聚在同一个节点)

以WordCount为例，假设有8个MapTask和3个ReduceTask

Map端整个流程分为4步：

（1）在MapTask执行时，其输入数据来源于HDFS的Block。Split和Block默认对应关系是一对一。在WordCount例子中，假设Map的输入数据都是像“aaa”这样的字符串。

（2）在经过Mapper运行后，输出是这样一个Key/Value对：Key是“aaa”，Value是1。我们知道这个Job有3个ReduceTask，到底“aaa”应该交由哪个Reducer去处理，是需要现在决定的。MapReduce提供了Partitioner接口，其作用是根据Key或Value及Reduce的数量来决定当前这对输出数据最终应该交由哪个ReduceTask处理。默认对Key进行哈希运算后，再以ReduceTask数量取模。在该例中，“aaa”经过Partition（分区）后返回0，也就是这对输出数据应当由第一个Reducer来处理。接下来需要将数据写入内存缓冲区中。缓冲区的作用就是批量收集Map结果，减少磁盘I/O影响。

（3）内存缓冲区的大小是有限的，默认是100MB。当MapTask输出结果有很多时，内存可能会不足，所以需要在一定条件下将缓冲区中的数据临时写入磁盘，然后重新利用这个缓冲区。这个从内存往磁盘写数据的过程被称为Spill，中文译为溢写。

（4）每一次溢写都会在磁盘上生成一个溢写文件，如果Map输入结果很大，就会有多次这样的溢写发生，磁盘上就会有多个溢写文件存在。当MapTask真正完成时，内存缓冲区中的数据将全部溢写到磁盘中形成一个溢写文件。最红磁盘中会至少有这样的一个溢写文件存在（如果Map的输出结果很少（小于100MB），那么当Map执行完成时，只会产生一个溢写文件）。因为最终的文件只有一个，所以需要将这些溢写文件归并（使用归并算法）到一起，这个过程就是Merge。至此，Map端所有工作都已结束。

每个ReduceTask不断地通过RPC（HTTP协议）从JobTracker（Hadoop2.0有了Yarn之后，是ResourceManager）那里获取MapTask是否完成信息。如果ReduceTask获知某台TaskTraker（Hadoop2.x中为AppMaster）上的MapTask执行完成，那么Shuffler的后半段过程开始启动。简单地说，ReduceTask在执行之前的工作就是不断地拉取当前Job里的每个MapTask的最终结果，然后对不同地方拉取过来的数据不断地进行Merge，最终形成一个文件作为ReduceTask的输入文件。

Reduce端整个流程分为3步：

（1）Copy过程。即简单地拉取数据。Reduce进程启动一些数据copy线程（Fetcher），通过HTTP方式请求MapTask所在的TaskTracker获取MapTask的输出文件。因为MapTask早已结束，所以这些文件就由TaskTracker管理。

（2）Merge阶段。同Map端的Merge动作，只是数组中存放的是不同Map端复制过来的数据。复制过来 数据会先放到内存缓冲区中，当内存中的数据达到一定阈值时，就会启动内存到磁盘的Merge。与Map端类似，这也是溢写过程，会在磁盘中形成众多的溢写文件，然后将这些溢写文件进行归并。

（3）Reducer的输出文件。不断地进行Merge后，最后会生成一个“最终文件”。这个文件可能存放在磁盘，也可能存放在内存中，默认存放在磁盘上。当Reducer的输入文件已定时，整个Shuffle过程才最终结束。

这里给出一个宏观的流程图：

总结

map每次读取split的数据（一行一行的读取）后先放在buffer缓冲区中，然后进行分区、 排序 、当缓冲区满了之后，会进行溢写磁盘。磁盘中会生成很多个溢写小文件，而这些小文件内部是有序的，但小文件和小文件之间是无序的，所以需要进行一次归并形成一个全盘有序的文件。 由于一个split对应一个map，reduce端是从多个map中拉取数据，所以也需要进行归并为一个有序的文件，最终每个相同的key分为一组执行一次reduce方法。

来自