云计算系统中查询处理及优化技术研究综述

　　0云计算的背景和意义

　　作为一种新出现的计算模式，云计算（CloudComputing）提供安全、可靠的数据存储，可以对海量数据管理提供有效支持。云计算就是使用构建于低成本硬件和网络设备基础上的大规模计算机集群，资源可在集群用户之间实现动态分配[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采用环状结构组织所有节点，并且采用consistenthashing划分数据。Dynamo保证用户总是可以执行写操作，并提供多版本数据冲突的解决方案。系统中通过参数来实现可用性和容错性的平衡，Dynamo采用冗余存储来保证容错性，当一个数据存储节点出现问题以后，数据存储即交由下一个节点进行处理。Amazon提出了具有可扩展性的云计算数据存储服务SimpleStorageServic（S3），存储数据。文献[6]提出了在S3中构建数据库的技术，包括S3中的B树索引、日志、安全等方面。

　　作为Yahoo！公司的云计算平台，PNUTs[7]重点关注了可扩展性和高可靠性，而放松了对一致性的要求。PNUTs只保证提供最终一致性，即用户可以更新数据的任何一个副本，并最终可以将更新应用到该数据的所有副本。PNUTs系统分布在全球多个数据中心，具有可扩展性，可支持记录数由几万条直至几亿条。数据容量增加不会影响性能。数据格式使用key/value存储，保持数据的弱一致性，并提供了容错机制。文献[2]介绍了Yahoo！设计使用的其他网络服务系统，包括云计算系统PNUTs[7]、ad-hoc分析查询语言Pig、云平台服务设计系统AppForce、网络信息提取系统PurpleSox、GUESTS等。文献[8]介绍了Yahoo！设计的PigLatin查询语言，该语言作用于MapReduce[3]系统中，使用类似SQL的声明语法，并实现了MapReduce机群中数据分析查询的各种基本操作。PigLatin提供了相应的调试组件，用以提高生产效率。

　　Dryad[9]是微软分布式并行计算基础平台，程序员可以利用数据中心的服务器集群对数据进行并行处理。Dryad程序员在操作数千台机器时，无需关心并行处理的细节。Dryad则设计为伸缩于各种规模的计算平台：从单台多核计算机、到由几台计算机组成的小型集群，直至拥有数千台计算机的数据中心。Dryad执行引擎负责处理大型分布式、并行应用程序中可能出现的各种难题：对计算机和其中的CPU进行调度，从通信或计算机的失败中恢复，以及数据在节点之间的传递等等。微软设计了可扩展的声明语言SCOPE[10]（StructuredComputationsOptimizedforParallelExecution），用于分析大规模数据集合。SCOPE无需用户显式的定义并行操作，实现了机群中的自动并行化。SCOPE使用关系数据和类似SQL语言的语法，并提供选择操作、内连接、外连接和聚集操作功能，同时还支持用户自定义的函数功能以及表达式的嵌套。

　　威斯康辛大学开发了Clustera[11]系统，用于提供具有可扩展性的系统功能，使得系统适用于不同的工作负载，包括计算密集型的任务、长期任务以及大规模数据集上的负载SQL查询等。Clustera使用服务器和数据库管理系统来管理工作负载信息和系统状态，以此获得通用性、可扩展性和更高性能。加利福尼亚大学设计实现了分布式文件系统Ceph[12]。Ceph在存储数据时区分数据和中间结果，并使用伪随机数据分布代替了数据定位表，以此获取更好的性能和可靠性。CephClient是Ceph文件系统的用户。CephMetadataDaemon提供了元数据服务器，而CephObjectStorageDaemon提供了实际存储（对数据和元数据两者）。最后，CephMonitor提供了集群管理。需要注意的是，Ceph客户，对象存储端点，元数据服务器（根据文件系统的容量）可以有许多，而且至少有一对冗余的监视器。

　　文献[12]针对MapReduce在处理异构数据以及关系数据连接操作时的相应缺点，将MapReduce编程模型做以改进，使其发展成为Map-Reduce-Merge模型。Map-Reduce-Merge在MR后期加入了一个Merge过程。Map-Reduce-Merge能够表达关系代数中的各种操作以及一些连接算法。

　　综上所述，现有的系统缺乏对海量数据复杂查询处理功能的支持，只能提供基于键值的有效查询处理。

　　2云计算系统中数据管理的研究工作