MapReduce-Shuffle机制运行解析
概述
在MapReduce（分布式计算框架，底层依赖HDFS）中，map阶段经过处理输出的数据怎样传递给reduce并保证reduce的输入都是按键排序好的，在MR中是极为关键的一个流程，这个流程叫做Shuffle，也称之为“洗牌”。可以说，Shuffle是整个MR的心脏。
Shuffle的结构
Shuffle是MR处理流程中的一个过程，连接了map task和reduce task，它的每一个处理步骤是分散在各个map task和reduce task节点上完成的。根据这张图，我们在理解上粗暴的将Shuffle“一刀两断”。左右两边分别称之为“Shuffle写”、“Shuffle读”。下面我们来逐步对其进行分析。
Shuffle写阶段分析
“Shuffle写”阶段是发生在map task上，接下来我们对“Shuffle写”分析。
文件分割为“block块”，“block”又通过“抽象意义”上的“FileInputFormat”“变为”切片（FileSplit对象
可以视为一条记录，splitSize=Math.max(minSize,Math.min(maxSize,blockSize))，所以默认情况下block的大小和切片一样）。
分片经过“FileInputFormat LineRecordReader”映射为K-V键值对（这里的K-V并非Map的K-V），K可以重复。这里默认K为偏移量，V为该行记录的数据内容。
每一条K-V数据，都会在读到内存后传给Mapper类，并在之后经过HashPartitioner分区器（默认就是对Recuder的数量取模%，Redecer的数量默认是1，可以由我们来设定），给每一条数据打上“P”的印记，此时这一条"K-V-P"数据就明白了自己的目的地是哪个分区。
然后，这一条"K-V-P"数据就会放到内存缓冲区buffer in memore，默认大小100M，但容量达到80%后，就会“转角遇到爱”。
溢写线程在80%就被自动触发触发，同时数据继续写，等这80%的数据溢写到磁盘后，会清空该部分，就又可以继续溢写了。
溢写的时候，调用快速排序，必须要给出一个比较器。如果未自定义排序比较器，会默认调用键K的比较器。此时这个“80M”的文件就排好序了。还会调用一个自定义的数据聚合程序combiner（目的是对某个“小文件”进行数据合并），用来合并这个“80M”的文件。假设这个“80M”的数据有1000条，每条都由“K-V-P”组成，有可能经过合并后就会变成200条。
combiner这个功能是极好的，系统没有提供，需要我们来自定义。combiner的内部过程和“Shuffle写”流程中的Reducer的“迭代器”流程一样。
经过上述快排、合并，最终写入磁盘。有多少分区，就写多少磁盘文件。当分区中的文件数量 >=3时，自动触发磁盘合并程序（和上一步的“数据合并”有所区分，该步骤为合并分区号相同的磁盘文件）。
此时的分区文件的特点是“内部有序，整体无序”，因此经过归并算法，调用比较器（当然自定义比较器的优先级更高）。最终合并为1个大的“分区1磁盘文件”。
Shuffle读阶段分析
经过归并、合并后，我们得到的就是一个大“分区1磁盘文件”。此时，Reducer类需要数据。于是，“拷贝线程”自动去所有的map输出的机器上拷贝某一个分区的数据，也就是我们手里的“大文件”。于是，所有的map的输出的“分区1磁盘文件”都会被“拷贝线程”抓取走。
“拷贝线程”拿到手的文件的状态，又是“内部有序，整体无序”，于是再次调用归并排序。归并排序也要走“比较器”。
之后的文件就是有序的，然后抽象为一个对象Iterator迭代器。迭代器就好比游标一样，它里面有“一坨”数据，依次弹出内部的数据。
分组程序会处理这部分数据，比如身高①160、②160、③160、④165、⑤165 。分组程序会调用“自定义分组比较器”（不过未自定义分组比较器，就会去调用用户自定义比较器和键K的比较器），分组比较器的结果只有0和非0 。数据相同为0，会被判定为一组。经过分组程序，①②③被划归一组，④⑤被划归另一组。
这样的第一组自动封装为一个“假迭代器”，第二组封装为另一个“假迭代器”。这里排序是很重要的，如果排序方法不对，分组也一定是错的！
最后，“假迭代器”开始传参给Reducer类，Redecer接收的就是一个个的“假迭代器”。Reducer执行完之后，通过“FileOutputFormat LineRecordWriter”，结果就写入到HDFS结果文件中了。
总结
以上的分析过程，完全符合MR的原语：相同的key为一组，调用一次Reduce方法，方法内迭代这一组数据进行计算！
Map所做的事情：
- 读懂数据
- 映射为KV模型
- 并行分布式
- 计算向数据移动
Reduce所做的事情：
- 数据全量/分量加工
- Reduce中可以包含不同的key
- 相同的Key汇聚到一个Reduce中
- 相同的Key调用一次reduce方法，排序实现key的汇聚
K,V使用自定义数据类型：
- 作为参数传递，节省开发成本，提高程序自由度
- Writable序列化：使能分布式程序数据交互
- Comparable比较器：实现具体排序（字典序，数值序等）