MapReduce: 一个巨大的倒退

ddatsh 发布于 2011/11/04 01:13
阅读 4K+
收藏 4

前言

databasecolumn 的数据库大牛们(其中包括PostgreSQL的最初伯克利领导:Michael Stonebraker)最近写了一篇评论当前如日中天的MapReduce技术的文章,引发剧烈的讨论。我抽空在这儿翻译一些,一起学习。

译者注:这种 Tanenbaum vs. Linus 式的讨论自然会导致非常热烈的争辩。但是老实说,从 Tanenbaum vs. Linus 的辩论历史发展来看,Linux是越来越多地学习并以不同方式应用了 Tanenbaum OS 研究者的经验(而不是背弃); 所以 MapReduce vs. DBMS 的讨论,希望也能给予后来者更多的启迪,而不是对立。

原文见:

http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html

MapReduce: A major step backwards/MapReduce: 一个巨大的倒退

注:作者是 David J. DeWitt Michael Stonebraker

18日,一位Database Column的读者询问我们对各种新的分布式数据库研究工作有何看法,我们就从MapReduce谈起吧。现在讨论MapReduce恰逢其时,因为最近 商业媒体充斥着所谓云计算(cloud computing革命的新闻。这种计算方式通过大量(低端的)并行工作的处理器来解决计算问题。实际上,就是用大量便宜货(原文是jelly beans)代替数量小得多的高端服务器来构造数据中心。

例如,IBMGoogle已经宣布,计划构建一个1000处理器的集群,开放给几个大学,教授学生使用一种名为MapReduce [1]的软件工具对这种集群编程。加州大学伯克利分校甚至计划教一年级新生如何使用MapReduce框架编程。

我们都既是教育者也是研究人员,MapReduce支持者们大肆宣传它代表了可伸缩、数据密集计算发展中的一次范型转移,对此我们非常惊讶。MapReduce就编写某些类型的通用计算程序而言,可能是个不错的想法,但是从数据库界看来,并非如此:

  1. 在大规模的数据密集应用的编程领域,它是一个巨大的倒退
  2. 它是一个非最优的实现,使用了蛮力而非索引
  3. 它一点也不新颖——代表了一种25年前已经开发得非常完善的技术
  4. 它缺乏当前DBMS基本都拥有的大多数特性
  5. 它和DBMS用户已经依赖的所有工具都不兼容

首先,我们简要地讨论一下MapReduce是什么,然后更详细地阐述上面列出的5点看法。

What is MapReduce?/何谓MapReduce

MapReduce的基本思想很直接。它包括用户写的两个程序:mapreduce,以及一个framework,在一个计算机簇中执行大量的每个程序的实例。

map程序从输入文件中读取"records"的集合,执行任何需要的过滤或者转换,并且以(key,data)的形式输出records 的集合。当map程序产生输出记录,"split"函数对每一个输出的记录的key应用一个函数,将records分割为M个不连续的块 (buckets)。这个split函数有可能是一个hash函数,而其他确定的函数也是可用的。当一个块被写满后,将被写道磁盘上。然后map程序终 止,输出M个文件,每一个代表一个块(bucket)

通常情况下,map程序的多个实例持续运行在compute cluster的不同节点上。每一个map实例都被MapReduce scheduler分配了input file的不同部分,然后执行。如果有N个节点参与到map阶段,那么在这N个节点的磁盘储存都有M个文件,总共有N*M个文件。

值得注意的地方是,所有的map实例都使用同样的hash函数。因此,有相同hash值的所有output record会出被放到相应的输出文件中。

MapReduce的第二个阶段执行Mreduce程序的实例, Rj, 1 <= j <= M. 每一个reduce实例的输入是Rj,包含文件Fi,j, 1<= i <= N. 注意,每一个来自map阶段的output record,含有相同的hash值的record将会被相同的reduce实例处理 -- 不论是哪一个map实例产生的数据。在map-reduce架构处理过后,input records将会被以他们的keys来分组(以排序或者哈希的方式),到一个reduce实例然后给reduce程序处理。和map程序一 样,reduce程序是任意计算语言表示的。因此,它可以对它的records做任何想做事情。例如,可以添加一些额外的函数,来计算record的其他 data field。每一个reduce实例可以将records写到输出文件中,组成MapReduce计算的"answer"的一部分。

SQL可以做对比的是,map程序和聚集查询中的 group-by 语句相似。Reduce函数和聚集函数(例如,average,求平均)相似,在所有的有相同group-by的属性的列上计算。

现在来谈一谈我们对这种计算方式的5点看法。

MapReduce is a step backwards in database access

  • Schemas是有益的。
  • schema和程序分开处理是有益的。
  • High-level存取语言是有益的。

MapReduce没有学到任何一条,并且倒退回了60年代,倒退回了现代数据库管理系统发明以前的时代。

DBMS社区懂得schemas的重要性,凭借fields和他们的数据类型记录在储存中。更重要的,运行状态的DBMS系统可以确定输入 的记录都遵循这个schema。这是最佳的保护程序不会添加任何垃圾信息到数据集中。MapReduce没有任何这样的功能,没有任何控制数据集的预防垃 圾数据机制。一个损坏的MapReduce数据集事实上可以无声无息的破坏所有使用这个数据集的MapReduce程序。

schema和程序分开也非常重要。如果一个程序员想要对一个数据集写一个新程序,他必须知道数据集的结构(record structure)。现代DBMS系统中,schema储存在系统目录中,并且可以被任意用户查询(使用SQL)它的结构。相反的,如果schema不 存在或者存在于程序中,程序员必须检查程序的代码来获得数据的结构。这不仅是一个单调枯燥的尝试,而且程序员必须能够找到先前程序的source code。每一个MapReduce程序员都必须承受后者的乏味,因为没有系统目录用来储存records的结构 -- 就算这些结构存在。

70年代DBMS社区,在关系型数据库支持者和Codasys型数据库支持者之间发有一次"大讨论"。一个重点议题就是DBMS存取程序应该写成哪种方式:

  • 描述你想要的 -- 而不是展示一个算法,解释如何工作的。 (关系型数据库的观点)
  • 展示数据存取的算法。(Codasyl 的观点)

 

讨论的结果已经是过去的历史, 但是整个世界看到High-level语言的价值,因此关系型数据库开始流行. High-level语言上编写/修改程序比较容易, 而且易于理解. Codasyl曾被批评为"DBMS存取的汇编语言". 一个MapReduce程序员和Codasyl程序员类似-他们在low-level语言基础上做low-level的记录操作. 没有人提倡回到汇编语言, 同样没有人被迫去编写MapReduce程序.

 

MapReduce提倡者也许反对这个说法, 宣称他们的目标数据集是没有schema. 我们不同意这个说法. 从输入数据集中抽取key, map函数至少依赖每个数据集的一个数据字段的存在, reduce函数也是如此, 从收到要处理的记录来 计算值.

googleBigTable(或者HadoopHBase)基础上写MapReduce的应用并没有改变这个事实. 通过自描述的元组 格式(row key, column name, (value)), 相同表的不同元组事实上有不同的schema. 另外BigTableHBase 并不提供逻辑独立, 例如view视图机制. 当逻辑schema改变时, View(视图)很重要地简化了程序的继续运行.

MapReduce is a poor implementation

2. MapReduce是一个糟糕的实现

所有现代DBMS都使用散列或者B树索引加速数据存取。如果要寻找记录的某个子集(比如薪水为10000的雇员或者是鞋类专柜的雇员),经常可以使用索引有效地将搜索范围缩小一到两个数量级。而且,还有查询优化器来确定是使用索引还是执行蛮力顺序搜索。

MapReduce没有索引,因此处理时只有蛮力一种选择。在索引是更好的存取机制时,MapReduce将劣势尽显。

有人可能会说,MapReduce的价值在于在计算机网格上自动地提供并行执行。这种特性数据库研究界在上世纪80年代就已经探讨过了,而 且构建了许多原型,包括 Gamma [2,3], Bubba [4], Grace [5]。而Teradata这样的系统早在80年代晚期,就将这些想法商业化了。

对这一点做个总结, 过去的20年曾出现过许多高性能,商业化的, 网格SQL引擎(带有schemas和索引). 与它们相比, MapReduce并没有表现出众.

MapReduce本身存在一些lower-level实现的问题, 特别是skew和数据交换.

MapReduce提倡者好象忽略的一个因素是skew问题. "Parallel Database System: The Future of High Performance Database Systems" 文章所述, skew是并行查询系统想要成功达到扩展应用的巨大障碍. 当有同样key的记录分布变化很广, 这个问题会发生在map阶段. 这个变化反过来会导致一些reduce实例比其他 实例要运行更长时间, 这就使整个计算执行时间是最慢的reduce实例的运行时间. 并行数据库业界已经研究这个 问题很深了, 并开发了一些解决方案, MapReduce社区也许想采用.

还存在一个MapReduce支持者曲解的严重性能问题. 想想Nmap实例产生M个输出文件-每个最后由不同的reduce实例处理, 这些文件写到运行map实例机器的本地硬盘. 如果N1,000, M500, map阶段产生500,000个本地文件. reduce阶段开始, 500reduce实例每个需要读入1,000文件, 并用类似FTP协议把它要的输入文件从map实例 运行的节点上pull取过来. 假如同时有数量级为100reduce实例运行, 那么2个或2个以上的reduce实例同时访问 同一个map节点来获取输入文件是不可避免的-导致大量的硬盘查找, 有效的硬盘运转速度至少降低20%. 这就是为什么 并行数据库系统不实现split文件, 采用push(推到socket套接字)而不是pull. 由于MapReduce的出色容错依赖 于如何实现split文件, MapReduce框架是否成功地转向使用push范式, 不是很清楚.

仅用实验结果来说, 我们严重怀疑MapReduce应用如何能很好地扩展. 甚至, MapReduce实现者应该好好学习一下近 25年来的并行DBMS研究文献.

MapReduce is not novel

MapReduce一点也不新颖

MapReduce社区好象觉得他们发现了一个崭新的处理大数据集的范式. 事实上, MapReduce使用的技术已经有20年了. 把大数据集切分成小的分区在"Application of Hash to Data Base Machine and Its Architecture"[11] 里作为一种新的join算法的基础就已经提出, "Multiprocessor Hash-Based Join Algorithms"[7], Gerber 展现了Kitsuregawa的技术如何被扩展, shared-nothing [8]的集群上结合 分区表, 分区执行, hash拆分来并行执行join. DeWitt [2]表明这些技术可以被采用来并行执行无论有无group 语句的合并. DeWittGray [6]描述了一些并行数据库系统,以及它们如何处理查询. ShatdalNaughton [9] 则探索了并行执行合并的替代策略.

Teradata已经利用这些技术实现了一个商业DBMS产品20年了; 特别是MapReduce人群宣称发明的那些技术.

MapReduce支持者肯定地声称写MapReduce函数是他们的软件不同于并行SQL实现的地方, 我们不得不提醒他们 POSTGRES1980年代中期就支持用户自定义函数和自定义合并了. 实质上,所有现代数据库系统已经提供这样的 功能很久了, 大约起源于1995年左右的Illustra引擎.

MapReduce is missing features

MapReduce缺乏的特性

以下特性在现代DBMS都已经缺省提供, MapReduce里没有.

  • Bulk loader - 把文件里的输入数据转成期望格式,然后导入DBMS.
  • Indexing - 如上所述.
  • 更新 - 在数据库里修改数据
  • 事务 - 支持并行更新, 更新过程中能从失败处恢复.
  • 完整性约束 - 用来挡住垃圾数据
  • 引用完整 - 也是用来挡住垃圾数据
  • 视图 - schema可以改变, 也无须重写应用程序

总之, MapReduce仅提供了现代DBMS功能的一小部分.

MapReduce is incompatible with the DBMS tools

它和DBMS工具不兼容

一个现代SQL DBMS可以有以下类别的工具:

  • 报告生成器(例如水晶报表), 可以提供可视化报告.
  • 商业智能工具 (例如Business Objects或者Cognos), 支持数据仓库的专门查询.
  • 数据挖掘工具(例如Oracle数据挖掘, IBM DB2智能挖掘), 允许用户在大数据集中发现结构.
  • 复制工具(例如Golden Gate), 允许用户从一个DBMS复制数据到另外一个.
  • 数据库设计工具(例如Embarcadero), 帮助用户创建一个数据库

MapReduce不能使用这些工具,但也没有自己的工具. 直到它成为SQL兼容, 或者有人写这些工具, 否则在完成一个终端应用时MapReduce会一直很难用.

In Summary

看到规模大得多的社区加入可伸缩的查询处理技术的设计与实现,非常令人兴奋。但是,我们要强调,他们不应该忽视数据库技术40多年来的教 训,尤其是数据库技术中数据模型、物理和逻辑数据独立性、像SQL这样的声明性查询语言等等,可以为应用程序的设计、实现和维护带来的诸多好处。而且,计 算机科学界往往喜欢自行其是,不理会其他学科的文献。我们希望更多人来一起研究过去25年的并行DBMS文献。MapReduce要达到能够与现代 DBMS相提并论的水平,还需要开发大量特性和工具。

我们完全理解数据库系统也有自己的问题。数据库界清楚地认识到,现在数据库系统还太使用,而且正在解决这一问题。数据库界也从 MapReduce为其应用程序提供的出色的容错上学到了有价值的东西。最后,我们注意到,一些数据库研究人员也开始研究使用MapReduce框架作为 构建可伸缩数据库系统的基础。雅虎研究院的Pig[10]项目就是其中之一。

加载中
1
中山野鬼
中山野鬼

从内容上看,作者还是有料的。MAPREDUCE确实不错,但只能解决一类问题。听说某大公司搞云平台也使用HADOOP做尝试。哈,回了朋友一句“SB”。因为他们的云平台未来肯定不是做个文件或语句搜索比对这种简单算法,可MAPREDUCE化的工作。

数据库研究了这么多年,应用了这么多年,特别是oracle等为代表的商业数据库,切实的解决了很多社会活动中的数据处理问题。其中的复杂性绝不是mapreduce能解决的。mapreduce可以作为一个新的手段,去处理上述商业数据库暂无法解决,或解决不好的部分问题。但如果认为mapreduce可以替换掉商业数据库现在能良好处理的解决方案,基本就是SB思维。

这如同发明了两轮驱动直立电动车,就认为可以替代火车一样。

我其他到觉得无所谓。唯一担忧的是,学校更着起哄,尝试拿HADOOP的MAPREDUCE乱做研究,这会害了一批学生。

1
宏哥
宏哥

引用来自“中山野鬼”的答案

从内容上看,作者还是有料的。MAPREDUCE确实不错,但只能解决一类问题。听说某大公司搞云平台也使用HADOOP做尝试。哈,回了朋友一句“SB”。因为他们的云平台未来肯定不是做个文件或语句搜索比对这种简单算法,可MAPREDUCE化的工作。

数据库研究了这么多年,应用了这么多年,特别是oracle等为代表的商业数据库,切实的解决了很多社会活动中的数据处理问题。其中的复杂性绝不是mapreduce能解决的。mapreduce可以作为一个新的手段,去处理上述商业数据库暂无法解决,或解决不好的部分问题。但如果认为mapreduce可以替换掉商业数据库现在能良好处理的解决方案,基本就是SB思维。

这如同发明了两轮驱动直立电动车,就认为可以替代火车一样。

我其他到觉得无所谓。唯一担忧的是,学校更着起哄,尝试拿HADOOP的MAPREDUCE乱做研究,这会害了一批学生。

说到点上了.

所以说, 所谓开源啊, 大多都是坑

没有无缘无故的钱.  客户愿意付钱, 就一定有他的道理.

贵,是一种态度

比贵更贵的,就是开源 -- 浪费青春

ddatsh
ddatsh
+1
0
mallon
mallon
作者明显一SB,硬把MapReduce往数据库上套。
mallon
mallon
@dd : MapReduce是很经典的并行计算算法,GOOGLE只是把它取了个好听的名字而已,而数据检索只是MapReduce很小的一个应用
ddatsh
ddatsh
等更多客观的评论,文章的作者还是很有水平的
0
p
pdzs
具体技术针对具体应用。并不能指望一个技术能搞定N多应用。
0
宏哥
宏哥

引用来自“中山野鬼”的答案

从内容上看,作者还是有料的。MAPREDUCE确实不错,但只能解决一类问题。听说某大公司搞云平台也使用HADOOP做尝试。哈,回了朋友一句“SB”。因为他们的云平台未来肯定不是做个文件或语句搜索比对这种简单算法,可MAPREDUCE化的工作。

数据库研究了这么多年,应用了这么多年,特别是oracle等为代表的商业数据库,切实的解决了很多社会活动中的数据处理问题。其中的复杂性绝不是mapreduce能解决的。mapreduce可以作为一个新的手段,去处理上述商业数据库暂无法解决,或解决不好的部分问题。但如果认为mapreduce可以替换掉商业数据库现在能良好处理的解决方案,基本就是SB思维。

这如同发明了两轮驱动直立电动车,就认为可以替代火车一样。

我其他到觉得无所谓。唯一担忧的是,学校更着起哄,尝试拿HADOOP的MAPREDUCE乱做研究,这会害了一批学生。

"其中包括PostgreSQL的最初伯克利领导:Michael Stonebraker"

Ingres 是RDBMS 的开山鼻祖, Postgresql 是Ingres的一个延续.

0
mark35
mark35
盘. 如果N是1,000, M是500, map阶段产生500,000个本地文件. 当reduce阶段开始, 500个reduce实例每个需要读入1,000文件,
这不会把卷node耗用光么?

 

 

0
Foureyes
Foureyes

贵,是一种态度

比贵更贵的,就是开源 -- 浪费青春

精辟呀!

返回顶部
顶部