基于平衡結(jié)構(gòu)的對等網(wǎng)絡(luò)存儲系統(tǒng)研究

何亞農(nóng)， 宋 瑋， 趙躍龍

(1.華南理工大學(xué)機械與汽車工程學(xué)院，廣東廣州510640；2.華南理工大學(xué)計算機科學(xué)與工程學(xué)院，廣東廣州510640)

0 引 言

目前，隨著信息量的迅速增長，用戶對海量的存儲需求越來越大，通過構(gòu)建對等網(wǎng)絡(luò)、聚集對等節(jié)點空閑或者自愿提供的存儲服務(wù)來擴大用戶的存儲能力已成為存儲系統(tǒng)的熱點研究問題。當(dāng)前對等網(wǎng)絡(luò)存儲系統(tǒng)的研究，主要涉及兩方面的內(nèi)容：一是底層覆蓋網(wǎng)絡(luò)的確定；二是建立在其上的數(shù)據(jù)存儲管理。本文提出的對等網(wǎng)絡(luò)存儲系統(tǒng)將以提高系統(tǒng)的可用性為目標(biāo)，以平衡為出發(fā)點，從節(jié)點空間均衡和文件在節(jié)點間均衡分布的兩個方面保證系統(tǒng)的平衡性。論文介紹了P-Grid系統(tǒng)虛擬二叉樹結(jié)構(gòu)和路由算法；給出了平衡樹覆蓋網(wǎng)絡(luò)的形式化描述和改進(jìn)節(jié)點的加入以及退出方式來保證樹的平衡性；最后給出了實驗分析和結(jié)論。

1 P-Grid覆蓋網(wǎng)絡(luò)

P-Grid是一個P2P平臺[1-2]，其中數(shù)據(jù)對象的索引值是通過保持原字母順序的散列函數(shù)得到，內(nèi)部各個節(jié)點之間隨機相遇，整個搜索空間被動態(tài)的劃分并被各對等節(jié)點管理。

P-Grid的虛擬二叉樹的構(gòu)建過程和其它以樹為基礎(chǔ)的覆蓋網(wǎng)相比，具有下列優(yōu)點：

(1)不存在根節(jié)點。從圖1可以看出在不斷劃分的過程中，各節(jié)點都最終位于樹的底端。根節(jié)點并不對應(yīng)實際的對等節(jié)點。文獻(xiàn)[3]提出的MPPBTree，BATON都需要一個初始節(jié)點為根節(jié)點，這往往成為樹的瓶頸。

(2)不需存儲大量的父親，兒子，兄弟指針。在樹的結(jié)構(gòu)中，設(shè)置大量的父親，兒子，兄弟節(jié)點會帶來搜索的便利，但同時這些指針的建立和維護是一個很大的問題。

圖1 P-Grid實例

當(dāng)然P-Grid也存在下列問題：

(1)未考慮樹的平衡問題。有可能出現(xiàn)空間劃分的不對稱，如1*空間被4個節(jié)點劃分為100*,101*,110*,111*的4個子空間，而0*則未被劃分。此時必然導(dǎo)致負(fù)責(zé)0*空間的節(jié)點的負(fù)載大于1*空間。

(2)節(jié)點的頻繁加入和退出對路由信息的維護仍然很大。

2 基于平衡樹結(jié)構(gòu)的對等網(wǎng)絡(luò)存儲的思想

根據(jù)文獻(xiàn)[4-5]得知，在P2P系統(tǒng)中只有20%的節(jié)點具有高可用性(93%)，而30%的節(jié)點具有中等可用性。文獻(xiàn)0指出節(jié)點的可用性分為兩種一種是幾乎長期在線的，一種是周期在線的。根據(jù)這個思想，本文對P-Grid中的虛擬二叉樹進(jìn)行改造。包括兩個方面：一是引入樹的平衡機制；二是對節(jié)點按照周期性質(zhì)分級。最終形成一棵主體為平衡二叉樹，底層為多叉樹的結(jié)構(gòu)。

