MapReduce(转)

　　这篇文章是由databasecolumn的几个数据库大牛写的，简要的介绍了MapReduce以及将其与现代数据库管理系统进行了对比，并指出了一些不足之处。本文纯属学习性翻译，从多方面来了解MapReduce，不代表完全赞同原文的观点。请读者也辩证的看。

         一月八号，一个数据库专栏的读者询问我们关于对新的分布式数据库研究成果的意见。我们在这结合MapReduce谈谈我们的看法。现在是讨论这个问题的不错的时机，因为最近媒体上到处充斥着新的革命所谓“云计算”的信息。这种模式需要利用大量的（低端）处理器并行工作来解决计算问题。实际上，这建议利用大量的低端处理器来构建数据中心，而不是利用数目少的多的高端服务器来构建。

        举例来说，IBM和Google已经宣布计划用1000台处理器构建的集群提供给部分大学，传授学生们如何使用MapReduce工具在这些集群上编程。加利福尼亚大学伯克利分校甚至打算开设使用MapReduce框架编程的课程。我们对MapReduce支持者大肆炒作它如何如何能够开发更加具有扩展性，以及数据密集型程序感到震惊。MapReduce可能在某些特定类型的通用计算上是个不错的想法，但是对于数据库社区来说：

1.    从大规模数据应用程序模型来说是一个巨大的倒退。
2.    不是一个最优实现，因为它使用蛮力来代替索引。
3.    一点都不新奇，它只是实现了一个特定的25年前就有的众所周知的技术。
4.    失去了大部分目前数据库管理系统的特性。
5.    不能兼容所有目前数据库管理系统用户已经依赖的工具。

      首先我们将简要的讨论下MapReduce到底是什么，然后我们将就上面5点进行更深层次的讨论。


MapReduce是什么？

        MapReduce基础出发点是很易懂的。它由称为map和reduce的两部分用户程序组成，然后利用框架在计算机集群上面根据需求运行多个程序实例来处理各个子任务，然后再对结果进行归并。

        Map程序从输入流中读取一组“记录”，然后对记录进行需要的过滤或者转换，然后输出一组记录(key,data)。当map程序生成输出记录时，一个分割方法将记录划分为M个不相交的块并赋予一个键值。这个分割方法一般是一个hash函数，只要这个决定性的函数能够满足就行。当一个块被填充后，它将写入磁盘，map程序结束的时候每个块都将输出M个文件。

        通常情况下，将有多个map的程序实例运行在计算机集群的不同的节点上。每个map实例都将由MapReduce调度程序分配一个不重复的输入文件来独立执行。如果有N个节点参与map程序执行，那么N个节点中的每个节点都将有M个文件存储在各自的磁盘上，也就是说，总共将有N*M个文件。Fi,j, 1 ≤ i ≤ N, 1 ≤ j ≤ M.

        其中有个值得注意的关键点是每个map实例都必须使用一个相同的hash方法。这样，所有的拥有相同hash值的输出记录才会写入相应的输出文件。

        MapReduce的第二个阶段就是执行M个reduce的程序实例。Rj, 1 ≤ j ≤ M.每个reduce实例Rj的输入文件由文件 Fi,j组成,1 ≤ i ≤ N。还有一个值得注意的是：所有从map阶段输出的拥有相同hash值的记录，无论是哪个map实例生成的，都将由一个相同的reduce实例处理。在map-reduce框架收集整理之后，所有的输入记录都将根据它们的键值(key)编组然后提供给reduce程序。跟map程序一样，reduce程序也可以做任意的计算。所以，你可以对输入的记录做任何你想要的事情。举例来说，可能会对记录的别的字段进行一些附加的计算。每个reduce实例都可以将记录写入输出文件，只要是MapReduce计算所需要的结果。

        用SQL来做类比，map象聚合(aggregate)查询中的group-by子句。Reduce则类似计算group-by起来的行的聚合函数(例如求平均等)。

        现在我们基于这个计算模型来讨论上面提到的五点：

1.    MapReduce是一个数据库存取的退步

        做为一个数据处理模型，MapReduce呈现出了一个巨大的退步。数据库社区从IBM在1968年第一次发布IMS以来的四十年中学到了以下三个经验：

