MapReduce是一个分布式并行计算框架。在MapReduce中，一个存储在分布式文件系统中的大规模数据集会被切分成许多独立的小数据块，这些小数据块可以被多个Map任务并行处理。MapReduce框架会为每个Map任务输入一个数据子集，Map任务生成的结果会继续作为Reduce任务的输入，最终由Reduce任务输出最后结果，并写入分布式文件系统。

MapReduce模型的核心是Map函数和Reduce函数。函数都是以作为输入，按一定的映射规则转换成另一个或一批输出。Map函数的输入来自于分布式文件系统的文件块，其格式是任意的，可以是文档、也可以是二进制格式。Reduce函数的输入是一系列具有相同键、以某种方式组合的值，并也以键值对的形式输出到文件。

MapReduce工作流程

MapReduce的核心思想可以用“分而治之”描述，也就是把一个大的数据集拆分成多个小数据块在多台机器上并行梳理。在MapReduce执行过程中，Map任务的输入文件、Reduce任务的处理结果都是保存在分布式文件系统，而Map任务的中间结果则保存在本地存储（比如磁盘），Spark则保存在内存。

注：不同Map任务间不会进行通信，不同Reduce任务间也不会发生信息交换，机器之间的任务交换由MapReduce框架实现，不需要用户定义实现。

Map Reduce执行阶段

shuffle详解

shuffle是指对Map输出结果进行分区（partition）、排序（sort）、合并（combine）、归并（merge）等处理并交给Reeduce的过程，此过程分为Map端的操作和Reduce端的操作，是MapReduce的核心环节。

Shuffle过程

Map端的shuffle过程

Map的输出结果首先被写入缓存，缓存满时就启动溢写操作，把缓存数据写入磁盘文件，并清空缓存。启动溢写操作时，首先把缓存数据进行分区，然后对每个分区数据进行排序、合并，在写入磁盘。每次溢写会生成一个新磁盘文件，随着Map任务的执行，磁盘会生成多个溢写文件，所以在Map任务全部结束前，这些溢写文件会归并成一个大的磁盘文件，然后通知相应的Reduce任务来领取属于自己处理的数据。

4个步骤：

(1)输入数据和执行Map任务。

        输入数据一般为保存在分布式文件系统的文件块(任意格式，文件或二进制)，以<key，value>作为输入，按一定一定映射规则转换成一批<key，value>输出。

(2)写入缓存。

        每个Map任务分配一个缓存，减少多次磁盘寻址开销，从而减少磁盘I/O。

(3)溢写（分区、排序、合并）

缓存数据形式，缓存容量有限，所以会启动溢写。溢写到磁盘前，缓存数据会先被分区，默认分区方式：采用Hash函数对key进行hash，再用Reduce任务的数量取模，表示为hash(key) mod R，R即是Reduce任务数量。这样就把Map输出结果均匀分配到R个Reduce任务并行处理。分区后，对每个分区数据根据key进行排序，以及可选的合并操作。合并，是指将相同key的的value加起来，比如<"xmu"，1>和<"xmu"，2>经过合并操作后得到<"xmu"，3>，一般累加、最大值场景可以使用合并操作。

        每次溢写操作后在磁盘新生成一个溢写文件，并且所有键值对都是经过分区、排序的。

(4)文件归并 <k，v>—><k，v-list>

        归并是指将相同key的键值归并成一个新的键值对。<k1, v1>，<k1, v3>......<k1, vn>被归并成<k1,<v1,v2......vn>>。

Reduce端的shuffle过程

Reduce任务从Map端的不同Map机器领回属于自己处理的数据，然后对数据进行归并后提交给Reduce处理。

3个步骤：

(1)领取数据

        Map端shuffle结束后，所有输出结果保存在Map机器的本地磁盘，Reduce任务会把(不是这一步)这些数据领取(fetch)回来放到自己所在机器的本地磁盘。

(2)归并数据

        领回的数据首先放在本机缓存，一样会进行溢写操作，因为会从多个Map机器领取数据，因此会进行归并，再合并数据。因此当所有Map端数据被领回，多个溢写文件会被归并成一个大文件（同样会对键值对排序）。

(3)数据输入给Reduce任务

        多轮归并得到若干大文件，直接将这些文件输入给Reduce任务。不再继续归并目的是减少磁盘读写开销。

Map Reduce过程示例