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

摘要：

MapReduce是一个编程模型，以及处理和生成大型数据集的一个相关实现，它适合各种各样的现实任务。用户指定计算的map和reduce函数。底层运行系统自动地将大规模集群机器间的计算并行化，处理机器故障，以及调度机器间通信以充分利用网络和磁盘。程序员会发现这个系统很好使用：在过去的去年中，超过一万个不同的MapReduce程序已经在Google内部实现，平均每天有十万个MapReuce作业在Google集群上被执行，每天总共处理20PB以上的数据。

1 简介

在MapReduce开发之前，作者和其他许多的Google员工实现了数以百计的处理大量原始数据(如抓取到的文档、Web请求日志等等)的专用计算方法，以计算各种导出的数据，如倒排索引、Web文档图结构的各种表示、每个host抓取到的页面数的总结、某一天最频繁的一组查询。大多数这样的计算在概念上是非常简单的，然而它们的输入数据量通常非常大。为了在合理的时间内完成这些计算，它们必须分布到成百上千的机器上。如何并行化计算，分发数据，以及处理故障，这些问题结合起来，往往会让程序员使用大量复杂代码来处理，而掩盖了原本简单的计算。

为了应对这一复杂性，我们设计了一个新的抽象，它允许我们表达试图执行的简单计算，但将并行化、容错、数据分布和负载均衡等凌乱的细节隐藏到了库中。这个抽象的灵感来源于出现在Lisp和许多其他函数式语言中的map和reduce原语。我们实现了大部分的计算，包括为输入的每一个逻辑记录应用一个map操作以计算一组中间键值对，然后对所有共享同一个键的值应用一个reduce操作以恰当地结合导出的数据。此函数式模型支持用户自定义map和reduce操作，使我们能非常容易地并行处理大型计算，和使用再执行(reexecution)作为主要的容错机制。

这项工作的主要贡献就是一个简单而强大的接口，它完成自动并行化、大规模分布计算，结合该接口的一个实现在大型商用PC集群上获得了很高的性能表现。该编程模型还可以用于同一台机器上多个核心间的并行计算。

第2部分描述了基本的编程模型并给出几个例子。第3部分描述了MapReduce接口专门针对基于集群的计算环境的一个实现。第4部分描述了我们发现的这个编程模型的几个很有用的改进(refinements)。第5部分描述了对各种不同任务的实现的性能度量。第6部分探索了MapReduce在Google中的应用，包括使用它作为重写我们的生产索引系统的基础的一些经验。第7部分讨论了相关和未来的工作。

2 编程模型

这个计算需要一组输入键/值对，并生成一组输出键/值对。MapReduce库的使用者将计算表达为两个函数：map和reduce。

map，由用户编写，需要一对输入并生成一组中间键/值对。MapReduce库将所有与相同键值 I 相关联的值组合到一起，并将它们传递给reduce函数。

Reduce函数，同样由用户编写，接受中间键 I 和这个键的一组值。它将这些值合并以形成一组可能更小的值。通常每次reduce调用只生成0个或1个输出值。中间值靠一个迭代器提供给用户的reduce函数。这使我们能够处理大量太大以至于不能装入内存的值列表。

2.1 例子

考虑一下在一个巨大的文档集合中统计每个单词出现次数的问题。使用者会编写与下面伪代码类似的代码：

map(String key, String value);  
// key: document name  
// value: document contents  
for each word w in value:  
 EmitIntermediate(w, "1");  
  
 
reduce(String key, String values);  
// key: a word  
// values: a list of counts  
int result = 0;  
for each v in values:  
 result += ParseInt(v);  
Emit(AsString(result)); 

map函数发出每个单词加一个相关的出现次数(count)(在这个简单例子中仅为1)。reduce函数对发给一个单词的所有数(count)求和。

此外，用户编写代码将输入和输出文件名以及可选的调优参数填入mapreduce规范对象中。然后调用MapReduce函数，将它传递给规范对象。用户的代码与MapReduce库(C++实现)相连接。我们最初的MapReduce资料中有这个例子的完整程序【8】。

2.2 类型

尽管前面的伪代码是按照输入输出字符串形式编写的，概念上由用户提供的map和reduce函数是有相关类型的。

map (k1, v1) --> list(k2, v2)  
reduce (k2, list(v2)) --> list(v2) 

也就是说，输入键和值与输出键和值来自不同的域。此外，中间键和值与输出键和值来自同一个域。

3 实现

MapRedue接口的许多不同实现都是可能的。正确的选择取决于环境。例如，一种实现可能适合一个小型的共享内存的机器，另外一种可能适合一个大型的NUMA多处理器，而另外一种可能适合一个更大的联网计算机集合。在我们最初的文章发表以后，已经发展出了很多MapReduce的开源实现【1， 2】，MapReduce在各种问题领域的适用性也得到了研究【7， 16】。

这一部分描述了我们的一种MapReduce实现，其目标是目前广泛应用在Google中的计算环境：由交换千兆以太网连接在一起的大型PC集群【4】。在该环境中，机器通常运行Linux系统，有双核 x86 处理器以及4-8GB内存。个别机器拥有1GB/s的网络带宽，但每台机器等分的带宽远远低于1GB/s。一个计算集群包含了成千上万台机器，因此机器故障是很常见的。存储由直接附在单独机器上的廉价IDE磁盘提供。GFS，Google内部开发的一个分布式文件系统【10】，用来管理存储在这些磁盘上的数据。文件系统使用复制来提供不可靠的硬件之上的可用性与可靠性。

使用者提交 jobs 给调度系统。每个 job 包含一组任务，且由调度程序映射(mapped)到集群间的一组可用的机器上。

3.1 执行概述

（编辑：辽源站长网）

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