软件学报  2014, Vol. Issue (4): 731-752   PDF    
大数据分析的分布式MOLAP技术
宋杰1, 郭朝鹏1, 王智1, 张一川1, 于戈2, Jean-Marc PIERSON3    
1 东北大学 软件学院, 辽宁 沈阳 110819;
2 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
3 Laboratoire IRIT, Université Paul Sabatier, Toulouse F-31062, France
摘要:大数据的规模效应给数据存储、管理以及数据分析带来了极大的挑战,学界和业界广泛采用分布式文件系统和MapReduce编程模型来应对这一挑战.提出了大数据环境中一种基于Hadoop分布式文件系统(HDFS)和MapReduce编程模型的分布式MOLAP技术,称为DOLAP(distributed OLAP).DOLAP采用一种特殊的多维模型完成维和度量的映射;采用维编码和遍历算法实现维层次上的上卷下钻操作;采用数据分块和线性化算法将维和度量保存在分布式文件系统中;采用数据块选择算法优化OLAP的性能;采用MapReduce编程模型实现OLAP操作.描述了DOLAP在科学数据分析的应用案例,并与主流的非关系数据库系统进行性能对比.实验结果表明,尽管数据装载性能略显不足,但DOLAP的性能要优于基于HBase,Hive,HadoopDB,OLAP4Cloud等主流非关系数据库系统实现的OLAP性能.
关键词大数据     多维数据模型     OLAP     MapReduce    
Distributed MOLAP Technique for Big Data Analysis
SONG Jie1, GUO Chao-Peng1, WANG Zhi1, ZHANG Yi-Chuan1, YU Ge2, Jean-Marc PIERSON3    
1 Software College, Northeastern University, Shenyang 110819, China;
2 School of Information and Engineering, Northeastern University, Shenyang 110819, China;
3 Laboratoire IRIT, Université Paul Sabatier, Toulouse F-31062, France
Corresponding author: SONG Jie, E-mail: songjie@mail.neu.edu.cn, http://faculty.neu.edu.cn/songjie/
Abstract: To address the new challenges that big data has brought on data storage, management and analysis, distributed file systems and MapReduce programming model have been widely adopted in both industry and academia. This paper proposes a distributed MOLAP technique, named DOLAP (distributed OLAP), based on Hadoop distributed file system (HDFS) and MapReduce program model. DOLAP adopts the specified multidimensional model to map the dimensions and the measures. It comprises the dimension coding and traverse algorithm to achieve the roll up operation on dimension hierarchy, the partition and linearization algorithm to store dimensions and measures, the chunk selection strategy to optimize OLAP performance, and MapReduce to execute OLAP. In addition, the paper describes the application case of the scientific data analysis and compares DOLAP performance with other dominate non-relational data management systems. Experimental results show that huge dominance in OLAP performance of the DOLAP technique over an acceptable performance lose in data loading.
Key words: big data     multi-dimensional data model     OLAP     MapReduce    

近年来,随着大数据时代的到来以及互联网、传感器和科学数据分析等领域的快速发展,数据量近乎每年在成倍地增长[1].无论是在科学领域(生物学、地理学、天文学、气象学等),还是在工程领域(网络数据分析、市场数据分析等),都面临着数据雪崩的问题[2],大数据的规模效应给数据存储、管理以及数据分析带来了极大的挑战[3, 4].OLAP(on-line analytical processing)联机分析处理是共享多维信息的、针对特定问题的联机数据访问和分析的快速软件技术[5],OLAP按照其实现方式不同,可以分为3种类型,分别是ROLAP,MOLAP和HOLAP[6].其中,ROLAP采用关系表存储维信息和事实数据;MOLAP则采用多维数据结构存储维信息和事实数据;而HOLAP称其为混合OLAP,该方法结合了ROLAP和MOLAP技术[7].无论是何种OLAP,都需要存储和计算平台的支持,尤其是在大数据环境下.

为了解决大数据所带来的诸多挑战,学界和业界涌现出许多新技术,如分布式文件系统[8]、NoSQL数据库系统[9]、MapReduce编程模型[10]以及相关的优化方法,这些技术都被广泛地运用到大数据分析中.MapReduce编程模型是广为人知的可扩展、灵活且高效的分布式编程框架.Hadoop是MapReduce的开源实现,可对海量数据进行可靠、高效、可扩展的并行处理.基于Hadoop[11]的实现,涌现出大量的分布式数据管理系统,并广泛地运用在大数据管理和分析领域,如Hive[12],HBase[13],HadoopDB[14]等.一方面,尽管这些数据管理系统均可支持OALP,但其性能往往不尽如人意.例如,基于HBase的OLAP引擎OLAP4cloud[15]框架属于一种基于云计算技术的OLAP实现,它采用列存储数据存储结构以及索引等技术优化OLAP的性能.但是,OLAP4cloud并不提供维信息的管理,也无法直接支持上卷下钻操作,因此,OLAP4cloud仅限于支持对度量数据的查询和简单的聚集操作.另一方面,这些数据库系统均未针对OLAP进行特殊的优化,我们之前的研究[16]表明,连接操作在ROLAP中是非常频繁且相当耗时的操作,当数据量或维数量增加时,连接操作会成为OLAP的瓶颈.MOLAP可以避免数据集的连接操作,因此在性能方面有着天生的优势,但MOLAP需要集中式存储多维数据模型,且耗费大量空间,如何基于分布式文件系统和MapReduce模型实现MOLAP模型则是一个难题.据我们所知,在大数据分析领域,尚未有关于分布式MOLAP技术的权威报道,也鲜有成熟的基于MapReduce的MOLAP系统,该问题亟待解决.

本文研究大数据环境下基于MapReduce的分布式MOLAP技术,称为DOLAP(distributed OLAP).DOLAP采用一种特殊的多维模型完成维和度量的映射;采用维编码和遍历算法实现维层次上的上卷下钻操作;采用数据分块和线性化算法将维和度量保存在分布式文件系统中;采用数据块选择算法优化OLAP的性能;采用MapReduce编程模型实现OLAP操作.在DOLAP技术的基础上,我们基于Hadoop实现了一个OLAP系统HaoLap (hadoop OLAP),设计了一系列测试用例,将HaoLap与Hive,HadoopDB,HBase和oalp4cloud等进行性能测试和比较.实验结果表明,HaoLap的数据装载性能不具优势,但其OLAP性能优势明显,且性能与原始数据集规模以及查询复杂程度无关,尤其适合高维数据立方的OLAP操作.HaoLap仅依赖分布式文件系统存储数据,不引入额外的存储代价,数据立方通过计算获得,对于立方的每个维,仅存储维级别名称和每个维级别中维值的个数,不同于传统MOLAP系统耗费大量空间存储数据立方.由于篇幅原因,本文略去了HaoLap系统的实现细节.

本文第1节介绍相关工作.第2节介绍维编码及事实存储,其中包括简化的多维数据模型的定义、维编码和维遍历算法、数据立方分块、存储以及寻址算法等,并给出数据立方建模和存储的应用案例OceanCube.第3节重点介绍基于MapReduce的OLAP算法.第4节首先采用真实的科学数据集OceanCube,通过3组实验分别测试和比较DOLAP在数值型数据上的数据装载、切块操作、上卷操作和存储代价,随后采用SSB基准测试比较DOLAP在枚举型数据上的OLAP性能,并总结实验结论.第5节总结全文并提出进一步工作.

1 相关工作

目前已有很多关于大数据或云计算环境下的OLAP优化方法研究,本节主要从以下两个方面介绍相关工作:大数据环境中的OLAP优化技术和分布式的OLAP系统.大数据环境中,常用的OLAP优化方法有以下两种:利用预计算和浓缩数据立方的结果优化OLAP性能[17]和通过优化存储结构和算法来优化OLAP性能,其中,后者与本文最为相关.文献[18]提出了OLAP查询中的SPAJG-OLAP子集,在存储、查询、数据分布、网络传输和分布式缓存等方面研究海量数据大规模并行处理框架的优化策略和实现技术,实验证明,效果良好.该研究基于并行数据库技术优化ROLAP性能,通过对OLAP查询以及存储的优化达到加速OLAP的目的.文献[19]指出:在Web应用中,需要同时提供对海量数据的事务操作和决策分析,并介绍一种能够同时有效支持OLTP和OLAP的数据存储系统.通过建立索引、数据分块、预计算等方式,有效地提高了OLAP的性能.本文同样是通过优化查询以及数据存储来提高OLAP的执行效率,但不同的是,本文研究的优化方案基于MapReduce.同时,针对MapReduce连接操作的低效性,本文研究提出了DOLAP技术,大大提高了OLAP的执行效率.

