宋瑋 趙躍龍

(華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院,廣東廣州 510006)

結(jié)構(gòu)化 P2P覆蓋網(wǎng)絡(luò)按照一定的邏輯拓?fù)浣Y(jié)構(gòu)將系統(tǒng)物理層的節(jié)點相互連接起來.在覆蓋網(wǎng)絡(luò)提供的加入、路由、查找、退出等基本功能之上可實現(xiàn)不同的應(yīng)用服務(wù).目前已有的建立在覆蓋網(wǎng)絡(luò)之上的P2P數(shù)據(jù)存儲系統(tǒng)有:使用MIT提出的Chord覆蓋網(wǎng)絡(luò)建立的開放文件存儲環(huán)境 CFS[1];使用Berkeley提出的Tapestry覆蓋網(wǎng)絡(luò)建立的Ocean-Store[2];使用微軟亞洲研究院提出的Xring覆蓋網(wǎng)絡(luò)建立的面向較少更新的存儲系統(tǒng)BitVault[3]以及清華大學(xué)提出的采用Tourist路由算法建立的面向?qū)ο蟮拇鎯ο到y(tǒng)Granary[4].覆蓋網(wǎng)絡(luò)層是整個P2P存儲系統(tǒng)運行的基礎(chǔ),其特性影響到整個系統(tǒng)的特性,是系統(tǒng)成功與否的關(guān)鍵.

P-Grid覆蓋網(wǎng)絡(luò)是一個分布式信息管理的P2P平臺,具有完全分散管理、自組織[5-6]、基于動態(tài) IP的數(shù)據(jù)管理(更新)[7-8]、分布式負(fù)載平衡[9-10]等特點.覆蓋網(wǎng)的構(gòu)建基于隨機(jī)算法和本地交互,面向低在線率的節(jié)點環(huán)境,該網(wǎng)絡(luò)既具有虛擬樹的結(jié)構(gòu),能以樹的形式組織資源實現(xiàn)系統(tǒng)的層次化管理,提高資源查找效率,又?jǐn)[脫了基于樹的覆蓋網(wǎng)絡(luò)結(jié)構(gòu)(如MPPBTree[11],BATON[12])中對根節(jié)點的依賴,非葉節(jié)點并不對應(yīng)實際的對等節(jié)點,各節(jié)點最終成為葉節(jié)點.整個樹的構(gòu)建過程不需要中心協(xié)調(diào),節(jié)點隨機(jī)漫步導(dǎo)致的相遇是樹構(gòu)建的動力,這樣一來,樹形成的速度(即收斂性)便是一個關(guān)鍵,它嚴(yán)重影響整個系統(tǒng)的性能.文中重點在兩種情況下討論了PGrid的收斂性,改進(jìn)了原有算法以加快構(gòu)建速度,為今后建立在其上的應(yīng)用系統(tǒng)提供更好的支撐.

1 P-Grid概述

1.1 P-Grid數(shù)據(jù)結(jié)構(gòu)

文獻(xiàn)[5-6]描述了P-Grid系統(tǒng)中基于虛擬二叉搜索樹的覆蓋網(wǎng)絡(luò)及路由算法.系統(tǒng)中每個對象,包括對等節(jié)點和數(shù)據(jù)對象都擁有一個二進(jìn)制索引值,對等節(jié)點還擁有路徑值(表示為path(peer)),表明節(jié)點在二叉樹中的路徑,動態(tài)形成于虛擬二叉樹的構(gòu)建過程.每個對等節(jié)點根據(jù)其路徑值對應(yīng)一個索引值區(qū)間;每個對等節(jié)點含有兩類信息:數(shù)據(jù)索引信息和路由信息.數(shù)據(jù)索引信息是存儲索引值最大前綴與節(jié)點路徑值相同的數(shù)據(jù)對象的索引信息.圖 1所示的P-Grid實例中節(jié)點4的路徑值為010,則存儲以 010為前綴的數(shù)據(jù)對象的索引信息.節(jié)點路由信息形成路由表,表中每一層路由項指向樹中與該節(jié)點在路徑值某位上具有相反值的節(jié)點信息.如節(jié)點 4中第二層路由項 00:7說明路徑值第二位與節(jié)點4相反的是節(jié)點 7.這樣當(dāng)節(jié)點 4收到查找索引值00*的請求時,就可以將其轉(zhuǎn)發(fā)到節(jié)點7.

圖1 P-Grid實例Fig.1 P-Grid example

1.2 P-Grid構(gòu)建過程

P-Grid中節(jié)點被假設(shè)局部隨機(jī)相遇,而不考慮是何種原因相遇.相遇后根據(jù)雙方已有的路徑值劃分并負(fù)責(zé)索引值空間,路徑值做相應(yīng)的調(diào)整.節(jié)點路徑的初始值表達(dá)為*,說明其初始負(fù)責(zé)全體索引值空間.下面簡單描述文獻(xiàn)[5]中的P-Grid構(gòu)建算法.節(jié)點相遇有3種情況:(1)兩節(jié)點原有路徑值相同(CASE1).如path(a1)=10,path(a2)=10,則兩者對10*空間進(jìn)一步劃分,或者二者互為冗余節(jié)點共同負(fù)責(zé)10*空間;劃分后path(a1)=100,負(fù)責(zé)100*空間; path(a2)=101,負(fù)責(zé)101*空間.(2)兩節(jié)點路徑值是一個子串關(guān)系(CASE2和CASE3).如path(a1)=10, path(a2)=101,此時讓path(a1)=100.(3)兩節(jié)點負(fù)責(zé)不同的空間(CASE4),如path(a1)=10, path(a2)=01,則兩節(jié)點根據(jù)自身的路由信息,相互把對方推薦給在另一空間的其它節(jié)點;若a1的一條路由表項為0:a3,則說明a3負(fù)責(zé)0*空間,a1將a2推薦給 a3,a2將和 a3根據(jù)相遇情況選擇處理方式,這有可能再次產(chǎn)生推薦;這樣,整個二進(jìn)制索引值空間被動態(tài)地劃分并被各對等節(jié)點管理.

1.3 P-Grid的收斂性

P-Grid的路徑長度是動態(tài)變化無限制的,這也是它和其它覆蓋網(wǎng)絡(luò)的區(qū)別.因此收斂性表現(xiàn)為在節(jié)點規(guī)模一定的前提下,多少次交互后每個節(jié)點的路徑不再變化,或是到達(dá)指定的長度,或是達(dá)到其它的限制條件.文獻(xiàn)[5]通過實驗指出了 3個參數(shù)對交互次數(shù)的影響:(1)推薦(遞歸)深度recmax,即CASE4導(dǎo)致再次推薦的次數(shù).recmax=0表示不推薦,即,若出現(xiàn)CASE4情況相遇節(jié)點相互不推薦,這導(dǎo)致整個構(gòu)建過程的交互次數(shù)較多.采用適當(dāng)?shù)纳疃戎悼梢允菇换コ晒Φ母怕试龃?但遞歸深度過大反而會導(dǎo)致節(jié)點過度細(xì)化,而使交互次數(shù)增多,文獻(xiàn)實驗指出recmax=2較好.(2)最大路徑長度k.這里并不是將P-Grid的路徑長度限制為k,而是指在節(jié)點個數(shù)允許的情況下,想達(dá)到的 k越長則需要的交互次數(shù)越多.(3)節(jié)點每層路由項中節(jié)點的個數(shù)refmax,refmax為在CASE4情況下進(jìn)行節(jié)點推薦的最大個數(shù),推薦的個數(shù)越多,交互次數(shù)越多,文獻(xiàn)實驗指出當(dāng)推薦選擇一個節(jié)點時效果最好.下面討論的收斂速度的提升是在指定k、recmax、refmax以及推薦個數(shù)的基礎(chǔ)上進(jìn)行的.

