7.2 溢写(spill)与 combine
7.1 讲了分区、排序、归并的「语义」,这一节讲 map 端 shuffle 的「物理实现」:内存缓冲怎么用、满了怎么办(溢写)、多个溢写文件怎么归并,以及 combiner 如何用一次 map 端预聚合把 shuffle 数据量砍掉一个量级。
map 端 shuffle 的流水线
一个 map 任务的中间输出,不是「算一个发一个」,而是走一条「内存 → 磁盘 → 网络」的流水线:
map 逐个产出 KV ──→ 环形缓冲区(内存)──(满)→ 溢写(spill,落盘)
↓
多个溢写文件 ──→ 归并成一个分区文件 ──→ 发给 reduce
关键设计:map 端 shuffle 不阻塞计算。map 一边算、一边把 KV 写进内存缓冲;缓冲满时后台溢写到磁盘,同时 map 继续算。这个「边算边落」的设计让 map 阶段和 shuffle 阶段重叠,是吞吐的根源。
环形缓冲区:内存的复用
溢写的起点是环形缓冲区(circular buffer):
| 参数 | 含义 | 影响 |
|---|---|---|
| 缓冲大小 | 一次能放多少中间 KV | 越大越少溢写(磁盘 I/O 少) |
| 溢写阈值 | 缓冲用到多少百分比触发溢写(如 80%) | 留出余量、避免溢出阻塞 |
| 序列化格式 | KV 按什么格式存 | 决定读写效率 |
环形缓冲的妙处:KV 数据与元数据(索引)分开存,各从一端写,读走时从另一端读——避免大对象搬移。缓冲接近满时触发溢写,map 线程不用停等,只是「写不进的就先落盘」。
溢写(Spill):缓冲满时的落盘
缓冲满到阈值,触发溢写——把当前缓冲里的 KV 写入一个磁盘文件。溢写过程本身做三件事:
溢写一个磁盘文件:
1. 按分区号排序(把 KV 分组到对应 reduce 分区)
2. 分区内按 key 排序(为 reduce 归并铺路,7.1)
3. 每个分区写成一个段(segment),文件里按分区顺序排列
溢写是「边算边落」的关键:一个 map 任务可能溢写多次(缓冲反复满),产生多个溢写文件。这些文件在 map 结束前要合并成一个,reduce 才能拿到「一个分区一个文件」的干净输入。
归并溢写文件:多段合一
map 任务结束时,可能有多个溢写文件。归并它们:
溢写文件 1: [分区0: (a,1)(b,1)] [分区1: (c,1)]
溢写文件 2: [分区0: (a,1)(b,1)] [分区1: (d,1)]
归并(按分区、按 key 的 K 路归并,7.1 的归并):
分区0: (a,1)(a,1)(b,1)(b,1)
分区1: (c,1)(d,1)
最终:每个分区一个有序段,发给对应 reduce
归并时机是个权衡:早归并(每次溢写后)内存占用小、文件少;晚归并(最后一次性)I/O 少但中间文件多。经典实现是「阈值控制」:溢写文件数超过阈值就做一次合并,否则留到最后。
Combiner:map 端预聚合
combiner 是减少 shuffle 数据量的最重要手段。它是在 map 端做一次「迷你 reduce」:
词频统计,一行「a a a b b」:
无 combiner:map 输出 5 条 KV → shuffle 传输 5 条
有 combiner:map 先按 key 聚合 → (a,3)(b,2) 2 条 KV → shuffle 传输 2 条
combiner 的本质:在数据量还小的 map 端,先把「同 key 的 value」合并,让 shuffle 传输的数据量从「每个 value 一条」降到「每个 key 一条(聚合后)」。对词频这类「值可合并」的计算,combiner 能把 shuffle 数据量砍掉一个量级。
Combiner 的适用条件:值必须「可结合」
combiner 不是任何 reduce 都能前置:它要求 reduce 的操作满足结合律(associative):
| 操作 | 结合律 | combiner 可用 |
|---|---|---|
| 求和(sum) | (a+b)+c = a+(b+c) | ✅ 词频、计数 |
| 取最大/最小 | 结合 | ✅ |
| 平均值 | 不结合(均值不能「均值的均值」) | ❌ 需特殊处理 |
| 去重集合 | 结合 | ✅ |
| TopN | 部分(取局部 TopN 再合并可取全局) | ✅(注意边界) |
判断依据:combiner 的输出要和 reduce 的输入语义一致——即「先 map 端聚合一部分、再 reduce 聚合剩余」,与「直接 reduce 聚合全部」,结果必须相同。满足结合律的聚合才满足这个条件。
Combiner 与二次排序的边界
combiner 会在 map 端把同 key 的 value 合并,这会不会破坏「同 key 内 value 有序」(二次排序)?
| 场景 | combiner 的影响 |
|---|---|
| 求和/计数 | 值被合并成聚合值,value 顺序自然消失(可接受,reduce 只要总和) |
| 二次排序(value 有序) | 不能随便 combine 掉 value 的多样性——需要「先局部排序再取前 N」的 combiner |
结论:combiner 不是万能的,它必须在「不破坏 reduce 语义」的前提下做。需要 value 有序(二次排序)时,combiner 要么不做、要么做「局部 TopN」这类保序的聚合。理解 combiner 的边界,才不会在需要保序的场景误用。
Combiner 的数据量账
combiner 省的是「map 端到 reduce 端的传输 + reduce 端归并」两笔账:
| 阶段 | 无 combiner | 有 combiner |
|---|---|---|
| shuffle 传输 | 每个 value 一条 | 每个 key 一条(聚合后) |
| reduce 归并 | 处理所有 value | 处理聚合后的 value |
| reduce 计算 | 全部聚合 | 合并 map 端已聚合的部分 |
对「值多可结合」的作业,combiner 的收益是数量级的(词频 5 条 → 2 条,稀疏大 key 集收益更大)。对「值少不可结合」的作业,combiner 不做反而更好(多一次计算、无收益)。combiner 是「是否值得」的工程决策,不是默认开启的银弹。
溢写文件与最终分区文件的布局
map 任务最终产出一个「分区文件」——但它不是「一堆 KV 的杂烩」,而是按分区组织 + 带索引的结构:
最终分区文件:
[数据区] 分区0 的有序 KV | 分区1 的有序 KV | ... | 分区 R-1 的有序 KV
[索引区] 分区0 的偏移/长度 | 分区1 的偏移/长度 | ...
| 结构 | 内容 | 用途 |
|---|---|---|
| 数据区 | 各分区的有序 KV 段 | reduce 读自己的段 |
| 索引区 | 每分区的偏移与长度 | reduce 能「跳读」到自己的分区段 |
这个「数据 + 索引」布局解决一个关键问题:reduce 只想读「自己那个分区」的段,不想读整个文件。
- 有索引:reduce 按索引跳到「分区 P 的段」,只读该段——按段读取,不浪费 I/O。
- 无索引:reduce 要么全读再丢弃、要么从文件头顺序扫到自己的分区段。
索引是「给 reduce 一张地图」:把「按 key 分区」的语义,变成「按偏移定位」的物理读取。这也是 9.3 列式存储「段 + 统计」结构的同源思想——文件内部按访问模式组织,读取才能有的放矢。
归并溢写文件时,归并后的最终文件同样按「分区段 + 索引」重排。所以溢写文件是「过程文件」,最终分区文件是「交付物」——过程文件的布局自由,交付物的布局必须规整(分区段 + 索引)。
溢写阈值与归并阈值要配合:阈值太低 → 频繁溢写、段多归并忙;阈值太高 → 缓冲扛满、甚至内存溢出。
| 阈值 | 太低 | 太高 |
|---|---|---|
| 溢写阈值(缓冲用满百分比) | 频繁溢写、I/O 多 | 缓冲扛满、可能内存溢出 |
| 归并阈值(溢写文件数) | 频繁合并、额外 I/O | 文件太多、最后归并负担重 |
工程按「map 输出量 vs 缓冲大小」预估:一个 map 输出量级是缓冲的几倍,就预期溢写几次——溢写次数是「map 输出量 / 缓冲大小」的自然结果,不是调出来的运气。
三个常见误解
误解一:溢写是「性能问题」,应该把缓冲区调大避免溢写。 真相:溢写是 map 端 shuffle 的正常机制(内存有限、必须落盘),不是故障。调大缓冲只是「减少溢写频率」,但大缓冲占用内存、挤占其他资源——工程上要平衡,不是「避免溢写」。
误解二:combiner 是「可选的优化,加了只会更好」。 真相:combiner 要求 reduce 满足结合律,且在某些场景(需保 value 有序、值不可结合)加了反而错或浪费。combiner 是「条件可用的优化」,不是无脑加。
误解三:combiner 和 reduce 一样,map 端跑一遍 reduce 就行。 真相:combiner 是「map 端的迷你聚合」,它的输出要满足「再经 reduce 聚合结果不变」(结合律);而 reduce 是「最终聚合」。两者在「何时做、对什么数据做」上不同——combiner 是对单个 map 任务的部分数据做,reduce 是对全部分区数据做。
一句话总结本节
map 端 shuffle 是一条「环形缓冲 → 溢写 → 归并」的流水线:缓冲满时把 KV 按分区、按 key 排序后溢写落盘,多个溢写文件在 map 结束前归并成每个分区一个有序段;combiner 在数据量还小的 map 端做一次「满足结合律的迷你聚合」,把 shuffle 传输从「每个 value 一条」压到「每个 key 一条」——溢写让内存有限成为可能,combiner 让 shuffle 数据量降一个量级。
本节 lab
在 bd-fs-lab/ 中复现 combiner 等价性:
- 源码:
src/mapreduce/MiniMR.java(Job.combiner在 map 端预聚合、shuffle归并时先走 combiner)与src/mapreduce/MapReduceSuite.java。 - 运行:
javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:
MapReduceSuite用例 5 验证「combiner 的输出与无 combiner 完全一致(a=3)」——证明「map 端预聚合 + reduce 再聚合」与「直接 reduce 聚合」结果相同(结合律)。 - 整卷 runner 的预期汇总为
TOTAL: 140 passed, 0 failed。
对应本节判断链:同一份输入,有 combiner 与无 combiner 的最终输出逐字节一致——「map 端预聚合不影响正确性」在断言里被直接证明。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。