文献[20]指出,传统的OLAP分析无法很好地适用于大数据分析.该文根据短消息数据的特点,设计了一种基于Hadoop的有效存储格式,并使用MapReduce实现了OLAP操作,更好地适应了SMS(short message service)业务中对短消息进行数据分析的需求.该文利用了特殊的数据结构来优化OLAP操作的性能,但该研究的适用面较窄.文献[21]基于MapReduce,通过数据的筛选策略减少了数据在网络中不必要的传输,从而优化了复杂云环境中的OLAP性能.该研究重点关注云环境的复杂性以及网络延迟等因素对OLAP性能的影响,是大数据环境下ROLAP的一种优化策略,其优化方法与本文研究存在本质区别.

就分布式的OLAP系统而言,一些基于Hadoop的数据库系统,例如Hive,HadoopDB,HBase,MongoDB, OLAP4cloud等都支持OLAP分析.Hive是一个基于Hadoop的数据仓库系统,为数据分析人员提供了类SQL接口,支持大数据分析.HadoopDB将MapReduce和关系数据库技术结合起来,以管理和分析大数据;HBase则是面向列存储的开源数据库系统.这些数据库将海量数据存储在分布式文件系统中,通过MapReduce完成上卷下钻等操作,属于分布式的ROLAP技术,其中,维表和事实表的连接运算是一个性能瓶颈.OLAP4cloud是基于HBase的OLAP引擎,它将维表直接压缩到事实表中,并提供一种特殊的索引来加快寻址,采用数据立方预计算方法,属于一种近似MOLAP实现.与分布式的MOLAP技术最为相关的是文献[22],该文尝试使用多维数组存储海量数据,并将建立的存储模型运用到了基于Hadoop的数据分析工具Pig[23]中,且通过实验证明了该存储模型在占用大量存储的同时提高了OLAP分析性能.为减少存储开销,本文使用多维数组存储维信息而非事实数据;除此之外,本文还提出了维相关的遍历算法以及数据筛选算法.

综上所述,尽管学界注意到大数据对OLAP分析提出的挑战,且已有部分研究分别从模型、存储、算法和预计算角度对传统OLAP进行了优化,但尚未有权威的大数据环境下分布式的MOLAP技术的研究报告.与此同时,Hadoop也逐渐成为开源领域大数据分析的主流技术,但是基于Hadoop的分布式的MOLAP系统研究仍然尚未成熟.

2 维编码及事实存储 2.1 数据模型

OLAP采用的多维数据模型包括维和事实两部分,其关键操作是找到维和事实的映射关系.ROLAP采用关系数据库以及星形模式或雪花模式,将维信息和事实数据分别存储于关系数据库表中,并使用外键完成维信息和事实数据的映射.但是ROLAP涉及到大量的连接操作,性能较低.MOLAP采用多维数组存储维和事实,通过对维进行编码和对事实数据直接寻址的方式获得其映射关系,从而避免了连接操作的开销.但MOLAP需要以一种集中的方式维护维和事实的映射,由于一个维可以包含多个层次,每个层次可以包含若干个级别,维和事实又是一对多的关系,所以维模型具有复杂性.为了避免额外的存储和维护代价,DOLAP首先对维进行了简化,以适应分布式环境,同时降低OLAP算法的复杂程度.本节重新定义维和事实数据,同时也定义了其他相关术语.

定义1(维(dimension)). 在多维数据模型中,维将所有的数据项分类至一个无重叠的数据结构中,并且提供数据项的筛选、组织和标识方法.本文研究对维的定义进行了简化,简化后的维基于多维模型的维定义,并遵循以下3个约束:设d为维,则,

1) d有且仅有1个维层次;

2) dm个维级别所组成的集合,记为{l1,l2,...,lm}.设li(iÎ[1,m])为任意一个维级别,则li仅包含1个维属性,且包含ni个维值;

3) 将d视作由各级别的维属性取值所组成的树形结构(维值树),则同一级别的兄弟节点包含有相同数目的子节点.

基于上述假设,维d由以下两部分组成:

1) 维模式(dimension schema)包含:① m个维级别的有限集L(d),且这些维级别仅包含一个概念层次(concept hierarchy);② 在集合L(d)上存在一个全序关系≻d,上卷(roll-up)操作是指沿着概念层次向上攀升.如果有关系ljdli(i,jÎ[1,m],i<j)成立,那么认为lj可以上卷到li;

2) 维实例(dimension instance)包含:① 函数md可以获得维级别的维属性取值集合,对于li而言,仅包含1个维属性,该维属性包含ni个取值,|md(li)|=ni;② 上卷函数对每个关系ljdli: ∀v jÎmd(lj),∃viÎmd(li)满足且∀v iÎmd(li),∃vjÎmd(lj)满足③ ∀

为简便起见,如果不加说明,本文中“维”均指符合定义1的维.

定义2(度量(measure)). 度量u是一个独立变量,它们参照每个维的某一维值,并作为OLAP的分析对象.度量的粒度是度量参照的维值所在的维级别,最细粒度的度量参照每一维d中的最低维级别的某一维值.设u参照维集合D={d1,d2,…,dn},∀dÎD,即集合D可以确定度量u,记作D®u,则满足:D®uÛ∃!vÎmd()Ùv®u(dm个维级别),其中,v®u是指维值v可以确定度量u.

定义3(单元格(cell)). 在逻辑视图中,单元格是由若干不同的度量组成的原子单元,这些度量都参照相同的维值.对于维集合D而言,单元格可以表示为度量的集合,记作{u|D®u}.

定义4(数据立方(cube)). 根据定义1~定义3,数据立方是OLAP中的多维数据结构,简称立方.数据立方的维符合定义1,且由若干单元格组成.

定义5(块(chunk)). 块是数据立方的逻辑划分,一个数据立方可以根据维的取值分成多个块.

图 1是由3个维(x,y,z)所组成的立方,图中较小的方格代表单元格,较大的方格代表块.在实际操作中,块中有可能包含一些空的单元格,即,该单元格中没有任何度量.在实际应用中,为了减少立方占用物理空间的大小,若单元格内没有任何度量,则在该块文件中不保存该单元格的记录.

Fig. 1 Example of data cube图 1 数据立方示例
2.2 维算法

在OLAP操作中,对维的操作是非常频繁的.维的编码和遍历算法是MOLAP的关键技术,本节将对DOLAP技术中维的编码和遍历算法进行阐述.

2.2.1 维编码算法

维编码方法主要包括二进制编码和十进制编码.二进制编码也称作位图编码,通过编码的拼接可以包含维的级别信息,通过编码的移位实现维的遍历,但是二进制编码会造成很大程度上的稀疏[24];十进制编码是对每个维级别的维值依次使用十进制数编码,但是无法直接获得编码和维值的映射.在大数据环境中,为了避免稀疏, DOLAP采用十进制的编码方法,同时提出了维的遍历算法来计算编码和维值间的映射关系.设l是维d中的某个维级别,对∀xÎ[1,|md(l)|],vxÎmd(l),vx的编码为code(vx),则code(vx)=x-1.该编码方法如算法1所示.

算法1. 维编码算法.

Input: Dimension d: A target dimension;

Function: DimensionCoding.

1. FOR i=1 TO |L(d)|;

2.         FOR j=0 TO |md(li)|-1;

3.                 Dimension value of Îmd(li)

4.                 

5.         END FOR

6. END FOR

在实际应用环境,绝大部分维是数值型的,例如高度、经度、价格、流水号等.数值型的维可以按照其值域进行划分,不同的划分步长可以确定不同的维级别,因此,数值型的维可以很容易地满足定义1的约束条件.但是还存在一部分非数值型的枚举型的维,例如日期、城市、部门等.为使枚举型维符合定义1,可以使用一些空值填补维值树,使同一级别的兄弟节点包含有相同数目的子节点.图 2展示了日期维的编码结果.在“月”级别上,每个月的天数是不同的,为了满足定义1,设每个月有31天,所以在图 2中的2月插入了“29日”、“30日”和“31日”这3个空值.

