- 1 -
中国科技论文在线
适合异构数据的数据库引擎设计和实现#
王毅，马建庆**
基金项目：博士点基金（200802461147）
作者简介：王毅（1987），男，硕士生，网络数据库
通信联系人：马建庆（1974），男，讲师，网络与通信，安全
（复旦大学计算机科学技术学院，上海 200433）
摘要：在网络信息化和大数据时代，如何高效地管理各类不同数据格式的数据文件是件很重5
要的事情。由于具有高性能的并行数据库不具有扩展性、容错性，而基于 MapReduce 的系
统在处理结构化数据时正好相反，性能不足。本文通过修改并行数据库的引擎，在保证高性
能的前提下，引入扩展性和容错性。实验结果表明，新的混合的并行数据库可以在性能，扩
展性和容错性之间做到很好的平衡。
关键词：并行数据库； 大数据；高性能；扩展性；容错性；MapReduce 10
中图分类号：
Heterogeneous Data Structure Based Database Engine
Designment and Implement
WANG Yi, MA Jianqing 15
(School of Computer Science, Fudan University, Shanghai 200433)
Abstract: In the erea of internet and big data , it is a vital important thing to how to manage different
data effectively. Usually, data should be not only scaled dynamically, but be analysed fastly and
effectively. Tranditianal parallel Database has high performance but lack scalability and fault tolerance.
MapReduce-based systems are just on the contrast when structured data are processed. This paper 20
hopes to introduce scalability and fault tolerance into parallel database by modifying its engine on the
premise of guaranteeing high performance. Experimental results show that the new hybrid parallel
database has a good balance between performance, scalability and fault tolerance.
Key words: parallel Database; big data; high performance; scalability; fault tolerance; MapReduce
25
0 引言
IDC报告称，全球数据存储需求为 1800亿 GB，预计 2015年将达到 7900亿 GB[1]。如
何有效地存储和分析如此巨大的数据，进而给企业、政府、社会决策提供支持，这对学术界
和工业界来说都是一个巨大的挑战。
由于成本和技术的原因，许多企业的数据分析系统都从少量的昂贵的高端机迁移到一种30
“无共享”的大规模并行计算框架上，这种架构经常构建在公共的或私有“云”上[2]。这种框架
用相对便宜的低端商用机和高性能的交换机组成集群，每个节点都有独立的 CPU、内存和
磁盘来方便并行地完成计算任务。这种环境下的数据分析目前有两种主流技术：一种是上个
世纪 80年代开始，以 Teradata、Gamma研究项目为代表的并行数据库逐步发展成熟，它的
计算是由一系列的操作符组成，前一操作符的输出流是下个操作符的输入流，记录按流水线35
的方式依次经过这些操作符，因而具有较高的性能。如果中间过程有一个步骤出错，整个计
算要从头开始，容错性不好，这也限制了并行数据库的规模，大部分节点在 100个左右[2]。
商用代表有 Vertica、Oracle的 Exadata和Microsoft的Madison等；另一种是以 Google为首
的基于MapReduce[3]和分布式文件系统 GFS[4]组成一种“无共享”的简单的函数式编程的并
行计算框架。Map-Reduce和 GFS可以说是 Google搜索引擎的基石，在 Google内部被广泛40
- 2 -
中国科技论文在线
使用，是支撑其每天亿万次搜索的最重要的组成部分。Apache的 Hadoop是一种MapReduce
的 JAVA开源实现[5]，像 Yahoo!、IBM、Facebook、淘宝、中国移动等许多公司都在使用
它。Facebook用 hadoop管理一个 PB的数据仓库[2]。
Hadoop的设计初衷与并行数据库的设计思想不同: (1)采用 Schema-Free方式，主要用来
处理非结构化数据; (2)一次写多次读; (3)放松事务性(ACID)要求，强调高可扩展性；(4)高扩45
展性必然要求系统具有容错性，来预防由低端机器组成的大规模集群可能发生的故障。
Google每次的分析任务平均出现 次故障[3]。在性能方面，由于数据巨大，不能在线实
时计算和查询，处理结构化数据时不能利用数据库中成熟的技术，如索引、视图等，依靠蛮
力进行穷举查找和计算。因此有观点认为MapReduce是一个巨大的倒退[6]。
两者谁更适合进行大规模的并行计算（主要指结构化数据）也在业界引起了巨大的讨论。50
Stonebraker在[7]详细分析了这两种技术的优缺点、架构差异和相同点。认为 Hadoop更像是
一种 ETL工具，两者的关系不是相互竞争而是互为补充。一些实践者已经在尝试把两者的
优点结合起来，像 Facebook的 hive[8]、耶鲁大学的 hadoopDB[2]、EMC的 Greenplum[9]。
中科院的 DBEHadoop(database engine integrated Hadoop)[10]也是不错的尝试。
本文研究了利用 Hadoop和 RDBMS构建一种并行数据库 FlexDB：利用 hadoop的55
MapReduce的并行计算框架作为通信层，调度和协调集群中各个节点的计算和通信，配合
HDFS（Hadoop Distributed FileSystem）的高扩展性和容错能力，加上具有高性能的 RDBMS
在处理结构化数据方面成熟的技术，形成一种混合的并行数据库系统。这种系统克服了传统
的并行数据库不宜大规模扩展的缺点，在性能效率方面接近于并行数据库，同时也拥有
hadoop的高扩展性和容错能力。我们也提供了一种类似 SQL的语言，具有独立的分析、生60
成查询计划、优化并执行的数据库引擎，还允许用户自定义数据类型和函数，这些都为数据
仓库式的分析和挖掘提供了可能。
1 FlexDB框架设计
与其他的行存储的并行数据库一样，FlexDB要解决两个主要的问题：(1)怎样水平地把
表分割成子表存放在不同的数据库节点上？(2)怎样把用户输入的 SQL语句转换成一系列的65
子 SQL 语句以便让相关的数据库节点并行操作，然后把各个子结果汇总给用户？对于第一
个问题，FlexDB采用了四种分表策略：hash、 range、round-robin 和 random。当一条记录
被 load时，把一个 hash函数作用于记录的一个或多个属性，然后根据得到的值来决定此记
录应该存放在哪个节点的数据库中，这样就可以把一个表分成若干个子表。目前 FlexDB只
实现了 hash和 random两种策略。第二个问题将在后面的章节中介绍。 70
FlexDB采用与 hadoop一样的Master/Slave结构。Hadoop有两个主要的子系统，Hadoop
分布式文件系统 HDFS和 Hadoop Map/Reduce。HDFS由 NameNode Master（存放文件系统
元数据）和 DataNode Slaves（存放文件分割后的 Blocks及其副本）组成。Hadoop Map/Reduce
由 JobTracker Master（分配、监视和协调子任务的执行与相互通信）和 TaskTracker Slaves
（执行子任务）组成。 75
FlexDB 是在 Hadoop 的基础上设计而来的： (1)ChunkNode，在每个 DataNode 节点上
增加一个独立的数据库来存储子表的数据；(2)Catalog，存放整个并行数据库的元数据，比
如表的属性、子表及其副本的存放位置、节点的数据库连接信息（驱动、ip、端口、用户名
和密码等）等信息；(3)FlexDB主节点，完成 SQL的解析、生成和优化查询计划、把查询计
划转变成一系列的 jobs，然后交给 JobTracker 利用 hadoop的并行计算框架完成整个查询任80
- 3 -
中国科技论文在线
务。我们提供了一种类 SQL 的声明式语言，DDL 语句,比如创建表(索引)、删除表(索引)经
过 DDL 处理部件后，被解析成子 SQL 语句，然后直接在子表所在的节点上并行执行；而
DML语句，比如 LOAD 数据、SELECT查询（两者都可能会访问到 HDFS）经过 DML处
理部件后生成一系列的 jobs，接下来的工作交给 JobTracker去完成，每个 job又会分成若干
个 task，task在执行时会把中间结果存储在 HDFS中，task出错时只要重新执行或让其它的85
节点来执行，来达到执行层的容错。ChunkNode 会定期地向 FlexDB 主节点发送 HeartBeat
来报告状态，FlexDB 主节点籍此保证子表的副本数满足要求，来达到数据层的容错。
Master/Slave结构可能会出现单点故障，hadoop社区的 zookeeper正是用来解决这个问题的。
FlexDB总体结构如图 1所示。
90
图1 FlexDB系统架构
Fig. 1 System Architecture of FlexDB
2 FlexDB 关键技术
FlexDB作为一种数据仓库分析工具，要想在性能上接近并行数据库，同时具有 Hadoop95
的容错性和高扩展性，必须仔细分析两者的优势并加以利用。总体思想是把大量复杂的操作
（比如说 join）尽量让 DBMS 来完成，利用 hadoop 的并行计算框架作为通信层， hadoop
更多的是做为一种 ETL工具。同时也要提供一种类似于 SQL的声明式语言，方便用户操作
和减少学习成本。
FlexDB的元数据管理 100
利用一个数据库来存储 FlexDB的元数据，给 SQL解析、Job执行提供支持。当创建表
时，比如 CREATE TABLE student(id int, name str) COPY 3 PARTITON BY hash(id) to 2
partitions,会把表名、属性列表（名称、类型）、副本数、分块的类型、分块的依据和子表的
数目等元数据存到相关的表中，ChunkNode 节点上数据库连接的一些参数、每个子表及其
副本对应的 ChunkNode节点等元数据在 load、select操作时都会用到。 105
这些元数据都集中存储在一个数据库中，系统启动时会加载到 FlexDB的主节点的内存
中，可以提高访问速度。FlexDB目前支持的数据库有 postgresql。
SQL的实现
一种友好方便的 SQL语言对于数据仓库的分析很是重要。FlexDB 的 SQL之前是
- 4 -
中国科技论文在线
用传统的词法语法工具 Lex/Yacc[11]实现的，生成的 C++代码和 JAVA用 JNI交互。后来用110
ANTLR[12]来重写这部分,可以直接生成 JAVA代码。Fackbook的 Hive的 HQL[8]也是用它
实现的。目前我们实现了CREATE/DROP TABLE(INDEX)LOAD/DELETE和SELECT 操作，
并允许用户自定义函数。后期会进一步进行 SQL的优化。
FlexDB主节点
SQL语句的解析和执行都需要查询或更新 Catalog。CREATE/DROP/DELETE语句会转115
换成一系列子语句，交由子表所在的节点数据库并行操作即可。FlexDB可以从 HDFS或本
地 LOAD数据到数据库表中，我们自己定义的Mapper来把文本文件中一条记录转换成对应
的属性值，再根据表的分割方式来决定此记录属于哪个子表， Reducer 完成记录的插入，
多个子表的 LOAD由子表所在的数据库节点并行完成。现在大部分数据库都支持 COPY操
作，用 COPY批量操作比单条记录 INSERT性能要高很多。 SELECT语句包括自定义函数、120
聚集函数(count、sum等)、GROUP BY、ORDER BY和 JOIN操作，目前 JOIN操作只能完
成属性值之间的等值连接。SELECT语句最为麻烦，需要根据 ANTLR生成的语法树转换为
查询树、生成查询计划、优化查询计划和生成 jobs 执行。查询计划的优化包括：把谓词过
滤放在查询树的叶子节点，在扫描表的操作中进行过滤，另外多个表 join时要考虑不同方案
的耗费，比如记录数、可能占用的内存数等因素。这里用动态规划的思想保证让整个查询计125
划的耗费最小。SELECT的操作会存储在 HDFS中。
3 实现结果与分析
实验环境：有一块百兆网卡连接的 4台机器，每台机器硬件环境为 2×的 Intel
Xeon CPU，1GB 的物理内存，160GB 的 IDE 磁盘，运行在内核为 的 CentOS
上，配置有 -openjdk和 。 130
实验所用的数据和基准测试都参照 Star Schema Benchmark(SSB)[13],另外还安装了
hadoopDB用来比较两者的性能。每个实验操作运行三次取平均值。
(1) LOAD 数据：hadoopDB 的 load 需要利用一些脚本来手动完成子表的分割和
数据的导入，而 flexDB 可以自动的完成这些操作。SSB 中最重要的表是 lineorder，我们使
用 Scale Factor（SF）=1生成了 6,001,215条记录，分成三个子表，load所需时间为 171s。 135
(2) SELECT查询：主要使用了 SSB 中的几个查询标准，主要是多个表的 join操
作，使用了 SSB 的 ,, 前三个查询语句。三条语句查询分别花费的时间为：
,,。FlexDB的
优化器使用动态规划来计算不同 join 顺序的花费，谓词过滤放在查询树的底端，使用 hash
join时要考虑读写磁盘的耗费，尽可能让 join的两个表在一个节点的数据库中完成操作等。140
HadoopDB的 join本实验中没有成功，[2]中说明了原因。
(3) 容错性：flexDB 的中间结果可以存储在 HDFS 或临时表中，而一个查询任务
是有几个 job来完成的，即使某个 job失败了，但借助与 hadoop MapReduce的并行框架就
可以重新执行失败的 job，避免了并行数据库中一个子任务的失败导致整个查询要重头开始。
我们根据 hadoop提供的命令手动 kill掉某个 job来模拟此种情况。Kill掉一个 job将导致查145
询时间增加 20%-30%。
由实验可以得出，flexDB 能够完成类似并行数据库的数据分析，在大数量节点并行计
算的情况下，在性能和容错性之间达到了某种平衡，后期还要进一步研究以企让 flexDB 达
- 5 -
中国科技论文在线
到更好的性能。还要优化 SQL来提供更好的交互性，增强用户体验。
4 结论 150
本文设计并实现了基于 Hadoop和 DBMS的一种混合并行数据库，通过把并行数据库的
一些中间操作让容错性比较好的 hadoop来模拟，而把一些 join等复杂操作交给 DBMS来完
成，hadoop作为一种优秀的并行计算框架可以很好地完成这个任务。目前 flexDB还处于一
个初级阶段，在下一步的工作中还要进一步优化 flexDB的引擎，以企生成更好的查询计划
来缩小和并行数据库的性能差距。 155
[参考文献] (References)
[1] EMC Corporation. 2011 IDC Digital Universe
Study[EB/OL]
[2] Azza A, Kamil B-P,Daniel et al. HadoopDB:An Architectural Hybrid of MapReduce and DBMS 160
Technologies for Analytical Workloads[C]//VLDB '09, August 24-28,Lyon, France, ACM 2009
[3] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters[C]//Proc. of the 6th
Symposium on Operating Systems Design and Implementation. San Francisco, USA: [s. n.],2004.
[4] Sanjay G, Howard G, Shun-Tak L The Google File System[c]// SOSP'03, October 19-22, Bolton Landing,
New York, 2003 165
[5] Apache Hadoop Org.. Hadoop[EB/OL].. .
[6] David J. DeWitt and Michael Stonebraker MapReduce: A major step backwards[EB/OL]
[7] Michael S, Daniel A, David MapReduce and Parallel DBMSs: Friends or Foes? [EB/OL]
http://database . 170
[8] Apache Hadoop Org.. Hive[EB/OL] http://hive.
[9] EMC [EB/OL] http://www.
[10] Mingyuan An, Yang Wang Weiping Wang, Integrating DBMSs as a Read-Only Execution Layer into
Hadoop [C]//The 11th International Conference on Parallel and Distributed Computing, Applications and
Technologies IEEE 2010 175
[11] Lex/yacc [EB/OL].
[12] ANTLR [EB/OL].
[13] Pat O N, Betty O,Xue D C Star Schema Benchmark
[EB/OL]
180
