[大牛翻译系列]Hadoop（6）MapReduce排序：总排序（Totalordersorting）

4.2.2 总排序（Total order
sorting）

有的时候需要将作业的的所有输出进行总排序，使各个输出之间的结果是有序的。有以下实例：

• 如果要得到某个网站中最受欢迎的网址（URL），就需要根据某种受欢迎的指标来对网址进行排序。


• 如果要让最活跃的用户能够看到某张表，就需要根据某种标准（发表文章数）对用户进行排序。

技术22
在多个reduce间对键进行排序

在MapReduce框架中，map的输出会被排序，然后被发送给reduce。不过，相同reduce的输入数据是有序的，不同reduce的输入数据就没有顺序关系了。如果要让不同的reduce的数据也存在顺序关系，就需要使用分区器（partitioner）。MapReduce的默认分区器是HashPartitioner。它使用map的输出键的哈希值进行分区。这保证了相同的map输出键的所有记录会到达同一个reduce。不过HashPartitioner并不会对所有map的全部输出键进行总排序。接下来说明如何在MapReduce中对所有map的全部输出键进行排序：

问题

需要对作业输出的所有键进行总排序，但是不能增加任何一个reduce的负担。

方案

这里要用到TotalOrderPartitioner类来保证所有reduce的全部输出是有序的。这个类由Hadoop自带。这个分类器保证了所有map的全部输出是完全有序的。那么只要reduce的输出键和输入键是一样的，作业的最终输出就是有序的。

讨论

TotalOrderPartitioner是Hadoop的内置分区器。它根据分区文件进行分区。分区文件是一个包括N-1个键的预先计算好的序列文件。（N是指reduce的个数。）分区文件中的键的顺序是由map输出键比较器决定的。每一个键对应着一个逻辑区间。TotalOrderPartitioner检查每一个输出键，确定它在那个区间，然后将这个键发送给相对应的reduce。

图4.15中说明了这个技术的两个部分。第一部分，创建分区文件。第二部分，将TotalOrderPartitioner加入MapReduce作业。

>

先用InputSampler从输入文件中抽样，以生成分区文件。抽样器可以选用RandomSampler类进行随机抽样，也可以选用IntervalSampler类进行间距为R的等距抽样。生成的分区文件中将包含有序的N-1个键。N是reduce的个数。InputSampler不是MapReduce作业。它从InputFormat读取数据。它在被调用的过程中生成分区。

下列代码说明了在调用InputSampler函数之前需要完成的步骤：

下一步在作业中指定TotalOrderPartitioner为分区器：

这个技术并不需要修改MapReduce作业本身，也就是说，不需要修改map或reduce过程。现在就可以开始运行代码了：

从MapReduce作业的结果中可以看到，在各个输出文件之间，map的输出键是有序的。

小结

这个技术中使用InputSampler来创建分区文件。TotalOrderPartitioner使用这个分区文件来分区map的输出键。

MapReduce也可以生成分区文件，但效率不高。另一个有效的的方法就是用自定义的InputFormat类来执行抽样，并将抽样后的键发送给一个reduce，由其创建分区文件。这也就是这一章下一个部分讲到的抽样。

[大牛翻译系列]Hadoop（6）MapReduce 排序：总排序（Total order sorting）,布布扣,bubuko.com