MapReduce Paper & Lab Report

MapReduce 论文阅读

编程模型

MapReduce 使用类似 fp 的原语来描述一个计算：

Map(k, v) => list(k2, v2)

Reduce(k2, list(v2)) => list(v2)

输入的k, v != 中间的 k2, v2 == 输出的k2, v2.

可以做倒排索引、wordcount、分布式排序等事情，前提是你能把你的任务描述成map – reduce 形式。

实现

主要流程

可以看到，这里有 map-worker 和 reduce-worker. Map Reduce 分区数量由用户定义。

操作按论文说有一些流程，照搬不太好，我就说下自己的理解：

1. 将输入文件分段，定义一定的数据段大小(原始论文给16-64MB)
2. 用户程序创建大量的 map reduce 工作副本
3. master 分配任务给空闲 worker，有M和R个任务
4. Map worker 完成计算，并且把数据缓存在内存中， k2, v2 对自动分区成 R 个，写在 本地文件 中，消息被传给master, master 把这个信息传给 reducer.
5. reducer 接收到 master 的消息后：
   1. 用 rpc 读取这些数据
   2. 把数据按照 k2 聚合，似乎要排序？
   3. 处理这些数据，按照分区追加写到输出文件
6. 完成后，R个分区有追加 的 map-reduce 文件。

故障处理

worker 故障

worker 故障的主要解决方案是标记成错误，如果是 map-worker 则通知 reduce-worker ，把任务交给别人执行。

我很弟弟，看的是论文中文翻译，但是感觉这段写的比我能总结的好很多：

master 周期性的 ping 每个 worker。如果在一个约定的时间范围内没有收到 worker 返回的信息，master 将
把这个 worker 标记为失效。所有由这个失效的 worker 完成的 Map 任务被重设为初始的空闲状态，之后这些
任务就可以被安排给其他的 worker。同样的，worker 失效时正在运行的 Map 或 Reduce 任务也将被重新置为
空闲状态，等待重新调度。

master 故障

类似内存备份吧，写wal／周期性写入磁盘什么的 …

任务粒度

理想情况下，M 和 R 应当 比集群中 worker 的机器数量要多得多。在每台 worker 机器都执行大量的不同任务能够 高集群的动态的负载 均衡能力，并且能够加快故障恢复的速度:失效机器上执行的大量 Map 任务都可以分布到所有其他的 worker 机器上去执行。

但是实际上，在我们的具体实现中对 M 和 R 的取值都有一定的客观限制，因为 master 必须执行 O(M+R) 次调度，并且在内存中保存 O(MR)个状态(对影响内存使用的因素还是比较小的:O(MR)块状态，大概每 对 Map 任务/Reduce 任务 1 个字节就可以了)。

备用任务

有的任务执行的很慢，我们有的时候会调度 backup (备份) 来处理剩下的、处理中的任务。