林業資源數據集群的快速索引設計

李惺穎,謝陽生,唐小明,羅 鵬,黃 龍,2

(1.中國林業科學研究院 資源信息研究所,北京 100091；2.北京林業大學 水土保持學院,北京 100083)

隨著林業信息化建設的推進,林業資源數據的總量、質量和時效性都持續增長.在日漸豐富的數據支持下,林業業務系統從單純的數據管理逐漸轉向集數據生產、分析、輔助決策為一體的綜合性業務系統.應用復雜度的增加對數據服務提出了更高速度和時效性的要求.目前,一些林業部門已經部署服務器集群以提高系統的整體性能,在這些集群中,通常由一個數據庫支撐所有業務系統的運行,相關的數據也都保存在共享的存儲空間上[1-5].這種模式下資源的訪問是競爭性的,需要分布式鎖處理互相沖突的數據訪問進程.為避免其他進程破壞正在進行修改的數據,必須將當前的數據鎖定,修改完畢后再解鎖,新的進程介入后再次鎖定,整個數據并行處理期間,分布式鎖不斷地重復鎖定和解鎖過程,并發進程越多,過程越復雜.該問題不能通過升級硬件得到解決,必須從存儲機制上解決資源沖突的瓶頸.因此,本文提出一種分布式索引結構,能關聯多個獨立數據節點中的數據,通過大量的數據節點共同負載數據請求,減少互斥的數據訪問過程.該索引分為兩級,第一級在主服務器上,可快速定位數據所在的數據節點；第二級在數據節點上,延續第一級索引的檢索過程,快速確認結果并返回所需數據.對于整個應用服務器集群,只需增加新的數據節點而不需變更數據結構和管理方式,業務系統的數據訪問和處理過程也基本不變,只增加訪問次數,最終能以較低成本提高整個數據集群的快速統計和更新能力.

1 快速數據索引的設計

數據索引是空間數據管理的關鍵,可高度并行的空間索引結構能大幅提高系統性能.在分布式環境中,索引結構的效率除依靠自身的效率和可并行度保證外,數據劃分也是提高系統效率的關鍵.合理的數據劃分可縮短查詢次數,在盡可能短的時間內命中所需數據.R樹是最常用的空間索引之一,在單機上通過多磁盤的I/O并發實現并行化.在多機環境中,M-R樹和MC-R樹采用主從模式分別存儲R樹的葉子節點和非葉子節點,以實現葉子節點查詢過程的并行化[6].GPR樹[7]和UPR樹[8]等R樹的變體也都是在共享內存環境下利用多磁盤存儲實現并行化,但這些索引方法并不適用于分布式的存儲環境.在分布式存儲環境下,一般先進行空間數據劃分,劃分方法包括輪轉法(round-robin)、散列劃分(hash partition)、范圍劃分(range partition)、混合劃分(hybrid-range partition)、CMD方法和Hilbert曲線劃分法等,劃分后能得到多個子區域并建立相應的索引,再為劃分后的所有子區域建立第二級索引,如R樹、R*樹和R*Q樹等,最后通過子區域的并行計算實現分布式空間數據的并行索引過程[9-12].

