8.1 二次排序与自定义分区
7.1 提到二次排序,这一节展开它和自定义分区:二次排序让 reduce 收到「同 key 内 value 有序」的数据;自定义分区让数据按业务规则(而非哈希)分布。两个技巧一个解决「顺序」,一个解决「分布」,是 MapReduce 进阶的第一块拼图。
二次排序:为什么需要 value 有序
默认 shuffle 只保证「按 key 分组」,同 key 的 value 顺序不保证(reduce 收到的 value 列表内部无序)。但很多场景需要「同 key 内按某字段有序」:
| 场景 | 需要的顺序 | 用途 |
|---|---|---|
| 日志按时间排序 | 同 key 的 value 按时间升序 | 输出有序结果 |
| TopN | 同 key 的 value 按分数降序 | 取每 key 前 N 条 |
| 时间序列分析 | 同 key 的 value 按时间戳 | 顺序处理事件 |
「reduce 端自己排序」可以,但把排序前置到 shuffle(map 端/归并时排好)更高效——这正是二次排序做的事。
二次排序的实现:组合键
二次排序的秘密是组合键(composite key)——把「key + 排序字段」合成一个键来排序:
需求:按 (key, 时间戳) 排序
组合键:key = ("word", timestamp)
排序规则:
先按 key(word)分组
同 key 内按 timestamp 排序
reduce 分组规则:只按「第一部分」分组(忽略 timestamp)
实现三要素:
| 要素 | 作用 |
|---|---|
| 组合键 | 把 key + 排序字段合成一个排序对象 |
| 排序比较器 | 先比 key、再比 timestamp(完整排序) |
| 分组比较器 | 只比 key(分组时忽略 timestamp) |
关键点:排序与分组用「不同的比较器」——排序按完整组合键(保证同 key 内有序),分组只按 key(保证同 key 的 value 汇到同一 reduce)。两者分离,是二次排序能「有序又不打散分组」的核心。
二次排序与「一次排序」的关系
二次排序不是「额外再排一遍」,而是「一次排序就排好两层」:
| 排序 | 键 | 比较器 | 结果 |
|---|---|---|---|
| 一次排序 | key | 只比 key | 同 key 的 value 无序 |
| 二次排序 | (key, value_sort_field) | 先比 key 再比 sort_field | 同 key 的 value 有序 |
从一次排序到二次排序,只是换了「排序键」和「分组键」的定义——排序框架不变,比较器从「只比 key」变成「先比 key 再比 value 字段」。所以二次排序不是新机制,而是「组合键 + 双比较器」的巧妙复用。
自定义分区:业务规则决定分布
默认哈希分区对大多数场景足够,但有些场景需要「按业务规则」决定 key 去哪个 reduce:
| 场景 | 需要的分区 | 哈希分区的问题 |
|---|---|---|
| 数据倾斜 | 热点 key 单独一个分区 | 热点 key 挤爆某分区 |
| 区域聚合 | 按地区分区(华东、华北…) | 哈希把地区打散 |
| 输出有序 | 范围分区(输出全局有序) | 哈希无序 |
自定义分区函数 partition(key, numPartitions) 返回「key 去哪个分区」。它替换默认哈希,让业务规则成为分布依据。
自定义分区与「正确性」约束
自定义分区有一个硬约束:同 key 必须进同分区。违反它会破坏 reduce 聚合:
| 约束 | 若违反 |
|---|---|
| 同 key 同分区 | 一个 key 的 value 被分到两个 reduce → 聚合错 |
| 分区范围覆盖全部 | 某些 key 无处可去 → 数据丢失 |
| 返回分区号 < numPartitions | 越界 → 错误 |
所以自定义分区只能改变「哪些 key 去哪个分区」,不能改变「同一个 key 只去一个分区」。工程上常见错误是「想按子字段分区却把同 key 拆开」——比如按「月份」分区但聚合键是「用户」,同用户的跨月数据会被拆散。
自定义分区如何治倾斜
自定义分区是治数据倾斜(6.1/7.1 提过)的经典手段:
场景:key "热门词" 占 50% 数据
默认哈希:热门词挤爆一个分区(长尾)
自定义分区:
热门词 → 单独分区(把它隔离出来)
其余 key → 其余分区
热点分区可再拆(如热门词拆多个子分区)或单独处理
关键:自定义分区「把热点隔离」,而不是「把热点均分」——热点仍是热点,但被隔离到独立分区后,其余分区的负载正常了。更进一步(现代引擎)用「倾斜感知」把热点 key 拆成多份分别处理(卷四第 7 章展开)。
分区函数的均衡性:静态 vs 动态
分区函数的均衡性分两档:
| 档位 | 做法 | 特点 |
|---|---|---|
| 静态分区 | 分区函数固定(哈希/自定义) | 简单;对静态分布的 key 有效 |
| 动态分区 | 预采样 key 分布后定分区边界 | 对倾斜/变化分布更稳 |
经典 MapReduce 用静态分区;大数据量、分布变化的场景用「预采样」——先抽样统计 key 分布,再按「均匀负载」设定分区边界(范围分区)。分区的均衡性最终取决于「分区函数是否与 key 分布匹配」,静态对静态、动态对动态。
二次排序 + 自定义分区的组合
两个技巧常组合使用(一次作业同时用):
作业:按 (key, 时间) 输出每 key 的 TopN
自定义分区:热点 key 单独分区(防倾斜)
二次排序:组合键 (key, 时间) 排序(保 value 有序)
reduce:取前 N 条(因为已有序)
组合的意义:二次排序保证「每 key 内有序」(处理顺序),自定义分区保证「key 分布均衡」(负载均衡)——一个管顺序、一个管分布,互不冲突,一起用是 MapReduce 进阶作业的标准打法。
二次排序与 TopN:有序的收益
二次排序最典型的收益场景是 TopN:取每个 key 的前 N 条。它让 reduce 端「不需要全量排序」。
| 做法 | reduce 端做的事 | 成本 |
|---|---|---|
| 无二次排序 | 收齐全部 value → 全量排序 → 取前 N | 全量排序 O(V log V) |
| 有二次排序 | 收到已有序的 value → 直接取前 N 条 | 只扫前 N 条 O(N) |
对「每 key 的 value 很多、只要前几条」的作业,差别是数量级的:全量排序 vs 扫描前 N 条。
二次排序还给 reduce 端省「内存」:无二次排序时,reduce 要缓存全部 value 才能排序取 TopN;有二次排序时,reduce 只需「保留前 N 大的」、读到更大的才替换(小顶堆),内存占用从「全部 value」降到「N 条」。
这就是「排序在 map 端做、收益在 reduce 端拿」的又一处体现(7.1):map 端一次排序的成本,换回 reduce 端「不全量排序 + 不缓存全部」两个收益。
TopN 这类「先局部 TopN 再合并」的操作,还与 7.2 的 combiner 兼容:map 端先取局部 TopN,reduce 合并局部 TopN 得全局 TopN——有序让「分段取优」成为可能。
自定义分区还有一个工程约束:分区函数要与 reduce 输出对齐——后续作业按「区域分区」继续处理时,前序作业的分区规则要保持一致,否则二次分区打乱后续处理的本地性。
| 约束 | 说明 |
|---|---|
| 跨作业一致 | 同一 key 在不同作业里分区规则相同 |
| 与业务对齐 | 分区边界(如区域)要与下游消费匹配 |
| 输出对齐 | reduce 输出按分区组织,下游才能本地读 |
分区规则是「跨作业的约定」,不是单作业的私事——一次作业的分区选择,会影响下游一系列作业的布局。
三个常见误解
误解一:二次排序是「reduce 收到数据后再排一遍」。 真相:二次排序是在 shuffle 的排序/归并阶段用组合键排好——reduce 收到时同 key 内已有序,不需要 reduce 端再排。它是「前置排序」,不是「reduce 内排序」。
误解二:自定义分区可以随意改,包括把同一个 key 拆到多个分区。 真相:自定义分区必须保证同 key 同分区——违反它会导致一个 key 的 value 分散到多个 reduce、聚合错。自定义分区只能改「key 去哪」,不能改「同 key 只去一个」。
误解三:二次排序会打乱分组,同 key 的 value 可能被拆散。 真相:二次排序用分组比较器只按 key,保证同 key 的 value 仍汇到同一 reduce——排序比较器(完整键)与分组比较器(仅 key)分离,正是为了「有序又不拆组」。
一句话总结本节
二次排序用组合键 + 双比较器(排序比完整键、分组只比 key)让 reduce 收到「同 key 内 value 有序」的数据;自定义分区用业务规则替换哈希分区,把热点隔离、把数据按业务对齐,但必须守住「同 key 同分区」的正确性红线——一个管顺序、一个管分布,组合使用是 MapReduce 进阶的标准打法。
本章实现对照
MapReduce Partitioners、Counters 和 DistributedCache
本节 lab
在 bd-fs-lab/ 中复现二次排序与自定义分区:
- 源码:
src/mapreduce/MiniMR.java(valueCmp支持同 key 内排序、partitioner支持自定义分区)与src/mapreduce/MapReduceSuite.java。 - 运行:
javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:
MapReduceSuite用例 6 验证「二次排序:同 key 的 value 按数值有序k=1,2,3,」;用例 3 验证「自定义分区:按键首字符奇偶分到 0/1 两区、各收 2 键」。 - 整卷 runner 的预期汇总为
TOTAL: 140 passed, 0 failed。
对应本节判断链:valueCmp 让同 key 内 value 有序(二次排序)、partitioner 让 key 按业务规则分布(自定义分区)——两个技巧在断言里各自可见。
机制边界与故障路径
二次排序要协调分区器、排序比较器与分组比较器。分区器按主键把同组送同一reducer,复合键排序产生组内次序;只改排序比较器不能保证组数据共置。
flowchart LR
KV["复合键(primary,secondary)"] --> PART["partition按primary"] --> SHUF["同primary落同reduce"]
KV --> SORT["sort按primary再secondary"]
SORT --> SHUF
SHUF --> GROUP["group只按primary"] --> VALUES["组内按secondary流式处理"]
GROUP -. "分区规则不一致" .-> BAD["同组分散,结果错误"]
这张图标明本章机制的组件和边界,不是本机已运行过所有分支的追踪记录。算例、原生观测与未测工程能力应按正文及实验 README 的范围分别核对。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。