2 提高收斂速度的改進(jìn)算法

提高收斂速度的改進(jìn)算法基于以下兩個前提:

(1)忽略節(jié)點動態(tài)性對構(gòu)建過程中路由維護(hù)帶來的影響,將提高兩個在線節(jié)點交互的有效性與路由維護(hù)看成獨立的兩個內(nèi)容,不管算法如何改進(jìn)都無法影響節(jié)點的上線和離線行為,所以將節(jié)點的動態(tài)行為對構(gòu)建的影響看成是一個不變的量,不再計入評價范圍內(nèi).

(2)P-Grid不僅僅用于動態(tài)的P2P系統(tǒng),還可以作為任何一個分布式應(yīng)用需求下的基礎(chǔ)結(jié)構(gòu).PGrid的構(gòu)建過程在分布式應(yīng)用中可位于兩個不同階段:第一,在完全新的分布式應(yīng)用中P-Grid的構(gòu)建位于初始化階段,節(jié)點專用于該應(yīng)用,此時節(jié)點上不存在任何數(shù)據(jù)索引信息;第二,在已有的分布式應(yīng)用中,由于某種原因,要求利用P-Grid重建基礎(chǔ)結(jié)構(gòu),此時節(jié)點上將保留原有的共享數(shù)據(jù)索引信息.下面的討論與改進(jìn)將從構(gòu)建前節(jié)點無數(shù)據(jù)索引和有數(shù)據(jù)索引兩方面進(jìn)行.

定義1 數(shù)據(jù)索引的消耗 數(shù)據(jù)索引在節(jié)點上的存儲除了帶來存儲上的消耗.還帶來其它的消耗,如某一數(shù)據(jù)是熱點數(shù)據(jù),則將為存儲它的索引的節(jié)點帶來較高的訪問頻率,這可看成對節(jié)點的一種消耗.這里并不區(qū)分特定的消耗類型,每一個數(shù)據(jù)索引將因為其自身數(shù)據(jù)的特點給節(jié)點帶來不同的消耗.同時假設(shè)數(shù)據(jù)索引的消耗是可分的,即當(dāng)一個數(shù)據(jù)索引被復(fù)制到另一個節(jié)點上時,其消耗也將被分割一部分到該節(jié)點;而當(dāng)一個索引被轉(zhuǎn)移至另一節(jié)點時,則其消耗也被轉(zhuǎn)移.