*　结构描述是好的。
*　将结构描述从程序中分离是好的
*　高阶的访问语言是好的

         MapReduce没有吸引上面三个经验中的任何一个，而且还退步到了现在数据库管理系统发明前的60年代。

         数据库管理系统社区学习到的关于最重要的结构描述就是：记录的字段和它的数据类型都记录在存储系统中。更重要的是，数据库管理系统的运行时可以保证所有的记录都遵守结构描述。这是避免将垃圾数据添加到数据集中的最好的方法。MapReduce没有这样的方法，也没有避免将垃圾数据添加到数据集中的控制。一个毁坏的数据集可以悄无声息的破坏整个使用这个数据集的MapReduce程序。

        将数据描述与程序分离也很关键。如果开发者想在一个数据集上开发一个新的程序，他必须先去了解记录结构。在现代数据库管理系统中，结构描述存储在系统目录中，而且可以被用户用SQL查询来了解它的结构。与此相反的是，如果数据描述不存在，或者隐藏在程序之中，开发者要了解这个数据结构必须通过检查原有的代码。这个工作不仅仅是非常沉闷的，而且开发者必须先找到这个程序的源代码。如果没有相应的结构描述存在，后面的这个沉闷的问题将在所有的MapReduce程序中存在。

        在1970年数据库管理系统社区，关系型数据库支持者和数据系统语言协会(Codasyl)支持者进行了一场“剧烈的辩论”。其中一个最大的争议是数据库管理系统的访问程序以何种方式访问：

*　用统计来获取你想要的数据(关系型的观点)
*　提供一个算法来进行数据访问(Codasyl的观点)

         争论的结果已经是古代史了，但是整个世界都看到了高阶语言的价值以及关系型系统的胜利。以高阶语言的形式编程更加容易编写，易于修改，而且方便一个新来者的理解。Codasyl被批判为“以汇编语言的形式来对数据库管理系统进行访问”。MapReduce程序员有点类似Codasyl程序员。他们用低阶的语言来处理低阶记录。没有人提倡回归汇编语言，类似的，不应该强制任何人用MapReduce来编程。

        MapReduce提倡者可能会反对说他们的数据集没有数据描述的假设。那么我们解除这个断言。在从输入数据记录中提取一个key时，map方法在每个输入记录中至少依赖一个存在的数据字段。相同Reduce方法的持有者从接受到的处理数据中计算一些值。

        基于Google的BigTable或者Hadoop的Hbase来编写MapReduce程序并不会真正重大的改变这种状况。在相同的表中使用一种自描述元组格式（行号，列名，值）确实可以拥有不同的架构。但是，BigTable和Hbase并没有提供逻辑上的独立。以视图机制举例来说，视图有一个明显的简化作用，当逻辑数据描述（logic schema）改变后，仍保持程序运行。

2.    MapReduce是一个粗燥的实现

       所有现在数据库管理系统使用hash或者B-tree来索引加快对数据的访问。如果一个用户在查找一个记录集的子记录集（比如雇员中谁的薪水在10000或者谁在鞋生产部门），那么他可以使用索引来有效的缩减查找范围。另外，还提供了一个查询优化器来决定到底是使用索引还是进行一个残忍野蛮的顺序查询。

        MapReduce没有索引，理所当然的只能使用蛮力来作为处理选项。而不管索引在当前情况下是否是一个最好的访问机制。

        一个值得争论的是，MapReduce提出的自动的在计算机集群中提供并行计算的价值。其实这个特性在1980年时代就被数据库管理系统研究社区研究过了，多个原型被提出来，比如Gamma，Bubba和Grace。商业化的利用这些思想在系统则在80年代末期，比如Teradata。

        概括起来说，在前20年已经出现了高性能，商业化的，面向网格计算机群的SQL引擎（带结构描述和索引）。MapReduce跟这些系统相比并没有那么好。

         MapReduce同时存在很多底层的实现问题，特别是数据交换和数据斜交的情况。

         一个因素是MapReduce支持者好像没有注意到关于数据斜交的问题。就像在“平行数据库系统：未来的高性能数据库系统”中提到的，数据斜交是构建成功高扩展性并行查询系统的巨大障碍。这个问题重现在map阶段，当拥有相同键的数据拥有大幅度差异的时候。这个差异，反过来导致某些reduce实例花费比其它实例更长甚至常很多的时间来运行。结果就是计算的运行时间由速度最慢的那个reduce实例决定。平行数据库社区已经广泛的研究了这个问题并且拥有了成熟的，MapReduce社区可能愿意采纳的解决方案。

        还有第二个严重的性能问题被MapReduce支持者掩盖了。回忆N个map实例中的每个实例都将生成M个输出文件。每个都分发给不同的reduce实例。这些文件都被写入本地硬盘以备map实例使用。如果N是1000，M是500，那么在map阶段将生成500000个本地文件。当reduce阶段开始，500个reduce实例必须读取1000个输入文件，必须使用类似FTP的协议将每个输入文件从各个map实例运行的节点中获取（pull）过来。在100秒内所有reduce实例将同时的运行起来，不可避免的会发生两个或者更多个reduce实例企图并行的从同一个map节点中获取输入文件，包括大量的磁盘搜索，当超过因子20时，将极大的降低磁盘的有效传输率。这就是为什么并行数据库系统不实现分割文件，而使用推(push to sockets)来代替拉(pull)。因为MapReduce通过实现分割文件来获得优秀的容错性，不好说如果MapReduce框架修改成使用推(push)模型是否会成功。

        鉴于实验评估，我们严重的怀疑MapReduce在大规模应用中会表现的很好。MapReduce的实现者还需要好好的研究过去25年来并行数据库管理系统的研究文献。

