《大规模分布式计算深入解析》7.1 分区、排序与归并

shuffle 的第一块拼图:map 端如何把中间 KV 按 key 分区、排序,reduce 端如何归并多个有序流。讲清分区函数决定 key 去向、排序为归并铺路、归并如何用 K 路合并把多个有序输入合成一个有序流,以及「排序在哪里做」的设计选择。lab 用迷你 MapReduce 复现分区与二次排序。

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 详述):

排序层次排序键用途
一次排序keyreduce 按 key 聚合
二次排序key + value同 key 的 value 也按某字段有序

二次排序不是「额外再排一遍」,而是在排序时就把「组合键 (key, value)」按指定顺序排——归并时自然得到「同 key 内 value 有序」的结果。它在 8.1 展开,这里只需知道:归并框架支持「按组合键排序」,是二次排序能实现的原因。

shuffle 数据量的量级与优化动机

shuffle 传输的数据量 = 中间 KV 总量(2.1 讲过)。做一次量级估算:

作业输入中间输出(shuffle 数据)占比
词频统计1 TB3–10 TB(每个词一条 KV)3–10×
过滤清洗1 TB0.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 的成本结构。

本章实现对照

MapReduce shuffle、排序和溢写配置

本节 lab

下载 bd-fs-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 内排序——分区与排序的可运行证明。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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