定義2 節(jié)點的意愿 每個節(jié)點會根據(jù)自己的資源現(xiàn)狀給出承擔(dān)數(shù)據(jù)索引消耗的總意愿,如設(shè)置訪問次數(shù)的上限防止對數(shù)據(jù)索引的過多的查詢.

定義3 節(jié)點的負(fù)載 存儲數(shù)據(jù)索引值帶來的總消耗稱為節(jié)點的負(fù)載.

定義4 節(jié)點的初始負(fù)載量loadpercentage 節(jié)點在進(jìn)入交互前因為其它原因而具有的負(fù)載量,用節(jié)點的負(fù)載與節(jié)點意愿的比值表示.

定義5 Ignore-of-Load構(gòu)建算法 構(gòu)建過程中不考慮節(jié)點的初始負(fù)載量.

定義6 Care-of-Load構(gòu)建算法 構(gòu)建過程中考慮節(jié)點的意愿及初始負(fù)載量.

定義7 數(shù)據(jù)索引路徑符合度satisfy 一個節(jié)點存儲的數(shù)據(jù)索引中符合與節(jié)點路徑具有最大前綴關(guān)系的索引個數(shù)百分比.節(jié)點路徑為“*”時路徑符合度為1.

定義 8 收斂狀態(tài)參數(shù) 描述交互算法的狀態(tài),用于衡量收斂性,采用路徑長度k和符合度 satisfy兩個參數(shù).在Care-of-Load情況下,受節(jié)點意愿的限制,導(dǎo)致本該能轉(zhuǎn)移的數(shù)據(jù)索引無法轉(zhuǎn)移,因此要求已存在的索引都轉(zhuǎn)移到具有最大前綴關(guān)系的節(jié)點上所需的交互次數(shù)非常大,所以應(yīng)該設(shè)置一定的符合度來描述收斂狀態(tài).

定義9 收斂速度 達(dá)到指定收斂狀態(tài)參數(shù)值產(chǎn)生的節(jié)點交互次數(shù).

2.1 Ignore-of-Load構(gòu)建算法

每次交互引起的路徑變化程度以及推薦的成功率影響交互的次數(shù).原有構(gòu)建算法中路徑的改變以“1位”為單位,如:兩節(jié)點a1、a2相遇,path(a1)= 01001、path(a2)=01,向下劃分后路徑為path(a1)= 01001、path(a2)=011.對于a2需要更多的交互才能使其路徑向下延伸.為了充分利用每次交互的信息,減少交互的次數(shù),給出如下式所示的改進(jìn)1:

即直接將a2的路徑延長為path(a2)=01000,使其最后一位與a1相反,a2與 a1交換前4層的路由.

根據(jù)原構(gòu)建算法,節(jié)點p向節(jié)點q推薦節(jié)點r采用的推薦方式有兩種,一種是在 p的路由表中隨機(jī)選取節(jié)點r[5],另一種是選取p的路由表中與q具有最大共同前綴的節(jié)點[9],但文獻(xiàn)并未對這兩種方式做出比較.通過觀察節(jié)點的路由表的特點,以path(q)=101、path(p)=01為例,若p的路由表第一層為1:a3(111),a4(100),a5(101),a6(10110),可以看出選擇推薦a6和a5會使q路徑向下劃分,而選擇a3則在q和 a3的交互過程中需要在第二層進(jìn)行推薦,若推薦的節(jié)點不合適還要進(jìn)行第三層的推薦,a4比 a3的情況好一點,只需要在第三層推薦一次.根據(jù)該特點給出改進(jìn)2以提高推薦的成功率:

p從路由表中首選一個以 q路徑為子串的節(jié)點;若沒有,則選與q同路徑的節(jié)點;若再沒有,則再選與q具有最大共同前綴的節(jié)點;若還是沒有,則最后隨機(jī)選.

2.2 Care-of-Load構(gòu)建算法

在構(gòu)建覆蓋網(wǎng)絡(luò)的過程中,數(shù)據(jù)索引會隨著節(jié)點路徑的形成而轉(zhuǎn)移到具有最大前綴關(guān)系的節(jié)點上.這里討論 3種思路,采用路徑長度及符合度作為收斂狀態(tài)參數(shù).

2.2.1 以路徑為主導(dǎo)的構(gòu)建算法

