7.1 分区、排序与归并
2.1 讲了 shuffle 是「全到全」通信,这一节深入它的第一块拼图:map 端的分区与排序、reduce 端的归并。这三件事合起来,回答「中间 KV 如何从 M 个 map 任务、按 key 汇聚到 R 个 reduce 任务」。
shuffle 的三步:分区、排序、传输
一个 map 任务的中间输出,要经历三步才能被 reduce 消费:
map 输出 KV ──→ ① 分区(按 partition(key) 分流)
──→ ② 排序(分区内按 key 排序)
──→ ③ 传输/落盘(发给对应的 reduce 分区)
- 分区:决定「这个 KV 属于哪个 reduce 分区」——
partition(key) → [0, R)。 - 排序:每个分区内按 key 排序(为归并铺路)。
- 传输:各分区的数据发往对应 reduce 节点(或落盘等待)。
这一节聚焦 ①②(分区 + 排序),③ 传输优化在 7.3 讲。
分区函数:同 key 同分区
分区函数是 shuffle 正确性的第一关:同一个 key 必须进同一个分区,否则它的 value 会被分到两个 reduce,聚合就错了。
| 分区函数 | 做法 | 特点 |
|---|---|---|
| 哈希分区(默认) | hash(key) % R | 分布均衡、实现简单 |
| 范围分区 | key 落在 [a,b) 区间 → 某分区 | 输出有序(如全局排序) |
| 自定义分区 | 业务规则(如按首字母) | 满足特殊需求(8.1 讲) |
哈希分区的均衡性依赖「key 分布均匀」——如果 key 本身倾斜(少数 key 大量出现),哈希分区也无法均衡(6.1 讲过「分片不治 key 倾斜」)。分区函数的两个目标:正确(同 key 同区)与均衡(各分区负载相近),后者在倾斜时只能靠自定义分区或二次分发。
为什么排序:归并的前提
map 端排序看起来是「额外开销」,但它是 reduce 端归并的前提。看归并需要什么:
- reduce 收到的是「来自多个 map 任务、同一分区的多个数据流」。
- 若每个流内已按 key 排序,reduce 只需做 K 路归并(merge)——同时比较 K 个流的当前 key,取最小的,合成一个有序大流。
- 若不排序,reduce 只能全量重新排序(开销大)或接受无序(无法按 key 聚合)。
所以 map 端的排序,是给 reduce 端「免费」得到有序输入的成本。排序发生在数据量最小的 map 端(中间输出),比发生在数据量最大的 reduce 端便宜得多。
归并(Merge):K 路合并有序流
reduce 端的归并是 shuffle 的正确性核心之一。它解决「同 key 的 value 来自多个 map 任务」的合并问题:
K 个有序输入流(各来自一个 map 任务):
map1: (a,1)(b,1)(c,1)
map2: (a,1)(b,1)
归并(K 路 merge):
同时看 K 个流的当前 key,取最小的:
→ (a,1)(a,1) [key a 的两个 value]
→ (b,1)(b,1) [key b 的两个 value]
→ (c,1)
reduce 按 key 处理:a→[1,1] b→[1,1] c→[1]
归并的关键:它把「同一个 key 的 value 散落在多个流」的问题,变成「按序从多个流取出同 key 的所有 value」的问题——这正是「按 key 聚合」的分布式实现。归并不用把全部数据再排一遍,只是把「已排序的多个流」合成「一个有序的聚合流」,开销与数据量线性相关、而非平方级。
排序在哪里做:map 端 vs reduce 端
「排序放 map 端还是 reduce 端」是一个设计选择,不同引擎有不同取舍:
| 方案 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| map 端排序(经典 MR) | map 输出先排序再传输 | reduce 归并便宜 | map 端多一次排序开销 |
| reduce 端排序 | 收齐后统一排序 | map 端更轻 | reduce 端数据量大、排序贵 |
| 两者结合(现代引擎) | map 端排序 + reduce 端归并 | 总开销最优 | 实现复杂 |
经典 MapReduce 是「map 端排序 + reduce 端归并」的结合:map 端把每批输出排好,reduce 端用 K 路归并把多个有序流合并。理解「排序位置的选择」= 理解 shuffle 的成本结构:排序要在数据量小的一端做,归并要在需要聚合的一端做。
归并与「二次排序」的关系
归并按 key 排序是「一次排序」。但真实场景常需要同 key 内的 value 也有序——这就是二次排序(8.1 详述):
| 排序层次 | 排序键 | 用途 |
|---|---|---|
| 一次排序 | key | reduce 按 key 聚合 |
| 二次排序 | key + value | 同 key 的 value 也按某字段有序 |
二次排序不是「额外再排一遍」,而是在排序时就把「组合键 (key, value)」按指定顺序排——归并时自然得到「同 key 内 value 有序」的结果。它在 8.1 展开,这里只需知道:归并框架支持「按组合键排序」,是二次排序能实现的原因。
shuffle 数据量的量级与优化动机
shuffle 传输的数据量 = 中间 KV 总量(2.1 讲过)。做一次量级估算:
| 作业 | 输入 | 中间输出(shuffle 数据) | 占比 |
|---|---|---|---|
| 词频统计 | 1 TB | 3–10 TB(每个词一条 KV) | 3–10× |
| 过滤清洗 | 1 TB | 0.1–0.5 TB(保留部分) | 0.1–0.5× |
| 一对一映射 | 1 TB | ~1 TB | ~1× |
shuffle 数据常和输入同量级甚至更大——这就是为什么 shuffle 是作业耗时的最大头(2.1)。三个优化杠杆:map 端过滤(少产)、combiner(7.2 预聚合压体积)、压缩(7.3 压传输)。理解分区/排序/归并,是理解这些优化的基础——它们优化的是「shuffle 数据量」与「排序/归并开销」。
归并的容错视角:中间数据落盘
归并依赖「中间数据可用」。但 map 任务结束后,其中间输出不能一直保留(占内存/磁盘)——所以 shuffle 中间数据的管理是个问题:
| 策略 | 做法 | 代价 |
|---|---|---|
| 落盘 | map 输出写磁盘,reduce 需要时读 | 磁盘 I/O,但失败可重读 |
| 内存保留 | 中间数据留内存,reduce 直读 | 内存占用大、节点故障即丢 |
经典 MR 用「落盘 + 内存缓冲」混合:小数据量在内存、大数据量落盘。reduce 读中间数据时若发现缺失(map 已结束、数据被清),会触发「重跑上游 map」(2.3 讲过 reduce 重放贵)。归并的正确性建立在「中间数据可用」上,而中间数据的可用性是调度与容错共同维护的。
分区数与 reduce 数的关系
分区数 R = reduce 任务数(类似分片数 = map 任务数)。R 的大小决定 reduce 并行度,也决定很多下游成本:
| R 的影响面 | 说明 |
|---|---|
| reduce 并行度 | R 越大,同时跑的 reduce 越多 |
| 输出文件数 | 每个 reduce 写一个输出文件 → R 决定输出文件数 |
| shuffle 传输粒度 | 每个 map 要把中间数据分给 R 个分区 |
| 负载均衡 | R 太少,一个 reduce 扛太多数据 |
R 太大与太小的代价:
| R | 代价 |
|---|---|
| 太大(如百万) | 每个分区只有少量数据,reduce 任务数爆炸、输出文件数爆炸 |
| 太小(如 1) | 一个 reduce 扛全部分区数据,无并行、单点 |
| 合适(数据量/R ≈ 合理量) | 每 reduce 处理适量数据,输出文件数合理 |
工程经验:R ≈ 数据量 / 期望的每 reduce 处理量,同时不小于节点数的若干倍(保证每个节点都有 reduce 可跑)。这与 map 端「分片数 ≈ 槽位 × 倍数」是同源直觉。
R 还直接影响输出质量:R 个输出文件,后续作业读它就是 R 个输入——R 太大制造「人为的小文件」(9.2),太小则单文件过大。所以 R 不只是并行度旋钮,还是「输出布局」的旋钮。
现代引擎的 repartition(调整分区数)正是对 R 的显式控制——理解 R 的决定因素(并行度 + 输出布局 + 负载),是理解后续一切分区调优的起点。
分区函数还有一个「可复现性」要求:同一个 key,在任何 map 任务里都算出同一个分区号——否则不同 map 对同一 key 的分区不一致,value 会被拆散。
| 分区函数 | 可复现性 |
|---|---|
| 哈希分区 | 确定:hash(key) 同输入同输出 |
| 范围分区 | 确定:key 落在固定区间 |
| 自定义分区 | 必须避免随机数/时间戳等不稳定输入 |
分区规则是「跨作业的约定」,不是单作业的私事——后续作业按同一规则处理,分区的语义才能延续。
MapReduce 从溢写到结果提交
Map 的分区号决定数据由哪个 Reduce 拉取。重试按任务尝试隔离,最终提交还受 OutputCommitter 契约约束。
flowchart TD
A[InputSplit] --> B[Map task attempt]
B --> C[缓冲区按分区和键排序]
C --> D[(spill 文件与索引)]
D --> E[合并 Map 输出]
E --> F[Reducer 拉取自己的分区]
F --> G[归并及分组]
G --> H[Reduce 写入尝试目录]
H --> I{允许提交}
I -->|是| J[提交最终输出]
I -->|否| K[清理失败或多余尝试]
三个常见误解
误解一:shuffle 就是「把数据发给 reduce」,分区、排序是顺带做的。 真相:分区、排序是 shuffle 的正确性前提——分区保证同 key 同区(否则聚合错),排序保证归并可做(否则 reduce 全量重排)。它们是 shuffle 的骨架,不是可选优化。
误解二:排序应该放在 reduce 端,因为数据最终在那。 真相:排序要放在数据量小的 map 端做(中间输出),reduce 端用 K 路归并「免费」得有序——若放 reduce 端全量重排,数据量大、开销高。排序位置的选择是 shuffle 成本结构的关键。
误解三:归并就是把多个流「拼接」起来。 真相:归并是按 key 的 K 路合并——同时比较多个流的当前 key,取最小的,合成有序聚合流。不是拼接(拼接会乱序),而是「多路有序合并」,这正是 reduce 能按 key 聚合的机制。
一句话总结本节
shuffle 的第一块拼图是分区、排序与归并:分区函数保证同 key 同区(正确性第一关),map 端排序为 reduce 端 K 路归并铺路(排序放数据量小的一端),归并把多个有序流合成一个有序聚合流、让 reduce 按 key 处理——排序与归并的位置选择,定义了 shuffle 的成本结构。
本章实现对照
本节 lab
在 bd-fs-lab/ 中复现分区与排序:
- 源码:
src/mapreduce/MiniMR.java(shuffle用 TreeMap 按 key 排序、partitioner决定分区、valueCmp支持同 key 内排序)与src/mapreduce/MapReduceSuite.java。 - 运行:
javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:
MapReduceSuite用例 3 验证「自定义分区器:按键首字符奇偶分到 0/1 两区、各收 2 键」;用例 6 验证「二次排序:同 key 的 value 按数值有序k=1,2,3,」。 - 整卷 runner 的预期汇总为
TOTAL: 140 passed, 0 failed。
对应本节判断链:分区函数决定 key 去向、TreeMap 排序让归并有序、valueCmp 支持同 key 内排序——分区与排序的可运行证明。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。