采用虛擬二叉樹構(gòu)建整個模型的主體部分。模型中存在3類節(jié)點：長期節(jié)點(longtermpeer，LTPeer)、周期節(jié)點(periodical node，PPeer)，普通節(jié)點(normalpeer，NPeer)。圖 2 中大圈部分是長期節(jié)點采用P-Grid算法構(gòu)造的虛擬二叉樹。小圈是某長期節(jié)點管理的周期節(jié)點。最底部為普通節(jié)點。長期節(jié)點和周期節(jié)點具有管理系統(tǒng)、貢獻(xiàn)存儲力和消費存儲力的作用。普通節(jié)點也能提供存儲力但以消費存儲力為主。以樹的形式組織資源，符合自然層次組織關(guān)系，容易實現(xiàn)系統(tǒng)的層次化管理，有利于減輕中心節(jié)點的負(fù)載和實現(xiàn)大規(guī)模應(yīng)用的負(fù)載平衡，提高資源的查找效率[7-15]。

圖2 虛擬二叉平衡樹實例

3 基于平衡樹的對等網(wǎng)絡(luò)存儲的形式化描述

3.1 平衡P-Grid形式化描述

定義1 一個樹是平衡樹，當(dāng)且僅當(dāng)對于樹中的節(jié)點其子樹的高度之差不超過1。在本文中，我們只考慮主干是一棵平衡二叉樹。這樣考慮的原因是，周期節(jié)點的加入和退出相對頻繁，若要時刻保持平衡，對系統(tǒng)的性能有一定的影響。

定義2 長期節(jié)點(LTPeer)為可靠的，高性能的節(jié)點，幾乎長期在線，可由研究中心，公共機構(gòu)或大企業(yè)提供，在受控的環(huán)境中運行。也可來自一般用戶提供的高性能資源，由其自愿加入。長期節(jié)點管理依據(jù)P-Grid構(gòu)建算法加入的周期節(jié)點和相關(guān)數(shù)據(jù)存儲索引信息。與P-Grid類似，長期節(jié)點具有路徑值(Path)，由其在虛擬樹中的位置決定，隨著樹動態(tài)變化而變化，其初始值表示為*，說明初始負(fù)責(zé)整個搜索區(qū)間。長期節(jié)點維護4張表。

(1)長期節(jié)點路由表。該表形成于虛擬二叉樹的構(gòu)建過程，其中每一項指向二叉樹同層中一個與該節(jié)點在某位路徑上具有相反值的節(jié)點。每個LTPeer由一個屬性的多元組ninf描述。該多元組記錄LTPeer的唯一ID號、主機名、IP地址、負(fù)載狀態(tài)、在線周期等信息。對于每一個LTPeer具有node(id)=LTPeer iff getinf(LTPeer)=id。路由表項可以組織成一個序列的集合 (l1,Ninf1)(l2,Ninf2)…(ln,Ninfn),li∈{0,1}，其中 Ninfi是 ninf的集合。定義 path(LTPeer)=l1…ln,prefix(i,LTPeer)=l1…li1≤i≤n，refs(i,LTPeer)=Ninfi.集合 Ninfi,1≤i≤n 是滿足下列性質(zhì)的節(jié)點屬性集合

(2)周期節(jié)點路由表。記錄所管理的周期節(jié)點的信息。為每個長期節(jié)點設(shè)置最大管理周期節(jié)點數(shù)2PPeerMaxLen。每個表項是一個三元組(PPeer,KeyPPeer,ninfPPeer)。KeyPPeer代表PPeer的路徑值。ninfPPeer代表PPeer的屬性。

(3)復(fù)制節(jié)點表。復(fù)制節(jié)點是該長期節(jié)點的冗余節(jié)點。

(4)數(shù)據(jù)對象表。記錄本地管理的數(shù)據(jù)對象信息。每一項是指向該數(shù)據(jù)對象實際所在位置節(jié)點的指針(KeyDataObject,Keypeer,AttrDataObject)。KeyDataObject表示邏輯文件名的散列值，AttrDataObject表示文件的屬性。Keypeer是數(shù)據(jù)文件實際所在的位置節(jié)點。謂詞exist_longest_common_prefix(a,b)表示字符串a(chǎn)和b有最大共同前綴；謂詞Store(a,b)表示對象b存儲在節(jié)點z上；謂詞Manage(a,b)表示節(jié)點a管理對象b。

