本文为阅读MapReduce论文的记录，内容主要是论文的第三部分——实现。方便本人今后查看。
1. 运行概述
下图展示了 MapReduce 过程的整体情况
当用户程序执行 MapReduce 时，会依次发生以下动作（对应图中的标号）：
用户程序中的 MapReduce 库将输入文件分成 M 个分片，每片有16M-64M（由用户决定），MapReduce 库还会将程序拷贝到集群机器上。
集群中有一个 master，多个 worker。在拷贝程序过程中，其中 master 获得的程序是特殊的。master 将分配工作给 worker。现在有 M 个 map 任务和 R 个 reduce 任务需要被分配。master 会选择空闲的 worker，分配给 map 任务或 reduce 任务。一个 worker 只能担任一个 map 任务或 一个reduce 任务。
被分配 map 任务的 worker 接下来会读取相应的输入块，将输入数据解析成 k-v 对，并将 k-v 对传给用户定义的 Map 函数。由 Map 函数生成的中间结果 k-v 对缓存在内存中。
缓存的中间结果将定期地被写到本地磁盘上。分区函数（例如，hash(key) mod R）将中间结果分割成 R 个分区。然后，中间结果在本地磁盘的位置将传回给 master，接着 master 将负责把这些位置传给reduce worker。
-
当 reduce worker 被 master 通知了中间结果的位置，它将通过 RPC 读取 map worker 本地磁盘上的中间结果。当完成读取工作，它会对中间结果进行排序，让具有相同 key 的对被分组在一块。
排序工作的重要性在于：通常具有不同 key 的对会被分到同一个 reduce 任务中（与分区函数有关）。如果由于中间结果过大，无法装进内存进行排序，需要使用外部排序。
reduce worker 对已排序的数据进行遍历，每遇到一个不同的 key，便将 key 与对应的一系列 value 传给用户定义的 reduce 函数。其输出将作为该 reduce 分区的结果，追加到最终的输出文件中。
当所有的 map 、reduce 任务完成， master 将唤醒用户程序。同时，用户程序中的mapreduce 调用得到返回。
在执行完成后，mapreduce 的输出将是 R 个文件（每个 reduce 任务一个）。通常，用户不需要将这 R 个文件合并成一个，可作为输入传给另一个 mapreduce 调用，或另一个分布式程序。
2. Master 数据结构
对于每个 map、reduce 任务，master 都会存储其状态（idle、in-progress、completed）和 non-idle的 worker 的信息。
master 在 map 任务到 reduce 任务之间传输中间结果的位置。对于每个完成的 map 任务，master 会存储其 R 个分区的位置和大小，并将该信息逐渐传输给处于 in-progress的reduce worker。
3. 容错
3.1 worker 故障
master 定期地 ping 所有 worker。如果一个 worker 长时间没有响应， master 认为该 worker 已故障。该worker 上，以下任务，将被重置为 idle 状态，并将该任务重新分配到其他 worker 上
- 处于 completed 状态的 map 任务
- 处于 in-progress 状态的 map、reduce 任务
- 处于 in-progress 状态的 reduce 任务
completed 状态的 map 任务需要重新执行的原因：输出存储在故障机器的本地磁盘上，已经不可访问了。
completed 状态的 reduce 任务不需要重新执行的原因：输出存储在全局文件系统（GFS）上。
worker A 执行 map 任务，由于 A 故障了，接着由 worker B 执行该 map 任务。所有在运行 reduce 任务的 worker 都将被通知重新执行，而还没有从 worker A 读数据的 reduce 任务，将转为 worker B。
3.2 master 故障
master 定期检查点记录状态，当 master 任务死亡时，从最近的检查点状态开始执行。
3.3 本地性
网络带宽是我们的计算环境中相对稀缺的资源。 我们通过利用输入数据（由 GFS 管理）存储在组成我们集群的机器的本地磁盘上的来节省网络带宽。 GFS 将每个文件分成 64MB 块，并在不同的机器上存储每个块的多个副本（通常是3个副本）。 mapReduce master 将输入文件的位置信息考虑在内，并尝试在包含相应输入数据副本的机器上分配 map 任务。否则，它将尝试在该任务的输入数据副本附近（例如，在与包含数据的计算机处于同一网络交换机上的机器上）安排一个 map 任务。 在集群中大部分 worker 上运行大型MapReduce操作时，大多数输入数据都是本地读取的，不会消耗网络带宽。
3.4 任务粒度
从上文我们可以得知，map 阶段被划分成 M 个 task，reduce 阶段被划分成 R 个 task，M 和 R 一般会比集群中节点数大得多。每个节点运行多个 task 有利于动态的负载均衡，加速 worker 从失败中恢复。
在具体的实现中，M 和 R 的大小是有实际限制的，因为 master 至少要做 O(M＋R) 次的调度决策，并且需要保持O(M * R)个状态（使用的内存并不大，一条 M-R 记录需要 1 字节）。
通常情况下，R 的大小是由用户指定的，而对 M 的选择要保证每个任务的输入数据大小，即一个输入分片在 16MB～64MB 之间（数据本地性最优）。R 的大小是 worker 数量的一个较小的倍数。
3.5 备份任务
一种最常见的延长 mapreduce 运行总时间的原因是 “straggler”：一台机器花费异常时间完成最后一个 map 或 reduce 任务。“straggler” 出现的原因有很多，例如：磁盘有问题，读取速度下降；集群调度在机器上安排了其他任务，由于竞争CPU、内存、本地磁盘或网络带宽，导致其更慢地执行 mapreduce 代码。
解决“straggler”的机制：当 mapreduce 操作快完成时， master 会备份剩余的 in-progress 状态的任务。无论主程序或备份程序执行完成，该任务都会被标记为已完成。
