MapReduce：大型集群上的简化数据处理

通过自动将输入数据分割为一个有M个分裂(splits)的组，map调用分布在多台机器间。输入分裂可以由不同的机器并行处理。reduce调用通过利用分割函数(比如，hash(key) mod R)将中间键空间划分为R片进行分布。分割数R和分割函数都是由使用者指定的。

图1展示了在我们的实现中MapReduce操作的整体流程。当用户程序调用MapReduce函数，以下顺序行为将会发生(图1中标记的数字对应下面列中的数字)。

用户程序中的MapReduce库首先将输入文件划分为M片，通常每片16~64MB(由用户通过可选参数控制)。然后启动集群中程序的多个副本。

这些程序副本中有一个特殊的master副本。其他副本则是由master分配了work的workers。集群中需要分配 M 个 map tasks 和 R 个 reduce tasks。master挑选闲置的workers且为每个worker分配一个 map task 或 reduce task。

分配了 map task 的一个worker读取相应输入划分的内容。它从输入数据中解析出键/值对并将每一对传递给用户定义的map函数。由map函数产生的中间键/值对缓冲在内存中。

缓冲区的键/值对定期地写入本地磁盘，由partition函数划分到 R 个区域中。这些本地磁盘上的缓冲对的位置被传递会master，它将负责转发这些位置给 reduce workers。

当一个 reduce worker 被 master 通知了这些位置后，它使用远程进程调用来读取来自map workers的本地磁盘中的缓冲数据。当reduce worker读取到了所有分区中的中间数据后，它按照中间键将其排序，从而使所有相同键的出现次数组合在了一起。排序是必要的，因为通常很多不同的键被map到了同一个reduce task。如果中间数据太大以至于不能放在内存中，还需要使用一个外部的排序。

reduce worker对排序好的中间数据执行迭代，对每个唯一的中间键，它将这个键以及相应的一组中间值传递个用户的 reduce 函数。reduce 函数的输出被附加到这个reduce分区的最终输出文件中。

当所有的 map tasks 和 reduce tasks 都完成后，master唤醒用户程序。在这一点上，用户程序的MapReduce调用返回到用户代码处。

execution

成功完成后，mapreduce执行的输出可以在R个输出文件中获得(每个reduce task一个，由用户指定文件名)。通常，用户无需将这R个输出文件合并到一个文件中;他们通常将这些文件作为另一个MapReduce调用的输入，或者在来自另外一个可以处理划分到了多个文件中的输入的分布式应用程序中使用它们。

3.2 master数据结构

master中有多种数据结构。对每一个map task和reduce task，它存储了其状态信息(限制，进行，或完成)和worker机器的身份(对于非闲置tasks)。

master是map tasks传播中间文件区域位置到reduce tasks的导管。因此，对于每个完成了的map task，master存储由这个map task生成的R个中间文件区域的位置和大小。master在map tasks称后接收到这些位置和大小信息的更新。这些信息将逐步推送到正在进行reduce tasks的workers中。

3.3 容错

由于MapReduce库旨在帮助利用成百上千的机器来处理大量数据，它必须优雅地容忍机器故障。

• 处理worker故障

master会定期地ping每一个worker。如果在一定时间内没有收到来自某台worker的响应，master将这个worker标记为故障。任何由worker完成的map tasks都被重置为初始闲置状态，因而可以在其他的workers中调度。同样，在故障worker上的任何正在进行的map task和reduce task也被重置为闲置状态以便进行重新调度。

故障worker上已完成的map task需要重新执行，因为它们的输出存储在了故障机器的本地磁盘中导致无法访问。已完成的reduce tasks无需重新执行，因为它们的输出存储在了全局文件系统中。

当一个map task首先由worker A执行然后又由worker B执行(因为A发生了故障)，所有执行reduce task的workers将被通知重新执行。任何还未从worker A读取数据的reduce task将从worker B读取数据。

MapReduce适应于大规模的worker故障。例如，在一个MapReduce操作中，在运行中的集群上的网络维护导致了一组80台机器在几分钟内无法到达。MapReduce master简单地重新执行无法到达的worker机器的工作且继续前进，最终完成MapReduce操作。

• 语义失败

当用户提供的map和reduce操作是它们他们的输入值的特定函数时，我们的分布式实现生成的输出将与整个程序的无错顺序执行生成的输出相同。

我们依靠map和reduce任务输出的原子的提交来实现这一性质。每个正在进行的task将其输出写入私有临时文件中。一个reduce task生成一个这样的文件，map task生成R个这样的文件(每个reduce task一个)。当一个map task完成后，worker发送一条消息给master，这条消息中包含了R个临时文件的名字。如果master接收到了来自一个已完成的map task的完成消息，它将忽略这条消息。否则，它将这R个文件名记录到master数据结构中。

当一个reduce task完成后，reduce worker自动重命名其临时输出文件为最终输出文件。如果同一个reduce task在多台机器上执行，同一个最终输出文件的多个重命名调用将被执行。我们依靠由底层文件系统提供的原子的重命名操作来保证最终文件系统状态仅包含来自一个reduce任务执行生成的数据。

绝大多数的map和reduce操作是确定的，事实上，我们的语义等价于这种情况下的一次顺序执行，这使得程序员能够非常容易地推断程序的行为。当 map 和/或 reduce 操作不确定时，我们提供了较弱但仍然合理的语义。在不确定操作存在时，一个特定reduce task R1的输出等价于由非确定性程序的一次顺序执行R1生成的输出。然而，另一个不同的reduce task R2的输出可能对应该非确定性程序的另一个不同顺序执行R2的输出。

考虑map task M和reduce task R1和R2。令 e(Ri) 作为作为R1的执行(这确实是一个这样的执行)。较弱的语义出现因为 e(R1) 可能读取了M的一次执行生成的输出，e(R2)可能读取了M的另一次执行生成的输出。

3.4 局部性

（编辑：辽源站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!