MapReduce 论文阅读笔记

粗略记录阅读 MapReduce^[1]论文时的要点。

• 可靠性保证的措施

  • Master 节点定期 ping 各个 worker 节点，ping 不通的则标记为 failed

  • 如果是做 map 的节点 fail 了，将会重做那个节点已经完成的工作和尚未完成的工作（为什么还要重做已经完成的工作？因为 map 产生的结果一般是存储在工作节点本地的，连节点主机都 ping 不通了，自然无法取得那个节点上存储的数据）；如果是做 reduce 的节点 fail 了，将会重做那个节点尚未完成的工作（因为 reduce 阶段的结果已经写进了 global file system 中，所以不必重做已经完成的任务）

  • 当所有的任务都快做完，Master 节点会让部分空闲节点重做当前仍在运行的任务，以避免「落伍者」(straggler)减慢整体的运行速度（因为这些迟迟没能完成任务的「落伍者」可能是出现了某些异常）。当这些备份节点有一个完成了任务，那么其他节点则丢弃这个任务

• 提高效率的措施

  • 局部性优化(locality optimization)：这里的局部性指的并不是计算机执行指令时的 saptial and temporal locality，而是主要指网络通信上的。要考虑到网络带宽是计算集群中比较稀缺的资源。map 阶段的输入数据一般也是存储在工作节点的磁盘中的，并且一份输入数据拥有备份。那么为了节省网络带宽，可以将某份输入数据的 map 工作交给本地存储了那份数据或其备份数据的节点完成。如果不存在这样的工作节点，那么 Master 也会调度一个接近与输入数据存储节点的工作节点来完成这份数据的 map 工作，比如连接在同一个交换机下的节点

• Reduce 细节

  Map 阶段产生的中间键值对的键决定了这个键值对会在哪个 reduce 节点上被处理。一种算法是将键的哈希值取 reduce 的模，来决定在哪个 reduce 节点上被处理

• Map 细节

  可以在 map 节点上进行中间键值对的部分合并，并且这个合并往往与 reduce 用的是同一段代码

2024-03-07 update:

MapReduce 模型的思想简述：

假设我们要处理若干个具有相同结构的「文档」

1. 对于每个输入的文档，均执行 map() 操作，它读取文档中的某些信息，输出一个键值对 (key, value)
2. 对于若干上一步产生的键值对，我们合并那些具有相同 key 的键值对的 value，构成集合 values。接下来，对于每个不同的 key，我们调用一次 reduce(key, values)，这一步的返回值是自定义的，可以是 values 的元素和或最值
3. MapReduce 的强大之处在于，第 1 步中的所有 map() 操作或第 2 步中的所有 reduce() 操作互相没有依赖，因此可以并行执行，发挥单机的多核优势或是分布式集群的优势

Ref:

1. 6th Symposium on Operating Systems Design and Implementation Technical Paper (usenix.org) ↩