2.1 map/shuffle/reduce 三阶段形式化
MapReduce 是整个分布式计算的思想源头。即便今天 Spark/Flink 已经进化到更复杂的地步,它们的骨架仍然是从 MapReduce 生长出来的:并行 map、按 key 聚合的 shuffle、reduce 收口。所以这一节先把三阶段的语义讲精确,后续所有引擎都在这张底图上叠加能力。
一次作业的三阶段
一个 MapReduce 作业输入是「一组文件/一组输入分片」,输出是「一组结果文件」。中间经历三个阶段:
输入分片 ──→ [map] ──→ 中间 KV 流 ──→ [shuffle] ──→ 按 key 分组的 KV ──→ [reduce] ──→ 输出
- map 阶段:每个输入分片被一个 map 任务独立处理。map 函数的签名是
(key_in, value_in) → list[(key_mid, value_mid)]——输入一行,输出零个或多个中间键值对。 - shuffle 阶段:把全部 map 任务的中间输出,按中间 key 重新分组,使得「同一个 key 的所有 value 汇到同一个 reduce 任务」。这是全到全通信:每个 map 任务的输出都要按 key 分发到所有 reduce 分区。
- reduce 阶段:每个 reduce 任务收到「一个 key + 该 key 的全部 value 列表」,调用
(key, list[value]) → list[(key_out, value_out)],输出结果。
关键设计点:只有一种数据类型
MapReduce 最重要的抽象是:整个计算过程只流通一种数据类型——键值对(KV)。 map 输入是 KV,map 输出是 KV,shuffle 按 key 分组,reduce 输入输出都是 KV。这把「任意业务」压缩成「键值对的变换」:
- 好处:调度、存储、传输、容错都只需要处理一种结构,框架可以做成通用引擎。
- 代价:不是所有计算都天然适合 KV 表达(图计算、矩阵运算),MapReduce 表达它们很别扭——这正是后续 Dryad、Pregel 等新模型出现的原因(卷一第 14 章)。
用词频统计走一遍
全书反复使用「词频统计(Word Count)」作为最小例子,因为它是「map 展开、shuffle 聚合、reduce 求和」的标准载体。输入三行:
hello world
hello hadoop
world hadoop
map(每个输入分片一个任务,这里一行一个):
- 第 1 行
hello world→(hello,1) (world,1) - 第 2 行
hello hadoop→(hello,1) (hadoop,1) - 第 3 行
world hadoop→(world,1) (hadoop,1)
中间结果共 6 个 KV。shuffle 按 key 分组:
hadoop → [1, 1]hello → [1, 1]world → [1, 1]
reduce 求和:
hadoop → 2,hello → 2,world → 2
最终输出 3 个键值对。注意:reduce 收到的 value 顺序是任意的(取决于 shuffle 实现),所以 reduce 函数必须对顺序不敏感——这是无副作用/幂等纪律的一部分。
shuffle 为什么是「全到全」
shuffle 的本质是 group by key 的分布式实现。如果有 M 个 map 任务、R 个 reduce 分区,那么每个 map 任务都要把自己的输出按 key 打散,分别发往 R 个分区——所以总通信量是「中间数据总量」而不是「某一块」:
- 分区函数
partition(key) → [0, R)决定每个中间 KV 去哪个 reduce。 - 同一个 key 一定进同一个分区(否则聚合就错了)。
- 分区后各分区内的 key 通常要排序(为 reduce 端做 merge 和后续有序输出)。
全到全通信是 MapReduce 最大的成本项,也是后续优化(combiner 减少数据量、二次排序、shuffle 服务)都围绕它的原因。读者现在只需要记住一句话:shuffle 数据量 = 中间数据总量,优化 shuffle 就是优化中间数据的体积与传输。
map 与 reduce 为什么必须「纯函数」
三阶段能在大规模上成立,靠的是 map/reduce 的纯函数性质:
- 无副作用:map/reduce 只读输入、只产输出,不写共享状态、不依赖执行顺序。于是任务可以在任意机器、任意顺序、任意次数执行。
- 可重放:任务失败了重跑,结果不变。这是上一节「容错靠重放」在模型层面的保证。
- 可组合:整个作业等价于「对输入做一次确定性变换」,并行与串行结果一致。
违背其中任何一条(比如 map 里写数据库、用随机数、读全局时钟),重放和并行就会产生不同结果。这是 MapReduce 铁律,也是全书反复强调的纪律。
输入分片:MapReduce 的并行度来源
「把输入切成多少份」决定了 map 任务的并行度。分片(split)是 map 任务的输入单元:
- 分片是逻辑概念,不是物理文件:一个分片通常对应 HDFS 的一个块(默认 128 MB),但也可能一个文件多个分片、或多个文件合成一个分片。
- 分片数量 = map 任务数量:每个分片由一个 map 任务处理,所以并行度 ≈ 分片数。
- 分片与本地性绑定:分片的位置(在哪个节点/机架)决定了 map 任务的调度本地性(2.2)——分片就是要「任务跟着数据走」的那个「数据单位」。
一个 1 TB 文件按 128 MB 块切 ≈ 8000 个分片 → 8000 个 map 任务,分布式地铺在集群上。并行度不是程序员指定的,而是数据量 ÷ 块大小自然决定的——这是 MapReduce 优雅的地方:不用显式管理线程,数据规模天然驱动并行规模。
为什么「排序」出现在 shuffle 而不是 map 或 reduce
经典的 MapReduce shuffle 在 map 端会做「分区 + 排序」。为什么排序?
- 归并的需要:同一 reduce 分区的中间数据来自多个 map 任务,reduce 端要合并成「同 key 的所有 value」。若每份都已按 key 排序,reduce 端只需归并(merge)多个有序流,不必全量再排。
- 有序输出的需要:很多 reduce 输出要按 key 有序(如 TopN、报表排序),shuffle 的排序让输出天然有序。
- 网络/磁盘友好的需要:有序数据压缩率更高、按 key 顺序读磁盘更高效。
所以排序不是「shuffle 顺带做的」,而是为 reduce 端的归并与输出有序铺路。这也是为什么 Spark 的宽依赖也要排序(卷二第 4 章),机制一脉相承。
map 端的「三次展开」与 shuffle 数据量
map 的输出大小直接影响 shuffle 成本,做一次量级估算。设输入 D,map 平均每个输入行展开为 k 个中间 KV:
| 场景 | map 展开系数 k | 中间数据量 | shuffle 成本 |
|---|---|---|---|
| 词频统计(行内多词) | 3–10 | 3–10 × D | 高:几乎全量传输 |
| 过滤清洗(少部分保留) | 0.1–0.5 | 0.1–0.5 × D | 低:大量被过滤 |
| 一对一映射 | 1 | ≈ D | 中:全量但等价 |
shuffle 数据量 ≈ 中间 KV 总量(不是输入量),所以减少中间数据是优化 shuffle 的第一杠杆。三种手段:map 端过滤(少产)、combiner 预聚合(压掉同 key 的多条 value)、压缩。这些在 7 章(Shuffle 实现)和 8 章(combiner)展开。
分区函数与数据倾斜的关系
shuffle 的分区函数 partition(key) → [0, R) 决定每个中间 key 去哪个 reduce 分区,它直接决定了负载均衡。默认的哈希分区 hash(key) % R 在大多数场景工作良好,但两个经典问题:
| 问题 | 表现 | 后果 | 解法 |
|---|---|---|---|
| key 分布不均 | 少数热点 key 占大量数据 | 一个 reduce 任务拿到一半数据,长尾拖慢整个作业 | 倾斜检测 + 单独处理热点 key(12 章) |
| 哈希碰撞集中 | 哈希后多个大 key 撞到同一分区 | 单分区过载 | 换分区函数(如范围分区)、预采样 |
| 空分区 | 数据量远小于 R | 一些 reduce 无事可做 | 调小 R、合并小分区 |
值得强调的是:倾斜不是 MapReduce 的 bug,而是「数据分布」与「分区策略」不匹配的必然结果。同一个作业,换一种分区函数或重新设置分区数,长尾可能完全不同。所以生产里「调分区参数」和「调代码」一样重要——这是 12 章性能模型的前置直觉。
另一层:分区函数还与「全到全」通信量相关。如果分区选择得当,每个 reduce 拿到的数据量接近,网络传输均衡;如果某分区数据量畸形,该分区的网络流也畸形。分区函数的两个目标——正确(同 key 同分区)与均衡(各分区数据量接近)——共同决定 shuffle 的吞吐。
分区数 R 与 reduce 并行度
reduce 的并行度由分区数 R 决定,R 的选择不是「越大越好」,而是要匹配数据量与集群:
| 场景 | R 太小 | R 太大 | 合理取法 |
|---|---|---|---|
| 数据量大、集群大 | reduce 少、单个任务重、长尾 | 任务多、调度开销大、空分区多 | R ≈ 集群可用 slot 的倍数 |
| 数据量小 | 勉强能跑 | 大量空分区、浪费 | R 降到接近 1 |
| 输出要小文件 | 输出文件数 = R | 输出碎片多 | R 取输出目标数 |
R 的工程含义:
- R = 输出文件数:每个 reduce 任务产出一个输出文件,所以 R 直接决定下游读到多少个文件——R 太大产生「小文件问题」(4.2 提到的小文件痛点的一个来源)。
- R 决定 shuffle 的分区粒度:分区越多,每个 map 输出要切给更多分区,partition 的随机 I/O 越多。
- R 与倾斜相关:热点 key 必然落在某个分区,R 再大,该分区仍拿全部热点数据——R 解决不了倾斜,倾斜靠分区策略(预采样)与二次分发。
所以 R 是「并行度、输出文件数、shuffle 开销、倾斜容忍」的联合权衡——生产里常按「目标并行度 × 槽位余量」取,而不是固定一个值。这也是后续 Spark 里分区数可配、Flink 里并行度可调的同源直觉。
三个常见误解
误解一:map 阶段只是「逐行处理」,重点在 reduce。 真相:map 承担「把输入展开为适合聚合的中间表示」的重任,是整个模型的入口和自由度所在。词频统计的 map 看似平凡,但 map 里可以做过滤、清洗、映射、二次计算——模型的能力一半在 map 的展开方式上。
误解二:shuffle 只是「排个序」,性能无关紧要。 真相:shuffle 是全到全通信,中间数据总量常和输入量同量级,是作业耗时的大头。一次大作业的 shuffle 数据可能达数 TB——排序只是它的副产品,传输与落盘才是成本。
误解三:reduce 输入是「有序的、确定的」。 真相:reduce 收到的 value 顺序由 shuffle 实现决定(通常无序或仅按键排序),reduce 必须对顺序不敏感。把「依赖输入顺序」的逻辑写进 reduce,是 MapReduce 编程里最隐蔽也最常见的正确性 bug。
MapReduce 的局限:KV 模型之外的世界
三阶段的 KV 模型优雅,但也不是万能。认识局限,才知道后来为什么出现新模型:
| 计算 | 为什么 KV 别扭 | 后续模型 |
|---|---|---|
| 图计算(PageRank、社交网络) | 图结构不是键值对,迭代中要反复传邻接信息 | Pregel(卷一 14 章) |
| 迭代/机器学习 | 每轮迭代要重扫全量数据、重新 shuffle,慢 | Spark 血缘缓存(卷二) |
| 交互式查询 | 一次作业要分钟级启动,无法即席 | SQL 引擎 / Presto 类(卷四) |
| 流计算 | 数据不是「批次」而是连续流,无法先切分再批处理 | Flink(卷三) |
这些局限不是「MapReduce 做错了」,而是「KV 批处理模型有它的适用域」。理解 MapReduce 不是终点,而是理解后来所有引擎的坐标系——Spark 补迭代与内存、Flink 补流式与状态、数据湖补表语义,都在 MapReduce 的底图上做加法。
一句话总结本节
MapReduce 把任意计算抽象成唯一的数据类型——键值对——的变换:map 把输入展开为中间 KV,shuffle 把全部中间 KV 按 key 全到全分组,reduce 按 key 聚合输出;三阶段能在大规模成立,全靠 map/reduce 的纯函数与可重放性质。
本章实现对照
Hadoop 3.4.2 MapReduce 执行、分区与任务输入
本节 lab
在 bd-fs-lab/ 中复现三阶段:
- 源码:
src/mapreduce/MiniMR.java(run方法完整实现 map→shuffle→reduce)与src/mapreduce/MapReduceSuite.java。 - 运行:
javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。 - 断言:
MapReduceSuite用例 1 用词频统计验证三阶段输出a=2;b=2;c=1(map 展开、shuffle 归并、reduce 求和),且两个 reduce 分区都有产出;用例 2 用自定义分区器验证分区函数决定 key 去向。 - 整卷 runner 的预期汇总为
TOTAL: 140 passed, 0 failed。
对应本节判断链:词频统计的三阶段输出、分区函数对 key 去向的决定作用,都在断言里直接可见——这就是「三阶段模型」的最小运行证明。
机制边界与故障路径
map 输出的键值对经分区、排序和分组送到 reduce;combiner是可选且可能多次执行,不能参与必须只算一次的语义。输出发布与任务重试另有边界。
flowchart LR
IN["输入split"] --> MAP["map产生键值对"] --> COMB["可选combiner,满足代数条件"]
COMB --> PART["partitioner决定reduce归属"] --> SORT["排序/合并/按键分组"] --> RED["reduce"]
RED --> TMP["attempt临时输出"] --> PUB["选定成功attempt后发布"]
MAP -. "失败" .-> RETRY["重试同一输入版本"] --> MAP
这张图标明本章机制的组件和边界,不是本机已运行过所有分支的追踪记录。算例、原生观测与未测工程能力应按正文及实验 README 的范围分别核对。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。