上述研究都針對基于空間范圍的查詢,假設P為空間對象集,r為某個空間區域,上述方法能夠高效地查詢到p?r,其中p∈P.但在實際應用中,空間查詢過程通常會附帶某些條件(如查詢所有滿足條件A

1.1 基于Hilbert碼的等差數據劃分

數據劃分是指將數據按一定規則分配到不同的存儲區域中.數據索引的效率取決于數據劃分的合理性,尤其是空間數據的劃分,直接影響整個系統的性能.空間數據的劃分一般通過編碼實現,文獻[13]對Morton碼、Gray碼、Hilbert碼和Sierpinsky碼的空間聚類特征進行了分析和比較,其中Hilbert碼在空間查詢中效率最高.文獻[14]利用Hilbert碼空間聚類特性,將關聯的數據盡可能集中在一個磁盤上.在共享內存和多磁盤存儲的情況下,這種思路效率較高,能減少磁盤讀取次數,提高效率.在本文以數據節點位存儲和運算單元的環境下,集中在相同數據節點的相鄰數據只能順次訪問,而分布在多個數據節點中的相鄰數據卻可同時訪問.

本文提出基于Hilbert碼的等差數據劃分,先利用Hilbert曲線的空間聚類特性,將空間要素順次編碼[14],然后以數據服務器個數作為公差d,按編碼順序將第i個要素放進編號為i%d的數據節點中.從而相鄰的要素將均勻地分布在所有的數據服務器上,能避免查詢數據過于集中在某個節點,提高處理過程的并行度.

劃分過程變量定義：hilCodeList為計算好的所有元素Hilbert及其編碼的列表;serverCount為數據節點數量.劃分算法偽代碼如下：

Distribute (hilCodeList,serverCount){

int fetCount=1;//設置要素計數器

for each (hilCode in hilCodeList){//遍歷列表中的每個要素

將要素hilCode分配至編號為fetCount%serverCount 的服務器上;

fetCount++;}//要素個數自增

}

1.2 快速索引結構

快速索引的核心思想是將數據請求分解為多個直接轉向數據節點的子請求.因此,索引結構中不存儲數據,只存儲數據所對應的數據節點地址.

每個數據節點中都存在大量的屬性字段,而數據劃分優先保證空間范圍的均勻劃分而不是數據量的均勻劃分,一旦有大量數據更新操作,保持屬性字段查詢樹的平衡即尤其重要,因此需要一種能快速查詢的自平衡查找樹以實現對屬性字段的索引.本文選用節點大小平衡樹(size balanced tree,SB樹),這是一種自平衡二叉查找樹,相比紅黑樹、AVL樹等自平衡二叉查找樹更易實現,查詢過程較穩定,其所有操作的時間復雜度不超過O(lgn).空間數據的索引通常使用R樹,但本文在進行數據等差劃分后,每個數據節點內部的數據間會相對分散.R樹在未達到分裂需求前,數據的鄰接距離差異較大會導致中間節點索引碼的覆蓋度增大,空間索引碼的交疊因子也會增大,最終節點分裂次數增多而降低索引效率.R*Q樹針對R樹的上述問題進行了優化[12],較適合本文的使用環境.

快速索引的結構如圖1所示,分為主服務器索引和數據節點索引兩類,結構上都由一棵SB樹和一棵R*Q樹構成,每棵樹都有一個查詢入口.主服務器索引中的SB樹記錄所有的屬性字段(Field),并記錄當前屬性存在于哪些數據節點(Server)上.數據節點索引中的SB樹每個節點都是一個子SB樹,記錄每個字段值所對應空間區域(Region)的索引地址.索引結構中的R*Q樹對要素的空間區域進行索引.主服務器上R*Q樹的葉子節點上記錄該區域的要素被分配在哪些數據節點中,數據節點上R*Q樹的葉子節點則保存該區域中要素擁有的屬性值及其對應的SB樹節點地址鏈接.

圖1 快速索引結構Fig.1 Structure of the fast index

主服務器上的索引,是為了快速找到數據所在的數據節點,數據節點上的索引是為了快速判斷自己是否存有所需數據,經過這兩次驗證用戶可同時向確實存有所需數據的數據節點發送數據請求,在避免網絡流量壓力過大的同時,也能避免在不存在所需數據的節點中盲目查詢而影響系統的整體效率.具體數據的查詢過程仍通過數據節點上的空間數據引擎進行.因此,主服務器上SB樹記錄的是整個系統所有的屬性字段,R*Q樹記錄的范圍是每個數據節點的整體區域.數據節點上的R*Q樹也不能記錄到具體要素,否則將導致樹的深度過大,反而降低整體速度.數據節點上的R*Q樹應該選取常用的最小查詢范圍,如一個行政村界.

1.3 數據查詢及更新

下面通過一個實例說明快速索引的查詢過程：查詢在Region 5區域中所有屬性Field 9的值在1～3的要素.查詢過程如圖2所示,首先從主服務器的R*Q樹開始,在第8步查詢到Region 5,然后向其列表中的所有數據節點同時發送請求,接到查詢請求的數據節點開始查找自己的SB樹,節點Server 1在第3步查找到Field 9屬性并在其子SB樹中查詢到1～3的值2,查詢結束.最后數據節點Server 1開始通過ArcSDE查詢所需數據并返回給客戶端.如果沒查詢到需要的Field值,則將空值返回客戶端,不經過ArcSDE查詢.

圖2 查詢過程Fig.2 Searching process

本文數據根據空間分布均勻劃分,如果數據節點不足,則系統數據初始劃分完后,主服務器R*Q樹的節點中將存在大量的重疊區域,對提高整個系統的效率意義較小.快速索引結構的速度優勢必須基于數據節點的數據保證.隨著數據節點的增多,數據重疊區域逐漸減少,數據處理的并行度逐漸提高,每個數據節點處理的數據量減少,因而同樣數據量的查詢所需時間將逐步縮短.對于數據更新,小量而頻繁的數據更新將在各自數據節點內進行,并不影響其他節點,只要不是整表,數據節點越多,整個系統中受數據更新影響的服務器比例就越小.對于整表或整個區域數據的更新,可直接將更新數據全部存放在新的數據節點上,建立好數據節點的索引后并入內網,對主服務器索引樹的部分節點進行更新,即可快速完成數據更新.索引的更新包括節點的增加、刪除及節點數據的更新,在數據產生變化后更新相關聯的節點.

索引更新過程偽代碼如下：

UpdateDataIndex ( ){

if (新增數據節點){

更新主服務器中的SB樹和R*Q樹;}

else {

if (整表更新){

更新當前數據節點的SB樹和R*Q樹;

更新主節點的SB樹和R*Q樹;}

else {

if (只更新邊界){

更新當前數據節點的SB樹和R*Q樹;

更新主節點R*Q樹;}

else if (只更新屬性){

更新當前節點的SB樹;

更新主節點SB樹;}

else {

更新當前節點的SB樹和R*Q樹;

更新主節點SB樹和R*Q樹;}

}

}

2 實驗分析

為驗證快速索引結構在大量數據訪問和更新時的效率,本文使用福建(2 354 322個要素,9.59 Gb)和廣西(3 148 779個要素,33.1 Gb)兩省5 503 101個林地保護規劃區共44.69 Gb的數據進行測試,使用10個數據節點.數據庫使用Orale,空間數據引擎使用ArcSDE,每個節點都安裝了數據庫和空間數據引擎.

根據快速索引的應用要求,先對這些數據進行劃分,結果列于表1.由表1可見,每個數據節點的要素個數基本一致,每個節點的數據量不同,但其標準差約為0.27,表明數據量的偏離程度較小.在實際系統中,這樣的數據傾斜度,并不會對系統效率產生太大影響.

表1 數據劃分結果Table 1 Result of data distribution

劃分結果的空間分布如圖3所示,這是10個數據節點中的4個,其中綠色區域為對應節點所存儲的要素.由圖3可見,劃分后的數據在數據節點上是分散的,但在數據節點間是連續的,表明在實際應用時可從不同的數據節點同時取到連續區域的數據.

圖3 劃分后的數據分布Fig.3 Distribution of data distributed

為了對比使用快速索引的分布式存儲系統性能和現有單數據庫存儲系統的性能,測試在大量數據查詢和更新上的效果,本文使用RAC建立了一個10個節點的單Oracle數據庫進行比較,單Oracle數據庫上也安裝了ArcSDE空間數據引擎.

為保證測試結果盡可能不受ArcSDE和Oracle存儲方式的影響,使用快速索引的所有節點和用于對比單數據庫中的節點,全部啟用ArcSDE的Spatial支持,在通過ArcSDE導入所有數據后為所有數據建立了數據庫中的索引,加快庫內查詢速度以減小其對最終結果的影響,同時數據更新時禁止重建數據庫中的索引.

單庫集群和多庫集群存儲查詢及更新數據的測試結果如圖4所示.由圖4可見,查詢和更新結果相似,在數據量不大時,多庫集群的性能不如或接近單庫集群.但隨著處理數據量的增大,多庫集群耗時的增加相對于單庫集群更慢.在達到一定數量級后,多庫集群的性能將超過單庫集群.

圖4 數據查詢和更新時間的對比Fig.4 Comparison of data searching time and updating time

圖5 數據節點數與處理速度的關系Fig.5 Relationship between number of data nodes and process speed

為了驗證節點數量與系統性能的關系,本文使用不同的數據節點查詢同樣數量的數據,結果如圖5所示.由圖5可見,系統處理的數據量越大,增加節點數對整體性能的提升效果越明顯.

綜上可見,本文提出的林業資源數據集群快速索引,能在不改變現有數據管理模式的前提下,以較低成本實現系統整體性能的提升.通過對數據進行劃分和索引平均分配數據節點壓力,通過增加數據節點減少每個數據節點的處理量,以達到提升系統整體性能的目的.該索引適用于林業系統中經常需要處理大量數據、能配置大量數據節點并有足夠內部帶寬的數據集群.

[1] ZHANG Dong-you,ZANG Shu-ying,FENG Zhong-ke.Design of Forestry Geographic Information Public Service Platform in Heilongjiang Province [J].Journal of Beijing Forestry University,2007,29(Suppl 2)：26-30.(張冬有,臧淑英,馮仲科.黑龍江省林業地理信息公共服務平臺設計 [J].北京林業大學學報,2007,29(增刊2)：26-30.)

[2] PANG Li-feng,TANG Xiao-ming,LIU Peng-ju.Development of the Provincial Forestry Information Sharing Platform Based on WebGIS [J].Journal of Northwest Forestry University,2011,26(2)：180-184.(龐麗峰,唐小明,劉鵬舉.基于WebGIS省級林業信息共享平臺的研發 [J].西北林學院學報,2011,26(2)：180-184.)

[3] TIAN Bo,DING Li-xia,ZHOU Yun-xuan,et al.Construction of a Multi-layered Distributed Forestry Information Service Platform [J].Journal of Zhejiang Forestry College,2006,23(4)：429-434.(田波,丁麗霞,周云軒,等.多層分布式林業信息服務平臺的構建 [J].浙江林學院學報,2006,23(4)：429-434.)

[4] FENG Tie,CHAI Sheng,ZHANG Jia-chen,et al.Approach of Dynamic Change Impact Analysis on Software Architecture [J].Journal of Jilin University：Engineering and Technology Edition,2011,41(2)：458-462.(馮鐵,柴勝,張家晨,等.一種軟件體系結構動態變動影響分析方法 [J].吉林大學學報:工學版,2011,41(2)：458-462.)

[5] ZHANG Xu,LI Zeng-yuan,DENG Guang,et al.Research and Implementation on Digital Forestry Platform [J].Scientia Silvae Sinicae,2006,42(Suppl 1)：37-40.(張旭,李增元,鄧廣,等.數字林業平臺技術研究與實現 [J].林業科學,2006,42(增刊1)：37-40.)

[6] Kamel I,Faloutsos C.Parallel R-Trees [C]//Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data.New York:ACM Press,1992:195-204.

[7] FU Xiao-dong,WANG Ding-xing,ZHENG Wei-min.GPR-Tree：A Global Parallel Index Structure for Multiattribute Declustering on Cluster of Workstations [C]//Proceedings on Advances in Parallel and Distributed Computing.Piscataway:IEEE Computer Society,1997:300-306.

[8] ZUO Chao-shu,LIU Xin-song,CHEN Xiao-hui,et al.DPslR+：A Distributed and Parallel Spatial Index Tree Based on Dynamic Spatial Slot [J].Computer Science,2006,33(2)：121-126.(左朝樹,劉心松,陳小輝,等.DPslR+：一種基于動態空間槽的分布式并行空間索引樹 [J].計算機科學,2006,33(2)：121-126.)

[9] CHEN Zhan-long,WU Xin-cai,XIE Zhong,et al.GSHR-Tree：A Spatial Index Tree Based on Dynamic Spatial Slot and Hash Table in Grid Environments [J].Earth Science (Journal of China University of Geosciences),2010,35(3)：463-470.(陳占龍,吳信才,謝忠,等.GSHR-Tree：一種基于動態空間槽和哈希表的網格環境下的空間索引樹 [J].地球科學(中國地質大學學報),2010,35(3)：463-470.)

[10] CONG Li,ZHANG Hai-lin,LIU Yi,et al.Particle Swarm Optimized Game Theory for Resource Allocation in Cooperative Networks [J].Journal of Jilin University：Engineering and Technology Edition,2012,42(1)：207-212.(叢犁,張海林,劉毅,等.基于粒子群優化的協作網絡資源分配的博弈策略 [J].吉林大學學報:工學版,2012,42(1)：207-212.)

[11] Lawder J K,King P J H.Using Space-Filling Curves for Multidimensional Indexing [C]//Proceedings of the 17th British National Conference on Databases：Advances in Databases.London:Springer,2000:20-25.

[12] YU Bo,HAO Zhong-xiao.Research of Distributed and Parallel Spatial Index Mechanism Based on DPR-Tree [J].Computer Technology and Development,2010,20(6)：39-42.(于波,郝忠孝.基于DPR樹的分布式并行空間索引機制的研究 [J].計算機技術與發展,2010,20(6)：39-42.)

[13] Breinholt G,Schierz C.Generating Hilberts Space-Filling Curve by Recursion [J].ACM Transactions on Mathematical Software,1998,24(2)：184-189.

[14] Kamel I,Faloutsos C.Hilbert R-Tree：An Improved R-Tree Using Fractals [C]//Proceedings of the 20th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publisher Inc,1994:500-509.