ACM通信

贡献的文章

MapReduce:一个灵活的数据处理工具

杰弗里·迪恩，桑杰·格玛沃特
ACM通讯，2010年1月，Vol. 53 No. 1, 72-77页
10.1145/1629175.1629198
评论(3)

Mapreduce是一种用于处理和生成大型数据集的编程模型。⁴用户指定一个map函数来处理键/值对，生成一组中间键/值对，以及一个reduce函数来合并与同一中间键相关的所有中间值。我们在2003年围绕这个编程模型构建了一个系统，以简化处理在的搜索的倒索引的构造Google.com．从那时起，已有超过10,000个不同的程序在谷歌上使用MapReduce实现，包括用于大规模图处理、文本处理、机器学习和统计机器翻译的算法。MapReduce的Hadoop开源实现已经被许多组织在谷歌之外广泛使用。^10，11

为了帮助说明MapReduce编程模型，请考虑计算每个单词在大型文档集合中出现的次数的问题。用户会编写如下的伪代码:

map函数发出每个单词以及相关的出现次数(仅'1在这个简单的例子中)。reduce函数将对特定单词发出的所有计数求和。

MapReduce会在一大堆普通机器上自动并行执行程序。运行时系统负责对输入数据进行分区、在一组机器上调度程序执行、处理机器故障以及管理所需的机器间通信等细节。MapReduce允许没有并行和分布式系统经验的程序员轻松地利用大型分布式系统的资源。一个典型的MapReduce计算在成百上千台机器上处理许多tb的数据。程序员发现该系统易于使用，每天在谷歌的集群上执行超过100,000个MapReduce作业。

回到顶部

与并行数据库的比较

并行数据库系统中内置的查询语言也用于表示MapReduce支持的计算类型。安德鲁·帕夫洛等人2009年发表的一篇论文(这里称为“比较论文”)。¹³)比较了MapReduce和并行数据库的性能。它评估了开源Hadoop实现¹⁰DBMS-X(一个未被识别的商业数据库系统)和Vertica(一个列式商店数据库系统，来自一家公司，该公司的创始人之一是这份比较论文的共同作者)。该论文的一些作者早些时候的博客文章将MapReduce描述为“重大的倒退”。^5，6在这篇文章中，我们解决了三个出版物中关于MapReduce的几个误解:

• MapReduce不能使用索引，这意味着对所有输入数据进行完整扫描;
• MapReduce的输入和输出总是文件系统中的简单文件;而且
• MapReduce需要使用低效的文本数据格式。

我们还讨论其他重要问题:

• MapReduce是独立于存储系统的，可以处理数据，而不需要先将数据加载到数据库中。在许多情况下，在将数据加载到数据库并完成单个分析之前，可以运行50个或更多单独的MapReduce分析来完成数据的完整传递;
• 复杂的转换在MapReduce中比在SQL中更容易表达;而且
• 在比较论文中的许多结论是基于实现和评估的缺点，而不是MapReduce模型的根本;我们将在本文后面讨论这些缺点。

我们鼓励读者阅读MapReduce的原始论文⁴对比论文¹³更多的上下文。

回到顶部

异构系统

许多生产环境都混合使用存储系统。客户数据可能存储在关系数据库中，用户请求可能被记录到文件系统中。此外，随着这些环境的发展，数据可能会迁移到新的存储系统。MapReduce为在这种异构系统中分析数据提供了一个简单的模型。最终用户可以通过定义在存储系统上操作的简单读取器和写入器实现来扩展MapReduce以支持新的存储系统。支持的存储系统的例子包括存储在分布式文件系统中的文件，⁷数据库查询结果,^2，9Bigtable中存储的数据^3.和结构化输入文件(如b -tree)。一个MapReduce操作就可以轻松处理和组合来自各种存储系统的数据。

现在考虑一个使用并行DBMS来执行所有数据分析的系统。这种分析的输入必须首先复制到并行DBMS中。这个加载阶段很不方便。它的速度也可能慢得令人无法接受，尤其是当数据在加载后只需要分析一两次时。例如，考虑一个面向批处理的Web爬行和索引系统，它获取一组Web页面并生成一个反向索引。将获取的一组页面加载到数据库中，只为了一次读取它们以生成倒索引，这似乎很笨拙，效率也很低。即使将输入加载到并行DBMS的成本是可以接受的，我们仍然需要一个适当的加载工具。这里是另一个可以使用MapReduce的地方;无需编写具有自己特别并行化和容错支持的自定义加载程序，只需编写一个简单的MapReduce程序就可以将数据加载到并行DBMS中。

回到顶部

指数