定義3 周期節(jié)點(PPeer)為固定時間段在線的節(jié)點。該節(jié)點具有路徑值，初始值為空，加入到樹中后，值為其管理節(jié)點的路徑值連上其在管理節(jié)點中位置的編碼。每個周期節(jié)點在長期節(jié)點中的編碼為長度PPeerMaxLen二進(jìn)制串。每個周期節(jié)點維護3張表：

(1)普通節(jié)點路由表。每一項是一個二元組(NPeer,ninfNPeer)記錄其管理的普通節(jié)點信息。

(2)普通節(jié)點數(shù)據(jù)文件表。每一項是一個三元組(DataObject,NPeer,AttrDataObject)。

(3)本地數(shù)據(jù)文件表。記錄存放在本地的數(shù)據(jù)文件信息。

定義4 普通節(jié)點(NGPeer)：性能一般的節(jié)點，提供一定的存儲力，并使用網(wǎng)格中的存儲力，在線行為無周期特征。含有一張本地數(shù)據(jù)文件表，并知道其管理節(jié)點。

證明：長期節(jié)點路徑中的每一位代表樹的層數(shù)。路徑的長度說明節(jié)點所處的層數(shù)。比節(jié)點路徑少兩位的節(jié)點意味著比該節(jié)點高兩層。若存在這樣的節(jié)點則說明樹不平衡。

推論1 當(dāng)新節(jié)點加入，入口節(jié)點entry需要向下劃分時，從entry的路由表中獲得集合pset=refs(length(path(entry))-1,entry)，找到pset中路徑值最短的節(jié)點p，若length(path(p))≥length(path(a))則說明可繼續(xù)劃分。

推論2 節(jié)點a離開，樹向上縮減時，從路由表中獲得集合pset=refs(length(path(a))-1,a)，查看相對層的下一層是否有節(jié)點，找到pset中路徑值最長的節(jié)點p，若length(path(p))≥length(path(a))+1則說明a不可離開。

定理2 局部的平衡最終會導(dǎo)致全局的平衡。

證明：對于每一個新節(jié)點的加入，都保證被劃分的入口節(jié)點entry，p∈ refs(length(path(entry))-1,entry)，length(path(p))≥length(path(LTPeer))成立。那么意味著加入對樹的影響的效果仍然是每個節(jié)點滿足定理1。每個節(jié)點的退出也同樣保證樹中每個節(jié)點滿足定理1。

3.2 節(jié)點的加入

節(jié)點的加入和退出的靈活性體現(xiàn)了系統(tǒng)的靈活性和可擴展性。有兩種加入方法：①入口點服務(wù)器(entrypointserver)；②帶外(outofband)。入口服務(wù)器用于返回目前系統(tǒng)中任一已存在節(jié)點作為新加入節(jié)點的入口點，可以以網(wǎng)頁的形式公布。帶外方法通常在入口服務(wù)器不可用時，通過Email或人際直接交流。這里我們延用P-Grid的思想，即節(jié)點隨機相遇，不管它們是什么原因相遇，只需考慮節(jié)點相遇后的處理。這意味著出現(xiàn)兩種相遇情況：第一，系統(tǒng)之外的節(jié)點和系統(tǒng)內(nèi)的節(jié)點相遇，即通常意義上的新節(jié)點加入；第二，系統(tǒng)內(nèi)部節(jié)點的相遇，互相更新路由信息。為了保證主干二叉樹是平衡樹，則需對PGrid的構(gòu)建算法做一些修改，以下節(jié)點主要是針對長期節(jié)點。

(1)系統(tǒng)內(nèi)節(jié)點相遇且兩節(jié)點原有路徑值相同。如path(a1)=1001,path(a2)=1001。

