MapReduce中实现全局排序方法

我不是女神ヾ 2022-12-05 10:12 177阅读 0赞

实现MapReduce全局排序有三种方法：

1.  使用一个reduce实现全局排序
2.  自定义分区函数实现全局排序
3.  使用TotalOrderPartitoner进行全局排序

### **使用一个reduce实现全局排序** ###

我们知道，MapReduce默认情况下只保证同一个分区中的key是有序的，不能保证全局有序。如果我们将所有的数据都用一个reduce来处理，就可以实现全局有序。

缺点：此方法的缺点也很明显，所有数据发送到一个reduce进行排序，不但不能充分利用集群的分布式资源，在数据量很大的情况下，很容易出现OOM的情况，效率也很低

### **自定义分区函数实现全局排序** ###

MapReduce默认的分区函数为HashPartitioner，其具体的实现原理是计算map的输出key的hashCode值，然后用该值对reduce个数取余，不同的余数对应不同的reduce，余数相同的key将会被发送到同一个reduce中。

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

*  所以的key < 1000的数据都发送到reduce0；
 *  所有1000 < key < 10000的数据都发送到reduce1；
 *  ……
 *  其余的key都发送到reduceN;

这样就实现了reduce0的数据一定全部小于reduce1的数据，reduce1的数据全部小于reduce2的数据，……，同时每个reduce中数据是局部有序的，这样就实现了全局有序

缺点：该方法的难点在于我们必须手动找到各个reduce的分界点，且尽量是的分散到每个reduce的数据均衡。如果想增加或减少reduce个数，必须再次寻找分界点，非常不灵活。

### **使用TotalOrderPartitioner实现全局排序** ###

MapReduce内部包含一个TotalOrderPartitoner的分区实现类，主要解决全排序问题。其原理和方法2类似，根据key的分界点将不同的key发送到不同的reduce中，区别在于方法2需要人工寻找分界点，而该方法是有程序计算得到。

**数据抽样**

为了寻找到合适的key分界点，我们需要对数据的整体分布有所了解；如果数据量很大，我们就不可能对所有数据进行分析然后选出N-1的分界点（假设reduce个数为N），最适合的方式就是通过数据抽样，对抽样的数据进行分析从而选出合适的分割点。MapReduce提供了三种抽样方法：

*  SplitSampler：从n个split中选择前m条记录取样（不适合有序数据）
 *  RandomSampler：随机取样（通用采样器）
 *  IntervalSampler：从n个split中按照一定间隔取样（通常适用于有序数据）

三种抽样方法都通过getSample(InputFormat inf, Job job)函数返回抽样得到的key数组，除了IntervalSampler方法返回的抽样key是有序的，其他都是无序的

获取到抽样的key之后就可以对其进行排序，然后选择N-1个分界点，最后将这些key的分界点存储到指定的HDFS文件中，存储的文件格式是SequenceFile，具体使用如下：

TotalOrderPartitioner.setPartitionFile(job.getConfiguration(), new Path(args[2]));    // 设置采样数据路径
    InputSampler.Sampler<Text, Text> sampler = new InputSampler.RandomSampler<>(0.01, 1000, 100);    //初始化采样器, 0.01为数据被采样到的概率，1000为采样样本数，100为数据被solit的最大片数
    InputSampler.writePartitionFile(job, sampler);    // 写入采样数据
    
    //在作业中指定TotalOrderPartitioner为分区器
    job.setPartitionerClass(TotalOrderPartitioner.class);

注意：以上配置需要写在配置文件之后，job执行之前

参考：

\[1\] [https://blog.51cto.com/kinglab/2445040][https_blog.51cto.com_kinglab_2445040]

\[2\] [https://www.jianshu.com/p/c537e971945a][https_www.jianshu.com_p_c537e971945a]

\[3\] [https://blog.csdn.net/Marlboro\_2/article/details/82084266][https_blog.csdn.net_Marlboro_2_article_details_82084266]

[https_blog.51cto.com_kinglab_2445040]: https://blog.51cto.com/kinglab/2445040
[https_www.jianshu.com_p_c537e971945a]: https://www.jianshu.com/p/c537e971945a
[https_blog.csdn.net_Marlboro_2_article_details_82084266]: https://blog.csdn.net/Marlboro_2/article/details/82084266