云計算系統(tǒng)中索引與查詢處理技術(shù)研究.pdf

1、云計算是一種新興的計算模式,它隱藏了計算資源以及計算的執(zhí)行過程,用戶只需要通過瀏覽器或者應用程序界面提交計算任務或者服務請求,而不必考慮如何構(gòu)建計算架構(gòu);如何組織、調(diào)度計算資源;如何使用計算資源完成計算任務或者服務請求。隨著越來越多的數(shù)據(jù)和應用服務從超級服務器遷移到公有云計算系統(tǒng)或私有云計算系統(tǒng)中,如何在云計算系統(tǒng)中有效地進行數(shù)據(jù)管理并成為一項具有重要意義的研究工作。與傳統(tǒng)的數(shù)據(jù)管理相比,云計算系統(tǒng)中的數(shù)據(jù)管理需要提供良好的可擴展性以及

2、高效的數(shù)據(jù)存取能力。查詢處理和查詢優(yōu)化也是云計算系統(tǒng)中的數(shù)據(jù)管理的核心技術(shù),查詢性能嚴重影響用戶使用云計算系統(tǒng)的服務質(zhì)量。索引技術(shù)在數(shù)據(jù)管理系統(tǒng)中能夠有效地提高查詢處理性能,減少查詢使用的CPU時間、磁盤讀取等操作,以此提高查詢處理性能,云計算系統(tǒng)也需要構(gòu)建有效的索引結(jié)構(gòu)來提高查詢處理性能。綜上所述,云計算系統(tǒng)中的查詢處理和索引技術(shù)是具有重要意義的研究課題。然而現(xiàn)有工作主要針對MapReduce計算框架下的并行數(shù)據(jù)分析操作,對于其他查詢

3、類型還缺乏研究成果。
　　本文的研究工作針對云計算系統(tǒng)中的查詢處理技術(shù)和索引技術(shù),運用數(shù)據(jù)管理技術(shù)、計算復雜性和算法學的理論和知識,針對云計算系統(tǒng)中不同查詢類型的處理算法和不同的數(shù)據(jù)類型的索引技術(shù)進行研究。本文的主要研究工作包括以下方面:
　　首先,本文提出了云計算系統(tǒng)中的多維索引結(jié)構(gòu)?，F(xiàn)有研究工作主要針對單個計算節(jié)點或者服務器-客戶端模型,在大量計算節(jié)點構(gòu)成的云計算系統(tǒng)中,使用單個計算節(jié)點中的多維索引將造成系統(tǒng)性能的瓶頸,

4、無法提供良好的可擴展性。本文提出了一種兩層的索引結(jié)構(gòu),在云計算系統(tǒng)中支持多維數(shù)據(jù)查詢,查詢過程中索引結(jié)構(gòu)在大量計算節(jié)點之間和單個計算節(jié)點的外存中同時為查詢提供剪枝能力,提高系統(tǒng)的吞吐量。本文給出了該索引結(jié)構(gòu)的構(gòu)建方法、維護方法,并在索引維護過程中提出優(yōu)化策略,進一步提高查詢處理的吞吐量。本文針對云計算系統(tǒng)中的多維數(shù)據(jù)提出點查詢、范圍查詢和k最近鄰查詢的處理算法,包括計算節(jié)點之間的分布式算法和計算節(jié)點內(nèi)部的索引選擇算法。真實云計算平臺中的

5、實驗驗證了本文提出的云計算多維索引結(jié)構(gòu)的有效性。
　　第二,本文提出了云計算系統(tǒng)中字符串相似性查詢的算法?，F(xiàn)有的字符串相似性查詢技術(shù)都針對單個計算節(jié)點,在處理大規(guī)模字符串數(shù)據(jù)集合時將導致內(nèi)存溢出和外存溢出兩個問題。針對以上問題,本文提出一種分布式索引結(jié)構(gòu),在云計算系統(tǒng)中支持字符串相似性查詢。為了獲取更好的本地查詢效率,本文將現(xiàn)有的字符串查詢優(yōu)化技術(shù)應用在外存環(huán)境中,設(shè)計了支持長度過濾器和位置過濾器的外存索引結(jié)構(gòu),及其構(gòu)建方法和實現(xiàn)

6、細節(jié)。在查詢過程中,使用非對稱的字符串概要模式,自適應地從查詢字符串的數(shù)據(jù)概要集合中選擇一部分元素,用于獲取查詢使用的倒排表。為了減少查詢在系統(tǒng)中使用計算節(jié)點的數(shù)量,本文設(shè)計了基于字符向量的數(shù)據(jù)劃分方法,用于劃分字符串數(shù)據(jù)集合。該方法將相似的字符串劃分到相同的計算節(jié)點中,并在查詢處理過程中確定查詢需要訪問的計算節(jié)點集合。模擬實驗結(jié)果驗證了本文提出的字符串相似性查詢算法的有效性。
　　第三,本文提出了云計算系統(tǒng)中空間近似關(guān)鍵字查詢算

7、法?，F(xiàn)有工作集中于單個計算節(jié)點中的索引結(jié)構(gòu),并提出了內(nèi)存中的精確算法和外存中的近似算法。然而,由于單個計算節(jié)點的CPU計算能力和磁盤帶寬有限,內(nèi)存方法乃至外存方法都無法滿足系統(tǒng)對性能的要求。本文設(shè)計了一種兩層索引結(jié)構(gòu),支持空間近似關(guān)鍵字查詢,提高系統(tǒng)相應查詢的吞吐量。本文設(shè)計一種新穎的樹形索引,在外存中支持空間近似關(guān)鍵字查詢,并高效地返回完整的查詢結(jié)果。本文的全局索引將整個空間劃分成多個劃分,全局索引維護在各個計算節(jié)點的內(nèi)存中,用于加速

8、查詢處理過程。本文給出了全局索引選擇方法,用于全局索引的初始化和周期性維護。在查詢處理方面,本文給出了基于編輯距離的范圍近似關(guān)鍵字查詢和最近鄰近似關(guān)鍵字查詢的算法。在分布式集群中的實驗結(jié)果驗證了本文提出的索引結(jié)構(gòu)的有效性。
　　第四,本文提出了云計算系統(tǒng)中多維聚集查詢處理算法?，F(xiàn)有云計算中的研究工作MapReduce計算框架缺乏對多維數(shù)據(jù)中聚集操作的有效支持。另一方面,使用MapReduce計算框架需要啟動大量計算節(jié)點,造成巨大的

9、系統(tǒng)功耗。針對以上問題,本文提出了云計算系統(tǒng)中的多維聚集操作方案,通過兩層索引結(jié)構(gòu)減少參與查詢的計算節(jié)點以及單個計算節(jié)點中聚集操作計算量。本文給出了使用兩層索引結(jié)構(gòu)處理多維聚集查詢的算法框架,并在該框架中提出了性能優(yōu)先模式和低功耗模式下的多維聚集查詢算法。在兩種模式下的多維聚集算法中提出了查詢分配問題,并證明了兩種模式中查詢分配問題都是NP完全問題。本文給出解決兩個NP完全問題的近似算法,并證明了兩個近似算法的近似比。理論證明分析和模擬