对比论文错误地说MapReduce不能利用预生成的索引，导致论文中的基准测试结果有偏差。例如，考虑将一个大数据集划分为一组非分布式数据库，可以使用散列函数。可以向每个数据库添加索引，使用该索引运行数据库查询的结果可以用作MapReduce的输入。如果数据存储在D个数据库分区中，我们将运行D个数据库查询，这些查询将成为MapReduce执行的D个输入。事实上，帕夫洛等人的一些作者在他们最近的工作中采用了这种方法。¹¹

使用索引的另一个例子是从Bigtable读取数据的MapReduce。如果数据需要映射到Bigtable行空间的一个子范围，我们将只需要读取该子范围，而不是扫描整个Bigtable。此外，与Vertica和其他列存储数据库一样，我们将只从分析所需的列中读取数据，因为Bigtable可以按列分隔存储数据。

另一个例子是处理特定日期范围内的日志数据;请参阅比较论文中的Join任务讨论，其中Hadoop基准读取1.55亿条记录，以处理在相关日期范围内的13.4万条记录。几乎我们所熟悉的每个日志系统都会周期性地转到一个新的日志文件，并在每个日志文件的名称中嵌入翻转时间。因此，我们可以很容易地只对可能重叠指定日期范围的日志文件运行MapReduce操作，而不是读取所有日志文件。

回到顶部

复杂的功能

Map和Reduce函数通常相当简单，具有直接的SQL等价物。然而，在很多情况下，特别是对于Map函数，函数太复杂了，不能很容易地用SQL查询来表达，就像下面的例子:

• 从HTML文档集合中提取出外发链接集，并按目标文档进行聚合;
• 将重叠的卫星图像拼接在一起，消除接缝，为谷歌地球选择高质量的图像;
• 使用为高效支持谷歌搜索查询而调优的压缩方案生成倒排索引文件集合;
• 处理世界上所有的道路段，并为谷歌地图绘制显示这些路段的地图贴图图像;而且
• 用高级语言(如Sawzall)编写的程序的容错并行执行¹⁴和拉丁语¹²)，跨一组输入数据。

从概念上讲，这种用户定义函数(UDF)可以与SQL查询结合使用，但是比较论文中报告的经验表明，对UDF的支持要么有缺陷(在DBMS-X中)，要么没有(在Vertica中)。这些问题可能会随着时间的推移而消失，但就目前而言，与SQL的强项选择和聚合相比，MapReduce是一个更好的框架，可以完成更复杂的任务(比如前面列出的那些)。

回到顶部

结构化数据和模式

Pavlo等人提出了一个很好的观点，即模式有助于允许多个应用程序共享相同的数据。例如，考虑以下来自比较论文的模式:

在比较论文中相应的Hadoop基准测试使用了一种低效且脆弱的文本格式，不同的属性由竖条字符分隔:

与专门的、低效的格式相比，实际上所有在谷歌上的MapReduce操作都以协议缓冲区格式读写数据。⁸高级语言描述输入和输出类型，编译器生成的代码用于对应用程序代码隐藏编码/解码的细节。排名数据对应的协议缓冲区描述如下:

下面的Map函数片段处理一条排行记录:

---

MapReduce是一种高效的大规模容错数据分析工具。

---

协议缓冲区框架允许(以受限的方式)升级类型，而不需要更改现有的应用程序(甚至重新编译或重建)。这种级别的模式支持已被证明足以允许数以千计的谷歌工程师共享相同的发展中的数据类型。

此外，协议缓冲区的实现使用了一种优化的二进制表示，它比比较论文中Hadoop基准测试使用的文本格式更紧凑，编码和解码速度更快。例如，自动生成的代码解析一个Rankings协议缓冲区记录的运行速度为每条记录20纳秒，相比之下，解析前面提到的Hadoop基准测试中使用的文本输入格式每条记录需要1731纳秒。这些测量结果是在2.4GHz Intel Core-2 Duo上运行的JVM上获得的。用于基准测试运行的Java代码片段如下:

考虑到这个记录解析基准测试有80倍的差异，我们怀疑比较论文中Hadoop基准测试的绝对数字被夸大了，不能用来得出关于MapReduce和并行DBMS性能的根本差异的结论。

回到顶部

容错

MapReduce实现使用拉模型在映射器和缩减器之间移动数据，而不是推模型，其中映射器直接向缩减器写入数据。Pavlo等人正确地指出，拉模型可以导致许多小文件的创建，以及许多磁盘试图在映射器和减少器之间移动数据。谷歌的MapReduce实现使用了批处理、排序和中间数据分组以及读取的智能调度等实现技巧来降低这些成本。

MapReduce实现往往不使用推模型，因为谷歌的开发人员需要容错属性。大多数在大型数据集上执行MapReduce至少会遇到一些失败;除了硬件和软件问题外，谷歌的集群调度系统还可以通过杀死MapReduce任务来抢占MapReduce任务，为更高优先级的任务腾出空间。在推送模型中，减速机失败将强制重新执行所有Map任务。