①先做平衡考察。根據(jù)推論1，首先在各自路由表中找到一個節(jié)點集合，如pset=refs(length(path(a1))-1,a1)，即找到路徑中第3位所對應(yīng)的節(jié)點集，獲得該節(jié)點集中路徑最小的節(jié)點p，若該路徑長度小于4，則說明若再繼續(xù)劃分則會出現(xiàn)不平衡。

②交換雙方負(fù)載情況。

若load(a1)遠(yuǎn)大于load(a2)，或二者負(fù)載均大，并且可以向下劃分，則繼續(xù)向下劃分空間。使a1負(fù)責(zé)10010空間，a2負(fù)責(zé)10011空間。

若load(a1)遠(yuǎn)大于load(a2)，或二者負(fù)載均大，但不可向下劃分，則a1，a2互為冗余節(jié)點。a2分擔(dān)一部分a1的負(fù)載。

若兩者負(fù)載情況差別不大，且負(fù)載均小，并且可以向下劃分，則繼續(xù)向下劃分空間。

若兩者負(fù)載情況差別不大，且負(fù)載均小小，但不可向下劃分，則將其中一個節(jié)點推薦到第一步中獲得的節(jié)點p。如，a1將a2推薦給節(jié)點path(p)=100。此時將a2的負(fù)載轉(zhuǎn)移到a1，a2和與p共同劃分100*空間。

(2)兩節(jié)點路徑值是一個字串的關(guān)系。

若 load(a1)遠(yuǎn)大于 load(a2)，此時使 path(a1)=100，a2 分擔(dān)101*空間的負(fù)載。

若load(a2)遠(yuǎn)大于load(a1)，此時使path(a1)=1011，將a1 上1000*，1001*，1010*轉(zhuǎn)移到相應(yīng)負(fù)責(zé)節(jié)點。

(3)沒有路徑值的節(jié)點和有路徑值的節(jié)點相遇。將無路徑節(jié)點的初始值賦為有路徑節(jié)點的值。然后根據(jù)(1)來調(diào)整。

周期節(jié)點加入到系統(tǒng)，意味著被某個長期節(jié)點管理，路徑值為其管理節(jié)點的路徑值連上其在管理節(jié)點中位置的編碼。每個周期節(jié)點在長期節(jié)點中的編碼為長度PPeerMaxLen二進(jìn)制串。用setPPeerPath(LTPeer,PPeer)來設(shè)置周期節(jié)點的路徑：首先判斷選定的長期節(jié)點的所管理的周期節(jié)點個數(shù)是否滿，即≥2PPeerMaxLen。若滿則在當(dāng)前長期節(jié)點已知的信息中選擇負(fù)載最輕的長期節(jié)點，做同樣的判斷。直到找到一個未滿的，按照編碼方案給PPeer設(shè)置路徑。

3.3 節(jié)點的退出

這里主要考慮長期節(jié)點。一般來說長期節(jié)點是幾乎長期在線的節(jié)點，但也不排除主動退出系統(tǒng)的情況。此時需要考慮節(jié)點退出對平衡的影響，以及節(jié)點上相關(guān)信息的轉(zhuǎn)移。

(1)根據(jù)推論2做平衡考察。設(shè)節(jié)點a1要退出，則a1路徑的長度len=(length(path(a1))，字符串sub=prefix(len-1,path(a1))，字符p表示a1路徑在第len位值，加號表示字符串連接，可構(gòu)造路徑path=sub+P～+*,*表示0或1。若存在具有這樣路徑的節(jié)點則，說明a1刪掉會導(dǎo)致不平衡。

(2)若可以刪除，且節(jié)點無子節(jié)點，則可以刪除

(3)若可以刪除，但有子節(jié)點，則將數(shù)據(jù)交與冗余節(jié)點?；驈淖庸?jié)點中選擇狀態(tài)好的節(jié)點替代。

(4)若不平衡，同(3)。

表1給出了根據(jù)平衡策略進(jìn)行數(shù)據(jù)查找的部分實驗結(jié)果。

表1 各種平衡策略進(jìn)行數(shù)據(jù)查找的成功概率

