MapReduce Versus Parallel DBMS

http://duanple.blog.163.com/blog/static/7097176720118179143877/

在 2010年1月的ACM上，有两篇文章非常吸引人注意。一篇文章是Google的Jeffrey Dean、Sanjay Ghemawat发表的标题为《MapReduce:一个灵活的数据库处理工具》，另一篇文章是Michael Stonebraker、Daniel Abadi、 David J. DeWitt、Sam Madden、Erik Paulson、Andrew Pavlo、Alexander、Rasin等人发表的《MapReduce和并行数据库：是朋友还是敌人？》。这两篇文章让我想起去年初Michael Stonebraker等人就MapReduce发表的一些评论而导致了一次MapReduce和数据库系统的大辩论。那篇文章的标题是《MapReduce：一个巨大的倒退》。这次辩论双方则准备了丰富的实践和实验案例。看上去更加有趣也更加有说服力。以下“正方”代表坚持并行数据库解决方案的Andrew Pavlo、 Michael Stonebraker等，而反方则是Google的MapReduce（下文简称MR）的拥趸Jeffrey Dean、Sanjay Ghemawat等。时间顺序如下:

正方抛出观点。2009 年Andrew Pavlo等人发表了一篇标题为《大规模数据分析的方法对比》（http://database.cs.brown.edu/projects/mapreduce-vs-dbms/ ）的文章，里面对比了数据库和MR两种大规模数据分析方法的对比。通过对比流行的MR软件 Hadoop和一种并行数据库之间的架设、使用和性能等方面的异同，指出MR并不是解决大规模数据分析的好方法，其在性能、易用性等方面有诸多问题：

MR没法用索引，总是对数据进行完全扫描；
MR输入和输出，总是文件系统中的简单文件；
MR需要使用不高效的文本数据格式。

反方接招。

对于正方第一个观点，反方如此应对：“错了！MR的输入本身可以是数据库的输出，所以，我们是可以用索引的。另外一个例子是MR从BigTable里面读取数据，如果数据落在一个行范畴里面，当然是可以用索引的。而且，在很多需要处理的数据里头，比如Web Server的日志，经过轮转之后天然就有索引（文件名包含时间戳）。”
对于第二个观点，反方认为：“现存的很多MR系统，本身就是一个异构环境，用户的数据可能存储在关系数据库里头，而其处理结果可能会记录在文件系统里头。而且，这样的环境可能会进化，用户的数据会迁移到新的系统里。而MR可以非常便利地在这些环境上运行。更进一步，用户可以扩展这些存储，比如分布文件系统、数据库查询结果，存储在BigTable里面的数据，结构化的数据（B-tree文件等）。对于这些场合，单个MR处理就可以很容易地捏合它们。”
对于第三个观点，反方认为：“这点的确很精辟。很到位，不过这个因素是取决于具体的实现的，比如在Google的MR实现里，有个 Protocol Buffer层，可以对输入的数据进行格式定义，因此就可以直接适用二进制类型，而不用有额外的格式转换的开销，在我们的测试里，原来要花1731ns的一个格式分析，用Protocol Buffer预定义之后，只要20几ns。所以，如果实现得足够好，我们认为MR系统不会只能处理文本格式的数据，而是可以处理二进制数据，因此效率还可以极大提升。”

除了这些之外，反方还抛出了几块大砖头，等着正方接招：

MR与存储系统无关，而且可以不用把数据装载到数据库就直接处理之，在很多场合下，在数据库系统把数据装载到数据库里头并且完成一次分析所花的时间，用MR的方式都能完成50次分析运算了。
MR可以表现更复杂的数据变换规则，很多反方的意见都是实现相关的，是针对一些不好的MR的实现做出来的，因此站不住脚。反方的最有力的证据就是，在Google里头跑得很好的一万多各种MR应用，从网页分析到索引建立，从日志分析到网图计算等等。

正方的回应。作为正方，Michael Stonebraker 教授等人在同一期杂志上发表了另外一篇文章，很有趣的是刚好排在反方的文章之前。这篇文章以批评与自我批评的方式提出了若干有趣的观点，其中有些刚好是对反方的一个回应：MR系统可以用于（注意：不是胜出）下列场合：