以路徑為主導(dǎo)的算法指節(jié)點路徑的向下延伸與數(shù)據(jù)索引的轉(zhuǎn)移是獨立的,即節(jié)點路徑向下延伸不受節(jié)點意愿和索引消耗的影響,而數(shù)據(jù)索引的轉(zhuǎn)移則是在每次節(jié)點相遇時根據(jù)雙方的路徑和意愿盡量將索引轉(zhuǎn)移到對方.因此該算法的實現(xiàn)直接在2.1節(jié)的兩個改進(jìn)上進(jìn)行,在每個CASE結(jié)束后加入數(shù)據(jù)索引交換環(huán)節(jié).最優(yōu)交換是一個最優(yōu)組合問題,這里不考慮最優(yōu)化的問題,只關(guān)心盡可能多地進(jìn)行索引的交換.交換分冗余和轉(zhuǎn)移兩種,當(dāng)兩節(jié)點路徑值相同時,相互冗余數(shù)據(jù)索引,否則根據(jù)對方路徑轉(zhuǎn)移.一個數(shù)據(jù)索引被冗余到目標(biāo)節(jié)點上,意味著減輕源節(jié)點一半的消耗,則索引消耗也將被分割一半到目標(biāo)節(jié)點;而一個索引被轉(zhuǎn)移目標(biāo)節(jié)點,則其消耗也被轉(zhuǎn)移.

2.2.2 以數(shù)據(jù)索引為主導(dǎo)的構(gòu)建算法

采用2.2.1節(jié)的算法每個節(jié)點可以很快達(dá)到指定的最大路徑長度,但符合度低,為了達(dá)到指定的符合度則需要花費更多的交互次數(shù).文獻(xiàn)[8]給出了考慮數(shù)據(jù)索引的思路:當(dāng)兩個節(jié)點相遇,若每個節(jié)點都能將兩個節(jié)點所擁有的所有數(shù)據(jù)索引全部放下,則兩節(jié)點冗余,否則就分區(qū).但該文獻(xiàn)假設(shè)所有節(jié)點是同質(zhì)的且具有相同的意愿,并且節(jié)點的意愿僅體現(xiàn)為愿意管理的數(shù)據(jù)索引個數(shù),數(shù)據(jù)索引之間無差別.這里結(jié)合節(jié)點的意愿和索引消耗對文獻(xiàn)[8]的算法進(jìn)行擴(kuò)展,形成以數(shù)據(jù)索引為主導(dǎo)的構(gòu)建算法.算法中路徑的延長不是任何時候都可以進(jìn)行的,即,原算法CASE1中先進(jìn)行是否冗余(isRedundent)和是否下分(isDivide)的判斷,在CASE2和CASE3中先進(jìn)行是否延伸路徑的判斷(isExtend).

isDivide的思路如下:Max(Min)表示兩個節(jié)點中具有高(低)意愿的節(jié)點;Ci是節(jié)點i中與兩節(jié)點路徑都不符的索引消耗總和;Preferi表示節(jié)點i的意愿;Totall表示兩個節(jié)點中以path+l為路徑的索引消耗總和,path表示兩節(jié)點的路徑(此時路徑相同),l∈{0,1}.當(dāng)存在l∈{0,1}使

成立時,則可以下分,即下分依賴于即將形成的兩個分區(qū)中的索引是否可以分別放在兩個節(jié)點中.

isRedundent的思路如下:Ax表示節(jié)點x中與相遇節(jié)點共有的且符合路徑的數(shù)據(jù)索引消耗總和,Bx表示節(jié)點 x獨有且符合路徑的數(shù)據(jù)索引消耗總和, a1和a2表示相遇的兩個節(jié)點,當(dāng)下式成立才能進(jìn)行冗余:

對于isExtend,只有當(dāng)長路徑的節(jié)點能夠完全接受短路徑轉(zhuǎn)過來的索引消耗時,短路徑才能向下延伸一位.

2.2.3 具有符合度調(diào)整的構(gòu)建算法

在2.2.2節(jié)算法中,盡管符合度相對較高,但路徑的延伸過程非常慢,若每個節(jié)點的意愿足夠大將導(dǎo)致一個節(jié)點放置所有的數(shù)據(jù)索引,而這樣的結(jié)果對于構(gòu)建P-Grid意義不大.因為P-Grid路由結(jié)構(gòu)的建立是本研究的主要任務(wù),構(gòu)建過程會影響索引的分布,這里僅僅期望索引能隨構(gòu)建過程達(dá)到一個較好的調(diào)整.

為了在收斂速度及符合度間獲得一個平衡,對2.2.1節(jié)算法進(jìn)行改進(jìn),形成具有符合度調(diào)整的算法.算法中的函數(shù)Peer.FindPeer()用于在節(jié)點交互結(jié)束后各自依據(jù)自身的路由信息盡量將索引轉(zhuǎn)移到合適的節(jié)點,以此提升符合度.Peer.FindPeer()算法如下:

通過分析可知一個節(jié)點中需要轉(zhuǎn)移的索引所具有的特點,如路徑為 0101的節(jié)點,其不合路徑的數(shù)據(jù)索引可分為 1、00、011、0100 4類,這正好與每層路由表項的前綴是一致的.因此可以考慮在路由表中選擇節(jié)點進(jìn)行索引的轉(zhuǎn)移以提高符合度,但由轉(zhuǎn)移導(dǎo)致的交互也應(yīng)該統(tǒng)計進(jìn)入交互總數(shù).此外存在一個現(xiàn)象,即節(jié)點a、b經(jīng)過CASE1、CASE2、CASE3向下延伸后,a的最后一層路由表項往往只有一個節(jié)點b,或是b的最后一層路由表項只有一個節(jié)點a,此時再次進(jìn)行轉(zhuǎn)移意義不大,需要利用倒數(shù)第二層表項來提高符合度.以a(0101)節(jié)點為例,若倒數(shù)第二層路由表項為011:a3(011),且a3的最后一層路由為010:a4(010),a5(0101),a6(0100),則若能挑出a6,將a上形如 0100的索引轉(zhuǎn)過去,將會提高a的符合度.

3 算法分析

3.1 Ignore-of-Load算法中路由更新相關(guān)問題

每個節(jié)點由于承擔(dān)路由功能而成為路由表項中的一員,節(jié)點的路徑是推薦的依據(jù).路由的更新來自于兩節(jié)點交互時充分交換最新信息.這里不討論如何設(shè)計出更好、更新的算法,側(cè)重分析在采用與原算法相同的更新算法下,Ignore-of-Load構(gòu)建算法是否會加重更新的負(fù)擔(dān),以及未及時更新的路由信息是否對推薦產(chǎn)生影響.

(1)路由更新的負(fù)擔(dān)與節(jié)點路徑改變的概率相關(guān).考慮到節(jié)點路徑的改變導(dǎo)致路由需要更新,將路由更新的負(fù)擔(dān)定義為整個系統(tǒng)中單位時間內(nèi)路徑改變的節(jié)點個數(shù).設(shè)每個節(jié)點在每次相遇中改變路徑的概率是s,在一定的時間段t內(nèi),有n個節(jié)點相遇,則單位時間內(nèi)改變路徑的節(jié)點為ns/t個.在節(jié)點相遇頻率不變的情況下,s越大,則更新負(fù)擔(dān)越大.

(2)原算法一次相遇中節(jié)點路徑改變的概率為1/2len(p),改進(jìn) 1不影響路徑改變概率.設(shè)節(jié)點 p的路徑為l1l2…llen,lj(0,1),j[1,len],節(jié)點路徑的改變來自于與同路徑或前綴為 l1l2…llen的節(jié)點相遇.設(shè)索引值均勻分布,節(jié)點相遇的概率平等,不存在過多的節(jié)點負(fù)責(zé)某些分區(qū),則與相遇的節(jié)點第一位相同的概率為1/2,在第一位相同的情況下第二位相同的概率為1/22,這樣在前l(fā)en-1位相同下最后一位相同的概率為 1/2len(p),則路徑改變的概率為1/2len(p).

按照改進(jìn) 1的延伸方法也不能導(dǎo)致負(fù)責(zé)某些特定分區(qū)的節(jié)點增多,如對于path(a1)=01與path(a2)= 01001相遇,使path(a1)=01000,這并不意味著負(fù)責(zé)0100區(qū)域的節(jié)點增多,因為根據(jù)P-Grid結(jié)構(gòu)若存在path(a2)=01001,則必然會存在路徑為1*、00*、011*、0101*的節(jié)點,而節(jié)點相遇的概率是一樣的,這樣仍然不存在過多的節(jié)點負(fù)責(zé)某些分區(qū),從而不影響路徑改變概率.

從上面可知路徑改變的概率不變,這樣改進(jìn) 1不會加重更新的負(fù)擔(dān).

(3)延時更新的節(jié)點路徑不會導(dǎo)致改進(jìn) 2低于原算法的收斂速度.節(jié)點路徑的變化是在前一次的路徑基礎(chǔ)上向下延伸,必定存在前綴關(guān)系.這樣對于未及時更新的節(jié)點,在改進(jìn) 2中只是降低了它被推薦的可能性.以path(q)=101、path(p)=01為例,若p當(dāng)前的路由表第一層為1:a3(111),a4(100), a5(101),a6(10);而 a6(10)實際的路徑為a6(10110),這樣根據(jù)改進(jìn) 2,a5被優(yōu)先選擇,但這種選擇仍然優(yōu)于原算法隨機(jī)方法或原算法最大前綴方法.因此改進(jìn)算法不會低于原算法的收斂速度.

3.2 改進(jìn)算法產(chǎn)生二叉樹的特性

特性1 Ignore-of-Load構(gòu)建算法、以路徑為主導(dǎo)的構(gòu)建算法及具有符合度調(diào)整的Care-of-Load構(gòu)建算法產(chǎn)生的是一棵完全二叉樹.指定最大路徑長度,在節(jié)點數(shù)量足夠的情況下,短路徑的節(jié)點總會與長路徑的節(jié)點相遇從而延伸直到所有的節(jié)點都達(dá)到最大路徑,并且根據(jù)P-Grid的構(gòu)建特性,節(jié)點路徑的每一位上都至少存在一個節(jié)點與之具有相反位.