我们猜测，随着数据集的增长，分析将需要更多的计算，容错将变得更加重要。每天使用MapReduce处理的谷歌大小超过1PB的不同数据集已经有十几个，还有几十个tb大小的数据集。在谷歌之外，Hadoop用户列表中列出了许多用户¹¹处理数百tb或更多的数据集。显然，随着数据集的持续增长，越来越多的用户将需要像MapReduce这样的容错系统，以便高效地处理这些大型数据集。

回到顶部

性能

Pavlo等人比较了Hadoop MapReduce实现与两种数据库实现的性能;在这里，我们讨论不同系统的性能差异:

工程注意事项．启动开销和顺序扫描速度是实现成熟度和工程权衡的指标，而不是编程模型的根本区别。这些差异固然重要，但可以通过多种方式加以解决。例如，启动开销可以通过保持worker进程活动来解决，等待下一次MapReduce调用，这是一年多前添加到谷歌的MapReduce实现中的优化。

谷歌还通过各种性能优化解决了顺序扫描性能问题，例如，对结构化数据(协议缓冲区)使用高效的二进制编码格式，而不是低效的文本格式。

读取的数据．比较论文说，“MR总是被迫扫描整个输入文件来开始查询。”MapReduce不需要对数据进行完全扫描;它只需要输入接口的实现来生成一组匹配某个输入规范的记录。输入规格的例子如下:

• 一组文件中的所有记录;
• 所有访问日期在[2000-01-15..2000-01-22]范围内的记录;而且
• Bigtable表T中“语言”列为“土耳其语”的所有数据。

正如Pavlo等人建议的那样，输入可能需要对一组文件进行完整的扫描，但通常使用替代实现。例如，输入可能是一个具有提供高效过滤的索引的数据库，或者是一个索引文件结构(例如用于高效的基于日期的日志数据过滤的每日日志文件)。

这个关于MapReduce的错误假设影响了比较论文中五个基准中的三个(选择、聚合和连接任务)，并使论文中关于MapReduce和并行数据库相对性能的结论无效。

合并的结果．在这篇比较论文中，所有5个基准测试中对Hadoop的测量包括最后阶段将初始MapReduce结果合并到一个文件的成本。在实践中，这种合并是不必要的，因为MapReduce输出的下一个消费者通常是另一个MapReduce，它可以轻松地操作第一个MapReduce产生的文件集，而不是需要单个合并输入。即使使用者不是另一个MapReduce，初始MapReduce中的减速进程也可以直接写入合并的目标(例如Bigtable或并行数据库表)。

数据加载．比较论文中的DBMS测量结果表明，在对输入数据进行分析之前将其加载到数据库的成本很高。对于比较论文中的许多基准测试，将输入数据加载到并行数据库所需的时间是通过Hadoop分析数据所需时间的5到50倍。换句话说，对于一些基准测试，从磁盘上文件集合中的数据开始，在可能将数据加载到数据库并完成单个分析之前，可以对数据运行50个单独的MapReduce分析。如果数据加载后会运行很多查询，那么长加载时间可能无关紧要，但通常情况并非如此;通常会生成数据集，处理一两次，然后丢弃。例如，在MapReduce论文中描述的web搜索索引构建系统⁴是一个MapReduce阶段的序列，其中大多数阶段的输出被一个或两个后续的MapReduce阶段消耗。

回到顶部

结论

在比较论文中关于性能的结论是基于MapReduce的错误假设，并且夸大了并行数据库系统的好处。在我们的经验中，MapReduce是一个高效的大规模容错数据分析工具。然而，从这次讨论中可以得出一些有用的经验教训:

启动延迟．MapReduce的实现应该通过使用像跨不同调用重用工作进程这样的技术来努力减少启动延迟;

数据转移．必须仔细注意数据洗牌阶段的实施，以避免生成O (M * R)在MapReduce中使用米地图任务和R减少任务;

文本格式．MapReduce用户应该避免使用低效的文本格式;

自然指数．MapReduce用户应该尽可能利用自然索引(比如日志文件名中的时间戳);而且

Unmerged输出．大多数MapReduce输出应该保持不合并，因为如果下一个消费者是另一个MapReduce程序，合并没有任何好处。

与并行数据库相比，MapReduce提供了许多显著的优势。首先，它为大型作业提供了细粒度的容错;在多个小时的执行过程中出现故障不需要从头开始重新启动作业。其次，MapReduce对于在具有许多不同存储系统的异构系统中处理数据处理和加载数据非常有用。第三，MapReduce为执行比SQL直接支持的更复杂的函数提供了一个良好的框架。

---

MapReduce为大型任务提供了细粒度容错;在多个小时的执行过程中出现故障不需要从头开始重新启动作业。

---

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2010 ACM有限公司

---

评论

---

显示3评论