4 結(jié)束語

本文提出了一種將長期在線的節(jié)點構(gòu)建為主體平衡虛擬二叉樹的方法，采用該方法能夠提高對等網(wǎng)絡(luò)中節(jié)點的空間均衡以及可用性，所構(gòu)建的系統(tǒng)具有的特征是：①可擴展性好：由于系統(tǒng)建立在P-Grid的基礎(chǔ)之上，所以對等節(jié)點的加入和退出由相應(yīng)的構(gòu)建算法保證，具有較高的靈活性。②可靠性高：按照節(jié)點可用性的周期特性進(jìn)行分類，將高可用性的節(jié)點組織成樹的主體，數(shù)據(jù)的存儲信息總是放置在高可用性的節(jié)點上。③負(fù)載均衡性好：平衡二叉樹保證了系統(tǒng)中對等節(jié)點在劃分負(fù)責(zé)空間的均衡性。目前，我們正在實現(xiàn)相關(guān)的算法和協(xié)議，同時也在開發(fā)平衡樹的原型系統(tǒng)。

[1]Song W,Zhao Y L,Zeng W Y,et al.Data grid model based on structured p2p overlay network[C].Proceedings of APPT,2007:282-291.

[2]孫知信,楊熙,宮婧.一種基于信任度推薦的P2P-Grid模型[J].吉林大學(xué)學(xué)報(工學(xué)版),2008,38(1):127-130.

[3]Xu L B,Wu G X,You F Q.A structured p2p system with match path and probability balance tree[C].Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences.Washington,DC,USA:IEEE Computer Society,2006:167-174.

[4]劉志忠,王懷民,周斌.一種雙層P2P結(jié)構(gòu)的語義服務(wù)發(fā)現(xiàn)模型[J].軟件學(xué)報,2007,18(8):1922-1932.

[5]劉德輝,周寧,尹剛,等.QFMA:一種支持負(fù)載均衡的多屬性資源定位方法[J].計算機學(xué)報,2008,31(8):1376-1382.

[6]Chandy,John A.Storage allocation inunreliable peer-to-peer systems[C].Proceedings of the International Conference on Dependable Systems and Networks,2006:227-236.

[7]齊德昱,林偉偉.一種新的網(wǎng)格環(huán)境模型——T Grid Model[J].計算機科學(xué),2006,33(12):6-9.

[8]Houssem Jarraya,Maryline Laurent.A secure peer-to-peer backup service keeping great autonomy while under the supervision of a provider[J].Computers&Security,2010,29(2):180-195.

[9]JariVeijalainen.Autonomyheterogeneityand trust inmobile p2p environments[C].International Conference on Multimedia and Ubiquitous Engineering.United States:IEEE Computer Society,2007:41-47.

[10]Lipo Chan,Shanika Karunaseker.CAESAR:Middleware for complex service-oriented peer-to-peer applications[C].Proceedings of the 2nd Workshop on Middleware for Service Oriented Computing,the ACM/IFIP/USENIX International Middleware Conference.USA:ACM,2007:12-17.

[11]田敬,代亞非.P2P持久存儲研究[J].軟件學(xué)報,2007,18(6):1379-1399.

[12]LI Hongxing,Chen Guihai.Data persistence in structured p2p networks with redundancy schemes[C].Proceedings of the 6th International Conference on Grid and Cooperative Computing.United States:IEEE Computer Society,2007:542-549.

[13]Liu Zhiyu,Yuan Ruifeng,Li Zhenhua,et al.Survive under high churn in structured P2P systems:Evaluation and strategy[C].6th International Conference on Computational Science,LNCS 3994.Germany:Springer Verlag,2006:404-411.

[14]Chandy,John A.Storageallocation inunreliable peer-to-peer systems[C].Proceedings of International Conference on Dependable Systems and Networks.United States:IEEE Computer Society,2006:227-236.

[15]Chun B,DabekF,Haeberlen A,etal.Efficient replica maintenance for distributed storage systems[C].Proc of the 3rd Symp on Networked Systems Design and Implementation,2006:45-58.