特性2 Ignore-of-Load構(gòu)建算法、以路徑為主導(dǎo)的構(gòu)建算法及具有符合度調(diào)整的Care-of-Load構(gòu)建算法最終產(chǎn)生前綴碼.與特性 1的分析類似,如果存在一個節(jié)點,它是另一個節(jié)點的前綴,則說明構(gòu)建還未完成,前一個節(jié)點必定會向下延伸,且最后一位相反.

特性3 以數(shù)據(jù)為主的Care-of-Load構(gòu)建算法不保證產(chǎn)生前綴碼.原因在于路徑的向下延伸受節(jié)點意愿的制約,使得路徑停留在某個長度.

3.3 數(shù)據(jù)索引查找成功率

設(shè)路徑長度為k,節(jié)點數(shù)為N,則第h層各分區(qū)擁有的平均節(jié)點數(shù)為N/2h,h[0,k],定義T為單個節(jié)點擁有的符合路徑的索引占其負(fù)責(zé)分區(qū)的總索引數(shù)比例,一般使refmax≤N/2h并對所有層取相同值,節(jié)點在線概率為Pr,則Care-of-Load構(gòu)建算法中對數(shù)據(jù)索引的查找成功率為(1-(1-Pr)refmax)k× T.當(dāng)不考慮節(jié)點的離線情況時Pr=1,則成功查找率由T決定.

最壞情況下的成功查找次數(shù)為log2(N/r′)× refmaxΘ(log2N),r′為負(fù)責(zé)最低層分區(qū)的節(jié)點平均個數(shù).

4 模擬實驗

模擬實驗采用P2P模擬器Peersim[13],PeerSim是一個Java編寫的模擬P2P Overlay的軟件.使用Peersim提供的占用較少資源的Cycle-based的模擬方式,模擬實驗共同參數(shù)定義為:recmax=2,最大路徑長度k=6,refmax=10,推薦時采用1個節(jié)點.

4.1 Ignore-of-Load構(gòu)建算法的模擬實驗

節(jié)點規(guī)模 N分別為 400、600、1000時,對原算法隨機(jī)版、原算法最大前綴版及 3個改進(jìn)算法(改進(jìn) 3為 1和 2的組合)分別執(zhí)行 100次后的平均交互次數(shù)如圖2所示.

圖2 5種Ignore-of-Load算法的交互次數(shù)Fig.2 Number of communications times of five Ignore-of-Load algorithms

由圖 2可見,3個改進(jìn)算法帶來的效果是非常明顯的.特別是改進(jìn) 3,交互次數(shù)的減少量超過原算法最大前綴版的50%.

4.2 Care-of-Load構(gòu)建算法的模擬實驗

數(shù)據(jù)索引的消耗以及數(shù)據(jù)索引的副本個數(shù)采用平均分布和Zip f分布,在不同的分布下分別比較3種Care-of-Load構(gòu)建算法在交互過程中的交互次數(shù)及查找失敗率.

4.2.1 平均分布

節(jié)點規(guī)模 N=400,每個節(jié)點的意愿數(shù)量級為103,平均分布在[1000,10000]之間,數(shù)據(jù)索引規(guī)模M=1000,數(shù)量級為 102,平均分布在[100,1 000]之間,數(shù)據(jù)索引在每個節(jié)點中存儲的概率是平等的.

3個算法在一次構(gòu)建過程中平均路徑長度及符合度的變化趨勢如圖 3所示,設(shè)隨機(jī)進(jìn)行 20000次交互.

圖3 3種Care-of-Load構(gòu)建算法平均路徑長度及平均符合度的變化趨勢Fig.3 Average path length and average satisfaction of three Care-of-Load algorithms

從圖 3可見,以路徑為主導(dǎo)的算法在路徑的延伸上很快,但符合度的下降也很迅速;以索引為主導(dǎo)的算法正好相反;具有符合度調(diào)整的算法效果是兩者的折中,并且符合度可以達(dá)到最好.同時由圖 3可見,3種算法中,數(shù)據(jù)的轉(zhuǎn)移跟不上路徑延伸的速度,當(dāng)路徑達(dá)到指定長度后,接下來的交互僅僅是在進(jìn)行數(shù)據(jù)索引的交換,而這個過程是緩慢的.

3種算法在不同的loadpercentage下同時達(dá)到指定路徑長度和符合度(satisfy=0.8)所需的交互次數(shù)如圖4所示.考慮到以數(shù)據(jù)索引為主導(dǎo)的算法在路徑延伸上的缺陷,參數(shù)設(shè)置為當(dāng)loadpercentage= 0.2,0.3,0.4時,指定k=2.8,4,5;loadpercentage= 0.5,0.6,0.7,0.8時,k=5.5.以路徑為主導(dǎo)的算法和具有符合度調(diào)整的算法k=6.

圖4 3種Care-of-Load構(gòu)建算法的交互次數(shù)Fig.4 Number of communications of three Care-of-Load algorithms

