4.4 排序与分组比较器

4.4 排序与分组比较器

本节摘要：排序在 MapReduce 里不只是整理数据，而是分组与归并的结构基础：溢写排序支撑 Map 端归并，区内排序支撑 Reduce 端归并，而"复合键排序加宽松分组比较器"组合出二次排序——值按键内再次有序的经典技术。本节讲透三个排序层次与两把比较器的分工，为第 6 章的经典模式铺好地基。

排序为什么无处不在

回头看前两章，排序已经出现三次：溢写时锁定区按"分区加键"排序（3.1）；分段归并靠流式取最小（4.1 第三步）；Reduce 端归并同样靠有序流切组（4.1 第五六步）。这不是巧合，是设计：归并有序流是分布式数据汇拢的最廉价方式。若各段无序，Reduce 端要全量重排；各段有序，只需一个多指针小顶堆边读边吐，内存占用是流数而不是数据量。MapReduce 甘愿在 Map 端付排序成本，就是为了第三幕能全程流式。

由此还能推出一个经常被问到的结论：Reduce 输入天然按键有序。无论是否需要，你拿到手的值列表顺序就是按键排定的。与其对抗它，不如利用它。

三个排序层次

层次一：区内排序（默认）。 每个分区内键有序，分区之间无关系。MapReduce 的缺省形态，够用于一般聚合。

层次二：单 Reduce 全排序。 只设一个 Reduce 任务，全部数据过一个分区，输出全局有序——代价是第三幕毫无并行可言，仅适合生成有序快照这类小数据任务。想要全排序又不想牺牲并行，用全排序采样（TotalOrderPartitioner）：先采样键分布，生成区间边界文件，自定义分区器按边界把键分进"区间递增"的各分区，分区 0 全是小于边界一的键、分区一全是边界一到边界二的键……各 Reduce 区内有序、区间又首尾相接，输出文件按分区号拼接即全局有序。

层次三：二次排序。 排序键不再是业务键本身，而是"业务键加辅助字段"的复合键，让同一业务键的值按键内顺序到达 reduce。这是本节主角。

复合键与两把比较器

二次排序的标准装备是三件：复合键类、排序比较器（决定到达顺序）、分组比较器（决定谁算同组）。

以经典需求"每个用户取下单时间最早的三条记录"为例。朴素做法是 reduce 里把该用户全部记录物化进列表、排序、取前三——用户记录多时内存爆炸。二次排序的做法是把"排序"交给框架：

// 复合键 用户加时间 compareTo 先比用户 再比时间
public class UserTimeKey implements WritableComparable<UserTimeKey> {
    private Text user = new Text();
    private LongWritable time = new LongWritable();

    public int compareTo(UserTimeKey o) {
        int c = user.compareTo(o.user);
        if (c != 0) return c;
        return time.compareTo(o.time);   // 同用户内按时间升序
    }
    public void write(DataOutput out) throws IOException {
        user.write(out); time.write(out);
    }
    public void readFields(DataInput in) throws IOException {
        user.readFields(in); time.readFields(in);
    }
}
​

// 分组比较器 只按用户判等 复合键里时间被无视
public class UserGroupComparator extends WritableComparator {
    public int compare(WritableComparable a, WritableComparable b) {
        return ((UserTimeKey) a).getUser().compareTo(((UserTimeKey) b).getUser());
    }
}

// 驱动端注册
job.setMapOutputKeyClass(UserTimeKey.class);
job.setGroupingComparatorClass(UserGroupComparator.class);
​

装配后的效果：同一个用户的所有记录经排序后按时间升序到达同一次 reduce 调用（分组比较器只认用户），reduce 里拿一个计数器数到三就够，全程流式、零物化。"取每组前 N"（TopN）、"每组取最大值"、"相邻记录差分"这些模式，全部是这套装备的变体。

图 4.4-1 二次排序的数据形态变化

排序与分组之外的第三个旋钮

完整起见还有 Partitioner 要对齐：复合键的分区若按整个复合键哈希，"同用户不同时刻"可能被分进不同分区，分组即被破坏。所以二次排序装配里，分区必须只按业务键（用户）计算——可以用自定义 Partitioner，也可以让复合键的 hashCode 只由业务字段参与。三件套（排序比较器、分组比较器、分区器）必须指向同一个业务键，这是装配二次排序时的检查口诀。

排序层次选择速查

一个真实的对账案例

支付对账需求：每个商户的流水按时间升序累计判断何时超额。商户数百万、流水数十亿条。物化排序方案在头部商户上反复超内存。改造成二次排序：复合键"商户加时间戳"，分组按商户，reduce 里拿一个累计变量流式判断——单组从头流到尾，内存占用常数级，作业稳定跑完。二次排序的价值就在于此：把"组内排序"从你的内存搬到框架的归并里。

本节要点回顾

• 排序即结构：三次排序支撑两端归并，Reduce 输入天然按键有序是设计馈赠。
• 三个层次：区内排序默认；全排序可用单 Reduce 或采样边界分区；二次排序靠复合键。
• 两把比较器：排序比较器定到达顺序，分组比较器定组边界，后者可比前者宽松。
• 三件套对齐：排序、分组、分区必须指向同一业务键，否则分组被打散。
• 应用形态：TopN、每组最值、组内差分、流式累计判断，全是这套装备的变体。

三幕机制至此全部讲透。下一章把镜头拉远，看支撑这三幕的舞台——从 v1 到 YARN 的架构与调度。