全局排序

目的

希望数据能够按照指定的键进行并行排序

动机

排序在顺序结构中很容易实现。但是在MapReduce中，或者更普遍地说在并行编程中，却不那么容易。

每个reducer将按照键对它的数据排序，但不幸的是，这种排序并不是全局意义上的包含所有数据的。

不管是从应用程序还是后端系统的角度看，都有无数的理由要求数据排好序。但是，使用MapReduce进行数据排序，作用不大，因此希望能谨慎使用这种代价高昂的操作。

使用范围

这种模式的要求是显而易见的：排序的键必须有可比性，只有这样数据才能排序。

结构

全排序是一个比较复杂的模式。原因是必须得先根据值的取值范围划分一组分区。并且每个分区将获得相同规模的数据子集。该范围将决定每个reducer将对多少数据进行排序。然后，做与分区模式相似的事情，即通过自定义的分区器按照排序键将数据分区。最低范围内的数据将被第一个reducer处理，接下来范围内的数据将被第二个reducer处理，以此类推。

该模式包含两个阶段：分析阶段和排序阶段。分析阶段确定每个分区的范围。排序阶段则是实际对数据进行排序在某些条件一下，分析阶段是可选的。

分析阶段首先对数据随机采样，然后基于随机样本进行分区。这其中的原理是分区能够均匀地拆分随机样本，那么也能均匀地拆分更大的数据集。分析阶段的结构如下：

• mapper进行简单的随机采样。在拆分记录时，将排序键作为输出键，这样在reducer时数据将是已排好序的。由于我们并不关心实际的记录，因此可以用null值以节省哦空间。
• 事先，要确定整个数据集的记录数并且计算出需要分析的记录所占的百分比，以确定一个合理的样本。
• 这里只需要用到1个reducer。reducer将排序键收集到一个已排序的列表中。然后，当所有的键被收集到后，键的列表将被切分成每个分区数据范围的边界。

排序阶段是一个使用自定义分区器的相对简单的MapReduce应用。排序阶段的结构如下：

• mapper采用与分析阶段相同的方式提取排序键。但是，在这里，记录本身将作为值存储起来，而不是直接忽略。
• 自定义分区器用于加载分区文件。在Hadoop中可以使用TotalOrderPartitioner,它是专门为了这个目的而设计的。TotalOrderPartitioner从前一步产生的分区文件中确定数据的范围，并决定将每条记录发给那个reducer。
• 在这里，reducer的工作相对简单。因为混排和排序承担了大部分工作，reduce函数只是简单地将获取到的值输出。为了使得TotalOrderPartitioner能正常的工作，reducer的个数应该等于分区数。

结果

输出文件将包含已排序的数据，并且输出文件名也是有序的，因此所有数据是全排序的。在Hadoop中，可以通过执行hadoop fs -cat output/part-r-*命令按照已排好顺序获取数据。

性能分析

这是一个代价高昂的操作，因为实际上该模式需要加载和解析两次数据，第一次是建立分区范围，随后才是真正地对数据排序。

建立分区这步简单且高效，因为只有一个reducer，并且只有很少量的数据通过网络发送。由于输出文件很小，所以将其落地这步是微不足道的。同时，该作业只是偶尔运行，所以随着时间的流逝构建分区的消耗也将得到均摊。

排序这步的性能特征和其他数据组织模式很相似。由于所有数据都需要通过网络传输，并且最后

参考

补一个详细的说明：MapReduce排序过程详解