云计算系统中查询处理及优化技术研究综述
开篇：润墨网以专业的文秘视角，为您筛选了一篇云计算系统中查询处理及优化技术研究综述范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
收稿日期：2013-04-24
基金项目：国家自然科学基金（60903016， 60773063）；国家自然科学基金重点项目（60933001）；黑龙江省博士后资金（LBH-Z09140）。
作者简介：王金宝（1983-），男，黑龙江哈尔滨人，博士研究生，主要研究方向：云计算系统中的查询处理和索引技术；
高宏（1966-），女，黑龙江哈尔滨人，博士，教授，博士生导师，主要研究方向：图数据库，数据挖掘，云计算数据管理。
王金宝， 高宏（哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001）摘要：云计算系统中的查询及优化技术是近年来倍受关注的热点研究领域，综合了并行计算、分布式计算和查询处理及优化技术等方面的研究成果，具有广阔的应用前景。云计算系统中的查询和优化是一项基础而重要的操作，被研究者们所广泛关注，也涌现出了很多研究工作。总结了近年来云计算系统中的查询处理和查询优化方向的研究工作，讨论了现有工作的内容和需要进一步研究的方向，并提供了广泛的参考文献。
关键词：云计算； 查询处理； 查询优化
中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）04-0051-04
Survey on Query Processing and Optimization in Cloud Systems
WANG Jinbao， GAO Hong
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001，China）
Abstract：Cloud computing is a research area with many hot research topics， which is widely concerned in recent years. Cloud computing integrates the technology of parallel computing， distributed computing， query processing and optimization and etc.， and provides significant application perspective. Query processing and optimization is an essential and important operation in cloud systems， which is widely concerned by researchers， and there are also large amounts of research work on cloud query processing. This paper introduces and summarizes the research work on system， data management and query processing in cloud computing systems. This paper discusses the existing solutions and the possible future work， and provides with plenty of references.
Key words：Cloud Computing； Query Processing； Query Optimization
0云计算的背景和意义
作为一种新出现的计算模式，云计算（Cloud Computing）提供安全、可靠的数据存储，可以对海量数据管理提供有效支持。云计算就是使用构建于低成本硬件和网络设备基础上的大规模计算机集群，资源可在集群用户之间实现动态分配[1]。云计算具有以下特点：
（1）超大规模。“云”具有相当的规模，Google 云计算已经拥有100 多万台服务器，Amazon、IBM、微软、Yahoo 等的“云”均拥有几十万台服务器。企业私有云也一般拥有数百上千台服务器。“云”能赋予用户前所未有的计算能力。
（2）虚拟化。云计算支持用户在任意位置、使用各种终端获取应用服务。所请求的资源来自“云”，而不是固定的、有形的实体。应用在“云”中某处运行，但实际上用户无需了解、也勿需担心应用运行的具置。
（3）高可靠性。“云”使用了数据多副本容错、计算节点同构可互换等措施来保障服务的高可靠性。
（4）通用性。云计算不针对特定的应用，在“云”的支撑下可以构造出千变万化的应用，同一个“云”可以同时支撑不同的应用运行。
（5）高可扩展性。“云”的规模可以动态伸缩，满足应用及用户数量增长的需要。
目前，TB/PB级海量数据的查询处理技术已逐渐引起世界各国数据库领域的研究学者和工业界人士的关注重视。人们在此领域开展了一定的研究工作。但是从数据库的角度，系统的研究工作还较为少见，除了在TB/PB级海量数据的数据存储、查询语言等方面取得了一些成果外[2]，在海量数据的代数操作及其实现技术、海量数据的查询处理和优化技术等方面并未获得显著进展。传统的数据库系统既不能提供针对TB/PB 级数据的有效存储与索引，也难以提供专门针对TB/PB 级海量数据的高性能基本数据操作算法以及高性能查询处理技术。数据网格查询处理的研究虽然取得了一定的进展，但是大多数查询处理器都是针对特定应用的。数据网格查询处理的研究工作主要集中在查询处理的体系结构、基于服务思想的分布式查询处理、基于语义本体的分布式查询处理等几个方面，而却没有从数据库系统的角度进行进一步研究。由于云计算系统能够提供可靠、安全的数据存储，以及对TB/PB级海量数据的管理提供稳固、有利的支持。目前，基于云计算环境的TB/PB 级海量数据查询处理技术的相关研究工作还处于初期阶段，研究成果还未形成规模，在针对TB/PB 级海量数据的存储与索引、各种数据操作算法、查询优化处理等方面，还有大量的理论和技术问题需要解决，研究工作任重道远。
基于此，开展研究基于云计算环境的TB/PB级海量数据查询处理的关键技术和理论研究，包括TB/PB级海量数据的存储与索引、数据的高效操作算法，查询优化与处理技术具有很大的学术价值和实际意义。
1云计算系统概述
目前，将计算和存储从客户的PC端移动到大规模的服务平台（数据中心）的思想逐渐流行，而为学术界熟悉与接受。这种态势一方面可以利于用户对个人数据的管理，用户不需要对数据进行配置或备份操作，并且只要能连接到Internet就可以随时随地获得数据；另一方面也可以方便服务供应商提供更好的服务，因为供应商可以通过随时更新软件来提高数据中心的服务质量。数据中心可以实现用户以较低的代价成本获得较高质量的服务。基于这种服务模式，工业界近年来设计了众多云计算系统，用于支持网络自身服务所需的数据管理功能。第4期王金宝，等：云计算系统中查询处理及优化技术研究综述智能计算机与应用第3卷
GFS[3]集群由一个master和大量的chunkserver构成。文件被分成固定大小的块。每个块由一个不变的、全局唯一的64位的chunk-handle标识，chunk-handle是在块创建时由master分配的。ChunkServer将块当作Linux文件存储在本地磁盘并可以读/写由chunk-handle和位区间指定的数据。每一个块均可复制到多个chunkserver上。Master维护文件系统所有的元数据（metadata），包括名字空间、访问控制信息、从文件到块的映射以及块的当前位置。GFS是Google网络服务的后台数据存储系统。BigTable[4]是由Google提出的、构建于GFS之上的用于管理结构化数据的分布式数据模型，其管理的数据规模可以达到PB级。Google的众多应用都构建于BigTable之上，如网络索引、Google地球、Google商务等。BigTable数据模型使用行值、列值和时间标识作为哈希键值来定位结构化的目标数据。在分布式文件系统GFS和数据模型BigTable的基础上，Google设计了并行编程模型MapReduce[5]用来在大规模集群环境中并行地处理TB/PB级数据。MapReduce将计算任务划分成若干Map和Reduce过程，由用户编写Map和Reduce功能代码。系统提供自动的并行化处理、计算节点状态检测、任务调度、负载平衡、容错性。MapReduce为并行编程提供了很大的便利。MapReduce使用BigTable作为数据存储模型，并将数据以及中间计算结果存储在GFS中。
Amazon成功设计了Dynamo[1]，将其作为具有高可靠性的分布式存储系统，其存储数据格式为。Dynamo采用环状结构组织所有节点，并且采用consistent hashing划分数据。Dynamo保证用户总是可以执行写操作，并提供多版本数据冲突的解决方案。系统中通过参数来实现可用性和容错性的平衡，Dynamo采用冗余存储来保证容错性，当一个数据存储节点出现问题以后，数据存储即交由下一个节点进行处理。Amazon提出了具有可扩展性的云计算数据存储服务Simple Storage Servic （S3） ，存储数据。文献[6]提出了在S3中构建数据库的技术，包括S3中的B树索引、日志、安全等方面。
作为Yahoo！公司的云计算平台，PNUTs[7]重点关注了可扩展性和高可靠性，而放松了对一致性的要求。PNUTs只保证提供最终一致性，即用户可以更新数据的任何一个副本，并最终可以将更新应用到该数据的所有副本。PNUTs系统分布在全球多个数据中心，具有可扩展性，可支持记录数由几万条直至几亿条。数据容量增加不会影响性能。数据格式使用key/value存储，保持数据的弱一致性，并提供了容错机制。文献[2]介绍了Yahoo！设计使用的其他网络服务系统，包括云计算系统PNUTs[7]、ad-hoc分析查询语言Pig、云平台服务设计系统AppForce、网络信息提取系统Purple Sox、GUESTS等。文献[8]介绍了Yahoo！设计的Pig Latin查询语言，该语言作用于MapReduce[3]系统中，使用类似SQL的声明语法，并实现了MapReduce机群中数据分析查询的各种基本操作。Pig Latin提供了相应的调试组件，用以提高生产效率。
Dryad[9]是微软分布式并行计算基础平台，程序员可以利用数据中心的服务器集群对数据进行并行处理。Dryad程序员在操作数千台机器时，无需关心并行处理的细节。Dryad则设计为伸缩于各种规模的计算平台：从单台多核计算机、到由几台计算机组成的小型集群，直至拥有数千台计算机的数据中心。Dryad执行引擎负责处理大型分布式、并行应用程序中可能出现的各种难题：对计算机和其中的CPU进行调度，从通信或计算机的失败中恢复，以及数据在节点之间的传递等等。微软设计了可扩展的声明语言SCOPE[10]（Structured Computations Optimized for Parallel Execution），用于分析大规模数据集合。SCOPE无需用户显式的定义并行操作，实现了机群中的自动并行化。SCOPE使用关系数据和类似SQL语言的语法，并提供选择操作、内连接、外连接和聚集操作功能，同时还支持用户自定义的函数功能以及表达式的嵌套。
威斯康辛大学开发了Clustera[11]系统，用于提供具有可扩展性的系统功能，使得系统适用于不同的工作负载，包括计算密集型的任务、长期任务以及大规模数据集上的负载SQL查询等。Clustera使用服务器和数据库管理系统来管理工作负载信息和系统状态，以此获得通用性、可扩展性和更高性能。加利福尼亚大学设计实现了分布式文件系统Ceph[12]。Ceph在存储数据时区分数据和中间结果，并使用伪随机数据分布代替了数据定位表，以此获取更好的性能和可靠性。Ceph Client 是 Ceph 文件系统的用户。Ceph Metadata Daemon 提供了元数据服务器，而 Ceph Object Storage Daemon 提供了实际存储（对数据和元数据两者）。最后，Ceph Monitor 提供了集群管理。需要注意的是，Ceph 客户，对象存储端点，元数据服务器（根据文件系统的容量）可以有许多，而且至少有一对冗余的监视器。
文献[12]针对MapReduce在处理异构数据以及关系数据连接操作时的相应缺点，将MapReduce编程模型做以改进，使其发展成为Map-Reduce-Merge模型。Map-Reduce-Merge在MR后期加入了一个Merge过程。Map-Reduce-Merge能够表达关系代数中的各种操作以及一些连接算法。
综上所述，现有的系统缺乏对海量数据复杂查询处理功能的支持，只能提供基于键值的有效查询处理。
2云计算系统中数据管理的研究工作
MapReduce被工业界广泛接受，除了设计者Google使用MapReduce之外，Yahoo！使用开源的项目Hadoop实现了MapReduce的功能，并作为内部数据并行处理的基础结构。大量研究人员在MapReduce系统中展开工作，研究各种数据管理技术在MapReduce中的实现方法以及MapReduce在数据管理领域的功能角色。如文献[13]设计了高级的数据流系统Pig，设计目标是在SQL和MapReduce之间建立联系通道。Pig系统实现了MapReduce系统中各种SQL基本操作的具体实现。文献[14]在MapReduce系统中提出了大规模数据集上的学习树模型的并行算法框架PLANET，定义了一系列分布式计算并在MapReduce中实现了其中的一个算法。文献[15]同样致力于MapReduce中SQL 语言的实现，并且实现了Aster Data System nCluster数据库系统，支持多种用户自定义函数功能。文献[16]评估了MapReduce在多核或者多处理器系统中的适用性，并设计了Phoenix作为MapReduce在共享内存系统中的改进版本，其功能主要包括自动管理进程建立、动态任务调度、数据划分以及处理器之间的容错性。文献[17]讨论了并行数据库和MapReduce之间的关系。文章指出并行数据库和MapReduce是互补型技术，两者可以互相借鉴，获取更好的工作效率。并行数据库和MapReduce都不能完全取代对方。文献[18]研究了MapReduce系统中的自动优化问题，用以减轻调节系统的复杂性。文献[19]通过测试研究MapReduce的系统性能，发现通过调整五种主要的设计因素，MapReduce的系统性能可以获得大幅提升（2.5-3.5倍），而与并行数据库系统的性能差异则明显缩小。文献[20]在MapReduce中使用三个阶段的Map-Reduce方法实现了并行集合的相似性连接操作。算法通过有效的数据划分平衡了工作负载并且实现了最小化备份参数。文献[20]给出了算法在内存资源不足情况下的实现方法。文献[21]讨论了在现有云计算平台（如Amazon的EC2）中部署数据管理系统的约束限制及机遇场合。论文提出如下观点，大规模数据分析、决策支持系统与事务处理数据库系统相比，更能利用云计算系统的优势。同时指出，利用二者结合的无共享并行数据库是云系统中数据库研究的切实有效的出发点。文献[22]使用大规模数据分析任务剖析比较了并行数据库和MapReduce的性能。与MapReduce相比，并行数据库的优势主要表现在数据模式的支持，索引等提升性能的技术，SQL语言的表达能力。而MapReduce的优势在于自动的并行化，任务的灵活性，高可靠的容错能力，在异构环境中的运行能力。实验表明，在集群同构且节点不发生失效的情况下，并行数据库的性能要远远优于MapReduce。而在节点频繁失效的情况下，并行数据库的性能就会出现显著下降，而MapReduce的性能影响则较小。HadoopDB[23]将数据库管理系统和MapReduce结合，使用PostgreSQL开源数据库管理系统作为MapReduce节点管理系统，而且使用Hadoop提供的MapReduce框架连接系统中的节点。HadoopDB具有较快的单机处理速度优势，并且兼有MapReduce的异构有效性、容错性的优势。HadoopDB支持SQL语言。
3无线传感器网络上数据聚集调度的研究工作
文献[24]提出了云计算数据存储系统中批量插入数据的有效方法，系统中的数据按照key值范围水平划分并分布在各个存储节点中。文献[24]考虑了在数据插入过程中的数据迁移代价和插入后系统吞吐量之间的折中，而且也证明了问题属于NP-hard问题。文献[25]研究了如何在系统中有效的并行化范围查询的问题。本文考虑到存储系统的客户应用消耗数据的速度与查询获取结果的速度之间的差异，通过动态适应的方式增加或减少并行处理范围内实现而需查询的节点个数，以此使得系统并行获取足够的查询结果发送到客户应用。文献[26]实现了在MapReduce中构建分布式数据流处理的系统。文献[27]研究了在大规模分布式数据管理系统中使用索引和视图的机制。本文使用两种视图，即远程视图表和本地视图表，并以此提供了系统吞吐量和视图更新速度之间的折中处理，同时也给出了构建和维护式图标以及使用视图回答聚集查询、连接查询、选择查询的方法。文献[28]设计了可扩展的分布式关系表系统Crescando用以支持大量的查询和更新，并提供可预测的操作延迟。Crescando使用并行协作的扫描指令以及数据流中“查询-数据”连接技术保证工作负载的反应时间和结果的新度。Crescando在处理各种工作负载时不能取得最优性能，但是在工作负载未知，而且变化的情况下，Crescando却具有独特优势。文献[29]设计了云计算数据存储系统Spinnaker，在数据的可获取性和一致性之间达到了更新的折中。Spinnaker使用一致性备份协议取得了高可获取性和timeline一致性，并在元组级的事务处理中实现了ACID。与Dynamo相比，Spinnaker具有更好的数据一致性，而只需付出较小的性能代价。文献[30]设计了云计算平台测试的模拟软件CloudSim，用于简化云计算中应用开发的性能评估。文献[31，32]设计了云计算平台中的单维索引CG-Index，用以支持key查询和范围查询。CG-Index通过两级索引结构，在本地构建B-Tree索引并选择若干B-Tree节点为全局索引。系统中的节点则组织成BATON Overlay结构，其的全局索引负责回答系统中收到的查询。文献[33]设计了ecStore，将数据对象分布并备份于云计算集群环境中。文献[34]设计了P2P数据管理系统中在线近似聚集的处理算法，通过不断获取数据，提高计算结果的精度。文献[35]比较了现有云计算平台的架构对构建云数据库的影响，其主要研究对象是在线事务处理而不是在线分析处理。结果表明现有的主流云计算系统具有不同的架构，对于相同的工作负载也具有不同的性能。文献[36]提出了一种分布式的B树索引。该索引结构将数据索引缓存在各个存储节点中，回答查询时，首先检查缓存内容是否过期，如果还未过期，则直接在本地回答查询，否则需要执行相应更新操作。这种索引结构在数据更新快的情况下，效率严重下降。
4结束语
目前，云计算系统中数据管理方面的研究已经引起广泛关注和浓厚兴趣，而查询处理和优化技术则是其中最为基础、且最为重要的研究内容，对此已经开展了较为详尽与深入的研究工作。本文中，归纳并总结了云计算系统、数据管理以及查询和索引技术等方向已有的研究，并对可能的研究方向进行了简要的分析与阐述。
参考文献：
[1]DECANDIA G， HASTORUN D， JAMPANI M， et al. Dynamo： Amazon’s highly available key-value store. SOSP’07 October 14-17， Stevenson， Washington， USA，2007.
[2]Community Systems Group Yahoo！ Research， Community Systems Research at Yahoo！， SIGMOD Record， September 2007，36（3）.
[3]GHEMAWAT S， GOBIOFF H， LEUNG S T. The Google File System， SOSP’03， October 19-22， Bolton Landing， New York， USA，2003.
[4]CHANG F， DEAN J， GHEMAWAT S， et al. BigTable： A Distributed Storage System for Structured Data[C]∥ USENIX Symposium on Operating Systems Design and Implementation （OSDI） ，2006.
[5]DEAN J， GHEMAWAT S. MapReduce： Simplified Data Processing on Large Clusters. SODI ，2004.
[6]BRANTNER M， FLORESCU D， GRAF D， et al. Building Database on S3. SIGMOD’08.
[7]COOPER B F， RAMAKRISHNAN R， SRIVASTAVA U， et al. PNUTS： Yahoo！’s hosted data serving platform. VLDB’08， august 24-30， Auckland， New Zealand， 2008.
[8]OLSTON C， REED B， SRIVASTAVA U， et al. Pig Latin： A not-so-foreign language for data processing， SIGMOD’08， June 9-12， Vancouver， BC， Canada， 2008.
[9]ISARD M， BUDIU M， YU Yuan. Dryad： distributed data-parallel programs from sequential building blocks. EuroSys’07， march 21-23， Lisboa， Portugal， 2007.
[10]CHAIKEN R， JENKINS B， LARSON P-A， et al. SCOPE： easy and efficient parallel processing of massive data sets， PVLDB’08， August 23-28， Auckland， New Zealand.
[11]DEWITT D J， ROBINSON E， SHANKAR S， et al. Clustera： an integrated computation and data management system， PVLDB’08， August 23-28， Auckland， New Zealand， 2008.
[12]YANG H， DASDAN A， HSIAO R-L， et al. Map-reduce-merge： simplied relational data processing on large clusters. SIGMOD’07， June 12-14， Beiing， China.
[13]GATE A F， NATKOVICH O， CHOPRA S， et al. Building a high-level dataflow system on top of map-reduce： the pig experience. VLDB’09， August 24-28， Lyon， France， 2009.
[14]PANDA B， HERBACH J S， BASU S， et al. PLANET： massively parallel learning of tree ensembles with MapReduce. VLDB’09， August 24-28， Lyon， France， 2009.
[15]FRIEDMAN E， PAWLOWSKI P， CIESLEWICZ J. SQL/MapReduce： a practical approach to self-describeing， polymorphic， and parallelizable user-defined functions. VLDB’09， August 24-28， Lyon， France， 2009.
[16]RANGER C， RAGHURAMAN R， PENMETSA A， et al. Evaluating MapReduce for Multi-core and Multiprocessor Systems[C]∥HPCA '07 Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture.
[17]STONEBRAKER M， ABADI D， DEWETT D J， et al. MapReduce and Parallel DBMSs： Friends or Foes？ Communication of the ACM， January， Vol. 53， No. 1.
[18]BABU S. Towards Automatic Optimization of MapReduce Programs， SoCC’10， June 10-11， Indianapolis， USA， 2010.
[19]JIANG Dawei， OOI B C， SHI Lei， et al. The performance of mapreduce： an in-depth study[C]// Proceedings of the VLDB Endowment， Vol 3， No. 1.
[20]BERNICA R， CAREY M J， LI Chen. Efficient parallel set-similarity joins using MapReduce. SIGMOD’10， June 6-11， Indianapolis， USA， 2010.
[21]ABADI D J. Data management in the Cloud： limitations and opportunities. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering， 2009.
[22]PAVLO A， PAULSON E， RASIN A， et al. A comparison of approaches to large-scale data analysis， SIGMOD’09， June 29- July 2， Providence， Rhode Island， USA， 2009.
[23]ABOUZEID A， BAJDA-PAWLIKOWSKI K， ABADI D， et al. HadoopDB： an architectural hybrid of MapReduce and DBMS technologies for analytical workloads. VLDB’09， August 24-28， Lyon， France， 2009.
[24]SILBERSTAIN A， COOPER B F， SRIVASTAVA U， et al. Efficient Bulk insertion into a distributed ordered table. SIGMOD’08， June 9-12， Vancouver， BC， Canada.
[25]VIFUSSON Y， SILBERSTEIN A， COPPER B F， et al. Adaptively parallelizing distributed range queries. VLDB’09， August 24-28， Lyon， France， 2009.
[26]LOGOTHETIS D， YOCUM K. Ad-Hoc data Processing in the Cloud. PVLDB’08， Auckland， New Zealand.
[27]AGRAWAL P， SILBERSTEIN A， COOPER B F. Asynchronous view for VLSD databases. SIGMOD’09， June 29- July 2， Providence， Rhode Island， USA， 2009.
[28]UNTERBRUNNER P， GIANNIKIS G， ALONSO G， et al. Predictable performance for unpredictable workloads. VLDB’09， August 24-28， Lyon， France， 2009.
[29]RAO Jun， SHEKITA E J， TATA S. Spinnaker： a consistent and highly available cloud data store，.VLDB’09， August 24-28， Lyon， France， 2009.
[30]CALHEIROS R N， RANJAN R， DE ROSE C A F， et al. CloudSim： a novel framework for modeling and simulation of cloud computing infrastructures and services.
[31]WU Sai， JIANG Dawei， OOI B C， et al. Efficient B-tree based indexing for Cloud data processing. VLDB， 2010.
[32]WU Sai， WU Kun-lung. An indexing framework for efficient retrieval on the cloud[J]. IEEE Data engineering Bulletin， 2009，32（1）： 77-84.
[33]VO H T， CHEN Chun， OOI B C. Towards elastic transactional Cloud storage with range query support. VLDB， 2010.
[34]WU Sai， JIANG Shouxu， OOI B C， et al. Distributed online aggregations. VLDB’09， Lyon， France.
[35]KOSSMANN D， KRASKA T， LOESING S. An evaluation of alternative architectures for transaction processing in the Cloud. SIGMOD’10， June 6-11， Indianapolis， USA， 2010.
[36]AGUILERA M K， GOALB W， SHAH M A. A practical scalable distributed B-Tree. VLDB’08， August 24-30， Auckland， New Zealand， 2008.