MapReducer之Partitioner与Sort

排序大概分为以下几类

1. MapReducer自带排序就可以满足
2. 自定义sort规则，只设置1个Reducer Task
3. 自定义Partition实现区内有序
4. 启用多个Reducer Task 并实现全局有序，MapReducer提供了TotalSortPartitioner

• 为了满足速度快的要求，对不同的key采用不一样的查找方法，分别是
  • 如果key是BinaryComparable(可以认为是字符串类型)的话会构建trie，时间复杂度是O(n), n是树的深度.
  • 如果是非BinaryComparable类型就构建BinarySearchNode，用二分查找，时间复杂度O(log(n))，n是reduce数。
• 为了满足负载均衡，提供了三个采样类，分别是
  • IntervalSampler：以一定间隔从分片中选择键，适合排好序的文件
  • RandomSampler：以指定的采样率均匀地从一个数据集中选择样本。
  • SplitSampler:取一片数据，把这些片数据进行处理，选出分区用的临界点，进行分区