《大规模分布式计算深入解析》7.2 溢写(spill)与 combine

map 输出的内存缓冲与落盘:环形缓冲区满时如何溢写(spill)到磁盘,多个溢写文件如何归并成一个;combiner 如何在 map 端预聚合减少 shuffle 数据量。讲清「内存缓冲 → 溢写 → 归并」是 map 端 shuffle 的流水线,以及 combiner 为什么能大幅压缩中间数据。lab 用迷你 MapReduce 复现 combiner 等价性。

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 源码 · 实验运行与版本说明

在 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 端预聚合不影响正确性」在断言里被直接证明。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路