Fig. 2 Example of date dimension coding图 2 日期维编码示例

对于实际应用中更为复杂的维,采取化简、划分维层次的方法使其形成维值树,使用空值填补维值树的方法使其满足定义1的约束条件.例如,针对TCP-H[25]数据集中的维模式,处理方法如下:① 通过取舍和合并的方法,化简TCP-H的雪花模式为星型模式,其结果为SSB[26]数据集中的维模式;② 针对SUPPLIER维表,使用区域属性(Nation,Region,City)作为划分维层次的依据,得到维层次Nation-Region-City;③ 在维Nation-Region-City的维值树中添加空值,使其满足定义1的约束.

2.2.2 维遍历算法

DOLAP的维可以看作是一棵特殊的单根树,记作Td,其中,ALLTd的根节点,记为第0级别.每个维级别中的维值可以看作维值树中的节点,同时,每一个兄弟节点都有相同数目的子节点,如图 2所示.OLAP操作中涉及到大量对维值树Td的遍历操作.例如,沿着Td攀升(即上卷)或沿着Td下降(即下钻).设有关系∀iÎ[1,m-1],li+1dli, viÎmd(li),vi+1Îmd(li+1),那么vivi+1之间的上卷关系是OLAP中的关键操作.编码机制将能够表 征这种上卷关系,我们可以通过编码运算实现Td中的上卷操作.本节首先引入维级别规模的概念,并通过对节点vivi+1的编码的运算获得关系.至于从vivi+1的下钻操作,可以等同地视作从vi+1vi的上卷操作,此处不再赘述.

定义6(维级别规模(dimension level size)). 设d是一个维,由m个维级别组成,第i个维级别记作li(iÎ[1,m-1]),维级别规模记作|li|,则|li+1|=|{vi+1|∀viÎmd(li),}|,其中,{vi+1|∀viÎmd(li),}是指维级别中符合条件的维属性取值的集合,|{vi+1|∀viÎmd(li),}|是指该集合的大小.

根据定义6,维级别规模是指在维值树中上层维级别中任意节点子节点的个数.

áv1,v2,…,vi,vi+1,…,vmñTd中自上而下的一条分析路径,vi在其兄弟节点间的位置记为order(vi)(兄弟节点拥有共同的父节点,且其位置计数从0开始,从左至右),则编码与位置的关系可表述为公式(1).对于图 2中的路径á19901,22,23ñ:code(23)=32,order(23)=1;code(22)=1,order(22)=1;code(19901)=0,order(19901)=0.

code(vi)=(…((0+order(v1)x|l2|+order(v2))x|l3|+order(v3))…)x|li|+order(vi) (1)

同理,当给出code(vi)时,order(v1)到order(vi)的值可通过公式(2)计算得到:

(2)

联合公式(1)和公式(2),对于给定的code(vi),可以计算出其对应的所有父节点的编码,即code(vi-1)到code(v1)的值,从而可以进行上卷操作.例如图 2中,在“天”维级别中,已知code(23)=32,其路径为á19901,22,23ñ,根据公式(2),已知code(23)=32,|l3|=31,|l2|=12,|l1|=50,则order(22)=1,order(19901)=0;再根据公式(1),可以计算得到code(22)=1, code(19901)=0.

2.3 数据立方分块

将数据立方划分为块的目的是在OLAP过程中对数据进行筛选,从而优化OLAP的性能.同时,块也可以作为数据立方的存储单元.本节首先定义维、数据立方以及块的规模和容量,而后讨论数据立方的分块策略.

定义7(维规模(dimension size)). 维规模是指最底层维级别的维值个数.设d是一个维,包含m个维级别,记作l1,l2,...,lm.记|d|为维d的规模,则.

定义8(立方规模(cube size)和立方容量(cube capacity)). 立方规模是由组成立方的维的规模构成的元组,立方容量则是立方内包含的单元格的个数.设立方由n维组成,其中第i个维记作di(iÎ[1,n]).立方规模为|cube|=á|d1|,|d2|,…,|dn|ñ,立方容量为.

定义9(块规模(chunk size)和块容量(chunk capacity)). 块规模是一个由该块包含的每个维最底层维级别上维值的个数构成的元组,块容量是块包含的单元格的个数.设块由n维组成,其中第i个维记作di(iÎ[1,n]),且di被划分为pi份.记块的规模为|chunk|,则|chunk|=ál1,l2,…,lnñ,其中,,块容量为

DOLAP的性能与|chunk|n的取值密切相关,|chunk|n取值越小,并行性越好,实际参与运算的单元格数量越少,但此时调度代价变高.如何折中地确定|chunk|n的取值,将变得十分关键.借鉴文献[27],本文提出了一种通过查询条件及其出现的概率来确定块容量的方法,但我们难以穷举所有查询条件及其出现概率,所以该方法采用随机抽样,抽取一些查询条件及其出现概率.除此之外,|chunk|n的取值还应该考虑算法的运行环境.DOLAP利用MapReduce来实现,所以|chunk|n的取值还需考虑MapReduce的一些特性,例如文件寻址时间、数据处理时间等.表 1列出了相关符号的定义,其中,li为变量,TNa是计算结果,其他为已知常量.

Table 1 Definition of notations 1 相关符号定义

平均一个查询命中的块个数Na可以通过每个查询条件出现的概率得到,如公式(3)所示:

(3)

考虑MapReduce相关的一些影响因素之后,可以得到一个OLAP操作消耗的平均时间,如公式(4)所示:

(4)

通过公式(4),可以计算出T取最小值时的li,也就得到了块规模.每个维上的块规模均可通过上述方法计算得到,从而可以得到块容量的最佳值.由公式(4)可以看出,‘⌈ ⌉’操作会导致块容量之和大于立方容量,所以块中会存在空的单元格.

2.4 数据存储

传统MOLAP数据立方的存储代价很大,尤其是在高维数据立方或每个维包含大量维值的情况下.事实上,传统MOLAP依赖访问内存中的多维数组来加快OLAP操作,这种方式在大数据环境中显然难以实现.DOLAP的“多维数组”是通过计算得到,无需存储,因此数据立方的存储代价非常小.DOLAP对维进行简化,可以保证在同一级别上维的编码是连续的十进制数,同时,每一个兄弟节点都有相同个数的子节点,所以维信息仅需存储每个维级别规模,极大地降低了维的存储代价.设维dm个维级别组成,记作{li|iÎ[1,m]},则d的物理存储可以表示为该维级别和维级别规模的序偶所组成的集合{áli,|li|ñ|iÎ[1,m]},其中,li表示该维级别的名称.DOLAP实现系统可以使用XML文件存储维信息,并保存于集群主节点.

逻辑上,“立方和其单元格”或是“立方和其块”的数据结构均可以类比为“多维数组和其元素”的数据结构.物理上,块是立方的存储单元,将块内的单元格线性化(linearization)后,块可以作为独立的文件进行存储.为了便于寻址,块和单元格都需要支持线性化和反线性化(reverse-linearization)运算,且该运算与多维数组的线性化和反线性化运算是一致的.设存在一个n维数组,其维规模记作áA1,A2,…,Anñ,多维数组中的元素X在多维空间中的坐标记作(X1,X2,…,Xn),其线性化后的坐标记作index(X),则其线性化方法如公式(5)所示,反线性化方法如公式(6)所示:

index(X)=(…((XnxAn-1+Xn-1)xAn-2+…+X3)xA2+X2)xA1+X1  (5)

(6)

对于单元格而言,构成该立方的维记作d1,d2,...,dn.设x是立方中的一个单元格,x在维di上对应的维值为vi, code(vi)=xi,则x的坐标为(x1,x2,…,xn),公式(5)将(X1,X2,…,Xn)替换为(x1,x2,…,xn),áA1,A2,…,Anñ替换为á|d1|, |d2|,…,|dn|ñ,公式(6)亦然,可得单元格的线性化和反线性化算法.在存储实现中,单元格存储为Hadoop HDFS[28]中MapFile[29]文件的一条记录,该记录包括该单元格线性化后的坐标及其包含的度量.

