苗 放，馬新凡，楊文暉

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

0 引 言

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

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

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

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

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

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

2 DHT-R 放置策略

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

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

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

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

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

2.2 DHT-R 放置策略

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

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

圖1 R 樹(shù)組織方式示意圖

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

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

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

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

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

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

S2［查找葉子節(jié)點(diǎn)］:如果A 是葉子節(jié)點(diǎn)，且A所對(duì)應(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)有已知的空間對(duì)象m、M，首先提取此空間對(duì)象的信息Info，按照(K，V)對(duì)的方式先存儲(chǔ)此Info，同時(shí)根據(jù)空間屬性，對(duì)其按照R 樹(shù)結(jié)構(gòu)組織，底層使用Hash 劃分并返回?cái)?shù)據(jù)存放地址到節(jié)點(diǎn)，再將節(jié)點(diǎn)信息返回，加入到(K，V)對(duì)中，從而以DHT 來(lái)組織這些空間數(shù)據(jù)索引.

3 實(shí)驗(yàn)與分析

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

表1 測(cè)試采用的計(jì)算機(jī)硬件配置

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

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

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

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

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

表4 操作時(shí)延測(cè)試結(jié)果

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

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

圖4 帶寬消耗

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

4 結(jié) 論

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

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

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

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

［4］劉翔，汪海玲.分布式存儲(chǔ)中的一種數(shù)據(jù)放置策略［J］.計(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 分布式存儲(chǔ)系統(tǒng)［D］.哈爾濱:哈爾濱工業(yè)大學(xué)，2010.