MIT 6.824 学习记录：MapReduce 论文阅读与思考

今天开始正式学习 MIT 6.824 分布式系统，按课程要求我阅读了经典论文《MapReduce: Simplified Data Processing on Large Clusters》。这篇文章介绍了 Google 提出的一个分布式计算模型 —— MapReduce，用来简化大规模数据处理任务的开发。

虽然我之前做过一些简单的任务调度框架项目，但这次阅读让我意识到 MapReduce 在工程层面的很多设计都特别巧妙，尤其是容错与备份任务机制，给了我不少启发。以下是我对这篇论文内容的笔记整理和一些个人理解。

论文下载地址：https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/mapreduce-osdi04.pdf

简单概述

定义：MapReduce 是一个参考了函数式语言的 programming model 编程模型

问题：许多任务在逻辑上很简单，但由于输入数据规模巨大，必须借助分布式系统进行处理。然而多机环境引入了数据分布、容错、并行调度等工程复杂性，MapReduce 通过引入新的编程抽象来隐藏这些底层细节

用途：MapReduce 可用于处理和生成大规模数据集，尤其适用于文本处理、日志分析、索引构建、统计计算等

设计：抽象划分为 map 函数和 reduce 函数：

• map 处理输入的 K/V 键值对并输出中间态的 K/V 键值对

• reduce 聚合具有相同 key 的所有中间值

系统特性：

• 将输入数据进行分片并分发给 Map 任务

• 调度任务在不同节点运行，并动态重试失败任务以实现容错

• 通过中间 key 对自动分组并将其送至相应 Reduce 节点

• 管理节点间的数据传输与通信

伪代码：

map(String key, String value):
  // key: document name
  // value: document contents
  for each word w in value:
    EmitIntermediate(w, "1");

reduce(String key, Iterator values):
  // key: a word
  // values: a list of counts
  int result = 0;
  for each v in values:
    result += ParseInt(v);
  Emit(AsString(result));

具体实现

工作流程

1. 用户传入数据，将数据划分为 M 份，具体大小由可选参数控制

2. 多机集群中有一个主节点，负责管理和分配任务，其他节点是 worker 节点，负责执行具体任务。整个系统会有 M 个 map 任务和 R 个 reduce 任务，主节点将它们分配给 worker 节点

3. 被分配到 map 任务的 worker 从输入数据中解析出 K/V 键值对，并将它们传递给自定义的 Map 函数，Map 函数生成中间态的键值对并缓存在内存中

4. 内存中的键值对会被定期写到本地磁盘，并通过分割策略被划分成 R 份，每一份的地址会被传递给主节点，由主节点传给执行 reduce 任务的 worker 节点

5. 当 reduce worker 获取地址信息后，通过 RPC 调用读取 map worker 本地磁盘中的缓存数据。读取完成后会对中间键值对进行排序，使得所有 key 相同的键值对排列在一起

6. 完成排序后，reduce worker 遍历序列，按 key 分组将键值对传参到 Reduce 函数，最终结果输出到一个文件中

7. 所有任务完成后，主节点唤醒用户程序，用户程序继续运行

主节点设计

主节点需要维护多个数据结构，例如：

• 保存各个 worker 节点信息

• 保存任务信息，重点包含任务状态，如：

  • idle

  • in-progress

  • completed

故障容忍

Worker 节点故障

主节点会定期向 worker 节点发起 ping 命令检测其存活状态，如果在一定时间内未收到响应，就视为节点宕机

重点来了：这些 worker 正在执行的 map 或 reduce 任务需要被重新设置为 idle 状态，供主节点重新调度执行。特别地，即使 map 任务已完成，如果其所在节点宕机，那保存在节点本地磁盘的任务结果也可能无法再读取，因此也必须重做

此处我想到一个问题：如果 map 任务的结果已经被 reduce 任务消费了，对应的 map worker 宕机，按照描述，似乎也会触发重做，但这种重做貌似是完全没必要的。
按照已知信息，map 任务完成后会将结果拆分成 R 份并把地址传递给主节点，而主节点必然记录了这些地址。只要 reduce 任务执行完毕之后也能告知主节点已消费的地址信息，那么这些 map 任务其实可以被标记为“已消费”。
是否可以考虑为任务添加一个 terminate 状态，或者在所有 reduce 任务消费完成后清除该 map 任务的状态，使其不再被重做？

主节点故障

为主节点定期创建 checkpoint，并在宕机时启动镜像节点相对容易。不过因为系统仅设计了一个主节点，Google 最终选择了主节点故障时重试整个 MapReduce 作业的策略，以保持设计简洁

一致性语义保障

MapReduce 系统通过原子提交（atomic commit）来保障一致性。任务结果一旦提交至主节点，便只有一个固定版本，即便任务被重复执行，也只采纳其中一个结果，确保一致性语义
当 map 和 reduce 函数本身是确定性的（例如不调用随机函数），那么整体输出的一致性是可保证的。若使用了非确定性函数，则整体语义也会受到影响

任务划分粒度

任务粒度与前面提到的 M 和 R 紧密相关，通常应让 M 和 R 的数量大于 worker 节点数，以便更好调度任务、提升并行度。同时也能在出错时减少资源浪费

但粒度划分过小也有代价：一个 map 任务对应 R 个 reduce 输出文件，主节点需要管理 M * R 个状态，任务越多，系统中间产物和最终产出文件数量也会爆炸式增长，增加管理成本

最佳实践：

• R 设置为 worker 数量的 1~3 倍，可以并行且控制输出规模

• M 设置得更大些，通常根据文件块大小划分

经验法则：

任务要足够细，调度要足够轻

备份任务机制

MapReduce 在调度系统中面临一个重大挑战：Straggler 问题，即某些 worker 因硬盘瓶颈、CPU 占用或 bug 导致任务执行缓慢，从而拖慢整体作业完成时间。这种现象被称为 tail latency（尾部延迟）

为解决此问题，MapReduce 在作业快结束时会对仍运行中的任务分配副本任务给空闲 worker，也就是执行Speculative Execution（推测执行）

两个或多个 worker 并发执行同一任务，谁先完成就采纳谁的结果，从而缓解尾部延迟问题，大幅提高整体任务完成时间的下界

总结 & 展望🧩

今天的学习让我从工程视角认识了 MapReduce。虽然概念简单，但真正做成一个稳定、高可用的系统却要面面俱到。

一些值得我自己反思的点包括：

• 备份任务机制（以前从没考虑过）：回头想想我之前做过的调度系统，压根没考虑过“尾部延迟”的问题。以后如果再设计类似系统，一定会考虑加上类似策略

• 原子提交带来的一致性

• map 和 reduce 的确定性对系统一致性的影响

接下来我会继续学习课程的视频和实验部分，看看这些机制如何在代码中实现，期待能够把这些思路应用到自己的项目中。