对于块而言,设y是一个块,它是立方的一个划分,|y|=ál1,l2,…,lnñ,y的坐标为(y1,y2,…,yn),y内任意一个单元格的坐标为(x1,x2,…,xn),则,公式(5)中,将(X1,X2,…,Xn)替换为(y1,y2,…,yn),áA1,A2,,Anñ替换为ál1,l2,…, lnñ,公式(6)亦然,可得单元格的线性化和反线性化算法.在存储实现中,一个块存储为Hadoop HDFS中一个MapFile文件,线性化后的块坐标作为块文件的文件名,以便进行块文件的寻址;块文件内每一条记录存储了该块内的一个单元格,块文件则存储于分布式文件系统Hadoop HDFS中.在块文件中按Key-Values对的形式存储所有的单元格数据,其中,Values对应事实数据,Key则是单元格(cell)坐标按公式(5)线性化后的索引值.该索引值是一个十进制正整数,在大数据环境中,数据立方规模会非常大,以Java语言为例,索引值会超出长整型(long)的最大取值范围264,因此,我们采用字符串表示的数字数据.此外,若采用Key-Values方式存储,Key的存储开销可能会比对应的Values存储开销大很多,这样就浪费了大量存储.因此对于一个块文件,仅记录一个最小的单元格索引值,而Key存储的则是相对于该值的偏移量.

2.5 应用案例

本节描述一个DOLAP的真实应用案例OceanCube.案例的数据模式来源于海洋科学中通过CTD[30]收集的海水温度数据,数据集来源于真实的国家海洋数据[30],该数据集中的数据项均为连续型数值数据.OceanCube数据集描述如下:3个维分别为时间维、区域维和深度维,对应Time,AreaDepth.Time共有5个级别:Year,Season, Month,Day,Slot.其中,Slot是指一天的3个时间段,其维值分别是“上午”、“下午”和“晚上”.Area共有7个维级别:1°,1/2°,1/4°,1/8°,1/16°,1/32°和1/64°.其中,1°是指由1°经度和1°纬度所组成的方形区域,地球表面可以划分为360x180个1°方区.Depth共有3个维级别:100m,50m,10m,其中,100m指的是“海洋的深度以100m的间隔进行划分”,若海水有1 000m深,则可以划分为10层,对应10个维值.见表 2.

Table 2 表 2

我们设每个月有31天,初始化数据立方为OceanCube,其中包括10年、5°、1 000m深度的海洋温度数据,维信息如下所示:

(1) Time={áYear,10ñ,áSeason,4ñ,áMonth,3ñ,áDay,31ñ,áSlot,3ñ};

(2) Area={á1°,5ñ,á1/2°,2ñ,á1/4°,2ñ,á1/8°,2ñ,á1/16°,2ñ,á1/32°,2ñ,á1/64°,2ñ};

(3) Depth={á100m,10ñ,á50m,2ñ,á10m,5ñ}.

因此,OceanCube一共产生1 550个块文件,每个块中将包含230 400个单元格,其中,每个单元仅有1个度量,即海水温度.

3OLAP算法

本节在数据模型的基础上介绍OLAP算法及其MapReduce实现,OLAP包括上卷、下钻、切片、切块以及旋转操作.切片、切块可以视作范围查询;上卷、下钻可以视作范围查询和数据聚集;旋转可以视作创建立方的不同视图.一个OLAP操作的输入可以抽象为四元组表示,记作áTarget,Range,Aggregation,Resultñ,其中,Target代表待分析的数据立方(元数据);Range代表立方中待分析数据的数据范围;Aggregation指的是聚集函数,例如mean(×),sum(×),maximum(×)以及minimum(×);Result则代表结果数据立方(元数据).当Target的最高维级别低于(高于)Result的最高维级别时,表示完成上卷(下钻)操作.OLAP操作的输入和输出均为数据立方,ResultTarget经过查询和聚集后新生成的立方.显然,ResultTarget的维规模可能有所不同.

我们通常通过维来查询度量,所以,OLAP操作的查询条件同样由维组成.Range是一个多维二元组,指出了Target中待分析数据的数据范围.设组成立方Target的维集合为{d1,d2,…,dn},对于维di,序偶áai,biñ(ai<bi)代表在该维上所需数据的取值范围,则Range={áai,biñ|iÎ[1,n]}.

为了便于表述,Range记为如á{a1,a2,…,an},{b1,b2,…,bn}ñ的形式.

3.1 块选择算法

本文提出的OLAP操作包括4种基本算法:块选择、数据查询、改变维级别、数据聚集,很多现有研究都讨论了如何在MapReduce中实现查询和聚集操作,改变维级别参见第2.2.2节的维遍历算法,因此本节仅针对块选择进行讨论.块选择是指“确定包含满足查询条件的数据的所有块”的过程.利用块选择算法减少OLAP操作输入块的个数,缩小查询空间,可以极大地提高OLAP性能.设一个OLAP操作中给定Rangeá{a1,a2,…,an}, {b1,b2,…,bn}ñ,满足Range的块的坐标为(c1,c2,…,cn),块规模为ál1,l2,…,lnñ,则∀iÎ[1,n],ci满足公式(7):

(7)

满足公式(7)的块会作为OLAP操作的输入,而非输入全部数据块,从而缩小了OLAP操作的查询空间;而且块选择算法无需额外的查询,仅通过编码计算,算法代价很小.图 3显示了块选择算法的示例.

Fig. 3 Example of chunk selection图 3 块选择算法示例

设某OLAP操作中给定Rangeá{x1,y1,z1},{x2,y2,z2}ñ.图 3中,F的坐标为(x1,y1,z1),D的坐标为(x2,y2,z2),则待查询的数据范围是ABCD-EFGH.通过公式(7)可得实际查询输入块的范围是A¢B¢C¢D¢-E¢F¢G¢H¢.对比整个立方,通过块选择可以筛选掉一大部分与查询无关的数据,但是A¢B¢C¢D¢-E¢F¢G¢H¢的边缘块中仍有少部分无关数据,这部分数据将在OLAP操作的查询阶段进行过滤.

3.2 基于MapReduce的算法实现

以上卷操作为例,基于MapReduce的OLAP算法由4部分组成:InputFormatter,Mapper,ReducerOutputFormatter,分别对应上卷操作中的查询、改变维级别、聚集和输出结果集的4个步骤.上卷操作执行流程如图 4所示.

Fig. 4 Process of MapReduce based OLAP algorithm 图 4 基于MapReduce的OLAP算法执行流程

在MapReduce任务执行前,OLAP查询四元组将会被终端提交,系统验证四元组中信息的有效性,防止任务因查询定义无效而失败.随后利用块选择算法获取输入块列表,称为chunk-file-list.InputFormatter扫描chunk- file-list中块包含的单元格,将线性化的单元格坐标反线性化,按查询条件对数据进行过滤.如果某一单元格符合查询条件,则该单元格的数据将会传递给Mapper进行后续处理;若不符合查询条件,该单元格将会被抛弃.

MapperReducer的输入和输出都是由用户来定义格式的键值对形式,其中,Mapper函数输入为 ,输出为;Reducer函数的输入为,输出为.其中,能够隐式地转换为是保存的集合.上卷操作中,是单元格的线性化坐标,则是由InputFormatter所读取的单元格内的度量.是更新维级别后单元格的线性化坐标,则与相同.相同,是具有相同的度量的集合.相同,的聚集值.

Mapper首先将反线性化,根据客户端给出的Result信息,完成维层次的攀升,对单元格坐标进行更新. Mapper将更新后的坐标线性化,作为输出.对于单元格内的度量不进行聚合运算,所以在Mapper输出过程中,.Reducer根据客户端指定的Aggregation内所有的值进行聚集运算,并将最终的聚集值作为输出.在这个过程中,保持不变,所以最终输出时,.Mapper输出数据后,由于Partition的作用,属于同一个块的单元格总会被分配到同一Reducer中进行分组处理,所以,Reducer的输出是每一个块文件内的所有单元格.

OutputFormatter接收Reducer的输出、计算块的坐标、并对坐标进行线性化,最终生成物理存储文件保存到分布式文件系统中,文件名是该块的线性化坐标.当所有的块文件生成后,将新产生的数据立方信息写入到Result中并返回给客户端.

4 实验分析

为了验证本文所提出的DOLAP在大数据环境中的高效性,我们实现了一个基于Hadoop的OLAP系统HaoLap(hadoop based OLAP).由于篇幅原因,本文略去HaoLap的实现细节.