圖4所示結(jié)果說明:(1)當(dāng)loadpercentage≤0.5時,以路徑為主導(dǎo)的算法的交互次數(shù)偏小,其原因之一為較小的loadpercentage使得當(dāng)路徑達(dá)到指定長度時,無需過多的交互用于數(shù)據(jù)索引的交換,但隨著loadpercentage的增加,需要大量的交互用于數(shù)據(jù)索引的交換;原因之二為構(gòu)建過程的終止條件satisfy=0.8是一個較容易達(dá)到的條件,若將satisfy設(shè)置得更高(如satisfy=0.9),則該算法不如具有符合度調(diào)整的算法(見圖5).另外在loadpercentage偏大時表現(xiàn)良好的算法才有意義,因為較小的loadpercentage無法體現(xiàn)出初始負(fù)載對構(gòu)建過程帶來的影響. (2)當(dāng)loadpercentage≤0.5時,以數(shù)據(jù)索引為主導(dǎo)的算法的交互次數(shù)偏小,但存在 2.2.3節(jié)中所述的缺陷,每個節(jié)點將放置所有的數(shù)據(jù)索引,而這樣的結(jié)果對于構(gòu)建P-Grid意義不大.(3)具有符合度調(diào)整的算法在具有較大loadpercentage時表現(xiàn)良好,因為通過符合度的調(diào)整,使得節(jié)點交互具有針對性.

圖5 Zipf分布下的交互次數(shù)Fig.5 Number of communications Zipf distribution

以數(shù)據(jù)為主導(dǎo)的算法和具有符合度調(diào)整的算法對初始數(shù)據(jù)索引的查找失敗率如表1所示.loadpercentage的取值在0.2～0.8之間,并采用了一個混合比例即每個節(jié)點的loadpercentage隨機(jī)在0.2～0.8之間取值;每個初始值下兩類算法各產(chǎn)生 20個P-Grid結(jié)構(gòu),對每個結(jié)構(gòu)查詢 2000次,統(tǒng)計失敗的次數(shù);為了比較兩類算法對查找的影響,設(shè)節(jié)點總是在線.表1中A和C表示以數(shù)據(jù)為主導(dǎo)的算法失敗次數(shù)和節(jié)點擁有索引占分區(qū)平均比例,即 3.3節(jié)中定義的T;B和D表示具有符合度調(diào)整的算法失敗次數(shù)和節(jié)點擁有索引占分區(qū)平均比例.表 1所示結(jié)果說明:(1)查找失敗率與節(jié)點擁有索引占分區(qū)平均比例相關(guān),如119≈2000×(1-0.92);(2)當(dāng)loadpercentage為0.2～0.4時,A與C的值不符合(1)的結(jié)論,原因在于,其路徑長度不超過 4,分區(qū)擁有的索引多,但因為剩余意愿大,所以每個節(jié)點都極大地放置了該分區(qū)的索引,使得整體查找失敗率減少;(3)隨著loadpercentage的增加,具有符合度調(diào)整的算法表現(xiàn)出較好的查找效果,原因在于有針對性地轉(zhuǎn)移了數(shù)據(jù).

表1 平均分布下的查找失敗率Table 1 Search failure rate in average distribution

4.2.2 Zipf分布

文獻(xiàn)[14]總結(jié)出 P2P環(huán)境下副本的數(shù)量和流行程度遵循Zipf分布.模仿文獻(xiàn)[15]產(chǎn)生Zipf分布數(shù)據(jù)的方式,選定一個特定的文檔將其中出現(xiàn)的不同的單詞個數(shù)(1793)作為數(shù)據(jù)索引個數(shù),單詞出現(xiàn)的頻率(不超過850)作為索引的消耗,并且同時作為索引的副本個數(shù),使得數(shù)據(jù)索引的消耗以及索引的副本個數(shù)符合Zipf分布.設(shè)置節(jié)點規(guī)模為1 000,數(shù)據(jù)索引規(guī)模M=1793.3種算法的平均路徑長度及符合度的變化趨勢與平均分布下的趨勢一致,這里不再給出圖形結(jié)果.

比較以路徑為主導(dǎo)的算法和具有符合度調(diào)整的算法在不同的loadpercentage下,同時達(dá)到指定k=6和satisfy=0.9所需的交互次數(shù)如圖5所示.根據(jù)2.2.3節(jié)中的分析,這里不再比較以數(shù)據(jù)為主導(dǎo)的算法,因為最終的平均路徑長度都在 2到 3的范圍內(nèi),這樣的構(gòu)建意義不大.

由圖 5可見,具有符合度調(diào)整的算法的效果較好.當(dāng)loadpercentage=0.8時,以路徑為主導(dǎo)的算法交互次數(shù)已超過 100000次,因此未在圖上顯示.

具有符合度調(diào)整的算法對初始數(shù)據(jù)索引的查找失敗率如表 2所示.同前,這里不再比較以數(shù)據(jù)為主導(dǎo)的算法的失敗率.

