云計算系統(tǒng)中查詢處理及優(yōu)化技術(shù)研究綜述
2013-01-01 00:00:00王金寶高宏
智能計算機與應(yīng)用 2013年4期
收稿日期：2013-04-24
基金項目：國家自然科學(xué)基金（60903016， 60773063）；國家自然科學(xué)基金重點項目（60933001）；黑龍江省博士后資金（LBH-Z09140）。
作者簡介：王金寶（1983-），男，黑龍江哈爾濱人，博士研究生，主要研究方向：云計算系統(tǒng)中的查詢處理和索引技術(shù)；
高宏（1966-），女，黑龍江哈爾濱人，博士，教授，博士生導(dǎo)師，主要研究方向：圖數(shù)據(jù)庫，數(shù)據(jù)挖掘，云計算數(shù)據(jù)管理。
云計算系統(tǒng)中查詢處理及優(yōu)化技術(shù)研究綜述
王金寶， 高宏（哈爾濱工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001）摘要：云計算系統(tǒng)中的查詢及優(yōu)化技術(shù)是近年來倍受關(guān)注的熱點研究領(lǐng)域，綜合了并行計算、分布式計算和查詢處理及優(yōu)化技術(shù)等方面的研究成果，具有廣闊的應(yīng)用前景。云計算系統(tǒng)中的查詢和優(yōu)化是一項基礎(chǔ)而重要的操作，被研究者們所廣泛關(guān)注，也涌現(xiàn)出了很多研究工作?？偨Y(jié)了近年來云計算系統(tǒng)中的查詢處理和查詢優(yōu)化方向的研究工作，討論了現(xiàn)有工作的內(nèi)容和需要進一步研究的方向，并提供了廣泛的參考文獻。
關(guān)鍵詞：云計算； 查詢處理； 查詢優(yōu)化
中圖分類號：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云計算的背景和意義
作為一種新出現(xiàn)的計算模式，云計算（Cloud Computing）提供安全、可靠的數(shù)據(jù)存儲，可以對海量數(shù)據(jù)管理提供有效支持。云計算就是使用構(gòu)建于低成本硬件和網(wǎng)絡(luò)設(shè)備基礎(chǔ)上的大規(guī)模計算機集群，資源可在集群用戶之間實現(xiàn)動態(tài)分配[1]。云計算具有以下特點：
（1）超大規(guī)模?！霸啤本哂邢喈?dāng)?shù)囊?guī)模，Google 云計算已經(jīng)擁有100 多萬臺服務(wù)器，Amazon、IBM、微軟、Yahoo 等的“云”均擁有幾十萬臺服務(wù)器。企業(yè)私有云也一般擁有數(shù)百上千臺服務(wù)器。“云”能賦予用戶前所未有的計算能力。
（2）虛擬化。云計算支持用戶在任意位置、使用各種終端獲取應(yīng)用服務(wù)。所請求的資源來自“云”，而不是固定的、有形的實體。應(yīng)用在“云”中某處運行，但實際上用戶無需了解、也勿需擔(dān)心應(yīng)用運行的具體位置。
（3）高可靠性?！霸啤笔褂昧藬?shù)據(jù)多副本容錯、計算節(jié)點同構(gòu)可互換等措施來保障服務(wù)的高可靠性。
（4）通用性。云計算不針對特定的應(yīng)用，在“云”的支撐下可以構(gòu)造出千變?nèi)f化的應(yīng)用，同一個“云”可以同時支撐不同的應(yīng)用運行。
（5）高可擴展性?！霸啤钡囊?guī)?？梢詣討B(tài)伸縮，滿足應(yīng)用及用戶數(shù)量增長的需要。
目前，TB/PB級海量數(shù)據(jù)的查詢處理技術(shù)已逐漸引起世界各國數(shù)據(jù)庫領(lǐng)域的研究學(xué)者和工業(yè)界人士的關(guān)注重視。人們在此領(lǐng)域開展了一定的研究工作。但是從數(shù)據(jù)庫的角度，系統(tǒng)的研究工作還較為少見，除了在TB/PB級海量數(shù)據(jù)的數(shù)據(jù)存儲、查詢語言等方面取得了一些成果外[2]，在海量數(shù)據(jù)的代數(shù)操作及其實現(xiàn)技術(shù)、海量數(shù)據(jù)的查詢處理和優(yōu)化技術(shù)等方面并未獲得顯著進展。傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)既不能提供針對TB/PB 級數(shù)據(jù)的有效存儲與索引，也難以提供專門針對TB/PB 級海量數(shù)據(jù)的高性能基本數(shù)據(jù)操作算法以及高性能查詢處理技術(shù)。數(shù)據(jù)網(wǎng)格查詢處理的研究雖然取得了一定的進展，但是大多數(shù)查詢處理器都是針對特定應(yīng)用的。數(shù)據(jù)網(wǎng)格查詢處理的研究工作主要集中在查詢處理的體系結(jié)構(gòu)、基于服務(wù)思想的分布式查詢處理、基于語義本體的分布式查詢處理等幾個方面，而卻沒有從數(shù)據(jù)庫系統(tǒng)的角度進行進一步研究。由于云計算系統(tǒng)能夠提供可靠、安全的數(shù)據(jù)存儲，以及對TB/PB級海量數(shù)據(jù)的管理提供穩(wěn)固、有利的支持。目前，基于云計算環(huán)境的TB/PB 級海量數(shù)據(jù)查詢處理技術(shù)的相關(guān)研究工作還處于初期階段，研究成果還未形成規(guī)模，在針對TB/PB 級海量數(shù)據(jù)的存儲與索引、各種數(shù)據(jù)操作算法、查詢優(yōu)化處理等方面，還有大量的理論和技術(shù)問題需要解決，研究工作任重道遠。
基于此，開展研究基于云計算環(huán)境的TB/PB級海量數(shù)據(jù)查詢處理的關(guān)鍵技術(shù)和理論研究，包括TB/PB級海量數(shù)據(jù)的存儲與索引、數(shù)據(jù)的高效操作算法，查詢優(yōu)化與處理技術(shù)具有很大的學(xué)術(shù)價值和實際意義。
1云計算系統(tǒng)概述
目前，將計算和存儲從客戶的PC端移動到大規(guī)模的服務(wù)平臺（數(shù)據(jù)中心）的思想逐漸流行，而為學(xué)術(shù)界熟悉與接受。這種態(tài)勢一方面可以利于用戶對個人數(shù)據(jù)的管理，用戶不需要對數(shù)據(jù)進行配置或備份操作，并且只要能連接到Internet就可以隨時隨地獲得數(shù)據(jù)；另一方面也可以方便服務(wù)供應(yīng)商提供更好的服務(wù)，因為供應(yīng)商可以通過隨時更新軟件來提高數(shù)據(jù)中心的服務(wù)質(zhì)量。數(shù)據(jù)中心可以實現(xiàn)用戶以較低的代價成本獲得較高質(zhì)量的服務(wù)?；谶@種服務(wù)模式，工業(yè)界近年來設(shè)計了眾多云計算系統(tǒng)，用于支持網(wǎng)絡(luò)自身服務(wù)所需的數(shù)據(jù)管理功能。第4期王金寶，等：云計算系統(tǒng)中查詢處理及優(yōu)化技術(shù)研究綜述智能計算機與應(yīng)用第3卷
GFS[3]集群由一個master和大量的chunkserver構(gòu)成。文件被分成固定大小的塊。每個塊由一個不變的、全局唯一的64位的chunk-handle標識，chunk-handle是在塊創(chuàng)建時由master分配的。ChunkServer將塊當(dāng)作Linux文件存儲在本地磁盤并可以讀/寫由chunk-handle和位區(qū)間指定的數(shù)據(jù)。每一個塊均可復(fù)制到多個chunkserver上。Master維護文件系統(tǒng)所有的元數(shù)據(jù)（metadata），包括名字空間、訪問控制信息、從文件到塊的映射以及塊的當(dāng)前位置。GFS是Google網(wǎng)絡(luò)服務(wù)的后臺數(shù)據(jù)存儲系統(tǒng)。BigTable[4]是由Google提出的、構(gòu)建于GFS之上的用于管理結(jié)構(gòu)化數(shù)據(jù)的分布式數(shù)據(jù)模型，其管理的數(shù)據(jù)規(guī)?？梢赃_到PB級。Google的眾多應(yīng)用都構(gòu)建于BigTable之上，如網(wǎng)絡(luò)索引、Google地球、Google商務(wù)等。BigTable數(shù)據(jù)模型使用行值、列值和時間標識作為哈希鍵值來定位結(jié)構(gòu)化的目標數(shù)據(jù)。在分布式文件系統(tǒng)GFS和數(shù)據(jù)模型BigTable的基礎(chǔ)上，Google設(shè)計了并行編程模型MapReduce[5]用來在大規(guī)模集群環(huán)境中并行地處理TB/PB級數(shù)據(jù)。MapReduce將計算任務(wù)劃分成若干Map和Reduce過程，由用戶編寫Map和Reduce功能代碼。系統(tǒng)提供自動的并行化處理、計算節(jié)點狀態(tài)檢測、任務(wù)調(diào)度、負載平衡、容錯性。MapReduce為并行編程提供了很大的便利。MapReduce使用BigTable作為數(shù)據(jù)存儲模型，并將數(shù)據(jù)以及中間計算結(jié)果存儲在GFS中。
Amazon成功設(shè)計了Dynamo[1]，將其作為具有高可靠性的分布式存儲系統(tǒng)，其存儲數(shù)據(jù)格式為
作為Yahoo！公司的云計算平臺，PNUTs[7]重點關(guān)注了可擴展性和高可靠性，而放松了對一致性的要求。PNUTs只保證提供最終一致性，即用戶可以更新數(shù)據(jù)的任何一個副本，并最終可以將更新應(yīng)用到該數(shù)據(jù)的所有副本。PNUTs系統(tǒng)分布在全球多個數(shù)據(jù)中心，具有可擴展性，可支持記錄數(shù)由幾萬條直至幾億條。數(shù)據(jù)容量增加不會影響性能。數(shù)據(jù)格式使用key/value存儲，保持數(shù)據(jù)的弱一致性，并提供了容錯機制。文獻[2]介紹了Yahoo！設(shè)計使用的其他網(wǎng)絡(luò)服務(wù)系統(tǒng)，包括云計算系統(tǒng)PNUTs[7]、ad-hoc分析查詢語言Pig、云平臺服務(wù)設(shè)計系統(tǒng)AppForce、網(wǎng)絡(luò)信息提取系統(tǒng)Purple Sox、GUESTS等。文獻[8]介紹了Yahoo！設(shè)計的Pig Latin查詢語言，該語言作用于MapReduce[3]系統(tǒng)中，使用類似SQL的聲明語法，并實現(xiàn)了MapReduce機群中數(shù)據(jù)分析查詢的各種基本操作。Pig Latin提供了相應(yīng)的調(diào)試組件，用以提高生產(chǎn)效率。
Dryad[9]是微軟分布式并行計算基礎(chǔ)平臺，程序員可以利用數(shù)據(jù)中心的服務(wù)器集群對數(shù)據(jù)進行并行處理。Dryad程序員在操作數(shù)千臺機器時，無需關(guān)心并行處理的細節(jié)。Dryad則設(shè)計為伸縮于各種規(guī)模的計算平臺：從單臺多核計算機、到由幾臺計算機組成的小型集群，直至擁有數(shù)千臺計算機的數(shù)據(jù)中心。Dryad執(zhí)行引擎負責(zé)處理大型分布式、并行應(yīng)用程序中可能出現(xiàn)的各種難題：對計算機和其中的CPU進行調(diào)度，從通信或計算機的失敗中恢復(fù)，以及數(shù)據(jù)在節(jié)點之間的傳遞等等。微軟設(shè)計了可擴展的聲明語言SCOPE[10]（Structured Computations Optimized for Parallel Execution），用于分析大規(guī)模數(shù)據(jù)集合。SCOPE無需用戶顯式的定義并行操作，實現(xiàn)了機群中的自動并行化。SCOPE使用關(guān)系數(shù)據(jù)和類似SQL語言的語法，并提供選擇操作、內(nèi)連接、外連接和聚集操作功能，同時還支持用戶自定義的函數(shù)功能以及表達式的嵌套。
威斯康辛大學(xué)開發(fā)了Clustera[11]系統(tǒng)，用于提供具有可擴展性的系統(tǒng)功能，使得系統(tǒng)適用于不同的工作負載，包括計算密集型的任務(wù)、長期任務(wù)以及大規(guī)模數(shù)據(jù)集上的負載SQL查詢等。Clustera使用服務(wù)器和數(shù)據(jù)庫管理系統(tǒng)來管理工作負載信息和系統(tǒng)狀態(tài)，以此獲得通用性、可擴展性和更高性能。加利福尼亞大學(xué)設(shè)計實現(xiàn)了分布式文件系統(tǒng)Ceph[12]。Ceph在存儲數(shù)據(jù)時區(qū)分數(shù)據(jù)和中間結(jié)果，并使用偽隨機數(shù)據(jù)分布代替了數(shù)據(jù)定位表，以此獲取更好的性能和可靠性。Ceph Client 是 Ceph 文件系統(tǒng)的用戶。Ceph Metadata Daemon 提供了元數(shù)據(jù)服務(wù)器，而 Ceph Object Storage Daemon 提供了實際存儲（對數(shù)據(jù)和元數(shù)據(jù)兩者）。最后，Ceph Monitor 提供了集群管理。需要注意的是，Ceph 客戶，對象存儲端點，元數(shù)據(jù)服務(wù)器（根據(jù)文件系統(tǒng)的容量）可以有許多，而且至少有一對冗余的監(jiān)視器。
文獻[12]針對MapReduce在處理異構(gòu)數(shù)據(jù)以及關(guān)系數(shù)據(jù)連接操作時的相應(yīng)缺點，將MapReduce編程模型做以改進，使其發(fā)展成為Map-Reduce-Merge模型。Map-Reduce-Merge在MR后期加入了一個Merge過程。Map-Reduce-Merge能夠表達關(guān)系代數(shù)中的各種操作以及一些連接算法。
綜上所述，現(xiàn)有的系統(tǒng)缺乏對海量數(shù)據(jù)復(fù)雜查詢處理功能的支持，只能提供基于鍵值的有效查詢處理。
2云計算系統(tǒng)中數(shù)據(jù)管理的研究工作
MapReduce被工業(yè)界廣泛接受，除了設(shè)計者Google使用MapReduce之外，Yahoo！使用開源的項目Hadoop實現(xiàn)了MapReduce的功能，并作為內(nèi)部數(shù)據(jù)并行處理的基礎(chǔ)結(jié)構(gòu)。大量研究人員在MapReduce系統(tǒng)中展開工作，研究各種數(shù)據(jù)管理技術(shù)在MapReduce中的實現(xiàn)方法以及MapReduce在數(shù)據(jù)管理領(lǐng)域的功能角色。如文獻[13]設(shè)計了高級的數(shù)據(jù)流系統(tǒng)Pig，設(shè)計目標是在SQL和MapReduce之間建立聯(lián)系通道。Pig系統(tǒng)實現(xiàn)了MapReduce系統(tǒng)中各種SQL基本操作的具體實現(xiàn)。文獻[14]在MapReduce系統(tǒng)中提出了大規(guī)模數(shù)據(jù)集上的學(xué)習(xí)樹模型的并行算法框架PLANET，定義了一系列分布式計算并在MapReduce中實現(xiàn)了其中的一個算法。文獻[15]同樣致力于MapReduce中SQL 語言的實現(xiàn)，并且實現(xiàn)了Aster Data System nCluster數(shù)據(jù)庫系統(tǒng)，支持多種用戶自定義函數(shù)功能。文獻[16]評估了MapReduce在多核或者多處理器系統(tǒng)中的適用性，并設(shè)計了Phoenix作為MapReduce在共享內(nèi)存系統(tǒng)中的改進版本，其功能主要包括自動管理進程建立、動態(tài)任務(wù)調(diào)度、數(shù)據(jù)劃分以及處理器之間的容錯性。文獻[17]討論了并行數(shù)據(jù)庫和MapReduce之間的關(guān)系。文章指出并行數(shù)據(jù)庫和MapReduce是互補型技術(shù)，兩者可以互相借鑒，獲取更好的工作效率。并行數(shù)據(jù)庫和MapReduce都不能完全取代對方。文獻[18]研究了MapReduce系統(tǒng)中的自動優(yōu)化問題，用以減輕調(diào)節(jié)系統(tǒng)的復(fù)雜性。文獻[19]通過測試研究MapReduce的系統(tǒng)性能，發(fā)現(xiàn)通過調(diào)整五種主要的設(shè)計因素，MapReduce的系統(tǒng)性能可以獲得大幅提升（2.5-3.5倍），而與并行數(shù)據(jù)庫系統(tǒng)的性能差異則明顯縮小。文獻[20]在MapReduce中使用三個階段的Map-Reduce方法實現(xiàn)了并行集合的相似性連接操作。算法通過有效的數(shù)據(jù)劃分平衡了工作負載并且實現(xiàn)了最小化備份參數(shù)。文獻[20]給出了算法在內(nèi)存資源不足情況下的實現(xiàn)方法。文獻[21]討論了在現(xiàn)有云計算平臺（如Amazon的EC2）中部署數(shù)據(jù)管理系統(tǒng)的約束限制及機遇場合。論文提出如下觀點，大規(guī)模數(shù)據(jù)分析、決策支持系統(tǒng)與事務(wù)處理數(shù)據(jù)庫系統(tǒng)相比，更能利用云計算系統(tǒng)的優(yōu)勢。同時指出，利用二者結(jié)合的無共享并行數(shù)據(jù)庫是云系統(tǒng)中數(shù)據(jù)庫研究的切實有效的出發(fā)點。文獻[22]使用大規(guī)模數(shù)據(jù)分析任務(wù)剖析比較了并行數(shù)據(jù)庫和MapReduce的性能。與MapReduce相比，并行數(shù)據(jù)庫的優(yōu)勢主要表現(xiàn)在數(shù)據(jù)模式的支持，索引等提升性能的技術(shù)，SQL語言的表達能力。而MapReduce的優(yōu)勢在于自動的并行化，任務(wù)的靈活性，高可靠的容錯能力，在異構(gòu)環(huán)境中的運行能力。實驗表明，在集群同構(gòu)且節(jié)點不發(fā)生失效的情況下，并行數(shù)據(jù)庫的性能要遠遠優(yōu)于MapReduce。而在節(jié)點頻繁失效的情況下，并行數(shù)據(jù)庫的性能就會出現(xiàn)顯著下降，而MapReduce的性能影響則較小。HadoopDB[23]將數(shù)據(jù)庫管理系統(tǒng)和MapReduce結(jié)合，使用PostgreSQL開源數(shù)據(jù)庫管理系統(tǒng)作為MapReduce節(jié)點管理系統(tǒng)，而且使用Hadoop提供的MapReduce框架連接系統(tǒng)中的節(jié)點。HadoopDB具有較快的單機處理速度優(yōu)勢，并且兼有MapReduce的異構(gòu)有效性、容錯性的優(yōu)勢。HadoopDB支持SQL語言。
3無線傳感器網(wǎng)絡(luò)上數(shù)據(jù)聚集調(diào)度的研究工作
文獻[24]提出了云計算數(shù)據(jù)存儲系統(tǒng)中批量插入數(shù)據(jù)的有效方法，系統(tǒng)中的數(shù)據(jù)按照key值范圍水平劃分并分布在各個存儲節(jié)點中。文獻[24]考慮了在數(shù)據(jù)插入過程中的數(shù)據(jù)遷移代價和插入后系統(tǒng)吞吐量之間的折中，而且也證明了問題屬于NP-hard問題。文獻[25]研究了如何在系統(tǒng)中有效的并行化范圍查詢的問題。本文考慮到存儲系統(tǒng)的客戶應(yīng)用消耗數(shù)據(jù)的速度與查詢獲取結(jié)果的速度之間的差異，通過動態(tài)適應(yīng)的方式增加或減少并行處理范圍內(nèi)實現(xiàn)而需查詢的節(jié)點個數(shù)，以此使得系統(tǒng)并行獲取足夠的查詢結(jié)果發(fā)送到客戶應(yīng)用。文獻[26]實現(xiàn)了在MapReduce中構(gòu)建分布式數(shù)據(jù)流處理的系統(tǒng)。文獻[27]研究了在大規(guī)模分布式數(shù)據(jù)管理系統(tǒng)中使用索引和視圖的機制。本文使用兩種視圖，即遠程視圖表和本地視圖表，并以此提供了系統(tǒng)吞吐量和視圖更新速度之間的折中處理，同時也給出了構(gòu)建和維護式圖標以及使用視圖回答聚集查詢、連接查詢、選擇查詢的方法。文獻[28]設(shè)計了可擴展的分布式關(guān)系表系統(tǒng)Crescando用以支持大量的查詢和更新，并提供可預(yù)測的操作延遲。Crescando使用并行協(xié)作的掃描指令以及數(shù)據(jù)流中“查詢-數(shù)據(jù)”連接技術(shù)保證工作負載的反應(yīng)時間和結(jié)果的新度。Crescando在處理各種工作負載時不能取得最優(yōu)性能，但是在工作負載未知，而且變化的情況下，Crescando卻具有獨特優(yōu)勢。文獻[29]設(shè)計了云計算數(shù)據(jù)存儲系統(tǒng)Spinnaker，在數(shù)據(jù)的可獲取性和一致性之間達到了更新的折中。Spinnaker使用一致性備份協(xié)議取得了高可獲取性和timeline一致性，并在元組級的事務(wù)處理中實現(xiàn)了ACID。與Dynamo相比，Spinnaker具有更好的數(shù)據(jù)一致性，而只需付出較小的性能代價。文獻[30]設(shè)計了云計算平臺測試的模擬軟件CloudSim，用于簡化云計算中應(yīng)用開發(fā)的性能評估。文獻[31，32]設(shè)計了云計算平臺中的單維索引CG-Index，用以支持key查詢和范圍查詢。CG-Index通過兩級索引結(jié)構(gòu)，在本地構(gòu)建B-Tree索引并選擇若干B-Tree節(jié)點發(fā)布為全局索引。系統(tǒng)中的節(jié)點則組織成BATON Overlay結(jié)構(gòu)，其發(fā)布的全局索引負責(zé)回答系統(tǒng)中收到的查詢。文獻[33]設(shè)計了ecStore，將數(shù)據(jù)對象分布并備份于云計算集群環(huán)境中。文獻[34]設(shè)計了P2P數(shù)據(jù)管理系統(tǒng)中在線近似聚集的處理算法，通過不斷獲取數(shù)據(jù)，提高計算結(jié)果的精度。文獻[35]比較了現(xiàn)有云計算平臺的架構(gòu)對構(gòu)建云數(shù)據(jù)庫的影響，其主要研究對象是在線事務(wù)處理而不是在線分析處理。結(jié)果表明現(xiàn)有的主流云計算系統(tǒng)具有不同的架構(gòu)，對于相同的工作負載也具有不同的性能。文獻[36]提出了一種分布式的B樹索引。該索引結(jié)構(gòu)將數(shù)據(jù)索引緩存在各個存儲節(jié)點中，回答查詢時，首先檢查緩存內(nèi)容是否過期，如果還未過期，則直接在本地回答查詢，否則需要執(zhí)行相應(yīng)更新操作。這種索引結(jié)構(gòu)在數(shù)據(jù)更新快的情況下，效率嚴重下降。
4結(jié)束語
目前，云計算系統(tǒng)中數(shù)據(jù)管理方面的研究已經(jīng)引起廣泛關(guān)注和濃厚興趣，而查詢處理和優(yōu)化技術(shù)則是其中最為基礎(chǔ)、且最為重要的研究內(nèi)容，對此已經(jīng)開展了較為詳盡與深入的研究工作。本文中，歸納并總結(jié)了云計算系統(tǒng)、數(shù)據(jù)管理以及查詢和索引技術(shù)等方向已有的研究，并對可能的研究方向進行了簡要的分析與闡述。
參考文獻：
[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.