本节比较了HaoLap,Hive,HadoopDB,HBase和Olap4Cloud的OLAP性能,HaoLap采用本文提出的DOLAP, Hive,HadoopDB和HBase采用基于星形模式的ROLAP,Olap4Cloud采用的则是MOLAP.除此之外,还对各个系统的数据装载过程和存储代价进行了对比.

本实验运行在真实的集群环境中,该集群中共包含13台PC机,包含1个NameNode,12个DataNode.每台PC机的软、硬件配置如下:Inter Core i5 2.80GHz CPU,8GB内存,1TB硬盘,CentOS 6.3,Linux 2.6.32-279.el6.i686操作系统.

在实验的初始阶段,我们拟将业界广泛关注的开源NoSQL数据库MongoDB纳入到实验中,但是最终没有采纳,原因如下:① MongoDB是一个文档型NoSQL数据库,如果将维和事实存储于同一个文档中,将会造成该文档的结构过于复杂而难以实现OLAP操作;② MongoDB并不原生地支持连接操作,我们可以采用星形模式将维和度量分别存储于MongoDB中,同时使用一些编程技巧实现连接操作,但是无法避免MongoDB连接操作时对中间数据进行不必要的分片过程,该分片过程相当耗时,会影响到性能对比.

HaoLap设计之初是为了应用于国家海洋科学数据中连续的数值型维的区间查询和OLAP操作,如第2.5节中的应用案例所述,但同样也适用于离散的枚举型维的OLAP操作.因此,针对数值型维,本节采用真实的科学数据集,比较HaoLap和其他主流云数据库系统的性能,将涉及4组实验,分别是数据装载、切块操作、上卷操作和存储代价.每个实验都将涉及多组实验用例,并通过3个不同规模的数据集对比5个系统的性能;针对枚举型维,将采用SSB基准测试用例,比较HaoLap和其他系统的性能;最后总结实验结论.为表述简单,我们采用SQL描述实验用例,针对不同数据库系统,采用不同的方式实现这些用例,具体实现方法从略.

4.1 实验案例

本节采用第2.5节描述的案例OceanCube作为实验数据.在实验中使用了3个数据集(S1,S2,S3),为了便于表述,使用Size(Si)(1≤i≤3)表示数据集的规模,Size(Si)的单位为数据条数.本文没有采用大数据研究中常用的GB为单位是因为:HaoLap,Hive,HadoopDB和HBase的数据文件格式不同,导致文件大小差异较大.各个数据集相关参数见表 3.

Table 3 Size of OceanCube experimental set 表 3 OceanCube实验数据集大小
4.1.1 数据装载

由于HadoopDB的数据是手工载入的,所以在本实验中无法比较HadoopDB的装载性能[31].我们对HaoLap, Hive和HBase进行单线程数据装载,若使用多线程装载,会因数据间的固有联系而产生数据不一致问题.对于Olap4Cloud而言,首先按照一定的文件格式生成所有的数据,再使用MapReduce载入数据,由于数据的生成是ETL阶段,在下文中,我们仅针对MapReduce过程所耗费的时间进行对比.

图 5展示了数据装载实验的实验结果.从图 5(b)可以看出,HaoLap的装载速度较为稳定,而Hive的装载速度是4个系统中最快的.这是由于Hive装载数据时将数据直接写入HDFS,并在数据装载完成后修改其元数据实现的,而HaoLap在数据写入时还需计算每一个单元格的坐标信息.

Fig. 5 Experimental results of data loading图 5 数据装载实验结果

与HaoLap和Hive不同的是,HBase的载入速度随数据量的增大而显著降低.这是由于HBase需要额外地维护表的模式信息,如Column,ColumnFamily,Index等.Olap4Cloud的装载速度与HBase相近,但在数据量增加后并没有出现装载速度的明显降低.这是因为Olap4Cloud的实现基于HBase,但在本实验中其装载采用MapReduce并行方式,并非像HBase那样使用单线程装载.

由于Hive,HBase和Olap4Cloud都提供了相应的API进行批量数据装载,且HaoLap需要对数据进行预处理,所以HaoLap在数据装载方面并没有先天的优势,我们目前考虑的优化方法包括根据数据的特点进行并行导入和优化立方的分块及存储算法.

4.1.2 切块操作

本组实验共包含3个切块操作用例C1,C2,C3(本文对切片和切块操作不加区别),每一个操作都将在S1,S2,S3这3个数据集上分别执行,因此每个OLAP系统均执行9次实验.对于用例Cj(1≤j≤3),有j个维参与OLAP操作,即,星形模式下(维表为Time,Area,Depth,事实表为Temperature)需要j次连接操作.

为了方便表述,在Si上的用例Cj记作SiCj(1≤i≤3,1≤j≤3),其结果数据立方数据量记作ResultSize(SiCj)(1≤i≤3,1≤j≤3),其执行耗时记作Time[system](SiCj)(1≤i≤3,1≤j≤3,systemÎ{HaoLap,Hive,HadoopDB,HBase, Olap4Cloud}).由于各个用例的查询条件不同,除了S3C1和S3C2外,其他ResultSize(SiCj)约为350万条. ResultSize(S3C1)为3 500万条,ResultSize(S3C2)为700万条.

图 6用直方图(对数坐标轴)展示了本组实验结果.在同一用例下,HaoLap的切块性能最优,Hive,Olap4Cloud和HadoopDB次之,HBase的切块操作性能最差.这种情况可以归结为以下原因:

① HBase,Hive和HadoopDB采用ROLAP技术,由于ROLAP涉及大量连接操作,性能上没有优势;

② Hive和HadoopDB对连接操作进行优化,而HBase则没有.例如,Hive可以利用分布式缓存进行Map端连接,HadoopDB则利用索引加速连接操作;

③ Hive和HadoopDB分别采用HDFS和DBMS作为存储,它们与本地文件系统高度集成,增强了本地文件读写,减少了网络数据传输;而HBase则独立于分布式文件系统,缺乏数据本地读写优化,大量的网络I/O操作降低了查询性能;

④Olap4Cloud在查询时,首先对查询条件进行解析并通过查询索引的方式,精确计算参与计算的数据地址,从而保证仅针对所需数据进行处理.

