大数据分析的分布式技术22

软件学报ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],2014,25(4):731−752[doi:10.13328/j.cnki.jos.004569]©中国科学院软件研究所版权所有.Tel/Fax:[phone]大数据分析的分布式MOLAP技术∗宋杰1,郭朝鹏1,王智1,张一川1,于戈2,Jean-MarcPIERSON31(东北大学软件学院,辽宁沈阳110819)2(东北大学信息科学与工程学院,辽宁沈阳110819)3(LaboratoireIRIT,UniversitéPaulSabatier,ToulouseF-31062,France)通讯作者:宋杰,E-mail:[e-mail],:大数据的规模效应给数据存储、管理以及数据分析带来了极大的挑战,学界和业界广泛采用分布式文件系统和MapReduce编程模型来应对这一挑战.提出了大数据环境中一种基于Hadoop分布式文件系统(HDFS)和MapReduce编程模型的分布式MOLAP技术,称为DOLAP(distributedOLAP).DOLAP采用一种特殊的多维模型完成维和度量的映射;采用维编码和遍历算法实现维层次上的上卷下钻操作;采用数据分块和线性化算法将维和度量保存在分布式文件系统中;采用数据块选择算法优化OLAP的性能;采用MapReduce编程模型实现OLAP操作.描述了DOLAP在科学数据分析的应用案例,并与主流的非关系数据库系统进行性能对比.实验结果表明,尽管数据装载性能略显不足,但DOLAP的性能要优于基于HBase,Hive,HadoopDB,OLAP4Cloud等主流非关系数据库系统实现的OLAP性能.关键词:大数据;多维数据模型;OLAP;MapReduce中图法分类号:TP311文献标识码:A中文引用格式:宋杰,郭朝鹏,王智,张一川,于戈,PiersonJM.大数据分析的分布式MOLAP技术.软件学报,2014,25(4):731−752.:SongJ,GuoCP,WangZ,ZhangYC,YuG,PiersonJM.DistributedMOLAPtechniqueforbigdataanalysis.RuanJianXueBao/JournalofSoftware,2014,25(4):731−752(inChinese).,GUOChao-Peng1,WANGZhi1,ZHANGYi-Chuan1,YUGe2,Jean-MarcPIERSON31(SoftwareCollege,NortheasternUniversity,Shenyang110819,China)2(SchoolofInformationandEngineering,NortheasternUniversity,Shenyang110819,China)3(LaboratoireIRIT,UniversitéPaulSabatier,ToulouseF-31062,France)Correspondingauthor:SONGJie,E-mail:[e-mail],:Toaddressthenewchallengesthatbigdatahasbroughtondatastorage,managementandanalysis,distributedfilesystemsandMapReduceprogrammingmodelhavebeenwidelyadoptedinbothindustryandacademia.ThispaperproposesadistributedMOLAPtechnique,namedDOLAP(distributedOLAP),basedonHadoopdistributedfilesystem(HDFS)andMapReduceprogrammodel.DOLAPadoptsthespecifiedmultidimensionalmodeltomapthedimensionsandthemeasures.Itcomprisesthedimensioncodingandtraversealgorithmtoachievetherollupoperationondimensionhierarchy,thepartitionandlinearizationalgorithmtostoredimensionsandmeasures,thechunkselectionstrategytooptimizeOLAPperformance,andMapReducetoexecuteOLAP.Inaddition,thepaperdescribestheapplicationcaseofthescientificdataanalysisandcomparesDOLAPperformancewithotherdominatenon-relationaldata∗基金项目:国家自然科学基金(61202088);中央高校基本科研业务费专项资金(N120817001);中国博士后科学基金面上项目(2013M540232);教育部博士点基金(20120042110028);教育部-英特尔信息技术专项科研基金(MOE-INTEL-2012-06)收稿时间:2013-10-15;修改时间:2013-12-18;定稿时间:2014-01-27732JournalofSoftware软件学报Vol.25,No.4,April2014managementsystems.ExperimentalresultsshowthathugedominanceinOLAPperformanceoftheDOLAPtechniqueoveranacceptableperformanceloseindataloading.Keywords:bigdata;multi-dimensionaldatamodel;OLAP;MapReduce近年来,随着大数据时代的到来以及互联网、传感器和科学数据分析等领域的快速发展,数据量近乎每年在成倍地增长[1].无论是在科学领域(生物学、地理学、天文学、气象学等),还是在工程领域(网络数据分析、市场数据分析等),都面临着数据雪崩的问题[2],大数据的规模效应给数据存储、管理以及数据分析带来了极大的挑战[3,4].OLAP(on-lineanalyticalprocessing)联机分析处理是共享多维信息的、针对特定问题的联机数据访问和分析的快速软件技术[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(distributedOLAP).DOLAP采用一种特殊的多维模型完成维和度量的映射;采用维编码和遍历算法实现维层次上的上卷下钻操作;采用数据分块和线性化算法将维和度量保存在分布式文件系统中;采用数据块选择算法优化OLAP的性能;采用MapReduce编程模型实现OLAP操作.在DOLAP技术的基础上,我们基于Hadoop实现了一个OLAP系统HaoLap(hadoopOLAP),设计了一系列测试用例,将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优化方法研究,本节主要从以下两个方面介绍相关工宋杰等:大数据分析的分布式MOLAP技术733作:大数据环境中的OLAP优化技术和分布式的OLAP系统.大数据环境中,常用的OLAP优化方法有以下两种:利用预计算和浓缩数据立方的结果优化OLAP性能[17]和通过优化存储结构和算法来优化OLAP性能,其中,后者与本文昀为相关.文献[18]提出了OLAP查询中的SPAJG-OLAP子集,在存储、查询、数据分布、网络传输和分布式缓存等方面研究海量数据大规模并行处理框架的优化策略和实现技术,实验证明,效果良好.该研究基于并行数据库技术优化ROLAP性能,通过对OLAP查询以及存储的优化达到加速OLAP的目的.