表2 Zip f分布下的查找失敗率Table 2 Search failure rate in Zip f distribution

loadpercentage的取值在0.2～0.8之間,并采用了一個混合比例.每個初始值下兩類算法各產(chǎn)生 20個P-Grid結(jié)構(gòu),對每個結(jié)構(gòu)查詢 10000次,統(tǒng)計失敗的次數(shù).表 2中符號定義與表1相同.從實驗結(jié)果可知,具有符合度調(diào)整的算法的查找失敗率與 T相關(guān),并且查找成功率在90%左右.

5 結(jié)語

(1)P-Grid構(gòu)建算法的收斂速度是影響建立在其上系統(tǒng)性能的關(guān)鍵因素,文中針對構(gòu)建的兩種初始情況Ignore-of-Load和Care-of-Load,對原構(gòu)建算法進(jìn)行改進(jìn);改進(jìn)的算法能保持原算法的分散性和自組織性,且不增加路由更新的負(fù)擔(dān).

(2)模擬實驗結(jié)果表明,Ignore-of-Load構(gòu)建算法能減少原算法交互次數(shù)的50%以上;具有符合度調(diào)整的Care-of-Load構(gòu)建算法在交互次數(shù)上表現(xiàn)良好,并且對數(shù)據(jù)索引的查找成功率在90%左右.

[1] Dabek F,Kaashoek M,Karger D.W ide-area cooperative storage with CFS[C]∥ACM Symposium on Operating Systems Princip les.New York:ACM,2001:202-215.

[2] Kubiatowicz J,Wells C,Zhao Ben.Oceanstore:an architecture for global-scale persistent storage[J].ACM SIgpan Notices,2000,35(11):190-201.

[3] Zhang Zheng,Lian Qiao,Lin Shi-ding.Bitvault:a highly reliab le distributed data retention p latform[J].ACM SIGOPSOperating Systems Review,2007,41(2):27-36.

[4] 胡進(jìn)鋒,洪春輝,鄭緯民.一種面向?qū)ο蟮腎nternet存儲服務(wù)系統(tǒng)Granary[J].計算機(jī)研究與發(fā)展,2007,44 (6):1071-1079.

Hu Jin-feng,Hong Chun-hui,Zheng Wei-min.Granary:an architecture of object oriented internet storage service [J].Journal of Computer Research and Development, 2007,44(6):1071-1079.

[5] Karl Aberer.P-Grid:a self-organizing access structure for P2P information system s[C]∥Proceedings of the 9th International Conference on Cooperative Information Systems.Berlin/Heidelberg:Springer,2001:179-194.

[6] Karl A,Magdalena P.Im proving data access in P2P systems[J].IEEE Internet Computing,2002,6(1):58-67.

[7] Karl A,Anwitaman D,Manfred H.Effcient,self-contained handling of identity in Peer-to-Peer systems[J].IEEE Transactions on Knowledge and Data Engineering,2004, 16(7):858-869.

[8] Manfred H,Anwitaman D,Karl A.Handling identity in Peer-to-Peer systems[C]∥Proceedings of the 14th International Workshop on Database and Expert Systems App lications.Washington:IEEE Computer Society,2003: 942-946.

[9] Karl A,Anwitaman D,Manfred H.Multifaceted simultaneous load balancing in DHT-based P2P systems:a new game with old balls and bins[EB/OL].(2005-01-01). http:∥www.p-grid.org/publications/papers/SelfStar2005. pdf.

[10] Karl A,Anwitaman D,Manfred H.The quest for balancing peer load in structured Peer-to-Peer systems[EB/OL]. (2003-01-01).http:∥www.p-grid.org/pub lications/ papers/TR-IC-2003-32.pdf.

[11] Xu Li-bo,Wu Guo-xin,You Feng-qin.A structured P2P system withmatch path and probability balance tree[C]∥Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences:Volume 2. Washington:IEEEComputer Society,2006:167-174.

[12] Jagadish H V,Beng C O,Quang H V.BATON:a balanced tree structure for Peer-to-Peer networks[C]∥Proceedings of the 31st International Conference on Very large Data Bases.Norway-Trondheim:VLDB Endowment,2005:661-672.

[13] Márk J,Alberto M,Gian P J,et al.PeerSim:a Peer-to-Peer simulator[EB/OL].(2009-01-01).http:∥peersim.sourceforge.net/.

[14] 張?zhí)?查冰,王勁林.對等網(wǎng)絡(luò)上數(shù)據(jù)分布模型的分析[J].電子技術(shù)應(yīng)用,2006,32(1):46-47.

Zhang Tai-le,Zha Bin,Wang Jin-lin.Analysis of content distribution in P2P files-share system[J].Application of Electronic Technique,2006,32(1):46-47.

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

Liu De-Hui,Zhou Ning,Yin Gang,et al.QFMA:an approach for multi-attribute resource addressing with load balancing[J].Chinese Journal of Computers,2008,31 (8):1376-1382.