5.1 MapReduce：分片、Shuffle 与失败恢复
分布式批计算把输入切成可并行任务，在节点失败时重跑确定性工作，并通过 Shuffle 把同一 key 的中间结果送到同一个 Reduce 分区。
MapReduce 的价值不只在两个函数，而在框架接管了调度、数据局部性、重试、排序和提交。
数据流
Input splits
↓
Map tasks: (k1, v1) → [(k2, v2)]
↓ local spill / sort
Partition + Shuffle
↓
Reduce tasks: (k2, [v2]) → [(k3, v3)]
↓
Committed outputMap task 按输入 split 并行，split 是输入格式定义的逻辑工作单元，不必等于一个文件或存储 block。Partitioner 决定中间 key 去哪个 reducer；同一 key 必须路由到同一分区。Shuffle 涉及本地落盘、网络传输、归并和排序，通常是最昂贵阶段。
Combiner 需要代数性质
Combiner 可以在 Map 端先聚合，减少网络字节，但框架可能不执行它，也可能执行多次，所以“有没有先合并”不能改变最终答案。操作应在输入输出类型上闭合，并满足能安全分组的结合/交换语义。
求和适合；直接求平均不适合，因为“各分片平均值再平均”会忽略样本数。正确做法是传 (sum, count)，最终再除。例如分片 A 为 [0, 10]、B 为 [100]，平均数再平均得到 (5 + 100) / 2 = 52.5，实际应为 110 / 3。局部输出 (10, 2) 与 (100, 1)，合并成 (110, 3) 后才保留了权重。
这里的结合律是业务运算的要求；浮点加法受舍入影响，并非位级严格结合。需要可复现结果时，还要约定数值类型、精度和比较容差。
失败通过重跑恢复
Worker 失败后，框架可以在其他节点重跑 Map/Reduce task。前提是任务对同一输入可重复执行，并且外部副作用受控制。
若 Mapper 直接调用外部支付或发送邮件，task 重试会重复副作用。分布式计算应写受框架提交协议管理的输出，外部效果再通过幂等消费处理。
投机执行可为慢 task 启动另一个 attempt，由提交协议选择一个成功 attempt 的输出并取消其他尝试。它能缓解偶发 straggler，却不能消除热 key 导致的固有大分区；多个副本一起算同一份巨量输入，只会让它更热闹。外部副作用仍可能重复发生。
Output commit 避免半成品
Task 通常先写临时输出，由提交协议发布一个成功 attempt 的结果。但“每个 task 只发布一个结果”不等于“整个 job 的所有分区原子出现”。消费者应使用引擎约定的完成标记、manifest 或表事务。一个通用做法是每次运行写独立版本目录，全部成功后再切换读者使用的版本指针；失败的目录不成为当前版本。
对象存储上的 rename 语义与文件系统不同，具体引擎需要 manifest、commit protocol 或原子元数据切换。不能假设所有存储的目录重命名都廉价且原子。
数据倾斜决定长尾
平均每分区 10 GB 不代表每个分区接近 10 GB。热门 key 可能把一个 reducer 推到数百 GB，让其余节点全部等待。
缓解方式：
- 用采样估计 key 分布；
- 对可拆分热点 key 加盐并二阶段聚合；
- 广播足够小的维表，避免大 shuffle；
- 自定义 partitioner；
- 在业务允许时单独处理超级 key。
加盐必须配套还原 key 的第二阶段：先按 (原 key, salt) 求局部 (sum, count)，再去掉 salt 合并。只加盐不再聚合，会把同一个业务结果拆成多行。MapReduce 的分区内排序也不等于所有输出分区天然全局有序。
容量与正确性指标
- 输入/输出字节与记录数；
- shuffle read/write、spill 和网络时间；
- task 分布、p50/p99 时长与 straggler；
- 重试、失败和投机 attempt；
- 数据倾斜和最大分区；
- 输出计数、校验和及业务不变量。
下一课进入 DAG 引擎，理解 Spark 如何通过 lineage、窄/宽依赖和结构化计划优化多阶段计算。
参考资料
Apache Hadoop, MapReduce Tutorial
Apache Hadoop, S3A Committers
Dean, Ghemawat, MapReduce: Simplified Data Processing on Large Clusters