苗 放，馬新凡，楊文暉

(1.成都大學 模式識別與智能信息處理四川省高校重點實驗室，四川 成都 610106;2.成都理工大學 地質(zhì)災(zāi)害防治與地質(zhì)環(huán)境保護國家重點實驗室，四川 成都 610059;3.成都理工大學 地球探測與信息技術(shù)教育部重點實驗室，四川 成都 610059)

0 引 言

空間信息技術(shù)，特別是高分辨率傳感器技術(shù)的飛速發(fā)展使得地理信息系統(tǒng)面臨日益嚴峻的數(shù)據(jù)量爆炸性增長的局面，有效利用空間數(shù)據(jù)庫的存儲需求已經(jīng)從目前的GB 級和TB 級達到了PB 級.海量空間數(shù)據(jù)已無法沿用傳統(tǒng)的集中存儲方式，空間數(shù)據(jù)顯著的海量性和地域分布特征使其更適合于網(wǎng)絡(luò)環(huán)境下的分布式存儲［1］，并利用網(wǎng)絡(luò)中的眾多節(jié)點聯(lián)合提供超大容量、高可用、高可靠的數(shù)據(jù)存儲服務(wù)［2］.為了有效利用分布式資源，必須解決有關(guān)數(shù)據(jù)放置的挑戰(zhàn)［3］.面向分布式存儲中，針對空間數(shù)據(jù)的復雜多維屬性，如何設(shè)計放置方法使得空間數(shù)據(jù)能夠高效地訪問是一個關(guān)鍵問題.本研究基于分布式存儲并根據(jù)空間數(shù)據(jù)的特點，提出一種DHT-R放置策略，結(jié)合分布式哈希表(Distributed Hash Table，DHT)和R 樹特點進行空間數(shù)據(jù)放置，從而實現(xiàn)空間數(shù)據(jù)的高效查找.

1 現(xiàn)有數(shù)據(jù)放置策略

目前，已有的分布式存儲系統(tǒng)中根據(jù)不同的網(wǎng)絡(luò)規(guī)模和應(yīng)用，其數(shù)據(jù)放置策略主要分為2 類.

1)順序放置策略.順序放置策略通常是把各個存儲節(jié)點看成是邏輯有序的，在對數(shù)據(jù)副本進行分配時先將同一數(shù)據(jù)的所有副本進行編號，然后采用固定的映射方式將各個副本放置到對應(yīng)序號的節(jié)點上.許多存儲系統(tǒng)在設(shè)計時的基本思路是基于成熟RAID 技術(shù)來實現(xiàn)數(shù)據(jù)的放置算法，從而能夠獲得較強的數(shù)據(jù)訪問能力和可靠性.

2)隨機放置策略.隨機放置策略通常是基于某個哈希函數(shù)來決定數(shù)據(jù)的放置目標，因而可將其稱之為偽隨機放置策略［2］.

順序放置策略通常能夠獲得比較穩(wěn)定的、可量化的可靠性，當節(jié)點發(fā)生故障時系統(tǒng)的容錯能力較強，但當發(fā)生故障的結(jié)節(jié)數(shù)量較多時，恢復系統(tǒng)可靠性的開銷比較大.而隨機放置策略可保證數(shù)據(jù)均勻的分布在系統(tǒng)中，從整體上看有利于存儲的負載均衡，且在節(jié)點發(fā)生故障時恢復所丟失數(shù)據(jù)的開銷遠小于前者，但其數(shù)據(jù)訪問的本地性較弱，對系統(tǒng)的性能影響較大，當系統(tǒng)隨機地出現(xiàn)較多的節(jié)點故障時，故障范圍覆蓋各副本放置目標的概率會比較大，因而隨機放置策略的容錯能力相對較差［4］.

2 DHT-R 放置策略

從空間數(shù)據(jù)需求的觀點看，任一地理空間實體的描述，必然涉及2 個最基本要素:空間要素和屬性要素.空間要素定義實體的空間位置特征，并以指定的空間坐標系為參考，按其幾何特征抽象歸結(jié)成點、線、面或規(guī)則幾何特征表示簡單實體，各實體由相應(yīng)的幾何元素表示.多維屬性的數(shù)據(jù)放置關(guān)系到數(shù)據(jù)的查找效率.利用R 樹可將這些多維屬性數(shù)據(jù)用其空間屬性以R 樹結(jié)構(gòu)的形式組織起來，而DHT 作為一種分布式存儲方法在不需要服務(wù)器的情況下，每個客戶端負責一個小范圍的路由，并負責存儲一小部分數(shù)據(jù)，從而實現(xiàn)整個DHT 網(wǎng)絡(luò)的尋址和存儲.

