书书书
第36卷 第2期2013年2月
计 算 机 学 报CHINESEJOURNALOFCOMPUTERS Vol.36No.2Feb.2013
收稿日期:20120228;最终修改稿收到日期:20120821.本课题得到国家自然科学基金(61070055,91024032,91124001)、
中国人民大学科学研究基金(11XNL010)、国家“八六三”高技术研究发展
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
项目基金(2012AA010701)资助.史英杰,女,1983年生,博
士研究生,主要研究方向为云数据管理、大数据上的在线聚集.Email:shiyingjie1983@yahoo.com.cn.孟小峰,男,1964年生,博士,教
授,主要研究领域为Web数据管理、移动数据管理、XML数据管理、云数据管理等.
云数据管理系统中查询技术研究综述
史英杰 孟小峰
(中国人民大学信息学院 北京 100872)
摘 要 作为一种全新的互联网应用模式,云计算在工业界和学术界备受关注.人们可以通过终端设备便捷地获
取云端服务,并以按需使用的方式获得存储资源、计算资源以及软硬件资源.云计算的发展带来了一系列挑战性问
题,而云数据的管理问题首当其冲.文中结合云数据的特点提出了一个云数据管理系统的框架,并在此基础上从索
引管理、查询处理、查询优化以及在线聚集等几个方面对云数据管理系统中查询技术的研究工作进行了总结分析,
指明了该领域面临的挑战和未来的研究工作.
关键词 云计算;云数据管理;查询处理;查询优化;索引管理;在线聚集
中图法分类号TP392 犇犗犐号 10.3724/SP.J.1016.2013.00209
犃犛狌狉狏犲狔狅犳犙狌犲狉狔犜犲犮犺狀犻狇狌犲狊犻狀犆犾狅狌犱犇犪狋犪犕犪狀犪犵犲犿犲狀狋犛狔狊狋犲犿狊
SHIYingJie MENGXiaoFeng
(犛犮犺狅狅犾狅犳犐狀犳狅狉犿犪狋犻狅狀,犚犲狀犿犻狀犝狀犻狏犲狉狊犻狋狔狅犳犆犺犻狀犪,犅犲犻犼犻狀犵 100872)
犃犫狊狋狉犪犮狋 Asarevolutionaryapplicationmodeintheinternet,cloudcomputinghasattracted
moreandmoreattentionsfrombothindustryandacademia.Userscanobtaincloudservicecon
venientlythroughterminals,andaccessresourcesofstorage,computingandhardwareinthePay
AsYouGomodel.Thedevelopmentofcloudcomputingbringsaboutaseriesofchallenging
problems,datamanagementinthecloudisofgreatimportance.Inthispaper,weproposea
frameworkofclouddatamanagementsystem.Basedonthisframework,thekeyresearchworks
ofquerytechniquesinclouddatamanagementsystemareclassifiedandsurveyedfromseveral
aspects:indexmanagement,queryprocessing,queryoptimizationandonlineaggregation.At
last,thesuggestionsforfutureresearchareputforward.
犓犲狔狑狅狉犱狊 cloudcomputing;clouddatamanagement;queryprocessing;queryoptimization;
indexmanagement;onlineaggregation
1 引 言
云计算是当今信息产业备受关注的一种全新领
先的计算模式.在云计算模式下,企业和个人可以根
据自己的需要购买存储设备和计算能力,而不用花
费大量资金购买大规模高性能计算机,这使得用户
在软硬件维护以及升级上的成本投入大大减少.作
为一项有望大幅降低成本的新兴技术,云计算受到
了众多信息业巨头的关注:Amazon、Google、IBM、
微软等公司都对云计算的研发进行了大规模的投
入.与此同时,云计算的发展也产生了一系列新的挑
战性问题,云数据管理是亟待解决的问题之一.
随着信息产业的发展,企业和各种组织产生的
数据量快速增长.据IDC(互联网数据中心)统计,
2011年全球产生的数据量达到1.8ZB,比2010年
增长了1ZB①.如何对这些海量数据进行有效管理
和分析以获取数据背后潜在的巨大价值,是目前互
联网、通信和生物医学等诸多领域面临的问题.传统
数据管理系统中的很多技术对于如此大规模的数据
管理往往不再有效,而且相关软硬件以及维护的昂
贵成本也是让大部分企业望洋兴叹.云环境是由大
量性能普通、价格便宜的计算节点组成的一种无共
享大规模并行处理环境[1],所以从成本和性能两方
面考虑,越来越多的组织更愿意把数据中心从昂贵
的高性能计算集群转移到公有云或私有云环境中.
另一方面,随着Web2.0和普适计算应用的流
行,其“瘦客户端+服务”的运行模式对服务器端的
计算能力和数据处理能力要求越来越高.在这种模
式下,用户通过浏览器就可获得各种各样的服务,所
有的计算都交由服务器端执行.为支持这些应用,服
务系统需要存储、索引和备份海量的异构万维网页
面、用户访问日志以及用户信息,并且还要保证对这
些数据进行快速准确的访问[2].同时,服务系统所要
处理的数据不仅包括产品和客户信息等结构化数
据,还包含大量半结构和非结构化数据.在上述应用
需求的推动下,云数据管理系统应运而生.
目前,随着Google、Yahoo!、Facebook等企业的推动,出现了不少基于云计算平台的数据管理系
统,而且大部分系统已经投入生产环境使用[34].与
传统数据库系统相比,目前云数据管理系统提供的
接口有很多限制,只提供简单的数据存取接口或者
极小化的查询语言,这增加了用户使用的难度,也增
加了开发人员的负担.同时,相比于传统的分布式关
系数据库,云数据管理系统的查询性能也有很大的
提升空间[56].如何在现有云计算平台的基础上,完
善云数据管理系统的查询功能并提高其数据处理的
性能,是目前备受关注的挑战性问题.
本文第2节对云数据查询技术进行概述;第3节
提出云数据管理系统的基本框架并依据该框架对云
数据查询的关键性技术进行总结分析;第4和第5
节对未来工作进行展望并对全文工作进行总结.
2 云数据查询处理概述
与传统关系数据库中的数据查询相比,云数据
管理系统中的查询处理特点鲜明.本节阐述云数据
管理系统的应用场景,结合已有的云数据管理系统
和相关研究工作,对云环境中数据的特性进行了分
析,指出云数据查询处理技术的目标,并总结云数据
管理系统中查询技术的特征与面临的挑战.
2.1 云数据管理系统的应用场景与传统的关系数据库相比,云数据管理系统具
有良好的扩展性和容错性,利用云计算平台中大规
模计算资源和存储资源管理海量异构数据,为用户
提供高性价比的数据管理方式.目前云数据管理系
统在实际生产环境中得到了广泛的应用,主要集中在
两个方面:海量数据分析和大规模Web数据管理.
数据分析主要用于生成报表、数据挖掘和决策
支持等.与事务型数据处理不同,在分析型的数据处
理中,数据是一次写多次读的,更新操作较少.数据
分析可以在并行数据库上完成,但是随着数据规模
的扩大以及对性能要求的提高,并行数据库系统的
维护需耗费大量的资金及人力.云数据管理系统在
扩展性和性价比上均占有天然的优势,其中类
BigTable系统[7](BigTable、HBase②、Hypertable③)、
HadoopDB[8]和Hive[9]等支持MapReduce框架的系统是面向数据分析型应用的.
随着Web2.0技术的发展,超大规模和高并发
的社交网站逐渐兴起,参与人数迅速攀升.以微博网
站Twitter为例,2010年2月用户每日发送的微博
数量是5千万,而到了2011年3月用户每日发送的
微博数量达到1亿4千万④,用户和网站交互产生
大量动态信息.这种海量Web数据管理应用要求数
据库能够满足高并发的数据读写和高效实时的数据
访问,同时要求数据库具备可扩展性以应付数据的不
断快速增长.关系数据库在这些需求面前显得力不从
心,云数据管理系统则以灵活的扩展性和高性能的数
据读写受到Web2.0网站的青睐,其中Cassandra⑤、
CouchDB⑥和PNUTS[4]等系统广泛应用在Face
book、Twitter和Yahoo!等大型网站中.
2.2 云数据的特点云计算将大量用网络连接的计算资源进行统一
管理和调度,以服务的方式为用户提供计算资源、存
储资源和软硬件资源,其最鲜明的特点是可扩展性、
高可用性和按需服务性.云计算环境中存储和管理
的数据具备如下特点[1,8,1011]:
(1)海量性.随着移动设备的普及、传感器技术
的发展以及社交网络的扩大,云计算平台存储和管
012 计 算 机 学 报 2013年
①
②③④⑤⑥
http://www.emc.com/collateral/demos/microsites/emcdigitaluniverse2011/index.htmhttp://hbase.apache.org/http://hypertable.org/http://blog.twitter.com/2011/03/numbershttp://cassandra.apache.orghttp://couchdb.apache.org/
理的数据量十分庞大,TB级别和PB级别的数据规
模十分常见.
(2)种类多样性.随着Web2.0的兴起,互联网
应用不断推陈出新.一些新兴应用领域(微博、社交
网络等)所处理的数据除了传统数据库里的结构化
数据,还包括半结构化数据和非结构化数据,使得云
计算平台中的数据种类纷繁多样.
(3)异地备份.数据的高可用性是云计算的重
要特征之一,而这种面临软硬件错误的高水平容错
性是通过对用户透明的数据异地备份实现的.
云数据的特征导致了传统的关系数据库无法满
足其多样化的应用需求.云数据管理系统必须提供
灵活的数据模型以有效管理多样化的数据,并针对
数据分布和冗余的特性设计相应的存储方式和查询
优化策略,从而向用户提供“按需所取”、可靠的、高
性能的数据存取与查询服务.
2.3 云数据查询处理的目标为了提供高效可靠的云数据管理服务,云数据
的查询处理技术需要达到以下目标[1,1114]:
(1)可扩展性.云平台的规模大小不一,小的私
有云平台规模为十几个节点,大的公有云平台规模
可达到几千个节点①[15].此外,云计算提供的是一种
“按需计费”的服务方式,随着应用需求的变化,云平
台的规模也会发生变化.这就要求云数据管理系统
中的查询处理及优化算法具备良好的扩展性,不仅
能够扩展到庞大规模的云平台上,而且能够实现资
源的可动态增长及其带来的性能提升.
(2)可用性.云平台由大量廉价计算机构成,与
高性能服务器构成的分布式系统相比,云平台的硬
件出错率较高.云数据管理系统需要将软硬件错误
看成系统运行的常态,错误发生时既要保证数据不
丢失,又要保证数据的读写操作能够正常进行.
(3)在异构环境运行的能力.随着应用的发展
以及数据量的不断增长,云平台势必要通过增加新
的节点来提高计算和存储能力.因此,保证一个云平
台中所有节点的硬件配置同构是非常困难的.即使
在一个硬件配置相同的环境中,不同节点的软硬件
性能也会出现波动[16].云数据的查询技术要有在异
构环境运行的能力,从而避免性能较差的节点影响
整个系统的运行效率这种“木桶效应”的出现.
(4)丰富灵活的用户接口.一方面,云数据管理
系统要提供SQL接口,这样习惯于关系数据库查询
语言的用户不必重新学习新的接口或者编程方法,
而原来基于关系数据库的各种应用也可以平滑的转
移到云上;另一方面,云数据管理系统还要提供
UDF(UserDefinedFunction)接口,用户可以根据
业务需求自己定义数据查询操作.
(5)高效的数据存取性能.云数据管理系统的
软硬件成本远远低于高性能分布式数据库,其处理
海量数据的效率也是云计算用户关注的重要问题.
云数据管理系统应当针对云数据的特点设计数据分
布策略和查询优化相关算法,从而提高其管理海量
数据的能力.
云数据管理系统可以通过云计算平台的资源虚
拟以及MapReduce[15]框架的使用而得到良好的扩展性和可用性,也可以在并行任务调度过程中采取
投机任务(speculativetask)[16]等措施保证其在异构环境中运行的能力.从支持的查询接口看,目前大
部分云数据管理系统只提供了简单的数据存取接口
或者极小化的查询语言,这限制了其对复杂数据查
询和分析的支持.从查询性能来看,目前云数据管理
系统的查询优化主要针对键值进行,而对非键值的
查询主要是依靠批量的全表扫描.因此,用户接口和
查询性能是目前云数据管理系统亟待提高的两个
方面.
2.4 云数据管理系统中查询处理的特征传统关系数据库中的查询技术无法同时满足上
节提到的目标,特别是可扩展性和可用性.现有的云
数据管理系统的查询技术和传统关系数据库系统的
查询技术在处理的数据类型、容错性和支持接口等
方面表现出明显差异,表1从多个方面对二者进行
了对比.
表1 云数据管理系统与关系数据库的查询技术比较
云数据管理系统的特点 关系数据库的特点
数据类型 结构化数据,半结构化数据,非结构化数据 结构化数据
数据模型 KeyValue模型,文档模型,简化的关系模型 关系模型扩展性 易大规模扩展(几百到几千节点) 不易大规模扩展(最多几百节点)
容错性 数据容错,查询容错 数据容错
服务方式 PayAsYouGo PayBeforeYouGo支持接口 简单的API和极小化的查询语言,亟待丰富 复杂的SQL语言查询优化技术 基于键值和基于规则的优化技术,亟待相关研究成果 基于规则和基于代价的优化技术,技术比较成熟
1122期 史英杰等:云数据管理系统中查询技术研究综述
①http://hadoop.apache.org/
传统关系数据库的查询主要面向结构化数据,
其数据模型基于关系模型.云数据管理系统处理的
数据对象除了结构化数据,还包括半结构化和非结
构化数据,其数据模型包括keyvalue模型、文档模
型和简化的关系模型[34,9].之所以称其为简化的数
据模型是因为它虽然以表的形式管理数据,但不提
供实体完整性和参照完整性.除此以外,关系数据库
的数据模型是一种模式优先(schemafirst)的逻辑
结构,即在数据入库之前设计好数据模式.而云数据
管理系统中的数据模型是从数据到模式(fromdata
toschema)数据模式可以是松散的、滞后的,可以在
数据入库时根据数据内容定义数据模式.
查询容错是指一个查询运行过程中出现了硬件
错误,该查询不必重新开始.传统的关系数据库系统
一般不保证查询容错.云数据管理系统把硬件错误
看成一种常态,它同时保证数据容错和查询容错.因
为云平台上硬件错误率较高,如果每次出现错误都
需要重启查询,那么一个耗时较长的查询很可能无
法完成.从服务方式来看,传统关系数据库是一种
paybeforeyougo的方式,即通过需求分析设计数
据库模式并构建数据库软硬件,并在较长时间内保
持相对稳定,因此查询优化的目标是在已有的软硬
件环境下获得最好的查询性能.而云数据管理系统
是一种payasyougo的方式,用户根据使用的计算
资源和存储资源向服务提供商付费,因而查询优化
的目标是如何利用更少的计算资源获得用户期望的
查询性能.从查询接口和查询优化技术来看,关系数
据库支持复杂的SQL语言,而且查询优化技术也非
常成熟.相比之下,现有的云数据管理系统支持的查
询语言比较匮乏,而且已有的查询优化技术主要集
中在基于规则的优化,因此在这两个方面亟待加强.
3 云数据管理系统中查询技术研究
作为一种新型数据管理技术,云数据管理系统
的研究仍处于起步阶段.这种新兴的数据管理技术
可以扩展到大量廉价节点上,为用户提供按需所取、
高性价比的数据管理服务.本节首先提出云数据管
理系统的整体框架,然后从数据存储与索引技术、查
询处理及优化、在线聚集几个方面对云数据查询相
关工作和研究成果进行分析总结.
3.1 云数据管理系统基本框架
为了有效管理海量、种类多样的云数据,并提供
“按需所取”的云服务,云数据管理系统必须具有可
扩展性、可裁剪性、可用性以及在异构环境中运行的
能力.这使得云数据管理系统在面临查询处理、查询
优化和索引管理等问题时采用不同于传统数据库的
全新解决方法.同时,一些在传统数据库中提出但是
没有得到广泛应用的研究问题在云环境下显现出重
要的意义,例如查询进程估计和在线聚集等.目前已
有的数据管理系统大都面向某一类特定应用,因此
系统架构和实现方式各有不同.我们结合云计算中
数据管理应用的特点以及数据查询处理的目标,提
出了云数据管理系统的整体架构,如图1所示,该架
构被划分为5个部分.
(1)应用接口层.负责接收用户提交的请求并
交给查询处理层相应的模块进行处理.提供查询语
言接口、用户自定义接口UDF(key/value操作)、数
据分析和在线聚集等应用.用户不仅可以通过查询
接口和UDF接口进行数据操作,还可以通过可视
化工具执行数据分析和在线聚集.
(2)查询处理层.对上层提交的查询语句进行
解析和逻辑优化后转化成操作符树,进而生成
MapReduce执行计划;如果上层提交的是用户自定
义操作,则直接生成MapReduce执行计划.如何根
据查询类型和数据分布等信息生成合适的查询计
划,以及如何利用云数据的特点对查询计划进行逻
辑优化是查询处理层的主要任务,也是云数据管理
领域备受关注的研究问题.
(3)数据控制层.该层主要负责3个方面的工
作:利用全局索引和元数据信息进行数据定位;备份
数据的一致性处理和数据迁移;在线聚集过程中进
行数据采样和进程估计.数据层涉及到查询执行和
在线聚集的核心部分,目前的研究工作主要围绕查
询处理优化、索引构建、数据采样和查询结果估计.
(4)数据存储层.负责数据的实际存储以及在
各节点范围内数据的索引设计、缓冲区管理和日志
管理.存储层的节点可通过多种方式组织,例如主
从结构或者点对点结构等,主要通过不同的通信协
议体现.无论采用哪种结构,数据都被分区到多个节
点存储.如何在保证数据分布均衡的情况下提高每
个节点上数据存取的效率是存储层必须解决的
问题.
(5)服务管理模块.负责元数据的管理、操作管
理和系统监控.元数据管理部分为查询处理层提供
访问接口,同时保证元数据与数据模式之间的一致
性.操作管理主要面向数据控制层,包括数据读写锁
机制、容错机制以及负载均衡.系统监控模块从数据
212 计 算 机 学 报 2013年
图1 云数据管理系统框架
存储层收集监控信息,并通过图形界面将其展示给
用户.资源分配模块负责管理系统中的负载,节点能
够被动态地添加或删除以适应工作负载的变化.
3.2 云数据管理系统关键技术研究
依据云数据管理系统的整体框架,可以看出云
数据的查询领域存在许多研究问题:数据存储与索
引设计、基于MapReduce的查询处理、查询优化、在
线聚集过程中的数据采样与置信区间计算等.目前
索引管理、查询处理、查询优化以及在线聚集等问题
已经得到了初步的研究,本节对目前已有的相关工
作进行分析总结.
3.2.1 索引技术
现有的云数据管理系统大都以keyvalue方式
存储数据,能够提供基于键值的快速查询,但是对于
非键值的查询只能通过全表扫描来完成.尽管可以
通过MapReduce实现并发扫描,但是面对海量数
据,对于选择度比较高的查询来说,全表扫描的效率
仍然比较低.目前很多学者对云数据管理系统中的
索引技术进行了研究.根据索引的实现方式,本文把
已有的索引分成3类:双层索引[1721]、二级索
引①②[22]和基于线性化技术的全局索引[23].
(1)双层索引
云数据管理系统中的双层索引框架由Wu等
人[17]在2009年提出,后续双层索引
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
的研究工
作大都基于该框架,其结构如图2所示.索引由局部
索引和全局索引两部分构成.为每个节点的数据建
立局部索引,该索引只负责本地节点上的数据.除局
部索引外,每个计算节点还要共享一部分存储空间
来存储全局索引.全局索引依据局部索引构建,由于
图2 云数据管理系统中的双层索引框架
3122期 史英杰等:云数据管理系统中查询技术研究综述
①②
https://github.com/hbasetrx/http://github.com/gkulbak/ibase
存储空间的限制和查询效率的要求,并不是所有的
局部索引都发布到全局索引中,而是按照一定的规
则对索引节点进行选择.
根据全局索引的组织方式,双层索引可以分成
两类:P2P结构的双层索引和集中式结构的双层索
引.如表2所示,前3种方案的全局索引均采用P2P
结构的覆盖网络[1719],这种方式易于实现可扩展性,
使系统能够同时支持大规模的查询.但是也存在一
些不足:首先,维护P2P网络需要一定的代价,查询
时往往需要较高的网络传输代价;其次,对于主从结
构(masterslave)的云数据管理系统,实现这种索引
要重新构建一个P2P网络,会增加原有系统的负
担.基于上述原因,文献[2021]在全局索引中采用
了集中式的索引方式.EMINC[20]在每个节点建立
KD树作为局部索引,其中每个索引节点被看成一
个多维度的立方体,全局索引利用R树对这些立方
体进行索引.当索引维度比较高,或者索引数据量比
较大时,R树各个节点之间的重叠部分较多,查询时
会产生大量的误判(falsepositive)结果.为解决这
一问题,文献[21]的全局索引采用带bloomfilter的
R树.进行查询时,首先通过bloomfilter来验证,如
果查询点不在其中,则不再进行R树查询.这样减
少了误判的几率,从而提高查询效率.上述各种索引
技术方案具有较好的扩展性,但总的来说实现过程
比较复杂,索引更新维护的代价比较高.特别是对于
数据更新比较频繁的应用,对系统性能的影响较大.
表2 云数据管理索引技术对比
索引方案 代表技术 索引构成 特点
双层索引
P2P
EfficientBtree[17]局部索引:B+tree 全局索引:BATON
RTCAN[18] 局部索引:Rtree 全局索引:CAN
QTChord[19] 局部索引:IMXCIFquadtree 全局索引:Chord
集中式EMINC
[20] 局部索引:KDtree全局索引:Rtree
ATree[21] 局部索引:Rtree+Bloomfilter全局索引:ArrayBased
优点:具有较好的扩展性缺点:索引实现较复杂;更新维护代价较高
二级索引 ITHBase
① 索引项内容:索引列信息+rowkey
IHBase② 索引项内容:索引列信息+rowkey
CCIndex[32] 索引项内容:索引列信息+rowkey+数据信息
优点:实现简单;维护代价较低缺点:多维查询效率较低;空间冗余大
基于线性化技术的全局索引 MDHBase[33] 索引项内容:最长公共前缀+Zvalue值 优点:写入吞吐量较高;维护代价较低缺点:数据一致性维护复杂
(2)二级索引
二级索引(secondaryindex)方案主要应用于
keyvalue存储的云数据库管理系统中,如Bigtbale、
HBase等.在这类系统中,针对非键值列的二级索
引通过为索引列构建索引表实现.索引表中的键值
由原数据表中键值和索引列的组合构成,实现索引
列与原有键值的映射.查询过程中,首先根据查询条
件在索引表找到相应键值的列表,然后根据这些键值
到原数据表中定位所需数据.目前基于二级索引的实
现方案主要有ITHBase①、IHBase②和CCIndex[22].
其中ITHBase和IHBase均是开源的实现方案,二
者实现方式相似,都从HBase源码级别进行扩展,
重新定义和实现了客户端和服务端的处理逻辑,具
有强侵入性.与IHBase相比,ITHbase更关注数据
一致性,其重要特性之一是事务性.
ITHBase和IHBase两种方案中的索引表仅存
放索引列与原表的键值信息.在查询过程中,先通过
查询索引表得到键值,再根据键值到原表查找数据.
由于得到的键值大都是随机的,所以需要进行大量
的随机查找才能得到最终的查询结果,效率较低.为
了减少随机查询带来的开销,Zou等人提出了另外
一种二级索引方案:互补聚簇式索引(Complemental
ClusteringIndex),简称CCIndex[22].CCIndex把数
据的详细信息也存放在索引表中,查询时可以直
接在索引表中通过顺序扫描找到相应的数据,从
而大大减少查询时间.然而把详细信息存储在索引
表中会造成存储空间的增加.为了尽可能地减少存
储空间的开销,作者把HDFS文件块备份数设为1
来保证存储空间不会增加太多,但同时数据的容错
性又成了新的问题.为了解决这一问题,作者创建了
聚簇检验表(clusteringchecktable),和索引表一起
来实现错误发生后的快速恢复.同时,CCIndex还给
出了一种查询优化机制以支持多维查询.该优化机
制主要利用HBase中的一些元数据信息(regionto
serverinformation)来估算子查询结果的大小,根据
估算结果生成合适的查询计划,从而减少查询时间.
二级索引方案易于实现,维护代价较低,但也存
在一些不足:当索引列较多时,存储开销比较大;索
引更新代价比较高,会影响系统的吞吐量;索引对多
412 计 算 机 学 报 2013年
①②
https://github.com/hbasetrx/http://github.com/gkulbak/ibase
维查询的支持效率较低.
(3)基于线性化技术的全局索引
上述两类索引方案均需维护特定的索引结构,
当数据更新十分频繁时,索引更新维护的代价很高.
在保证系统性能的前提下,为降低索引更新维护的代
价,文献[23]提出了一种基于空间目标排序的索引方
案.其基本思想是:按照一定的规则将覆盖整个研究
区域的范围划分为大小相等的格子,并给每一个格子
分配相应的编号,用这些编号为空间目标生成一组具
有代表意义的数字.其思想是将犽维空间的实体映射
到一维空间,从而可以利用比较成熟的一维索引技
术.常见的用一维数值对多维空间目标进行排序的方
法有犣排序、Hilber曲线、位置键等.这些技术的思路
基本相同,利用一个线性序列来填充空间,构造一种
空间填充曲线.文献[23]以HBase作为数据存储方
案,用犣排序技术对数据进行排序,以犣value作为每
条
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
的键值.单纯的犣排序方法在搜索过程中会带
来一些不必要的搜索空间(falsepositivesearch),作者在此基础上利用KD树或四叉树对多维数据空间
进行划分,根据最长公共前缀计算每个子空间的名
称,并以此作为索引项对各个子空间的数据进行索
引,从而提高搜索效率.但是,该方法在进行空间划
分的过程中会产生数据一致性的问题.虽然目前有
相应的解决方案[24],但是实现起来仍比较复杂,并
且带来额外的负担.而且当数据分布不均匀时,KD
树和四叉树的深度会很大,影响查询效率.
3.2.2 查询处理从支持的查询接口和查询语言来看,早期的云
数据管理系统,例如BigTable、HBase和Cassandra仅支持一些基本的数据插入和获取接口[3,10].随后很多
公司和研究机构在丰富查询语句上开展了工作并提出
一些“类SQL语言”,例如Yahoo!的PigLatin[25],
Facebook的HQL[9],微软的SCOPE[26]和Dryad
LINQ[27]以及IBM的JAQL[28]等等.从查询处理算
法来看,目前针对云数据的查询处理和优化主要集
中在基于MapReduce框架的查询处理.MapReduce天然地支持分组聚集操作和选择操作,而连接操作的
实现则比较复杂.在分布式环境下数据传输和数据
倾斜等问题的出现使得在MapReduce上实现连接成为一个非常具有挑战性的问题,下面主要对云数据
的连接查询工作进行深入的总结分析.已有的相关工
作主要分为两类,一类是直接在MapReduce上实现连接[9,25,2833],一类是修改MapReduce框架使之更利于连接的实现[3435].下面我们分别介绍这两类工作.
(1)基于原始MapReduce的连接算法这类算法通过设计Map函数、Reduce函数和数据流来完成连接,涉及到的连接方式包括两表等
值连接[9,25,2829]、两表θ连接[30]、多表等值连接[3132]和两表集合相似性连接[30]3种类型.如表3所示,我
们首先对两表等值连接的算法进行分析比较.设参加
连接的两个表分别为犚和犛,并且犚为其中数据量较
小的表.
表3 基于原始犕犪狆犚犲犱狌犮犲的连接算法对比
算法名称 支持的连接类型 数据传输代价 作业个数 主要特性
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
重分区算法[9,25,2829] 两表等值连接 |犚|+|犛| 1
优点:算法简单,易于实现缺点:若部分连接键值对应数据量较大,会造成内存溢出和计算资源不均
改进的标准重分区算法[29]两表等值连接 |犚|+|犛| 1 优点:连接阶段对内存要求较小缺点:当出现数据倾斜时,会造成计算资源不均
广播算法[9,25,2829] 两表等值连接 狊×|犚|(狊为犛表数据所在节点个数) 1
优点:适用于连接的表中有一个较小情况,可减少数据排序和传输代价缺点:适用范围比较狭窄
半连接算法[29]两表等值连接犾×|犚狊|(犚狊为利用犛表过滤后的数据) 3 优点:减少了数据广播过程中的传输代价,可用于广播的表比较大的情况缺点:增加了对两表进行全表扫描的代价
分片半连接算法[29] 两表等值连接 ∑|犚犛犻| 3 优点:可进一步减少数据广播过程中的传输代价缺点:要对广播的表进行多次扫描
冗余重分区算法[30] 两表θ连接 最大值为4狉|犚||犛|/槡 狉(狉为reducer个数) 1
优点:可实现两表θ连接,解决重分区过程中带来的数据倾斜问题缺点:混洗过程中数据传输代价较大
数据冗余传输算法[31]
多表等值连接(星形连接,链式连接) ∑|犚犻|×∏ω( )犼(犚犻为参加连接的表,ω犼为属性共享值) 1 优点:一个MapReducejob即可实现多表的连接缺点:链式连接会引起较大数据传输代价
基于二部图连接算法[32] 多表等值连接(链式连接) ∑|犚犻.狌犽|(犚犻.狌犽为最终参加连接的数据)4狀-3(狀是表个数) 优点:数据传输代价较小缺点:MapReducejob个数较多,不支持星形连接
基于前缀过滤的算法[33]两表集合相似度连接|犚狆狉犲|+|犛狆狉犲|(犚狆狉犲犛狆狉犲为前缀过滤后的数据)3
优点:通过前缀过滤减少数据传输代价,利用索引提高连接性能缺点:只适用于字符串类型的相似连接,分词处理要重复执行多次
5122期 史英杰等:云数据管理系统中查询技术研究综述
标准重分区算法[9,25,2829].该算法类似于DBMS
中的排序合并算法,由一个MapReduce作业构成.
Mapper读入两个表的数据文件,并根据查询条件对
数据进行过滤.输出的键值对中,键值是连接的列
值,数值部分包括记录值和标签两部分,标签用于标
识该记录来自哪个表.在reduce的混洗(shuffle)过
程中,具有相同连接值的记录被分区到同一个
reducer上.针对每一个连接值,reducer根据标签把
记录分成两个集合,然后计算两个集合元素的向量
积从而完成连接.标准重分区算法在现有云数据管
理系统比较常见,Pig、Hive和Jaql均实现了这种算
法[8,25,28].该算法的一个潜在问题是针对某个连接
键值计算向量积时,两个表的相关数据都要放入内
存进行缓存.当连接键值基数比较少或者出现数据
倾斜时,会导致某个连接键值对应的数据量较大,一
方面可能会造成内存溢出,另一方面造成计算资源
分布不均匀.
改进的重分区算法[29].为了解决标准重分区算
法的内存缓存问题,该算法从两个方面进行了改进:
首先,map阶段输出的键值由连接的列值和表名的
标签值混合构成,标签值放到键值中可以保证在
reduce阶段进行排序时,来自其中一个表的数据总
是排在另一个表的前面.其次,在计算卡氏积时,内
存中只缓存较小表的数据,而另一个大表的数据以
数据流的方式读入内存.这样,算法对内存大小的要
求大大降低.
广播算法[9,25,2829].该算法将两个表中较小的
一个以广播的形式传输到另一个表数据所在的节点
上,然后在每个节点上直接进行连接.算法由一个只
有map函数而reduce函数为空的MapReduce作业
完成.作业初始化阶段对小表犚进行数据广播,然
后在Map阶段直接对数据进行Hash连接.由于广
播算法没有reduce操作,因此避免了混洗过程中的
数据传输和排序.当进行连接的两个表数据量相差
很大时,广播小表的数据传输代价将会大大小于混
洗过程中的数据传输代价,从而提高连接效率.
半连接算法[29].半连接算法基于广播算法进行
改进,旨在减少广播过程中的数据传输量.广播的表
犚中并不是所有的数据都会参与连接,因此在传输
数据之前通过半连接操作去除部分数据.该算法由
3个MapReduce作业构成.第1个作业主要扫描犛
表并生成其连接键值文件犛.狌犽.第2个作业根据文
件犛.狌犽中的键值过滤犚中每个子表的数据,生成
一系列的数据文件犚犻.第3个作业依据过滤后的犚
表数据执行广播算法.尽管半连接算法减少了广播
过程中的数据传输量,但增加了对表犛和犚的扫
描.因此具体选择哪种算法要根据连接表的大小以
及连接键值的分布情况决定.
分片半连接算法[29].该算法将半连接的粒度缩小
到犛的每个分片子表犛犻,它同样由3个MapReduce
作业构成.第1个作业生成犛的链接键值文件,与前
一个算法不同的是这个作业只有map操作,针对每
个子表犛犻生成连接键值文件犛犻.狌犽.第2个作业执
行半连接,针对每个犛犻,根据犚的匹配记录文件和
标记生成与子表犛犻相对应的广播数据文件犚犛犻.第
3个作业只有map操作,每个mapper读入对应的
数据文件犚犛犻并直接进行连接操作.与普通的半连
接算法相比,分片半连接算法在广播过程中数据传
输量较少,但是需要为每个子表犛犻过滤一次犚.
冗余重分区算法[30].该算法使用一个二维矩阵
表示两表的笛卡尔积,通过将满足连接条件的元素
设定为“真”表示各种不同连接类型的结果.所有的
连接均由一个MapReduce作业完成,通过均衡每个
reducer任务输入和输出的数据量来达到减少查询
执行时间的目的.算法根据reducer任务的个数狉将
二维矩阵分成狉个大小均衡的区域,每个reducer负
责产生相应区域的连接结果,其输入的数据量则等
于区域矩形的周长之半.与以往的连接算法不同,在
冗余重分区算法中,一个记录可能被重定向到多个
reducer任务的区域中.算法正是通过这种冗余重定
向实现了非等值连接,并减轻了数据倾斜的影响,但
增加了混洗过程中的数据传输量.
除了两表等值连接,多表等值连接在数据分析
和决策支持中的应用也非常广泛,星形连接和链式
连接是主要的两种连接形式.文献[31]提出了一种
基于“数据冗余传输”的算法.该算法只包含一个
MapReduce作业,数据的冗余传输在map之后的混
洗过程中进行,冗余传输的次数和方式则由“map
key”决定.Map键值是多个连接属性的集合,其中
每个连接属性对应着一个共享值(share),表示该属
性Hash后的桶数.Mapper输出的每个键值对可能
传输到多个reducer,其个数由Map键值中没有被
该表覆盖的连接属性共享值的乘积决定.在reduce
阶段,直接对传输到本地的数据进行连接.这种算法
比较适合星形连接或者表数不多的链式连接,随着
链式连接的表数不断增多,传输代价也成倍增加.文
献[32]提出了一种利用二部图进行连接的算法,该
算法主要应用在链式连接上.设参加链式连接表的
612 计 算 机 学 报 2013年
个数为狀,首先使用狀个MapReduce作业为每个表
生成一个二部图,然后执行2(狀-1)个作业根据二
部图按照和链式连接相反的顺序减少每个表参与连
接的记录数,最后利用浓密树提高连接的并行度,这
样最少再执行(狀-1)个作业执行连接.该算法从最
大程度上减少了连接过程中的数据传输量,但是需
要的MapReduce作业个数较多.
与等值连接不同,集合相似性连接要求计算两
个表(或者集合)中所有元素的相似度,因此减少数
据传输的方法比等值连接复杂.文献[33]提出了一
种使用MapReduce实现集合相似性连接的算法,利
用“前缀过滤”[36]原则减少参加连接的候选数据对.
该算法包括3个步骤:第1步计算用于前缀过滤的
全局词项排序,包括两个MapReduce作业,分别用
于统计和排序,第2步利用词项排序执行前缀过滤
并生成连接结果的行键值对(rowIDpair),第3步
根据行键值对取得实际的连接结果,这两步各使用
一个MapReduce作业.该算法通过前缀过滤减少了
连接过程中的数据传输代价,但其应用范围比较固
定,适用于字符串类型的相似连接.
(2)基于调整后MapReduce的连接算法
原始的MapReduce框架是一个“过滤聚集”的
过程,这对处理同构的数据源比较有效[37],然而在
处理多表连接时会遇到两方面的问题.一方面,参加
连接的数据源往往是异构的,因此在连接处理过程
中需要对不同数据源的数据进行同构化处理,例如
增加数据源标记等.同构化处理过程不但需要额外
的存储开销,而且增加了数据传输量.另一方面,原
始的MapReduce框架在处理多表连接时会产生大
量中间结果和检查点,这也增加了数据传输量.
文献[34]针对异构数据源问题对MapReduce
框架进行了扩展,在reduce步骤结束后增加了一个
merge的步骤,形成MapReduceMerge框架.
Merge的输入数据可以来自不同reducer的输出,
这样在一个MapReduce作业里可以处理多个数据
源.实现连接的过程类似于传统MapReduce上的重
分区连接,不过在map阶段不需要为不同表的数据
登记标签,merge阶段可以将两个表对应reduer输
出的排序数据进行合并连接.新加坡国立大学的研
究人员提出了MapJoinReduce框架[35],并对原始
MapReduce的处理过程进行了两方面的扩展.针对
第1个问题,文献[35]提出了“过滤连接聚集”的
编程框架,连接函数可从多个数据源读入数据进行
处理,连接函数内容和连接顺序由用户定义.针对第
2个问题,MapJoinReduce对Map完成后的混洗
过程进行了扩展,将原来的“一对一”模式扩展成“一
对多”模式,Map函数输出的中间结果一次可以传
给多个连接函数.这样通过相应的分区策略可以用
一个MapReduce作业完成多表连接,从而减少多个
作业处理过程带来的大量中间结果存储和传输
问题.
与基于原始MapReduce的连接算法相比,基于
调整MapReduc的连接算法可以通过较少的作业完
成原始MapReduc框架需要多个作业才能完成的复
杂连接,因此可以减少中间结果的数据传输和检查
点数量.对MapReduce框架的调整主要通过增加处
理函数或者扩展部分数据流程实现,这使得原来简
单易用的MapReduce框架变得复杂,也增加了编程
接口的使用难度.
3.2.3 查询优化
在数据管理系统中,对于一个给定的查询,通常
有多种处理策略,查询优化技术负责从多种策略中
找出最有效的查询处理计划.云数据管理系统中的
查询优化可以从两个方面进行:一方面在解析查询
语句并生成MapReduce计划时进行,根据数据的元
信息选择执行更为高效的MapReduce计划;另一方
面在执行MapReduce任务时进行,根据数据的统计
和资源分配等信息构造详细的任务执行策略.已有
的查询优化工作主要集中在第2个方面,下面从任
务的调度、任务的处理优化两个方面对已有工作进
行总结.
(1)调度优化
云计算是一个多用户的环境,服务提供商依据签
订的相关
协议
离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载
向用户提供不同级别的服务,因此对不
同用户提交的查询进行调度以保证服务质量是非常
必要的.另一方面,云计算环境通常是分布式异构的,
查询往往被分解成多个任务并行执行,根据资源的占
用情况和节点的运行情况对任务进行有效的调度对
查询优化有着至关重要的作用.目前针对调度的优
化已经有不少工作,根据调度对象的粒度,可以把已
有工作分成3个类型:查询调度[38]、MapReduce作
业调度[39]和MapReduce任务调度[16,40].
文献[38]提出了一种在云环境下对用户提交的
查询进行调度的算法iCBS.服务提供商和用户之间
通过签订服务等级协议SLA(ServiceLevelAgree
ment)来保障云服务的质量和可靠性,SLA定义了
为用户提供的服务标准以及服务商不能满足服务需
求的惩罚代价.SLA涉及云服务中可用性、安全性
7122期 史英杰等:云数据管理系统中查询技术研究综述
等多个方面,iCBS主要关注查询响应时间.该算法
根据查询的提交时间和该查询的SLA相关定义以
增量的方式计算其优先系数,依据优先系数对查询
进行调度,以尽量减少查询的响应时间,并减少服务
提供商因不能满足SLA需求而产生的代价,iCBS
的时间复杂度为犗(log犖),其中犖为查询的数量.
表4 调度优化算法
算法名称 调度粒度 优化目标 算法复杂度
iCBS[38] 查询 最小化SLA代价 犗(log犖)
FAIR[39]MapReduce作业 保证资源平均分配 犗(1)
CSP模型算法[40] MapReduce任务 最小化实时作业的延迟响应时间 NP完全问题
LATE[16]MapReduce任务 最小化异构环境下作业执行时间 犗(log犕)
文献[39]提出了一种对MapReduce作业进行
调度的算法FAIR来优化作业的执行效率.传统的
MapReduce作业调度方法是先进先出(FIFO)算
法,这种算法实现起来比较简单,但是在多用户的环
境下会影响作业的执行效率.FAIR提供了一种让
用户公平获取计算资源的调度算法,它使用资源池
组织作业,并把资源公平的分到资源池中.每个用户
使用一个资源池,这样每个用户可以获得等同的资
源分配.除此之外,FAIR允许赋给资源池保证最小
共享资源(guaranteedsharedresourece),这样可以
保证特定用户、群组或生产应用程序总能获取到足够
的资源.Phan等人[40]关注异构环境下MapReduce
作业的任务调度优化,把每个任务的执行时间、心跳
检测时间间隔、数据输入时间等5个变量组合成约
束集合,以最小化作业的延迟相应时间为目标函数,
将MapReduce作业调度问题转化成约束满足问题
(ConstraintSatisfactionProblem,CSP)进行解决.
文献[16]的调度粒度也是MapReduce任务,主要关
注掉队任务(stragglertask)的调度优化.在传统的
MapReduce调度中,为了防止作业执行过程中“木
桶效应”的出现,会将掉队任务进行备份执行.然而
原有的掉队任务调度方法假设集群环境的同构性和
任务执行的等速性,这在实际的云计算环境中往往
是无法保证的.基于上述问题,文献[16]提出了
LATE算法,根据所在节点的性能预测每个任务的
剩余完成时间,并选择剩余时间最长的任务作为掉
队任务进行调度.在调度过程中,如果有空闲的任务
槽位(taskslot)出现并且正在运行的任务总数小于
特定阈值,则创建该任务的执行副本.该算法需要对
所有正在运行的任务进行剩余时间的预测和排序,
算法复杂度为犗(犕),犕为正在运行的任务个数.
(2)任务处理优化
基于MapReduce实现云数据的查询可以获得
良好的扩展性、容错性以及较高的性价比,然而粗犷
的批处理模式导致基于原始MapReduce框架的查
询性能有很大的提升空间.查询任务处理的优化问
题引起了学术界的广泛关注,已有的优化措施包括
以下几种:
①任务共享.云环境中的数据查询通常是以批
处理的方式处理大规模数据,在该模式下通过查询
之间的任务共享来减少冗余计算将有效减少查询执
行时间和耗费的计算资源.Hive[9]提供了一种用户
自定义模式的数据扫描共享(scanshare),如果两个
作业的输入数据文件相同,则会创建一个新的
MapReduce作业负责数据的读入和解析,并为两个
作业产生相应的临时输入文件.这种任务共享方法增
加了一个MapReduce作业,而且还需要用户自已定
义共享函数.另一类任务共享方法是把满足共享任务
条件的作业分到一个组中,使用一个MapReduce作
业来完成原来多个作业需要完成的工作,不需要用户
自定义,也不需要产生临时文件[4144].文献[4243]主
要支持数据扫描共享,而文献[4344]则支持扫描共
享、Map输入Map输出以及Map函数的共享.
②增量计算.目前在大多数云数据管理应用
中,查询的数据规模往往随着新数据的产生而不断
增加.如何使查询流程增量化,并利用已有的查询结
果处理新的查询也是目前学术界关注的一个问题.
根据增量计算的触发方法,已有的工作可以分为两
类:对用户不透明的方法[4546]和透明的方法[42,4748].
Google的Percolator建立在GFSBigTable之上,
它通过快照隔离实现了跨行和跨表数据的一致性,
使得用户可以跟踪计算过程中的状态,并实现增量
计算[45].Yahoo!的CBP提出了一个新的并行编程
模型,用来存储和使用运行状态,并实现查询的增量
处理[46].这两种方法的基本缺陷是要求用户自己编
写动态程序来对数据进行有效的增量处理.Nova[42]
在Pig/Hadoop基础上创建了一个数据流管理器,用
来管理不同查询的数据集和查询结果,并支持有状态
的数据追加操作.当查询提交后,管理器判断该查询
任务是否可以利用已有的结果进行增量计算.与
Nova不同,HaLoop[47]和Incoop[48]从MapReduce
任务的层次进行增量计算的处理.Incoop在分布式
文件层使用基于内容的数据块划分方法来增加map
任务的重用度,并通过在combine阶段将混洗的数
据粒度减小来最大化reduce任务的重用度.
812 计 算 机 学 报 2013年
③数据组织优化.云数据管理系统中的数据被
分布到多个节点进行管理,在进行查询特别是多表
查询时,需要在各个节点间进行数据传输.如果较多
的相关数据存储在一个节点上,那么网络传输代价
就会减少,查询时间也会随之减少,因此数据的组织
方式会对查询性能产生很大的影响[49].Ha