MapReduce 全排序

有三种方法实现Hadoop(MapReduce)全局排序，下面分别介绍

1、使用一个Reduce进行排序

MapReduce默认只是保证同一个分区内的Key是有序的，但是不保证全局有序。如果我们将所有的数据全部发送到一个Reduce，就可以实现结果全局有序。

缺点：
所有的数据都发送到一个Reduce进行排序，这样不能充分利用集群的计算资源，而且在数据量很大的情况下，很有可能会出现OOM问题

2、自定义分区函数实现全局有序

MapReduce默认的分区函数是HashPartitioner，其实现的原理是计算map输出key的 hashCode ，然后对Reduce个数 求余，余数相同的 key 都会发送到同一个Reduce。

如果我们能够实现一个分区函数，使得：

• 所有 Key < 10000 的数据都发送到Reduce 0；
• 所有 10000 < Key < 20000 的数据都发送到Reduce 1；
• 其余的Key都发送到Reduce 2；

这就实现了Reduce 0的数据一定全部小于Reduce 1，且Reduce 1的数据全部小于Reduce 2，再加上同一个Reduce里面的数据局部有序，这样就实现了数据的全局有序。

缺点：
我们必须手动地找到各个Reduce的分界点，尽量使得分散到每个Reduce的数据量均衡。而且每次修改Reduce的个数时，都得手动去找一次Key的分界点！非常不灵活。

3、使用TotalOrderPartitioner进行全排序

Hadoop 内置还有个名为 TotalOrderPartitioner 的分区实现类，它解决全排序的问题。其主要做的事 实际上和 上面介绍的第二种分区实现类很类似，也就是根据Key的分界点将不同的Key发送到相应的分区。
问题是，上文用到的分界点是我们人为计算的；而这里用到的分界点是由程序计算的。

数据抽样

寻找合适的Key分割点需要我们对数据的分布有个大概的了解；如果数据量很大的话，我们不可能对所有的数据进行分析然后选出 N-1 （N代表Reduce的个数）个分割点，最适合的方式是对数据进行抽样，然后对抽样的数据进行分析并选出合适的分割点。Hadoop提供了三种抽样的方法：

• SplitSampler：从s个split中选取前n条记录取样
• RandomSampler：随机取样
• IntervalSampler：从s个split里面按照一定间隔取样，通常适用于有序数据

这三个抽样都实现了 getSample(InputFormat inf, Job job)方法；

这个方法返回抽样到的Key数组，除了 IntervalSampler 类返回的抽样Key是有序的，其他都无序。

获取到采样好的Key数组之后，需要对其进行排序，然后选择好N-1 （N代表Reduce的个数）个分割点，最后将这些Key分割点存储到指定的HDFS文件中，存储的文件格式是SequenceFile，使用如下：

TotalOrderPartitioner.setPartitionFile(job.getConfiguration(), new Path(args[2]));
InputSampler.Sampler<Text, Text> sampler = new InputSampler.RandomSampler<>(0.01, 1000, 100);
InputSampler.writePartitionFile(job, sampler);

//在作业中指定TotalOrderPartitioner为分区器
job.setPartitionerClass(TotalOrderPartitioner.class);

    /**
     * Create a new RandomSampler.
     * @param freq Probability with which a key will be chosen.
     * @param numSamples Total number of samples to obtain from all selected
     *                   splits.
     * @param maxSplitsSampled The maximum number of splits to examine.
     */
    public RandomSampler(double freq, int numSamples, int maxSplitsSampled) {
      super(freq, numSamples, maxSplitsSampled);
    }