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

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

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

1 快速數據索引的設計

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

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

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

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

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

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

Distribute (hilCodeList,serverCount){

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

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

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

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

}

1.2 快速索引結構

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

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

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

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

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

1.3 數據查詢及更新

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

圖2 查詢過程Fig.2 Searching process

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

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

UpdateDataIndex ( ){

if (新增數據節(jié)點){

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

else {

if (整表更新){

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

更新主節(jié)點的SB樹和R*Q樹;}

else {

if (只更新邊界){

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

更新主節(jié)點R*Q樹;}

else if (只更新屬性){

更新當前節(jié)點的SB樹;

更新主節(jié)點SB樹;}

else {

更新當前節(jié)點的SB樹和R*Q樹;

更新主節(jié)點SB樹和R*Q樹;}

}

}

2 實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

[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.(張冬有,臧淑英,馮仲科.黑龍江省林業(yè)地理信息公共服務平臺設計 [J].北京林業(yè)大學學報,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省級林業(yè)信息共享平臺的研發(fā) [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.(田波,丁麗霞,周云軒,等.多層分布式林業(yè)信息服務平臺的構建 [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.(馮鐵,柴勝,張家晨,等.一種軟件體系結構動態(tài)變動影響分析方法 [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.(張旭,李增元,鄧廣,等.數字林業(yè)平臺技術研究與實現 [J].林業(yè)科學,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+：一種基于動態(tài)空間槽的分布式并行空間索引樹 [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：一種基于動態(tài)空間槽和哈希表的網格環(huán)境下的空間索引樹 [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.(叢犁,張海林,劉毅,等.基于粒子群優(yōu)化的協(xié)作網絡資源分配的博弈策略 [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].計算機技術與發(fā)展,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.