MapReduce的shuffle机制

shuffle过程（简单理解）：从map的输出到reduce的输入之间的过程。

概念：Map是映射，负责数据的过滤分法，将原始数据转化为键值对；Reduce是合并，将具有相同的key值的value进行处理后再输出新的键值对作为最终结果。为了让Reduce可以并行处理Map的结果，必须对Map的输出进行一定的排序与分割，然后再交给对应的Reduce，Map端的输出作为Reduce的输入的过程叫做Shuffle.

注意点：一个分片对应一个 Map 任务，每个 Map 任务里面会根据分片中的记录执行多次 mapper 函数。一个分区对应一个 reduce 任务，每个 Reduce 任务中根据分区中的键来执行多次 reducer 函数。

1、Map端：每个map任务维护着一个环形缓冲区，用于存储任务的输出，默认100MB。当map输出数据时，先写到内存缓冲区，当内存缓冲区达到设置的阈值之后，始溢出成spill文件，然后进行分区（ partion）排序（快速排序），对每个分区的数据按key进行排序，如果有 combiner函数，则会在排序后的输出上运行，使map的输出结果更加紧凑，然后写入磁盘。map任务输出量很大时，可能进行好几次分割，这样spill文件就会分布在不同的磁盘上。当最后一个spill文件写完之后，将多个spill文件进行合并到一个已经分区并排序的大文件，如果有combiner函数，在合并spill时，也会运行。将压缩的Map输出写到磁盘是不错的，可以减少磁盘的IO量，减少传输给的数据量。

2、 Reduce端：Reduce通过HTTP方式从map获取数据， Reduce有少量的复制线程并行从map端复制数据到 Reduce端。一般需要从多个map端复制数据，有一个map完成就可以开始复制了。

如果map输出比较小，会直接复制到内存。如果数据大，当达到内存缓冲区的阈值后，会合并溢出到磁盘。如果有 combiner，合并期间运行，降低写入磁盘的数据量。

最后一次合并结果作为 reduce函数的输入，最后一次合并不一定合并成一个大文件，可能会直接合并到 reduce上。合并因子默认是10，一趟合并的文件数。

对已经排序输出中的每一个键调用reduce函数，然后输出到文件系统（HDFS）。