MapReduce:Simplified Data Processing on large Clusters－翻译版（下）

实现
拥有多个不同的MapReduce接口的实现是可能的。具体选择取决于环境。比如，一种实现适合于共享内存的机器，一种适合于NUMA(Non-Uniform Memory Access )多处理器，另外一种适合于大量的网络机器。
这节将描述在Google内部大量使用，适合于大量PC构成的集群系统这种计算环境的实现。在这个环境中：

1. 双CPUx86机器，运行Linux，具有2-4G内存。
2. 网络采用的是100M/s或1G/s的配置硬件，然实际的平均使用值大概为它们的一半。
3. 采用由成百上千PC构成的集群系统，机器故障很经常。
4. 存储采用的是直连每个机器的IDE硬盘。通过我们自己开发的GFS来管理磁盘上的数据。此文件系统使用复制策略使得自己在不可靠的硬件上具有很好的可用性和可靠性。
5. 用户提交作业到调度系统。每个作业由一系列任务构成，这些任务被映射到集群范围内可用的机器上。

• 执行概貌

通过把输入文件分割成M等份，Map调用能够在多台机器上分布执行。这M等分数据在不同机器上可以并行处理。通过使用分割函数（比如 hash(key) mod R）把中间形式的key空间分成R份，Reduce调用能够分布执行。分区数目和分割函数是由用户指定。
图1展示了整个MapReduce的操作流程。当用户程序调用MapReduce函数，将执行如下步骤（图上的数字号码与如下列表中的数字号码是一一对应的）：

1. MapReduce库首先把输入文件分成大小为16-64M之间块大小的M份（通过一个可选的用户参数控制），然后它在多台机器上启动程序副本。
2. 其中存在于master上的一个副本是特殊的，其余的worker都将由master分配工作。
3. 被分配map任务的worker将读取输入份中的内容。它从输入数据中解析key/value对，然后把这些对传给用户定义的Map函数。产生的中间key/value对将由内存缓存。
4. 处在缓存中的对将被间隔性的写入磁盘，这些对将散步在由分割函数指定的R个区域中。这些缓存对在局部磁盘的具体位置被传回给master，然后master负责把这些信息转发给reduce worker。
5. 当reduce worker从master得到位置信息，它将使用远程过程调用从map worker的局部磁盘中读取数据。读取完所有数据之后，reduce worker按照中间key进行排序，以使得相同值的key被分在一起。因为许多不同的key有可能映射到相同的reduce任务，所以排序是必须的。当 数据太大而不能将它们全部放入内存时，一种外部排序方法将被使用。
6. reduce worker遍历排好序的中间数据，当它遇到一个唯一的中间形式key，它将把key和与它对应的中间value传给用户提供的Reduce函数。Reduce函数的输出将被附加到与这个reduce对应的最终输出文件中。
7. 当所有的map和reduce任务被完成之后，master唤醒用户程序。于是MapReduce调用返回到用户代码。

当成功完成之后，输出结果将存在于R个输出文件中，每一个reduce任务对应一个。一般来说，用户没有必要合并这R个文件为一个。这些文件将被传给另一个MapReduce调用当作输入，或者能够处理输入被分割的其余形式的分布式程序。

• master数据结构

master保存有多种数据结构。对于每个map和reduce任务，它存储有它们的状态（空闲，正在处理或者完成）和非空闲worker所在机器的标志。
关于中间文件的位置信息是通过master从map任务传递给reduce任务的。因此，对于每个完成的map任务，master存储有它所产生的R文件 的位置和大小信息。一旦map任务完成，master就更新这些信息，然后把这些信息传给正在处理中的reduce任务。

• 容错

因为MapReduce库是用来在成百上千台机器上处理大量数据，所以库必须很好的进行容错处理。

1. worker故障

master间隔性的ping worker。当尝试多次之后没有响应，master将认为worker已经出现故障。任何已经在wokrer上完成的任务将被设置为空闲状态，以使得它 可以重新被调度。同样，正在处理的map或reduce任务也将被设置为空闲状态，以便重新调度。
完成的map任务需要重新执行，那是因为它们的输出是存储在出现故障机器上的本地磁盘，而导致不可访问。完成的reduce任务输出结果是存储在全局文件系统而不存在这个问题。
当一个map任务首先在woker A上执行，然后在worker B上（因为A出现故障），所有执行reduce任务的worker将得到重新执行的通知。对于还没有从worker A上读取数据的reduce任务将从woker B上读取。
MapReduce对worker故障具有很强的适应能力。比如在一次MapReduce操作中，网络维护一次性造成80台机器变得不可抵达。此时MapReduce重新执行这些出现问题机器上的任务，以至最终完成任务。

参考：(1) 什么是MapReduce? Google的分布运算开发工具!