一種并行r樹空間的并行計算分析與管理

一種并行r樹空間的并行計算分析與管理

空間數(shù)據(jù)處理、空間決策的支持、空間維度動態(tài)可視化、空間績效模型和模型等屬于計算形式和i/o型空間應(yīng)用，目前的gis計算方法無法滿足應(yīng)用的需求。隨著網(wǎng)格計算技術(shù)在GIS中的應(yīng)用逐漸成為研究熱點,其分布式并行計算模式與系統(tǒng)架構(gòu)將有助于提高GIS的整體性能和運行效率。因此,分布式并行計算將成為解決傳統(tǒng)GIS計算能力不足問題的重要方法。海量空間數(shù)據(jù)的組織與管理技術(shù)是各類復(fù)雜空間應(yīng)用的基礎(chǔ),也是GIS技術(shù)的核心問題。其中,空間索引技術(shù)是數(shù)據(jù)組織與管理的重要研究內(nèi)容。目前,在數(shù)據(jù)庫管理系統(tǒng)及GIS等科研領(lǐng)域,空間索引技術(shù)的研究成果非常豐富,應(yīng)用較為廣泛。然而,針對海量空間數(shù)據(jù)的組織、管理、存取、處理與應(yīng)用的分布式并行空間索引技術(shù)研究成果較少,已有的研究存在應(yīng)用平臺和應(yīng)用領(lǐng)域的不同。本文提出一種分布式并行計算環(huán)境下基于R樹索引和線性鏈表結(jié)構(gòu)的分布式并行空間索引結(jié)構(gòu),其設(shè)計與開發(fā)是以經(jīng)典的IanFoster并行計算方法論為依據(jù),充分考慮數(shù)據(jù)劃分、負載平衡等影響并行索引機制效率的因素,使得該索引結(jié)構(gòu)更適合于網(wǎng)格等分布式并行計算環(huán)境中的各類復(fù)雜應(yīng)用。1并行r樹結(jié)構(gòu)存儲方式在并行GIS研究領(lǐng)域,已有的研究成果中并未涉及太多的海量空間數(shù)據(jù)存儲方面的問題。然而,在分布式并行計算環(huán)境下,海量空間數(shù)據(jù)的組織與管理是關(guān)系到并行GIS整體性能優(yōu)劣的關(guān)鍵。因此,人們開始研究和探索并行空間索引,以提高空間數(shù)據(jù)訪問效率,其中針對R樹并行化方法的研究成果較多。Karnel等最早提出了并行R樹索引方法,其并行R樹的硬件基礎(chǔ)為單CPU多磁盤系統(tǒng),使用并發(fā)I/O方法提高查詢的數(shù)據(jù)吞吐量。Schnitzer等提出了M-R樹和MC-R樹(Master-ClientR樹)方法,兩種方法的相同之處在于均是將R樹的所有非葉節(jié)點存儲在多機環(huán)境中的主計算機上。兩者的區(qū)別在于M-R樹的葉節(jié)點和實體對象直接存儲在子節(jié)點上,而MC-R樹的各子節(jié)點存放在子R樹。以上3種并行R樹結(jié)構(gòu)均采用主從模式,所以主節(jié)點很容易成為訪問的熱點和瓶頸,這將增加事務(wù)處理的響應(yīng)時間,進而降低了系統(tǒng)的整體性能。R樹空間索引結(jié)構(gòu)具有固有的并行性特征,適合于并行GIS和并行空間數(shù)據(jù)庫的應(yīng)用,但從目前已有的并行R樹索引研究成果發(fā)現(xiàn),R樹在并行計算環(huán)境下應(yīng)用時存在如下不足:1)R樹中越靠近根節(jié)點的非葉節(jié)點被數(shù)據(jù)庫事務(wù)訪問的概率越大,其成為熱點的可能性越大;2)當R樹的葉節(jié)點進行分裂或合并時,通常會影響該節(jié)點鄰近的節(jié)點,甚至整個R樹都需做相應(yīng)調(diào)整;3)訪問R樹中的節(jié)點時,通常需在該節(jié)點附加共享鎖或排他鎖,如果對R樹進行更新等操作,則被訪問的節(jié)點將被鎖住,其他事務(wù)也不能對該R樹進行任何操作,從而降低了R樹的事務(wù)并發(fā)處理能力。雖然R樹存在弊端,但實踐證明,經(jīng)過優(yōu)化設(shè)計,其仍是構(gòu)建并行空間索引的最佳選擇。從已有的并行R樹索引機制可以看出,分布式并行計算環(huán)境中并行R樹的構(gòu)建關(guān)鍵在于新創(chuàng)建的葉節(jié)點如何在多個磁盤間分配,其原則包括:1)數(shù)據(jù)平衡準則,即理想狀態(tài)下每個磁盤具有同等數(shù)量的葉節(jié)點,同時需保證數(shù)據(jù)總量平衡;2)面積平衡準則,即每個磁盤上存儲的空間實體所覆蓋的空間區(qū)域面積平衡,否則存儲空間區(qū)域面積較大的磁盤很可能成為訪問的熱點和瓶頸;3)空間關(guān)系平衡準則,即盡量將重疊或空間距離較近的葉節(jié)點存儲在不同的磁盤,以提高查詢時的數(shù)據(jù)吞吐能力。本文根據(jù)這些準則,給出分布式并行計算環(huán)境(如網(wǎng)絡(luò)集群)中并行R樹空間索引結(jié)構(gòu)的構(gòu)造方法。2r樹空間索引機制2.1空間數(shù)據(jù)特征在數(shù)據(jù)庫領(lǐng)域,數(shù)據(jù)劃分技術(shù)是解決劃分后的數(shù)據(jù)塊在各磁盤之間分布不均衡問題(即數(shù)據(jù)傾斜現(xiàn)象)的有效方法。同樣,空間數(shù)據(jù)劃分技術(shù)在空間數(shù)據(jù)庫中也發(fā)揮著重要作用,在避免產(chǎn)生數(shù)據(jù)傾斜的前提下,可提高空間數(shù)據(jù)的并行查詢與檢索效率?？臻g數(shù)據(jù)劃分策略是本文并行R樹空間索引結(jié)構(gòu)的基礎(chǔ),也是保證該索引機制具有高效率與高性能的前提條件。為遵循上述創(chuàng)建并行空間索引機制的原則,并滿足空間數(shù)據(jù)劃分策略的需求,本文采用文獻中基于Hilbert空間填充曲線的空間數(shù)據(jù)劃分算法(SpatialDataPartitioningbasedonHilbertCurve,HCSDP)。在充分考慮空間信息的海量特征以及矢量數(shù)據(jù)存儲記錄的不定長等特點的前提下,該算法可實現(xiàn)空間數(shù)據(jù)庫中海量空間數(shù)據(jù)在多個磁盤上的均衡分布,從而避免出現(xiàn)數(shù)據(jù)傾斜現(xiàn)象。2.2r樹索引結(jié)構(gòu)組成已有的并行R樹索引機制大部分采用兩層或多層索引結(jié)構(gòu)。本文構(gòu)造的并行R樹空間索引結(jié)構(gòu)是基于HCSDP空間數(shù)據(jù)劃分算法的多層并行R樹索引(HilbertSpace-FillingCurvebasedMulti-tiersParallelR-tree,HCMPR-tree),圖1給出HCMPR-tree索引結(jié)構(gòu)組成。HCMPR-tree索引結(jié)構(gòu)的設(shè)計遵循IanFoster的并行算法設(shè)計方法論,即經(jīng)過劃分、通信、聚集和映射,使得并行R樹索引結(jié)構(gòu)更適合于并行計算環(huán)境下的應(yīng)用。其各層的功能如下:(1)空間實體對象間關(guān)系的持續(xù)性原則該層包括所有具有統(tǒng)一空間參考系統(tǒng)的空間實體對象和對應(yīng)的屬性數(shù)據(jù)的集合。使用HCSDP算法對空間區(qū)域進行劃分,劃分后的每個子區(qū)域所擁有的空間實體對象均具有連續(xù)的Hilbert排列碼,這既保證了每個子區(qū)域中空間實體對象之間具有較強的空間相關(guān)性(如相鄰關(guān)系等),從而避免經(jīng)由數(shù)據(jù)劃分后空間實體對象彼此之間的空間關(guān)系被嚴重割裂;同時,又保證了每個子區(qū)域之間空間實體對象總量上的平衡。(2)層是子區(qū)域的級別該層是待劃分空間區(qū)域經(jīng)由HCSDP算法處理后的結(jié)果集層。(3)vpe優(yōu)化策略虛擬處理單元(VirtualProcessingElement,VPE)的引入有助于“聚集”操作的實現(xiàn)。該層中虛擬處理單元的個數(shù)為m,通常m<<n(n為子區(qū)域個數(shù))。VPE物理上是不存在的,其將被映射到實際的處理單元上。實踐證明,影響R樹索引性能的一個主要因素是節(jié)點之間的重疊度,而產(chǎn)生重疊的重要因素之一是聚集后的空間實體對象之間彼此鄰近,即最小邊界矩形(MinimumBoundingRectangle,MBR)之間重疊度較高。VPE將為解決這一問題提供較好的策略。子區(qū)域?qū)又械拿總€子區(qū)域通過某種數(shù)據(jù)劃分策略(如輪循法)分別映射到VPE集合中,而VPE包含的子區(qū)域所覆蓋的空間區(qū)域是彼此分離的。(4)處理單元映射該層對應(yīng)實際的物理存儲單元或處理單元(ProcessingElement,PE),即網(wǎng)絡(luò)集群環(huán)境中的控制節(jié)點、計算節(jié)點和存儲節(jié)點,可認為處理單元即為存儲單元。PE的個數(shù)對應(yīng)著集群中實際存在的計算節(jié)點的數(shù)目k,該值通常小于或等于VPE的個數(shù)m。該層實現(xiàn)了“映射”操作,即使用輪循法或其他數(shù)據(jù)劃分算法將VPE映射到PE上。映射后的每個PE將包含一個或多個VPE,而包含的子區(qū)域個數(shù)的上限則根據(jù)n、m、k確定。(5)pe上的r樹索引如圖1所示,通過一次劃分、一次聚集和一次映射操作,最終將所有的子區(qū)域分別存放到物理處理單元上。因為每個PE包含兩個或兩個以上的子區(qū)域,而子區(qū)域所覆蓋的空間范圍彼此是分離的,因此每個PE上R樹的建立可以按照所包含的子區(qū)域進行分塊處理,從而加快R樹索引的創(chuàng)建速度。每個PE上所建立的R樹索引實質(zhì)上是一般的R樹索引,其空間數(shù)據(jù)訪問方法和R樹索引的插入與刪除操作均與傳統(tǒng)R樹索引的處理方法相同;而對于集群環(huán)境中所有的PE,所有的R樹索引之間是彼此獨立的,可以實現(xiàn)空間數(shù)據(jù)并行查詢與更新。2.3子節(jié)點指向的r樹HCMPR-tree索引的葉節(jié)點的物理存儲包括一組項,其格式為(I,元組標識符),其中I為葉節(jié)點對應(yīng)的MBR,元組標識符是數(shù)據(jù)庫中對應(yīng)于該MBR的對象的元組唯一標識符。HCMPR-tree索引的非葉節(jié)點分為兩類,一類是子區(qū)域?qū)?yīng)的非葉節(jié)點,其由一組(RID,I,子節(jié)點指針)表示,RID用于標識子區(qū)域,I為該節(jié)點對應(yīng)的MBR,即子區(qū)域?qū)?yīng)的MBR,子節(jié)點指針指向該子區(qū)域?qū)?yīng)的R樹的根節(jié)點;另一類是子區(qū)域?qū)?yīng)的R樹內(nèi)的非葉節(jié)點,由(I,子節(jié)點指針)表示,I為該節(jié)點對應(yīng)的MBR,子節(jié)點指針指向下一層節(jié)點。每個PE上的R樹的根節(jié)點由(SID,I,子節(jié)點指針)表示,SID標識該R樹所在的PE的標識符,I為該PE所覆蓋的MBR,子節(jié)點指針指向非葉節(jié)點。與前人提出的并行R樹索引不同,HCMPR-tree索引的最上層用鏈表保存,鏈表中每個元素包含5項(RID,SID,I,HS,HE):RID用于標識子區(qū)域,SID是存儲該元素對應(yīng)的子區(qū)域的PE的標識符,I表示該元素對應(yīng)的子區(qū)域的MBR,HS表示該元素對應(yīng)的Hilbert排列碼的起始值,而HE表示其終止值。該鏈表保存于網(wǎng)絡(luò)集群系統(tǒng)的主控制節(jié)點上。由于n的個數(shù)是有限的,因此可一次性裝入內(nèi)存,使其具有很快的查詢速度。這種鏈表結(jié)構(gòu)避免了將R樹所有非葉節(jié)點存儲于主控制節(jié)點而帶來的訪問沖突等限制。鏈表結(jié)構(gòu)簡單,查詢與排序運算速度快,適合于分布式并行計算環(huán)境下的并行R樹的應(yīng)用。3hcmpr-創(chuàng)造設(shè)備的選擇如前所述,HCMPR-tree索引結(jié)構(gòu)的最下一層是對每個PE上的子區(qū)域建立的R樹索引。與傳統(tǒng)R樹索引不同的是,HCMPR-tree索引的葉節(jié)點選擇將關(guān)系到并行計算環(huán)境中針對并行R樹進行的空間數(shù)據(jù)查詢與檢索的效率問題。葉節(jié)點大小的確定一般分為兩種情況:1)如果葉節(jié)點過小(如只包含一個空間實體對象),則在進行小范圍查詢時必須訪問多個PE,這就增加了網(wǎng)絡(luò)通信量,從而會造成網(wǎng)絡(luò)阻塞;2)如果葉節(jié)點過大,則在進行較大范圍查詢時很可能只在一個PE上進行,這樣大大降低了空間數(shù)據(jù)查詢與檢索的并行化程度,進而減弱了并行GIS和并行空間數(shù)據(jù)庫的整體性能優(yōu)勢。HCMPR-tree索引葉節(jié)點大小的確定受多種因素影響,如網(wǎng)絡(luò)數(shù)據(jù)傳輸速度、PE的計算能力和PE的個數(shù)等。本文把針對空間數(shù)據(jù)庫的空間范圍查詢的系統(tǒng)響應(yīng)時間作為性能評估指標,在努力獲得最小化系統(tǒng)響應(yīng)時間的同時找到最優(yōu)的葉節(jié)點值。表1是確定系統(tǒng)響應(yīng)時間的各類參數(shù)的說明,其參考標準為運行Windows2000professional的IntelPentiumIV2.4GHz的計算機。表2是確定最優(yōu)葉節(jié)點大小所需參數(shù)及其說明。用K表示某個查詢需要訪問的PE的個數(shù),并建立如下C、K和Q的函數(shù)關(guān)系:Copt=?QNpe×log(1?Kopt/Npe)(1)Copt=-QΝpe×log(1-Κopt/Νpe)(1)任何一個空間數(shù)據(jù)查詢首先必須通過對主控制節(jié)點上的HCMPR-tree的頂層鏈表結(jié)構(gòu)進行操作,以確定查詢范圍qx和qy所覆蓋的PE的個數(shù)及其SID;然后由主控制節(jié)點向這K個PE發(fā)送數(shù)據(jù)查詢消息,并等待查詢結(jié)果從這K個PE返回到主控制節(jié)點。在表1所示的計算機硬件配置條件下,C的最優(yōu)取值為1個磁盤頁大小,即1Spage。為驗證HCMPR-tree索引結(jié)構(gòu)選擇的最優(yōu)葉節(jié)點的有效性,本文采用空間查詢系統(tǒng)響應(yīng)時間和葉節(jié)點大小兩個變量作為參數(shù)。實驗方案中空間數(shù)據(jù)集選用全國1∶100萬縣市級行政區(qū)域邊界圖,大小為17.6Mbytes;處理單元個數(shù)分別為2、4、8,查詢范圍則選擇0.1～0.5(qx=qy)。圖2是3種PE配置條件下空間數(shù)據(jù)查詢系統(tǒng)響應(yīng)時間與葉節(jié)點大小變化關(guān)系的對比。其中,每個子圖中的5條曲線從上至下分別為查詢范圍邊界0～0.1的5種狀態(tài)。本文采用的驗證方案參考了Koudas等的相關(guān)測試方法,實驗結(jié)果總體上與Koudas等的實驗結(jié)果有相似之處,即在最優(yōu)葉節(jié)點大小(1Spage)處,任何一種范圍的空間數(shù)據(jù)查詢在具有不同的PE個數(shù)條件下均獲得了最小的系統(tǒng)響應(yīng)時間。4基于數(shù)據(jù)的并行算法設(shè)計已有的基于