一種并行r樹(shù)空間的并行計(jì)算分析與管理

一種并行r樹(shù)空間的并行計(jì)算分析與管理

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