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

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

0 引 言

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

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

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

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

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

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

圖1 P-Grid實(shí)例

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

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

(2)節(jié)點(diǎn)的頻繁加入和退出對(duì)路由信息的維護(hù)仍然很大。

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

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

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

圖2 虛擬二叉平衡樹實(shí)例

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

3.1 平衡P-Grid形式化描述

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

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

(1)長(zhǎng)期節(jié)點(diǎn)路由表。該表形成于虛擬二叉樹的構(gòu)建過程，其中每一項(xiàng)指向二叉樹同層中一個(gè)與該節(jié)點(diǎn)在某位路徑上具有相反值的節(jié)點(diǎn)。每個(gè)LTPeer由一個(gè)屬性的多元組ninf描述。該多元組記錄LTPeer的唯一ID號(hào)、主機(jī)名、IP地址、負(fù)載狀態(tài)、在線周期等信息。對(duì)于每一個(gè)LTPeer具有node(id)=LTPeer iff getinf(LTPeer)=id。路由表項(xiàng)可以組織成一個(gè)序列的集合 (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é)點(diǎn)屬性集合

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

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

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

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

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

(2)普通節(jié)點(diǎn)數(shù)據(jù)文件表。每一項(xiàng)是一個(gè)三元組(DataObject,NPeer,AttrDataObject)。

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

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

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

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

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

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

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

3.2 節(jié)點(diǎn)的加入

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

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

①先做平衡考察。根據(jù)推論1，首先在各自路由表中找到一個(gè)節(jié)點(diǎn)集合，如pset=refs(length(path(a1))-1,a1)，即找到路徑中第3位所對(duì)應(yīng)的節(jié)點(diǎn)集，獲得該節(jié)點(diǎn)集中路徑最小的節(jié)點(diǎn)p，若該路徑長(zhǎng)度小于4，則說明若再繼續(xù)劃分則會(huì)出現(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é)點(diǎn)。a2分擔(dān)一部分a1的負(fù)載。

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

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

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

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

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

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

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

3.3 節(jié)點(diǎn)的退出

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

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

(2)若可以刪除，且節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)，則可以刪除

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

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

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

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

4 結(jié)束語(yǔ)

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

[5]劉德輝,周寧,尹剛,等.QFMA:一種支持負(fù)載均衡的多屬性資源定位方法[J].計(jì)算機(jī)學(xué)報(bào),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].計(jì)算機(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持久存儲(chǔ)研究[J].軟件學(xué)報(bào),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.