6.824 分布式系统 MapReduce

总览

MapReduce 是一个编程模型, 也是一个处理和生成超大数据集的算法模型的相关实现

用户需要做的事情:

1. 用户指定 Map 函数处理一个键值对的集合, 输出基于键值对的中间数据
2. 用户指定 Reduce 函数把中间数据中具有相同 Key 的 Value 值整合起来

MapReduce 需要做的事情: 封装并行计算, 容错, 负载均衡, 数据分布的复杂细节

实现

1. 用户程序在主机群中 fork 出一个 Master 程序, 以及多个 Worker 程序
   把原始数据划分成 M 个数据片段, 决定 R 个不同分区用来存储中间数据
2. Master 分配任务, M 个 Map 任务和 N 个 Reduce 任务
3. 被分配了 Map 任务的 Worker 程序读入相应的数据片段, 调用 Map 函数解析为键值对
4. 按照用户提供的分区函数 (比如 hash(key) % R) 把键值对放到对应的分区中
   
   把存储位置传回 Master, 让 Master 过后传递给 Reduce 任务的 Worker 中
5. 被分配了 Reduce 任务的 Worker 程序使用 RPC 从之前执行 Map 任务的 Worker 主机中
   
   对应分区读取数据并排序(可能用到外部排序)
6. 遍历键值对, 对于相同 Key 的键值对, 调用 Reduce 函数合并数据, 输出到对应分区的输出文件中
7. 所有任务完成之后, Master 唤醒用户程序, 调用结束

在最后, 用户可能会把所有 R 个输出文件合并

数据结构

Master

1. 存储每个任务的状态(待完成, 完成中, 已完成)
2. 对于每个已完成的 Map 任务, 存储 R 个中间文件的大小和位置

容错

Worker错误

1. Master 周期性地 ping 每个 Worker
   
   如果在规定的时间内没有收到返回信息, Master 标记失效的 Worker
   
   这个 Worker 的任务被重新设置为空闲状态
   • 对于该 Worker 已完成的 Map 任务, 需要全部重新完成, 因为 Map 任务的结果存储在这台主机中.
     并且重新执行的动作会被通知给所有的执行 Reduce 任务的 Worker, 从新主机中读取数据
   • 对于该 Worker 已完成的 Reduce 任务输出存储在全局文件系统上, 所以不需要重新执行

Master错误

一般有两种办法

1. 每隔一段时间把之前 Master 存储的所有东西写入硬盘作为一个检查点, 故障时从最近一个检查点恢复
2. 重新执行所有任务

故障时语义

当用户定义的 Map 和 Reduce 函数是输入确定性函数(相同输入产生相同输出)时, 那么不会产生语义问题

1. 每个 Map 任务创建 R 个临时文件, 完成时把这 R 个临时文件的信息传给 Master
   
   如果 Master 发现这个任务之前被别的 Worker 完成了, 那么他忽略这条消息, 否则就记录在数据结构里
2. 每个 Reduce 任务创建一个临时文件(存放在全局文件系统中), 完成时把它重命名(原子的)
   
   如果多个机器都在执行一个 Reduce 任务, 他们的重命名请求只在第一次的时候生效

对于非输入确定性的函数 MapReduce 只有较弱的失效处理

存储位置

Master 调度 Map 任务的时候会知道输入文件的位置, 所以尽量在输入文件存储的机器或者附近的机器执行
这样可以减少网络带宽的消耗从而提高整体的效率

任务粒度

Master 执行 $O(M+R)$ 次调度, 内存存储 $O(M \times R)$ 个状态

选择合适的 M 值从而让输入文件被分成 16M ~ 64M 的块被处理(配合存储系统)

选择合适的 R 值, 一般是想使用的 Worker 机器的倍数

任务备份

落伍者指的是对于一台主机, 可能有其他的故障或者任务让它执行 Map 或 Reduce 任务的效率极低, 这会拖延整个任务完成的时间

针对可能出现落伍者的问题, Master 在所有的任务快执行完的时候, 调度备用的 Worker 来处理剩下来的任务

这种策略比正常操作多几个百分点的计算资源, 却能显著减少超大 MapReduce 任务的运行时间

拓展功能

1. 分区函数: 用户指定特殊的分区函数来满足特殊要求, 比如把来自同一个主机的 URLs 放在同一个输出文件中
2. 有序输出: 在给定的分区中按照 Key 值增量排序处理数据
3. 合并函数: 用户指定合并函数, Map 结束之后先合并一次再传递给 Reduce 任务, 可以显著提高一些 MapReduce 操作的效率
4. 输入输出: 用户可以指定输入输出格式
5. 跳过故障记录: 如果每次执行一个任务的时候都会出现错误, 在到达一定次数的时候就会忽略这次任务
6. 本地运行: 提供本地化运行的 MapReduce, 方便调试
7. 使用 HTTP 显示状态信息, 使用计数器统计不同事件发生次数