事實上，采用DHT 來維護網(wǎng)絡(luò)中的各個節(jié)點，主要有以下優(yōu)勢:①這種放置方式使得哈希表在節(jié)點失效、遭受攻擊和突發(fā)性高負載情況下都能表現(xiàn)出很好的健壯性;②這種放置方式具有良好的可擴展性，能以較低的系統(tǒng)開銷獲得較大的系統(tǒng)規(guī)模;③可以自我配置，不需要人工干預就可以自動把新加入節(jié)點合并到系統(tǒng)中;④能提供簡單靈活的接口.

R 樹作為一棵用來存儲高維數(shù)據(jù)的平衡樹，當需要進行一個高維空間查詢時，只需要遍歷少數(shù)幾個葉子節(jié)點所包含的指針，查看這些指針指向的數(shù)據(jù)是否滿足要求即可.這種方式使用戶不必遍歷所有數(shù)據(jù)即可獲得答案，效率顯著提高.DHT-R 可使空間數(shù)據(jù)按照分布式設(shè)置并易于組織索引，使用R樹結(jié)構(gòu)組織復雜的空間多維數(shù)據(jù)，便于實現(xiàn)快速訪問.

2.1 空間數(shù)據(jù)設(shè)置索引

空間數(shù)據(jù)索引被表示成一個(K，V)對，K 稱為關(guān)鍵字，可以是數(shù)據(jù)名(或空間數(shù)據(jù)的其他描述信息)的哈希值，V 是空間數(shù)據(jù)在R 樹中cp 指針(cp指針指向?qū)?yīng)的子節(jié)點在R 樹中的存儲位置).所有的空間數(shù)據(jù)索引條目(即所有的(K，V)對)組成一張大的文件索引哈希表，只要輸入目標文件的K值，就可以從這張表中查出該文件的存儲位置.然后，再將上面的大文件哈希表分割成很多局部小塊，按照特定的規(guī)則把這些小塊的局部哈希表分布到系統(tǒng)中的所有參與節(jié)點上，使得每個節(jié)點負責維護其中的一塊.將索引和R 樹相結(jié)合的存儲便于實現(xiàn)快速查找.

2.2 DHT-R 放置策略

索引建立之后，以經(jīng)緯度作為葉子節(jié)點，可將空間數(shù)據(jù)按照其特定的屬性以樹型結(jié)構(gòu)組織起來，具體如圖1 所示.

R 樹采用了一種稱為MBR(Minimal Bounding Rectangle)的方法［5］，從葉子節(jié)點開始用矩形(rectangle)將空間框起來，節(jié)點越往上，框住的空間就越大，以此對空間進行分割.所有最基本的最小邊界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住這些矩形.把相鄰的經(jīng)緯度段劃分到同一塊區(qū)域，劃分好所有經(jīng)緯度段之后，再把鄰近的區(qū)域劃分到更大的區(qū)域，劃分完畢后再次進行更高層次的劃分，直到劃分到只剩下兩個最大的區(qū)域為止.圖1中CDE，F(xiàn)GH 分別是作為A 區(qū)域和B 區(qū)域內(nèi)的按照經(jīng)緯度段劃分的子區(qū)域.

圖1 R 樹組織方式示意圖

2.3 DHT-R 空間數(shù)據(jù)查找

按照“2.1”項的方法設(shè)置好空間數(shù)據(jù)索引，輸入空間數(shù)據(jù)名稱，使用DHT 的直接定址法，

H(KEY)=KEY 或H(KEY)=a.key+b

得到空間數(shù)據(jù)在R 樹中cp 指針，然后再利用R 樹的Search 算法查找空間數(shù)據(jù)的存放位置，其查找方法為:

假設(shè)A 為一棵R 樹的根節(jié)點，查找所有搜索經(jīng)緯段1 覆蓋的記錄條目.

S1［查找子樹］:如果A 是非葉子節(jié)點，且A 所對應(yīng)的矩形與C 有重合，那么檢查所有A 中存儲的條目，對于所有這些條目.

S2［查找葉子節(jié)點］:如果A 是葉子節(jié)點，且A所對應(yīng)的矩形與C 有重合，那么查找C 所指向的經(jīng)緯段1，最后檢查經(jīng)緯段1 直接指向的指所有記錄條目.返回符合條件的記錄.

DHT-R 空間數(shù)據(jù)查找的程序如圖2 所示.

圖2 DHT-R 數(shù)據(jù)查找示意圖

2.4 空間數(shù)據(jù)放置流程

空間數(shù)據(jù)放置流程如圖3 所示.

圖3 空間數(shù)據(jù)放置流程示意圖

