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

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

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

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

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

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

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

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

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

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