面向分布式存儲的空間數據放置方法研究

苗 放，馬新凡，楊文暉

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

0 引 言

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

1 現有數據放置策略

目前，已有的分布式存儲系統中根據不同的網絡規模和應用，其數據放置策略主要分為2 類.

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

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

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

2 DHT-R 放置策略

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

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

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

2.1 空間數據設置索引

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

2.2 DHT-R 放置策略

索引建立之后，以經緯度作為葉子節點，可將空間數據按照其特定的屬性以樹型結構組織起來，具體如圖1 所示.

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

圖1 R 樹組織方式示意圖

2.3 DHT-R 空間數據查找

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

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

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

假設A 為一棵R 樹的根節點，查找所有搜索經緯段1 覆蓋的記錄條目.

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

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

DHT-R 空間數據查找的程序如圖2 所示.

圖2 DHT-R 數據查找示意圖

2.4 空間數據放置流程

空間數據放置流程如圖3 所示.

圖3 空間數據放置流程示意圖

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

3 實驗與分析

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

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

表2 測試所需的軟件環境

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

表3 可靠性測試結果

表3 數據表明，在完成數據操作時，基本不會出現保存用戶數據的3 個節點同時失效的情況.

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

表4 操作時延測試結果

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

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

圖4 帶寬消耗

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

4 結 論

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

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

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

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

［4］劉翔，汪海玲.分布式存儲中的一種數據放置策略［J］.計算機與數字工程，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 分布式存儲系統［D］.哈爾濱:哈爾濱工業大學，2010.