ETL类的应用：从多个不同的源读取日志信息；分析以及清理日志数据；执行复杂的变换，比如“会话转换”；决定存储什么样的属性以及把信息装载到DBMS或者其他存储引擎中；
复杂分析应用：这种挖掘类型的应用需要对数据进行多步骤的计算和处理，通常一个程序的输出会是另外一个程序的输入，因此很难用单个SQL语句来表示，这种应用场合下，MR是很好的候选方案；
半结构化数据：因为MR不需要对数据的存储进行格式定义，因此MR比较适合处理半结构化数据，这些数据通常都是一些键值对。这些场合下，MR非常适合做 ETL的事情，如果并行数据库选用了面向列的存储方案，并且查询大多是分析性的查询，那么数据库方案依然是更好些的选择（正方有试验结果支撑）；
快速实施的系统：并行数据库最大的缺点就是架设和调优难度要比MR大得多，虽然一旦架设、调优完毕，并行数据库系统表现出远胜MR的性能和特性，但对大多数急于上手的入门级用户来说，并行数据库系统的学习门槛显然要高得多。最后就是成本，虽然并行数据库在性能和应用编写简易性方面明显胜于MR系统，但现实世界里确实还缺乏完善和健壮的低成本开源解决方案，这点是MR最大的优点。数据库社区显然在这个方面输了一阵。

正方认为，把适合于数据库的工作交给MR去做结果其实并不好。在正方的试验里，证实了MR更加适用于做数据转换和装载的（ETL）工作，在这些场合，MR可以成为并行数据库的良好补充，而不是替代品。为了证明上述论点，正方做了一些有趣的试验，试验对比的双方是并行数据库集群和Hadoop集群，试验的主要内容有：

Grep任务：两个系统都对分布在100个节点上的1TB数据进行无法使用排序和索引的Grep处理，按说应该是面向更低层数据接口的Hadoop胜出，结果却出乎人们的意料，是并行数据库快了两倍左右。
Web 日志分析：两个系统都对分布在100个节点上的2TB数据进行类似GROUP BY的操作，对每个来源IP的点击和计费记录进行统计运算，这也是一个对所有数据进行扫描的操作，没有办法使用排序和索引。所以，直觉认为直接操作数据文件、更低层的Hadoop应该胜出，结果依然让人大跌眼镜，并行数据库胜出面甚至比Grep任务还要大。
连接（Join）任务的性能：把上面测试的用户访问日志和另外一个包含18M URL的100GB的PageRank表连接起来。这个连接有两个子任务，分别对两个数据集进行复杂的计算。第一个子任务连接在一个特定用户数据范围内找出收入最高的IP地址，找到后再由第二个子任务连接计算这个范围内被访问页面的平均PageRank。数据库对付这种设计复杂连接的分析性查询是非常在行的。最后的结果是并行数据库比Hadoop快了21~36倍。

针对上面的结果，正方做了一些分析，认为这些差距的来源主要来自于具体实现，而非并行数据库模型和MR模型之间的差异。比如，MR可以使用并行数据库为低层的存储，所以所有分析都针对现实中两种模式的具体实现。正方分析了导致差距的几个实现相关的架构原因：

数据解析。Hadoop需要用户代码来对输入的文本数据进行解析，然后再加以计算，而这个解析是每个Map和每个Reduce过程都要进行的，相比之下，并行数据库系统只在装载数据的时候解析一次数据，中间计算的开销大大降低。
数据压缩。并行数据库系统使用数据压缩后，性能显著提升，而MR系统却不能，甚至倒退，在反方的试验中，也没有使用压缩，这方面让人感到奇怪，分析出来的可能原因是商业数据库系统对压缩的调优做得比较好，很多压缩算法，比如gzip，未经调优的话，在现代的CPU上，甚至都不能提供什么优势。
管道化。现代数据库系统基本上都是先生成一个查询规划，然后在执行的时候把计算分发到相应节点上。在该计划里一个操作符必须向下一个操作符发送数据，不管下一个操作符是否在同节点上，因此，合格数据是由第一个操作符“推送”给第二个操作符的。这就构成了良好的从生产者到消费者的流水线作业。中间状态的数据不会写到磁盘上，这种运行时的“背压”会在生产者把消费者整崩溃之前把生产者停下来。这种流水线方式和MR的实现不同，MR是把中间状态写到一个本地的数据结构中，然后由消费者“拖取”。这种本地数据结构通常是相当庞大的，虽然这种做法可以在中间步骤上设置更多检查点，从而可以有更好的容错性，但很显然也引入了新的瓶颈。
调度。在测试的并行数据库一方，查询规划是编译时生成，运行时执行。而MR的调度方案是运行时针对每个存储块，在处理节点上调度一次。这种对每个存储块一次的调度显然开销要大得多。当然，这种调度方式可以让MR适应不同的负载风格和不同性能的节点。
面向列的存储。这个在对比双方的系统里都不存在。但却是并行数据库可以进一步提升的手段。

正方经过试验得出的结论是：MR和并行数据库结合是最好的方案，MR负责数据装载、转换等工作，并行数据库负责查询密集型的任务。正方最后发出的振聋发聩的呼吁是：很多事情并行数据库系统已经做得很好了，我们为什么不站在这个巨人的肩膀上？