MapReduce 流程详述

一、MapReduce的提出、介绍

MapReduce 是一个编程模型，也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一个 Map函数处理一个基于key/value pair 的数据集合，输出中间的基于 key/value pair 的数据集合；然后再创建一个 Reduce 函数用来合并所有的具有相同中间 key 值的中间 value 值。因此，可以将许多数据处理问题，转化为 Mapreduce的处理模型来处理。

二、MP的工作流流处理。

理解了Mapreduce的执行流程，有益于后期更好的使用。

进行任务执行。当一个mapreduce任务进来时，如下处理

1、  文件分块。hadoop对输入的文件进行分块，按照每块不大于64M的规格进行划分。

2、  Mapper处理。

a)        执行map函数。每个结点获取相应的数据块，进行mapper处理，处理的结果以key-value的形式输出（还未真正从mapper端输出）。

b)        进行Combine。如果用户定义了Combine类，则对该结点的mapper阶段的输出进行一次reduce（自定义的combine类需要继承Reducer类）。并将值以key-value的形式输出。注意，combine是在每一个map结点上对分块数据进行处理，旨在减少map端的输出，进而提高效率。

3、  进行partition。假设总共有n个Reducer，那么使用num =hash（key）%n，对key值进行哈希以将值输出给相应序号的Reducer。

4、  Reducer处理。将获取的值调用reduce函数，进行处理并输出最终值。

三、MapReduce的深入理解，shuffle

         Map阶段产生的Key-Value值对，需要传输到Reduce任务中处理，但MapReduce是用于分布式大量数据处理的，意味着这些数据并非在同一个计算机上的内存中进行处理，需要进行数据在各个slaver中传输，Hadoop中，使用HDFS作为传输的中介。Map任务将所有处理完毕的数据写入HDFS中，Reduce从HDFS中拉取相应的数据。这样，Map只管按照一定的格式存储，而无需知道各个Reduce的信息去传输数据；Reduce只管从HDFS中获取属于自己的数据，无需关注Map的情况。

         这就涉及到一个问题，如何定义Map的输出格式，以方便Reduce读取属于自己的数据块。这方面，应该是使用了索引的方式来快速定位，有待研究。

         关于shuffle，意思是“洗牌”，主要涵盖以下内容：在Map中将文件读入并处理，存储到HDFS中，Reduce中从HDFS拉取对应的数据进行处理。因此，分为map阶段（前半段），和reduce阶段（后半段）

         这是一张官方的shuffle图，从这张图，可以很好地解释shuffle的整个过程。

1、  Map读取各个split进行处理。若文件很大，Map会自动将其划分为多个文件，使用多个Map线程进行处理。每一个Map线程都会生成相应的Key-Value输出值，以及要分发给哪个reduce的partition值。这里，有一个小插曲，就是关于内存缓冲区。

a)        内存缓冲区。Map生成的结果值都是先保存在内存中的，但是这个内存缓冲区是有大小限制的，默认是100MB当map task的输出结果很多时，就可能会撑爆内存，所以需要在一定条件下将缓冲区中的数据临时写入磁盘，然后重新利用这块缓冲区。这个从内存往磁盘写数据的过程被称为Spill，中文可译为溢写，字面意思很直观。这个溢写是由单独线程来完成，不影响往缓冲区写map结果的线程。溢写线程启动时不应该阻止map的结果输出，所以整个缓冲区有个溢写的比例spill.percent。这个比例默认是0.8，也就是当缓冲区的数据已经达到阈值（buffer size * spill percent = 100MB * 0.8 = 80MB），溢写线程启动，锁定这80MB的内存，执行溢写过程。Maptask的输出结果还可以往剩下的20MB内存中写，互不影响。当溢写线程启动后，需要对这80MB空间内的key做排序(Sort)。排序是MapReduce模型默认的行为，这里的排序也是对序列化的字节做的排序。

b)        Combiner。在记录进行处理时，应该尽量将映射到同一个reduce的数据拼接到一块，若设置了combiner，会将有相同key的key/value对的数据进行处理，减少溢写到磁盘的数据量。既然combiner会先在局部进行使用（先每一个溢写文件执行一次），再对局部生成的结果合并处理（在merge的时候再执行合并），而不能保证使用使用combiner时，处理的数据集的完整性，因此，只适合于那些能够进行简单切分的任务。用combiner需慎重，否则会导致结果有误。

既然有了内存缓冲区，将结果多次写入文件，还需要在拼接记录时，将相同的Reduce号的结果拼接到一块，以方便Reduce阶段数据读取，这就是下面的merge过程。

2、  将map中的溢写文件进行merge。每次溢写会在磁盘上生成一个溢写文件，如果map的输出结果真的很大，有多次这样的溢写发生，磁盘上相应的就会有多个溢写文件存在。当map task真正完成时，内存缓冲区中的数据也全部溢写到磁盘中形成一个溢写文件。最终磁盘中会至少有一个这样的溢写文件存在。如前面的例子，“aaa”从某个map task读取过来时值是5，从另外一个map 读取时值是8，因为它们有相同的key，所以得merge成group。什么是group。对于“aaa”就是像这样的：{“aaa”, [5, 8, 2, …]}，数组中的值就是从不同溢写文件中读取出来的，然后再把这些值加起来。请注意，因为merge是将多个溢写文件合并到一个文件，所以可能也有相同的key存在，在这个过程中如果client设置过Combiner，也会使用Combiner来合并相同的key。

至此，map端的所有工作都已结束，最终生成的这个文件也存放在TaskTracker够得着的某个本地目录内。每个reduce task不断地通过RPC从JobTracker那里获取map task是否完成的信息，如果reduce task得到通知，获知某台TaskTracker上的map task执行完成，Shuffle的后半段过程开始启动。

         Reduce端的shuffle过程

Shuffle在reduce端， Reducer真正运行之前，所有的时间都是在拉取数据，做merge，且不断重复地在做。

1、 Copy过程，简单地拉取数据。Reduce进程启动一些数据copy线程(Fetcher)，通过HTTP方式请求map task所在的TaskTracker获取map task的输出文件。因为maptask早已结束，这些文件就归TaskTracker管理在本地磁盘中。

2、 Merge阶段。这里的merge如map端的merge动作，只是数组中存放的是不同map端copy来的数值。Copy过来的数据会先放入内存缓冲区中，这里的缓冲区大小要比map端的更为灵活，它基于JVM的heap size设置，因为Shuffle阶段Reducer不运行，所以应该把绝大部分的内存都给Shuffle用。这里需要强调的是，merge有三种形式：1)内存到内存  2)内存到磁盘  3)磁盘到磁盘。默认情况下第一种形式不启用，让人比较困惑，是吧。当内存中的数据量到达一定阈值，就启动内存到磁盘的merge。与map 端类似，这也是溢写的过程，这个过程中如果你设置有Combiner，也是会启用的，然后在磁盘中生成了众多的溢写文件。第二种merge方式一直在运行，直到没有map端的数据时才结束，然后启动第三种磁盘到磁盘的merge方式生成最终的那个文件。

3、Reducer的输入文件。不断地merge后，最后会生成一个“最终文件”。为什么加引号？因为这个文件可能存在于磁盘上，也可能存在于内存中。对我们来说，当然希望它存放于内存中，直接作为Reducer的输入，但默认情况下，这个文件是存放于磁盘中的。当Reducer的输入文件已定，整个Shuffle才最终结束。然后就是Reducer执行，把结果放到HDFS上。

 

四、MapReduce工作流

现阶段，许多处理并不是使用一次就能够完成数据的处理，需要多次mapreduce。这就涉及到工作流了。待续...