Fig. 6 Execution time of dice operation (logarithmic coordinate图 6 切块操作的运行时间(对数坐标)

图 7(a)展示了HaoLap各个切块操作在不同数据集下的运行时间的变化趋势.

Fig. 7 Tendency of dice performance when data set is changed 图 7 切块性能随数据集变化趋势

可以看出:除Time[HaoLap](S3C2)运行时间稍长,Time[HaoLap](S3C1)运行时间明显增加外,Time[HaoLap](SiCj)基本上保持稳定.出现这种现象的原因是ResultSize(S3C1)的数据量为3 500万条,ResultSize(S3C2)的数据量为1 000万条,其他结果的数据量均为350万条.由此可见,HaoLap切块性能与结果集(或实际参与运算的数据集)大小相关,与原始数据集大小以及操作复杂程度(维的个数)无关.以SiC3为例:一方面,其性能与实际参与运算的数据量有关,而在HaoLap中,数据立方分块和块选择算法导致SiC3实际参与运算的数据集大小是相同的;另一方面,块选择算法是基于块文件的直接寻址而不是文件搜索算法,所以块选择算法与原始数据集大小无关.

图 7(b)~图 7(d)分别展示了Hive,HadoopDB,HBase的切块操作在不同数据集下运行时间的变化趋势.由于这些系统采用ROLAP技术,用例Cj(1≤j≤3)涉及的连接数量随着j的增大而增多,因此切块更耗时.且在不存在连接优化的情况下,表内数据量越大,连接操作越耗时.图 7(b)显示出Hive的切块性能符合ROLAP的普遍规律. Time[Hive](SiCj)随着Size(Si)以及所需连接表的数量而增加.Hive仅通过分布式缓存优化Map端连接操作,但仅适用于有限的情况.同时,Hive没有提供索引或分区等优化机制以加速连接和查询的速度,所以Hive的性能趋势符合ROLAP的普遍规律.

HadoopDB与Hive,HBase的不同之处是其底层采用关系数据库存储数据.HadoopDB将数据进行分片,建立索引并存储于DBMS中.在图 7(c)中,Time[HadoopDB](S2C3),Time[HadoopDB](S3C3)与其他用例相比变化很大,导致Time[HadoopDB](SiC1)和Time[HadoopDB](SiC2)几乎重合.根据图 7(c)以及图 6中的HadoopDB实验数据可得: Time[HadoopDB](SiC1)和Time[HadoopDB](SiC2)曲线规律符合ROLAP的一般规律.HadoopDB采用了索引优化查询,所以S1C1和S2C1,S1C2和S2C2这两组对比实验的查询时间很相近.但是,随着数据量的增加,索引优化效果明显降低,导致S3C1和S2C1,S3C2和S2C2这两组对比实验的执行时间相差很大;Time[HadoopDB](S2C3)和Time[HadoopDB](S3C3)对比其他用例非常耗时,这是由于HadoopDB采用的分片方法加速了连接操作,同时避免了数据在节点间的传输,但是,当数据量显著增大、连接表的数量增多时,这种优化效果明显降低,所以,Time[HadoopDB](SiC3)曲线对比其他曲线要增长得更快.

图 7(d)可知,HBase对于OLAP没有任何优化策略,其性能符合ROLAP的一般规律.但是,HBase在相同用例下的切块操作执行时间对比其他系统要长很多.图 8(a)展示在用例S1C1中,HBase的MapperReducer数量分别是Hive的2.8倍和13倍;图 8(b)则说明,用例S1C1中,MapperReducer的执行时间HBase是Hive的20倍和2.3倍.HBase的任务执行性能比Hive要低很多.这种现象表明,HBase并不适合执行多表的连接以及切块操作.

Fig. 8 Performance comparison of Hive and HBase on S1C1 testcases 图 8 Hive和HBase对于用例实验数据对比

图 7(e)展示了Olap4Cloud的切块操作在不同数据集下运行时间的变化趋势.从图中可以看出,Olap4Cloud的整体切块性能较前4者都有很大不同.首先它并没有表现出一个固有趋势.其中,C1C2任务在各个节点上运行时间较为稳定,但是C3在不同的数据集下,运行时间差异非常明显,特别是S1C3S2C3S3C3相差较大.为了对这一现象进行分析,我们考虑Olap4Cloud查询中的两个关键因素:查询索引时间和MapReduce任务时间.我们知道,MapReduce处理时间与Map,Reduce任务的个数、数据量以及算法复杂度相关.在本实验中,查询方法是相同的,所以我们忽略算法复杂度所带来的影响.由于Olap4Cloud的索引技术,除S3C1S3C2外的任务参与计算的数据量也是相同的.同时,由于Olap4Cloud基于HBase,所以我们设定Reducer的个数固定为12个,即集群中datanode的个数.SiC1SiC2的曲线的趋势是相同的,我们仅针对SiC1进行研究.

图 9(a)和图 9(b)中展示了SiC1中各个用例的详细信息.参与S3C1的数据量为S1C1S2C1的3倍,但S3C1所启动的Mapper数量则是S1C1S2C1的7.25倍;同时,由于C1仅针对一个维进行操作,所以使得查询索引的时间很快,各个操作所使用的时间差不多.这就导致了SiC1各个用例运行时间较为稳定的现象.图 9(a)和图 9(b)中展示了SiC3中各个用例的详细信息.对于C3操作而言,在各个数据集下参与计算的数据量是相同的.但是各个数据集中维的取值不同,导致其索引文件的大小不相同.维的取值越多,索引文件越大.同时,在对HBase中HTable进行扫描的过程中,由于数据集的构成不同,从而使得在MapReduce任务中所启动的Mapper任务个数有所不同,其中,S1C3S2C3Mapper分别为9个、10个,但是S3C3Mapper数量近乎是两者的6倍.所以,S3C3任务在MapReduce任务中所使用的时间比S1C3S2C3要少.但是,S3数据集所含数据量分别是S2的10倍,S1的100倍,从而导致最终生成的索引文件更加庞大,所以S3C3中扫描索引的时间较长.同时,Olap4Cloud执行查询时,首先在主节点中单线程地扫描整个索引表,然后再执行MapReduce任务,所以导致扫描索引的时间成为限制整个任务的瓶颈.

Fig. 9 Detail information about test cases of Olap4Cloud 图 9 Olap4Cloud中用例的详细信息

Olap4Cloud将维表压缩如事实表的方式避免了连接操作,同时,使用索引的方式确定参与计算的实际数据量,缩短了OLAP运行时间.但是,当数据量过大、同时操作较为复杂涉及维较多时,容易产生系统瓶颈问题.从总体上看,DOLAP的切块性能要优于Olap4Cloud.

由本组实验可以得出:DOLAP的切块操作性能优势非常明显,且操作的性能与原始数据集的规模以及参与计算的维数无关.

4.1.3 上卷操作

本组实验共包含3个上卷操作用例U1,U2,U3,每个操作都将在S1,S2,S3这3个数据集上分别执行.对比切块用例,Uj和Cj的查询条件是完全相同的.Uj比Cj包含维攀升和对度量的聚集操作,Uj将度量从Time维的Slot级别聚集到Month级别.为了表述方便,实验用例记作SiUj(1≤i≤3,1≤j≤3),其结果数据的数据量记作ResultSize(SiUj)(1≤i≤3,1≤j≤3),用例的执行时间记作Time[system](SiUj)(1≤i≤3,1≤j≤3,systemÎ{HaoLap,Hive, HadoopDB,HBase,Olap4Cloud}).由于聚集操作,ResultSize(SiUj)约为ResultSize(SiCj)的1%.

各个用例的运行时间如图 10所示,图 11展示了在各个系统中上卷操作的性能趋势.

Fig. 10 Execution time of roll-up operation (logarithmic coordinate) 图 10 上卷操作的运行时间(对数坐标)

Fig. 11 Tendency of roll-up performance when data set is changed图 11 上卷操作性能随数据集变化趋势

图 11可知,HaoLap的上卷性能优于其他系统,Hive,Olap4Cloud和HadoopDB次之,HBase的上卷性能最差.图 11的曲线趋势与图 7非常接近,这是由于维攀升是通过维遍历算法计算来实现的,代价很小,而聚集操作并没有主导上卷性能.

通过计算Time[system](SiUj)与Time[system](SiCj)(1≤i≤3,1≤j≤2,systemÎ{HaoLap,Hive,HadoopDB,Olap4Cloud})的比值来对上卷操作与切块操作进行对比分析,该比值记作.如果,表明在该系统上卷操作与切块操作的性能相当;如果,表明该系统中SiUj的执行速度时间比SiCj要短;反之亦然.由于结果数据集大小不同以及HBase整体性能较差,我们仅计算并分析1≤i≤3,1≤j≤2,systemÎ {HaoLap,Hive,HadoopDB,Olap4Cloud}的.实验结果如图 12所示.

Fig. 12 Performance comparison of roll-up and dice图 12 上卷操作与切块操作对比

图 12所示,,HaoLap,Hive和HadoopDB的上卷操作性能比切块操作性能要高.原因是:上卷操作中的聚集运算导致上卷结果数据集是切块结果数据集的1%,从而大大减少了数据输出时的I/O操作.但是Olap4Cloud的切块和上卷操作性能差不多,这是由于Olap4Cloud是基于HBase的,其数据写入性能本身较低,从而I/O操作无法成为整个操作性能中的主要因素.通过对比得出结论,额外的维攀升和聚集操作并没有影响DOLAP的性能.

4.1.4 存储代价

本实验从数据存储和多维模型存储两个方面来度量分析HaoLap的存储代价.我们首先比较了上述Si‑在HaoLap,Hive,HadoopDB,HBase和Olap4Cloud的存储数据集大小;随后介绍数据立方(cube)存储方法,并通过理论和实验分析证明:即使在高维数据集下,数据立方的存储代价仍然很小.

图 13对比了各数据集在HaoLap,Hive,HadoopDB,HBase和Olap4Cloud系统中的存储代价.在实际实验中,备份数量采用Hadoop默认值为3,图 13中所列出的数值均不含数据备份的大小.以数据集S3为例,HBase和OLAP4Cloud的存储开销约是HaoLap和Hive的8倍,是HadoopDB的2倍.HaoLap和Hive所占用磁盘空间相差无几,且小于其他系统,这是由于HaoLap和Hive均直接采用分布式文件系统HDFS中的原生文件格式存储数据,存储结构简单,并没有引入额外元数据而仅存储数据本身.由于OLAP4Cloud是基于HBase的OLAP系统,所以OLAP4Cloud和HBase的存储代价相似,且高于其他系统.HadoopDB采用关系数据库系统PostgreSQL存储数据,首先采用哈希算法将事实数据分割为多个子数据集,并将子数据集分别导入到不同的数据节点的PostgreSQL数据库中,同时创建索引;为优化连接操作,HadoopDB要求将维数据复制到每一个数据节点中.上述操作均导致额外的存储开销,造成HadoopDB的存储代价较高.此外,由于S1,S2,S3数据集大小相差10倍,对应的HaoLap的数据文件大小也相差近10倍,说明存储代价和数据集大小呈良好的线性关系.

Fig. 13 Storage comparison of HaoLap, Hive, HadoopDB, HBase and Olap4Cloud图 13 数据集在HaoLap,Hive,HadoopDB,HBase和Olap4Cloud的存储代价对比

HaoLap的数据立方存储代价非常小且可以忽略.为适应大数据环境,本文提出的DOLAP与传统MOLAP的本质不同在于:前者不需要存储庞大的“多维数组”,而是通过计算获得该“多维数组”.根据第2.2节中的描述,DOLAP对维进行简化,同一级别上维值的编码是连续的,维值树的每一个兄弟节点都有相同个数的子节点,所以对于每一个维,在DOLAP中仅需存储维级别名称和维级别规模,极大地降低了维的存储代价.例如在HaoLap的实现中,对于Time维,仅在主节点采用XML文件存储{áYear,10ñ,áSeason,4ñ,áMonth,3ñ,áDay,31ñ, áSlot,3ñ}这一条数据,并在运行时加载至内存.HaoLap通过维编码和遍历算法确定单元格(cell)位置,并通过数据立方分块以及线性化算法完成单元格和物理存储位置(MapFile)的映射,通过MapReduce完成数据查询和聚集.因此,可以认为HaoLap的数据立方是零实例化的.实验结果表明,即使是高维数据立方,如将Time维存储1 000次,内存中数据对象也仅有50.3KB.上述分析和实验证明,HaoLap的数据立方存储代价可以忽略.

4.2 基准测试

为证明HaoLap系统以及本文提出的DLOAP算法能够适用于枚举型维的数据集,我们采用了SSB基准测试用例.如图 14所示的SSB标准[26]是TPC-H标准的星型模型,目前被学术界所广泛采用.它将模式清晰地分解为4个维表和1个事实表,消除了TPC-H中LIENITEM和ORDER表的巨大连接代价,也消除了雪花状模型带来的复杂查询执行计划,从而使其更加适合于大规模并行计算环境下的简单数据分布[18].

Fig. 14 Schema of SSB图 14 SSB 数据集的模式

图 14可以看出,与第2.5节描述的案例OceanCube中的连续数值型维属性不同,SSB中维表属性多为枚举型数据,如CUSTOMER表的CITY属性以及SUPPLIER表中的NAME属性,且每个维上的维值远大于OceanCube,属于高维数据.我们采用的分析用例D的SQL描述如下:

D
SELECT C_NATION, S_NATION, D_YEAR, SUM(LO_REVENUE) AS REVENUE
FROM CUSTOMER, LINEORDER, SUPPLIER, DATE
WHERE LO_CUSTKEY=C_CUSTKEY AND
LO_SUPPKEY=S_SUPPKEY AND
LO_ORDERDATE=D_DATEKEY AND
C_REGION=‘ASIAAND S_REGION=‘ASIAAND
D_YEAR>=1992 AND D_YEAR<=1997 AND
GROUP BY C_NATION, S_NATION, D_YEAR
ORDER BY D_YEAR ASC, REVENUE DESC

为了对比第4.1节的实验结果,我们同样选择了S1,S2,S3这3个测试数据集作为测试数据,按SSB的数据生成规则,SF(scale factor)分别对应为10,30和60,数据集大小见表 4.对比表 3中OceanCube数据集可知,SSB数据集为高维数据集,维数据量大于OceanCube;而维和事实数据并非一一映射,这就导致在相同维数据的情况下,事实数据量小于OceanCube.另外,表 3所给出的数据为生成数据文件的大小,由于各个系统实现不同,会导致在各个系统内数据文件的大小会有明显差异.

Table 4 Size of SSB experimental set 表 4 SSB实验数据集大小

基准测试实验比较了HaoLap,Hive,HadoopDB和Olap4Cloud在S1,S2,S3这3个测试数据集上执行用例D的性能.根据第4.1节的分析,HBase的连接性能较其他系统差距显著,因此基准测试略去了上述实验.

图 15所示的基准测试实验结果可以看出:即使采用由离散型数据组成的高维数据立方,HaoLap的分析性能仍然明显优于其他3个系统.具体分析如下:

Fig. 15 Performance comparison of SSB query图 15 在SSB数据集中查询的性能对比

① 整体上,HaoLap的分析性能略优于Hive,且明显优于HadoopDB和Olap4Cloud;

②HaoLap在图 15中的分析性能规律和图 6以及图 10中呈现的规律是一致的,连接聚集查询性能与数据量和查询语句的复杂性无关,仅取决于选中的数据集大小.用例D对查询结果进行了聚集操作,因此,S1,S2,S3的结果数据集大小是一致的,但查询命中率不同,因此性能不同;

③ 对比HaoLap和Hive的性能可以看出,HaoLap的性能优势在SSB数据集中没有其在OceanCube数据集中那样明显.这是因为在高维数据集下,HaoLap的单元格索引值已经超出了Java语言长整型(long)的数据范围(264),因此,HaoLap采用字符串表示大整数且进行数学运算,这种运算的性能开销难以忽略;

④ 基于DOLAP的HaoLap的分析性能明显要优于基于MOLAP的Olap4Cloud,原因在于Olap4Cloud依赖索引在数据立方中可以精确地定位数据存储位置,这样做减少了数据搜索范围,但在高维数据立方下,索引查询和维护的开销很大.实验中,Olap4Cloud查询非常不稳定,经常出现无法响应的情况,为了得到完整结果,我们对Olap4Cloud的索引作了一些手工优化.而HaoLap则通过维编码和线性化算法初步确定数据存储位置,块选择算法选中的是包含目标数据的最小数据块集合,并没有精确定位到数据本身,数据查询则采用基于MapReduce的并行算法扫描数据块,避免了维护和查询索引的代价.

4.3 实验结论

HaoLap是DOLAP在大数据环境中的实现系统,本节比较了HaoLap,Hive,HadoopDB,HBase,Olap4Cloud的数据装载、切块操作、上卷操作性能以及存储代价;实验数据采用了真实的由连续数值型维组成的真实数据集OceanCube以及由离散枚举型维组成的高维SSB数据集.实验结果表明:尽管HaoLap在数据装载方面没有优势,但其OLAP性能明显高于其他4个系统,且性能不取决于原始数据集的规模以及操作的复杂程度,存储代价和Hive相当并低于其他3个系统.产生这种现象的主要原因有以下两点:DOLAP技术采用了简化的维模型和编码机制,使得维和度量的映射、维层次的遍历都更加高效;DOLAP技术使用分块策略存储度量并在OLAP执行过程中使用块选择算法,尽量缩小数据查询范围.此外,本实验还分析了Hive,HadoopDB,HBase,Olap4Cloud的OLAP性能特征和成因.

5 结论与进一步工作

本文提出了一种用于大数据分析的DOLAP技术.该技术包括以下6个方面:① 采用特殊的多维模型来组织维和度量;② 维编码和遍历算法实现了维值树上的上卷下钻操作;③ 简化的维存储方法,且数据立方分块算法实现了维和度量的映射关系以及度量的分布式存储;④ 线性化和反线性化算法实现了块和单元格的高效寻址算法;⑤ 通过块选择算法来优化OLAP性能;⑥ 提出基于MapReduce的OLAP算法实现.与此同时,本文还实现了基于Hadoop的DOLAP实现系统HaoLap,并比较了HaoLap,Hive,HadoopDB,HBase,Olap4Cloud的装载性能和OLAP性能.实验结果表明:尽管HaoLap在数据装载方面没有优势,但其OLAP性能明显高于其他4个系统,且性能与原始数据集的规模以及操作的复杂程度无关,存储代价和Hive相当并低于其他3个系统.同时,本文还分析了其他系统的OLAP性能,总结了相关规律.

本文的进一步工作将着重于以下几个方面:① 讨论数据块是否应被压缩、如何被压缩、如何在压缩数据立方上执行OLAP操作,以及压缩对OLAP性能将带来哪些影响;② 优化HaoLap数据装载的性能.

参考文献
[1] Gray J, Liu DT, Nieto-Santisteban M, Szalay A, DeWitt DJ, Heber G. Scientific data management in the coming decade. ACM SIGMOD Record, 2005,34:34-41 .
[2] Miller HJ. The data avalanche is here. Shouldn’t we be digging? Journal of Regional Science, 2010,50(1):181-201 .
[3] Wang S, Wang HJ, Qin XP, Zhou X. Architecting big data: Challenges, studies and forecasts. Chinese Journal of Computers, 2011, 34(10):1741-1752 (in Chinese with English abstract) .
[4] Meng XF, Ci X. Big data management: Concepts, techniques and challenges. Journal of Computer Research and Development, 2013,50(1):146-169 (in Chinese with English abstract).
[5] Shim JP, Warkentin M, Courtney JF, Power DJ, Sharda R, Carlsson C. Past, present, and future of decision support technology. Decision Support Systems, 2002,33:111-126 .
[6] Chaudhuri S, Dayal U. An overview of data warehousing and OLAP technology. ACM Sigmod Record, 1997,26:65-74 .
[7] Luk WS, Li C. A partial pre-aggregation scheme for HOLAP engines. In: Proc. of the 6th Int’l Conf. on Data Warehousing and Knowledge Discovery (DaWaK 2004). Berlin: Springer-Verlag, 2004.129-137 .
[8] Bolosky WJ, Douceur JR, Ely D, Theimer M. Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs. ACM SIGMETRICS Performance Evaluation Review, 2000,28(1):34-43.[doi:10.1145/345063.339345]
[9] Shen DR, Yu G, Wang XT, Nie TZ, Kou Y. Survey on NoSQL for management of big data. Ruan Jian Xue Bao/Journal of Software, 2013,24(8):1786-1803 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4416.htm
[10] Dean J, Ghemawat S. Mapreduce: Simplified data processing on large clusters. Communications of the ACM, 2008,51:107-113 .
[11] Hadoop home page. http://hadoop.apache.org .
[12] Thusoo A, Sarma JS, Jain N, Shao Z, Chakka P, Anthony S, Liu H, Wyckoff P, Murthy R. Hive: A warehousing solution over a map-reduce framework. Proc. of the VLDB Endowment, 2009,2(2):1626-1629.
[13] Vora MN. Hadoop-HBase for large-scale data. In: Proc. of the 2011 Int’l Conf. on Computer Science and Network Technology. Piscataway: IEEE, 2011. 24-26.
[14] Abouzeid A, Bajda-Pawlikowski K, Abadi D, Silberschatz A, Rasin A. HadoopDB: An architectural hybrid of mapreduce and DBMS technologies for analytical workloads. Proc. of the VLDB Endowment, 2009,2(1):922-933.
[15] Olap4cloud home page. http://code.google.com/p/olap4cloud/ .
[16] Song J, Li TT, Zhu ZL, Bao YB, Yu G. Benchmarking and analyzing the energy consumption of cloud data management system. Chinese Journal of Computers, 2013,36(7):1485-1499 (in Chinese with English abstract).
[17] You JG, Xi JQ, Zhang PJ, Chen H. A parallel algorithm for closed cube computation. Computer and Information Science, 2008,8: 95-99 .
[18] Zhang YS, Jiao M, Wang ZW, Wang S, Zhou X. One-Size-Fits-All OLAP technique for big data analysis. Chinese Journal of Computers, 2011,34(10):1936-1946 (in Chinese with English abstract) .
[19] Cao Y, Chen C, Guo F, Jiang DW, Lin YT, Ooi BC, Vo HT, Wu S, Xu QQ. ES2: A cloud data storage system for supporting both OLTP and OLAP. In: Proc. of the Int’l Conf. on Data Engineering (ICDE). 2011. 291-302 .
[20] Tian X. Large-Scale SMS messages mining based on map-reduce. Computational Intelligence and Design, 2008,1:7-12 .
[21] Han H, Lee YC, Choi S, Yeom HY, Zomaya AY. Cloud-Aware processing of MapReduce-based OLAP applications. In: Javadi B, ed. Proc. of the 11th Australasian Symp. on Parallel and Distributed Computing. Darlinghurst: Australian Computer Society, 2013. 31-38.
[22] D’Orazio L, Bimonte S. Multidimensional arrays for warehousing data on clouds. In: Hameurlain A, ed. Proc. of the Data Management in Grid and Peer-to-Peer Systems. Berlin, Heidelberg: Springer-Verlag, 2010. 26-37.
[23] Olston C, Reed B, Srivastava U, Kumar R, Tomkins A. Pig latin: A not-so-foreign language for data processing. In: Lakshmanan LVS, ed. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data. New York: Association for Computing Machinery, 2008. 1099-1110.
[24] Hu KF, Dong YS, Xu LZ, Yang KH. A novel aggregation algorithm for online analytical processing queries evaluation based on dimension hierachical encoding. Journal of Computer Research and Development, 2004,41(4):608-614 (in Chinese with English abstract).
[25] TPC-H homepage. http://www.tpc.org/tpch/ .
[26] O’Neil P, O’Neil B, Chen XD, Stephen R. The star schema benchmark and augmented fact table indexing. In: Proc. of the 1st TPC Technology Conf. on Performance Evaluation and Benchmarking (TPCTC 2009). Berlin: Springer-Verlag, 2009. 237-252 .
[27] Sarawagi S, Stonebraker M. Efficient organization of large multidimensional arrays. In: Proc. of the Int’l Conf. on Data Engineering. IEEE, 1994. 328-336. http://dl.acm.org/citation.cfm?id=645479.655138&coll=DL&dl=GUIDE&CFID=419816811&CFTOKEN=55823079 .
[28] Shvachko K, Kuang H, Radia S, Chansler R. The hadoop distributed file system. In: Proc. of the 2010 IEEE 26th Symp. on Mass Storage Systems and Technologies (MSST 2010). IEEE, 2010.1-10 .
[29] Yang L, Shi ZZ. An efficient data mining framework on Hadoop using Java persistence API. In: Proc. of the 2010 IEEE 10th Int’l Conf. on Computer and Information Technology (CIT 2010). IEEE Computer Society, 2010. 203-209 .
[30] China oceanic information network. http://mds.coi.gov.cn/jcsj.asp
[31] Qin XP, Wang HJ, Du XY, Wang S. Big data analysis—Competition and symbiosis of RDBMS and MapReduce. Ruan Jian Xue Bao/Journal of Software, 2012,23(1):32-45 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4091.htm
[3] 王珊,王会举,覃雄派,周烜.架构大数据:挑战、现状与展望.计算机学报,2011,34(10):1741-1752 .
[4] 孟小峰,慈祥.大数据管理:概念、技术与挑战.计算机研究与发展,2013,50(1):146-169.
[9] 申德荣,于戈,王习特,聂铁铮,寇月.支持大数据管理的NoSQL系统研究综述.软件学报,2013,24(8):1786-1803. http://www.jos.org.cn/1000-9825/4416.htm
[16] 宋杰,李甜甜,朱志良,鲍玉斌,于戈.云数据管理系统能耗基准测试与分析.计算机学报,2013,36(7):1485-1499.
[18] 张延松,焦敏,王占伟,王珊,周烜.海量数据分析的One-size-fits-all OLAP技术.计算机学报,2011,34(10):1936-1946 .
[24] 胡孔法,董逸生,徐立臻,杨科华.一种基于维层次编码的OLAP聚集查询算法.计算机研究与发展,2004,41(4):608-614.
[31] 覃雄派,王会举,杜小勇,王珊.大数据分析——RDBMS与MapReduce的竞争与共生.软件学报,2012,23(1):32-45. http://www.jos.org.cn/1000-9825/4091.htm