MapReduce的shuffle和排序

系统执行排序、将map输出作为输入传给reduce的过程称为shuffle。

MapReduce的shuffle

上图表示MapReduce的shuffle执行过程。大致分为五个步骤：
map端

1. 每个map任务都有一个环形的内存缓冲区(图中的buffer in memory)用于存储任务输出。缓冲区达到一定的阈值(默认80%)，一条后台线程便开始把内容溢出(spill)到磁盘。每次内存缓冲区达到溢出阈值，就会新建一个溢出文件(spill file)。
2. 在写磁盘之前，线程首先根据数据最终要传的reduce把数据划分成相应的分区(partition)(图中partitions)。在每个分区中，后台线程按键进行内存中排序(排序是在map端进行的)。如果有combiner函数就会在排序后的输出上运行，为了让map输出结果更加紧凑。
   在任务完成之前，溢出文件被合并成一个已分区且已排序的输出文件(图中merge on disk)。如果溢出文件多于设置的数量，combiner就会在输出文件写到磁盘之前再次运行。

reduce端

3. 复制阶段(图中Copy Phase)，如果map的输出相当小，会被复制到reduce任务的JVM内存中；否则map输出被复制到磁盘。随着磁盘上副本增多，后台线程会将它们合并为更大的、排好序的文件。
4. 排序阶段(图中“Sort” Phase)，准确的说是合并阶段。复制完成map的输出后，将合并map输出，维持其顺序排序。最后一趟的合并来自内存和磁盘片段。
5. Reduce阶段，执行reduce任务，把最后一趟合并的数据直接输入reduce函数，从而省略了一次磁盘往返行程。

reduce如何知道要从哪台机器取得map输出？
map任务成功后，它们会使用心跳机制通知它们的application master。因此，对于指定作业，application master知道map输出和主机位置之间的映射关系。reduce中的一个线程定期询问master以便获取map输出主机的位置，知道获得所有输出位置。

reduce端如何合并文件的？
合并文件是循环进行的，合并因子默认是10。目标是合并最小数量的文件以便满足最后一趟的合并系数。例如40个文件，不会四趟中每趟合并10个文件，最后得到4个文件。而是，第一趟合并4个文件，随后三趟合并10个文件，在最后一趟中，4个已经合并的文件加上余下的6个未合并的文件，总共10个文件。这样做是一种优化措施，目的是尽量减少写到磁盘的数据量，因为最后一趟总是直接合并到reduce中。