現(xiàn)有已知的空間對象m、M，首先提取此空間對象的信息Info，按照(K，V)對的方式先存儲此Info，同時根據(jù)空間屬性，對其按照R 樹結(jié)構(gòu)組織，底層使用Hash 劃分并返回數(shù)據(jù)存放地址到節(jié)點，再將節(jié)點信息返回，加入到(K，V)對中，從而以DHT 來組織這些空間數(shù)據(jù)索引.

3 實驗與分析

在實驗中，本研究采用DHT-R 放置策略實現(xiàn)一個基于局域網(wǎng)環(huán)境的分布式存儲系統(tǒng)，并對其性能進行實驗分析.實驗所用的計算機硬件資源和軟件環(huán)境分別如表1、2 所示.

表1 測試采用的計算機硬件配置

表2 測試所需的軟件環(huán)境

1)可靠性.依據(jù)數(shù)據(jù)一致性操作流程時節(jié)點的增刪改查成功的次數(shù)占總的操作次數(shù)的百分比，由于節(jié)點的失效，刪除等會導致業(yè)務(wù)操作的失敗.可靠性測試結(jié)果如表3 所示.

表3 可靠性測試結(jié)果

表3 數(shù)據(jù)表明，在完成數(shù)據(jù)操作時，基本不會出現(xiàn)保存用戶數(shù)據(jù)的3 個節(jié)點同時失效的情況.

2)操作時延.響應(yīng)速度是評價一個存儲系統(tǒng)系能的重要標準，為了測試系統(tǒng)的時延，采取批量上傳和下載不同大小的文件，然后統(tǒng)計其響應(yīng)時延，按照業(yè)界的測試數(shù)據(jù)，在此應(yīng)用場景下，能接受的時延閥值為300 ms［6］.操作時延測試結(jié)果如表4 所示.

表4 操作時延測試結(jié)果

從表4 可以看出，數(shù)據(jù)取出的的平均操作時延明顯低于數(shù)據(jù)插入的操作時延，這主要是因為執(zhí)行數(shù)據(jù)取出操作，只需要把數(shù)據(jù)從從某個存儲該數(shù)據(jù)的節(jié)點s 上找尋其對應(yīng)的在R 樹的存儲位置，即代表完成操作，而數(shù)據(jù)插入操作需要執(zhí)行從建立R 樹子節(jié)點到地址返回〈K，V〉的存儲和原始數(shù)據(jù)的存儲才代表完成操作［6］.

3)帶寬消耗.在模擬生命周期內(nèi)對于帶寬的消耗量，包括節(jié)點的出口帶寬消耗分布，測試結(jié)果如圖4 所示.

圖4 帶寬消耗

從圖4 可以看出，域內(nèi)帶寬消耗一般都不超過20 000 Mb，其中主要是應(yīng)用流量所占的比例，其次是備份流量和目錄流量，而修復流量和維護流量所占的比例極小，可以忽略不計，這主要是因為正常情況下節(jié)點穩(wěn)定，很少發(fā)生節(jié)點失效下線的情況.

4 結(jié) 論

本研究根據(jù)空間數(shù)據(jù)的特點設(shè)計了一種分布式哈希表(DHT)和R 樹相結(jié)合的放置策略:按照分布式哈希表存儲空間數(shù)據(jù)基本信息和索引地址，同時以R 樹型結(jié)構(gòu)組織和存放空間仿真據(jù)，R 樹存儲使得快速訪問空間數(shù)據(jù)成為可能.實驗證明，使用DHT-R 放置策略得到數(shù)據(jù)存取的可靠性較高，數(shù)據(jù)的吞吐時延也明顯低于業(yè)界的閥值.

［1］朱慶，周艷.分布式空間數(shù)據(jù)存儲對象［J］.武漢大學學報(信息科學版)，2006，31(5):391－395 +422.

［2］陳惟康，杜松.分布式存儲中數(shù)據(jù)放置策略的研究［J］.計算機應(yīng)用與軟件，2009，26(1):6－8 +56.

［3］湯小春，胡杰.分布式計算中可靠的數(shù)據(jù)放置方法［J］.計算機工程，2008，34(23):76－78.

［4］劉翔，汪海玲.分布式存儲中的一種數(shù)據(jù)放置策略［J］.計算機與數(shù)字工程，2009，37(5):27－29.

［5］Guttman A.R-trees:a dynamic index structure for spatial searching［C］//Proceedings of ACM Management of Data(SIGMOD).Massachussetts，USA:ACM Press，1984:47－57.

［6］溫安宇.基于DHT 的key-value 分布式存儲系統(tǒng)［D］.哈爾濱:哈爾濱工業(yè)大學，2010.