MapReduce 简读

MapReduce 论文阅读

本文主要介绍了 MapReduce 论文的第三章。第四章等内容最好自行再去阅读。

编程模型

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

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

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

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

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

实现

机器

  1. x86 架构、运行 Linux 操作系统、双处理器、2-4GB 内存的机器。

  2. 普通的网络硬件设备，每个机器的带宽为百兆或者千兆，但是远小于网络的平均带宽的一半。

  3. 集群中包含成百上千的机器，因此，机器故障是常态。

  4. 存储为廉价的内置 IDE 硬盘。一个内部分布式文件系统用来管理存储在这些磁盘上的数据。文件系

    统通过数据复制来在不可靠的硬件上保证数据的可靠性和有效性。

  5. 用户􏰂交工作(job)给调度系统。每个工作(job)都包含一系列的任务(task)，调度系统将这些任

    务调度到集群中多台可用的机器上。

在原始论文中，提到了上述的环境，但是不知道如果用内存计算并写存取都在内存的话，会不会对机器性能要求高很多。

主要流程

mapreduce流程

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

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

  1. 将输入文件分 M 段，定义一定的数据段大小(原始论文给16-64MB)
  2. 用户程序创建大量的 map reduce 工作副本, 有 workers 和 master。论文里面只有一个 master, 似乎 Hadoop MapReduce 允许你配置备用的 Master.
  3. master 分配任务给空闲 worker，有M和R个 map 和 reduce 任务
  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 任务也将被重新置为
空闲状态，等待重新调度。

  1. 总的来说， master 会跟 worker 保持 heaet beat
  2. 没有返回的话，任务从 类似 执行中 的状态被更改为 未知性
  3. 等待任务被调度给别的 worker

master 故障

类似内存备份吧，写wal／周期性写入磁盘什么的 … 主要是写入 ckpt, 然后让系统能够 recover

任务粒度

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

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

备用任务

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