一、Mapreduce概述

• Hadoop MapReduce 是一个分布式计算框架，用于编写批处理应用程序。编写好的程序可以提交到Hadoop集群上用于并行处理大规模的数据集。
• MapReduce 作业通过将输入的数据集拆分为独立的块，这些块由Map以并行的方式处理。每个作业都包含map和reduce两个阶段。

二、工作流程概述

大数据处理包括：分布式存储和分布式计算。

MapReduce的核心思想可以用**"分而治之"**来描述，即把一个大的数据集拆分成多个小数据块在多台机器上并行处理，也就是说，一个大的MapReduce作业的处理流程如下：

• 首先，会被分成许多个Map任务在多台机器上并行执行。每个Map任务通常运行在数据存储的节点上，这样，计算和数据就可以放在一起运行，不需要额外的数据传输开销。当Map任务结束后，会生成以<key,value>形式表示的许多中间的结果。
• 然后，这些中间结果会被分发到多个Reduce任务在多台机器上并行执行，具有相同key的<key,value>会被发送到同一个reduce任务那里，reduce任务会对中间结果进行汇总计算得到最后结果，并输出到分布式文件系统中。

MapReduce算法的执行过程：

• MapReduce框架使用InputFormat模块做Map前的预处理。作用：验证输入的格式是否符合输入定义，如果符合，将输入文件切分为逻辑上的多个InputSplit,InputSplit是MapReduce对文件进行处理和运算的输入单位，只是一个逻辑概念，每个InputSplit并没有对文件进行实际切割，知识记录了要处理的数据的位置和长度。

• 因为InputSplit是逻辑切分，所以，还需要通过RecordReader(RR)并根据InputSplit中的信息来处理InputSplit中的具体记录，加载数据并转换为适合Map任务读取的键值对，输入给Map任务。

• Map任务会根据用户自定义的映射规则，输出一系列的<key,value>作为中间结果。

• 为了让Reduce可以并行处理Map的结果，需要对Map的输出进行一定的分区，排序(Sort)、合并(Combine)和归并等操作，得到<key,value-list>形式的中间结果，再交给对应的Reduce程序进行处理，这个过程称为shuffle。

• Reduce以一系列<key,value-list>中间结果作为输入，执行用户定义的逻辑，输出结果给OutputFormat模块。

• OutputFormat模块会验证输出目录是否已经存在，以及输出结果类型是否符合配置文件中的配置类型，如果都满足，就输出Reduce的结果到分布式文件系统。

提示1：不同的Map任务之间不会进行通信，不同的reduce任务之间也不会发生任何信息交换；用户不能显示地从一台机器向另一台机器发送消息，所有的数据交换都是通过mapreduce框架自身去实现的。 在MapReduce的整个执行过程中，Map任务的输入文件，reduce任务的处理结果都是保存在分布式文件系统中的，而Map任务处理得到的中间结果则保存在本地存储（如磁盘）中。

提示2：在reduce端的shuffle过程。Reduce任务从Map端的不同Map机器领回属于自己需要处理的那部分数据，然后，对数据进行归并(Merge)后交给Reduce处理。

Map端的shuffle过程：

shuffle过程是MapReduce整个工作流程的核心环节，理解shuffle过程的基本原理，对于理解MapReduce流程至关重要。

所谓shuffle，是针对Map输出结果进行分区、排序和合并等处理,并交给reduce的过程。因此，shuffle过程分为Map端的操作和Reduce端的操作。

1. 在Map端的shuffle过程。Map的输出结果首先被写入缓存，当缓存满时，就启动溢写操作（分区、排序、合并），把缓存中的数据写入磁盘文件，并清空缓存，当启动溢写操作时，首先需要把缓存中的数据进行分区，然后对每个分区的数据进行排序(sort)和合并（Combine）,之后写入磁盘文件。 每次溢写操作会生成要给新的磁盘文件，随着Map任务的执行，磁盘中就会生成多个溢写文件。在Map任务全部结束之<前[todo]，这些溢写文件会被归并(merge)成一个大的磁盘文件，然后，通知相应的reduce任务来领取属于自己需要处理的数据。
2. 在reduce端的shuffle过程。Reduce任务从Map端的不同Map机器领回属于自己需要处理的那部分数据，然后，对数据进行归并(Merge)后交给Reduce处理。

map端的shuffle步骤：

1. 输入数据和执行Map任务 k1,v1 -> list(k2,v2)

2. Map任务的输入数据一般保存在分布式文件系统(如GFS或HDFS)的文件块中，这些文件块的格式时任意的，可以是文档，也可以是二进制格式的。Map任务接受<key,value>作为输入后，按一定的映射规则转换成一批<key,value>进行输出。

3. 写入缓存：每个Map任务都会被分配一个缓存，Map的输出结果不是立即写入磁盘，而是首先写入缓存。在缓存中积累一定数量的map输出结果以后，在一次性批量写入磁盘，这样可以大大减少对磁盘I/O的影响。

4. 因为，磁盘包含机械部件，它事实通过磁头移动和盘片的转动来寻址定位数据的，每次寻址的开销很大，如果每个Map输出结果都直接写入磁盘，回引入很多寻址开销，而一次性批量写入,就只需要一次寻址，连续写入，大大降低了开销。需要注意的是，在写入缓存之前，key于value值都会被序列化成字节数组。

5. 溢写（分区、排序和合并）：提供给MapReduce的缓存的容量是有限的，默认大小是100MB. 随着Map任务的执行，缓存中Map结果的数量不断增加，很快就会占满整个缓存，这时，就必须启动溢写（spill）操作，把缓存中的内容一次性写入磁盘，并清空缓存。