3.    MapReduce并不新奇

        MapReduce社区看起来感觉他们发现了一个全新的处理大数据集的模型。实际上，MapReduce所使用的技术至少是20年前的。将大数据集划分为小数据集的思想是在Kitsuregawa首次提出的“Application of Hash to Data Base Machine and Its Architecture”的基础上发展出来的一个新的连接算法。在“Multiprocessor Hash-Based Join Algorithms”中，Gerber演示了如何将Kitsuregawa的技术扩展到使用联合分区表，分区执行以及基于hash的分割来连接并行的无共享集群。DeWitt演示了如何采用这些技术来执行有group by子句以及没有group by子句的并行聚合。DeWitt和Gray描述了并行数据库系统以及他们如何处理查询。Shatdal和Naughton探索了并行聚合的替代策略。

       Teradata已经出售利用这些技术构建的数据库管理系统20多年了，而这些技术正是MapReduce一伙声称的发明的技术。

        当然MapReduce提倡者将毫无疑问的声称他们编写的MapReduce函数实现他们的软件与使用并行SQL实现有多么大的不同，我们必须提醒他们，POSTGRES已经在80年代中期就支持了用户自定义函数以及用户自定义聚合。本质上来说，从1995年Illustra引擎开始算，所有现代数据库系统都提供了类似的功能很长一段时间了。

4.    MapReduce失去了很多特性

       所有下面的特性都被现在的数据库管理系统提供了，而MapReduce没有：

* 批量导入     —— 将输入数据转化成想要的格式并加载到数据库中
* 索引               —— 如上文所述
* 更新               —— 改变数据集中的数据
* 事务               —— 支持并行更新以及从失败的更新中恢复
* 完善的约束        —— 防止垃圾数据添加到数据集
* 完善的引用        —— 类似FK，防止垃圾数据的存在
* 视图               —— 底层逻辑数据描述可以改变但不需要重写程序

       简单的说来，MapReduce只提供了现在数据库管理系统的函数性功能。

5.    MapReduce与现有的数据库管理系统工具不兼容

      一个现代的SQL数据库管理系统都拥有如下可用的工具：

* 报表                —— (比如水晶报表) 将数据友好的展示给人
* 商业智能工具        —— (比如Business Objects or Cognos)允许在数据仓库中进行特定查询
* 数据挖掘工具        —— (比如Oracle Data Mining)允许用户在大数据集中发现数据规律
* 复制工具            —— 允许用户在不同的数据库中进行复制传输
* 数据库设计工具    —— 帮助用户构建数据库

        MapReduce不能使用这些工具，同时它也没有自己的工具。直到它能与SQL兼容或者有人编写了这些工具，MapReduce仍然在端到端的任务中显得十分困难。



总结

        看到一个庞大的社区参与到设计和实现可扩展的查询处理技术中是值得振奋的。但是，我们认为他们不应该忽视超过40年的数据库技术的经验。——特别是拥有巨大优势的数据描述模型以及物理数据与逻辑数据互相独立；描述性的查询语言（比如SQL）；提供设计，实现，以及维护程序。此外，计算机科学社区不应该孤立起来而应该多读读别的社区的技术文献。我们鼓励好好的研究下近25年来的并行数据库管理系统的技术文献。最后，在MapReduce达到现代数据库管理系统之前，还有很多的没实现的特性以及必须的工具需要添加。

        我们完全的理解利用数据库来解决他们的问题是可以的。数据库社区意识到数据库系统解决他们的问题使用起来操作过于“复杂”。数据库社区也从MapReduce提供的优秀的容错机制中学到了不少的有价值的东西。最后我们注意到一些数据库的研究者开始探索以MapReduce框架为基础来构建可扩展的数据库系统，yahoo!研究中心的Pig项目就是其中一个努力的结果。


本翻译属于原创，转载请注意出处，英文原版请查看:
http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html