ＩｎｄｅｘＰｅｅｒ：半結構化Ｐ２Ｐ系統資源發現模型及其ＤＨＴ算法

摘要：提出了一種基于半結構化P2P系統的資源發現模型——IndexPeer模型。該模型采用三層索引結構，由下至上分別為virtual organization 層、service peer 層和indexpeer層。IndexPeer充分利用P2P系統中的節點性能差異，具有高效的查找功能，且對網絡的高度動態性有良好的適應性。針對Index Peer模型的體系結構，對該模型的結構化層DHT算法進行了研究和設計。基于small－world的仿真實驗表明，IndexPeer模型的體系結構及其結構化層DHT算法具有較好的魯棒性和一定的可擴展性。

關鍵詞：分布式哈希表; 點對點系統; 索引; 資源發現; 搜索

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)06－1648－04

P2P是實現資源共享的一種分布式技術[1]，是當前研究的熱點。P2P系統中各個節點松散地結合在一起，節點可以隨意加入或退出系統。當前的P2P網絡一般可以歸納為三種結構：集中協調式、完全分布式和混合式結構[2]。集中協調式結構有單點故障的缺陷；完全分布式P2P系統的資源發現查詢請求以泛洪(flooding)方式在網絡中傳播，會產生過多的通信負載[3]；混合式結構引入超級節點(ultra－peer)的概念，指定一些節點成為與其相鄰節點的服務器，成為超級節點，各超級節點通過完全分布式結構連接起來。混合式非結構化P2P系統對系統拓撲結構的高度動態性有較好的適應性，但由于搜索查詢過程需通過點與點之間的聯系來完成，資源發現及檢索效率受查詢算法的影響較大。

近年來， 基于分布式哈希表（DHT）的分布式資源組織、管理與發現服務正在應用到P2P系統、網格計算、Web 服務等分布式環境中，成為構建大規模分布式應用的基礎結構[4~7]。DHT的主要思想是：首先將每條文件索引表示成一個(K，V)對。其中：K稱為關鍵字(key)，可以是文件名(或文件的其他描述信息)的哈希值；V(value)是實際存儲文件的節點的IP地址(或節點的其他描述信息)。所有的文件索引條目(即所有的(K，V)對)組成一張大的文件索引哈希表，只要輸入目標文件的K值，就可以從這張表中查出所有存儲該文件的節點地址。然后再將上面的大文件哈希表分割成很多局部小塊，按照特定的規則把這些小塊的局部哈希表分布到系統中的所有參與節點上，使得每個節點負責維護其中的一塊。這樣，節點查詢文件時，只要把查詢報文路由到相應的節點即可(該節點維護的哈希表分塊中含有要查找的(K，V)對)。為了完成上述查詢，節點要按照一定的規則來分割整體的哈希表，進而也就決定了節點要維護特定的鄰居節點，以便路由能順利進行。這個規則因具體系統的不同而不同，CAN、Chord、Pastry和Tapestry都有自己的規則，也就呈現出不同的特性[8]。基于DHT的分布式檢索和路由算法因為具有查找可確定性、簡單性和分布性等優點，正成為國際上結構化P2P網絡研究和應用的熱點。

1相關工作

P2P系統的資源發現請求是按照一定的擴散策略轉發到各個節點進行匹配的。由于P2P系統具有高度的動態性、異構性和自治性，資源發現算法的效率和質量成為影響P2P系統性能最重要的因素[9]。當前P2P系統中的資源發現與搜索算法一般可分為結構化與非結構化兩種。結構化算法包括Chord、Pastry、CAN和Tapestry等[10]，它們在可擴展性、容錯能力和搜索效率等方面存在一定缺陷；非結構化算法的典型代表是Gnutella[11]和Freenet[12]。其中，Gnutella將查詢請求以廣播方式發給所有鄰居節點，搜索算法簡單、有效，但是通信開銷較大；Freenet通過沿途文件復制和LRU(least recently used)算法實現相似標志文件聚集。但是，Freenet大量的沿途復制文件會造成較大的網絡通信負載，而且不能保證對稀有文件對象的查詢結果[13]。

文獻[13]基于用戶節點命中查詢的歷史信息，提出了一種無結構P2P環境下占用帶寬較小、易維護的自適應搜索策略PeerRank。但是，文中沒有給出實際P2P系統下PeerRank的性能表現。考慮到實際P2P系統中路由表的更新速度無法跟上網絡拓撲的變化速度，文獻[7]提出了一種基于DHT的加速路由表資源搜索算法ROAD(routing on active and demand)。 ROAD算法通過構建加速路由表、加快發現服務的速度降低消息轉發的延時，并通過冪次序組播算法改善對超級點的依賴性。

2IndexPeer模型體系結構

IndexPeer是一種基于半結構化P2P索引技術的資源發現模型。底層以集中式資源發現模型為基礎；中間層由服務節點組成非結構化分布式網絡；頂層采用結構化P2P網絡技術，引入IndexPeer方法，采用分層的查詢機制。IndexPeer模型將結構化與非結構化P2P網絡的優點相結合，對于非結構化網絡查詢代價較高的缺點有較好的改進，并解決了結構化網絡節點異質性的問題，能適應P2P系統高度的動態性。IndexPeer資源發現模型分為三層，如圖1所示。

底層由提供資源服務的各virtual organization（VO)節點組成。VO節點可以采用現行的各種集中式P2P結構向外提供服務。各節點需要在上一級的分布式service peer（SP）中注冊信息。VO節點可以是資源的提供者，同時也可以是資源的請求者。

第二層的SP以對等的形式構造非結構化P2P網絡。任一個SP在一個或多個IndexPeer中注冊，并與IndexPeer下屬的SP建立鄰居節點關系。SP在加入和離開時需要在下層VO節點中尋找新的替代者。如果沒有符合的VO節點，便根據各VO節點與鄰居SP的連接響應時間與該鄰居SP的飽和度，將VO節點重新注冊到鄰居SP上，并將結果提交給所屬IndexPeer，以修改其資源對應表(路由表)。SP相對于IndexPeer來說可以自由地加入或離開。SP將下屬VO節點的資源信息以關鍵字K1，K2，K3，…的形式發往所在的IndexPeer注冊，并將資源關鍵字K以及K所在的資源位置V一道存儲在SP的資源表中。

IP（index peer)層由IndexPeer組成結構化P2P網絡。該網絡建立了一個分布式哈希索引表，每個IP有特定的ID號以及各自下屬SP的資源對應表。索引表中的ID號與節點的網絡路由地址有惟一對應的關系。IP的選取根據其在線的穩定時間與可靠性確定，選擇的是高效率、變動少、可靠性高的節點，類似于非結構化P2P混合網絡中的超級節點。但是與非結構化網絡的節點不同的是，IP的加入與相鄰節點建立聯系時需要遵循結構化P2P網絡的構建原則，加入與退出需要對頂層網絡進行修復工作。另外IP層中，各節點之間的聯系通過分布式哈希索引表來檢索資源，而不像非結構化網絡中通過點與點之間的聯系來直接查找。

3DHT搜索算法

3．1需要解決的問題

要將DHT算法引入IndexPeer資源發現模型中，應該解決以下幾個方面的問題：a)DHT算法在IP層的設計應該遵循的原則是在節點失效、遭受攻擊和突發性高負載面前都能表現出很好的魯棒性[14]；b)具有良好的可擴展性，能以較低系統開銷獲得較大的系統規模；c)可以自我配置，不需要手工干預就可以自動把新加入的節點合并到系統中；d)提供簡單靈活的接口，可以為SP層的多個P2P系統同時使用。

為解決以上問題，本文提出了一種滿足IndexPeer資源發現模型的IP層改進算法。

3．2DHT算法設計

IndexPeer模型中，關鍵字標志符Sreq通過哈希關鍵字本身得到，而IP節點的ID號則通過散列(hash)節點的IP地址得到。所有IP節點按照其ID號從小到大(取模2m后)沿著順時針方向排列在一個邏輯的標志圓環上。圓環的映射規則是:關鍵字標志符為Sreq的(Sreq，Saddr)對存儲在IP節點下的非結構化SP網絡中，存儲方式遵循空間均勻分布原則。該IP節點的節點標志等于Sreq或者在環上緊跟在Sreq之后，這個節點被稱為Sreq的后繼節點，表示為successor(Sreq)。因為標志符采用m位二進制數表示，并且在0~2m-1順時針排列成一個圓圈，successor(Sreq)就是從Sreq開始順時針方向距離Sreq最近的節點。

SP層網絡中提供一個隨機的資源分配算法，如依據SP號的泊松分布，將該資源的地址Saddr存儲在資源表res(Sreq)=Saddr上。當SP節點正常退出時，它將資源表上的資源信息轉移到鄰居SP節點中，以保證資源始終處于IP節點下。這種規則可以在小范圍內準確定位資源的位置，SP節點的加入和退出對資源的區域定位沒有影響。

圖2給出了一個m=6的圓環，環中分布了10個IP節點，存儲了5個關鍵字，節點標志前加上ID而關鍵字前加上Sreq以示區別。因為successor(2)=6，所以關鍵字2存儲到節點6下的SP網絡中；同理，關鍵字20和28存儲到節點30中，關鍵字44存儲到節點46中，而關鍵字50則存儲到節點50中。當網絡中的節點發生變動時，上面的映射規則仍然要成立。為此，當某IP節點n加入網絡時，某些原來分配給n的后繼節點的關鍵字將分配給新構成的SP網絡。當IP節點n離開網絡時，所有分配給它的關鍵字將重新分配給n的后繼節點下的SP網絡。除此之外，網絡中不會發生其他變化。以圖2為例，當標志為26的IP節點接入時，原有標志為30的節點負責的標志為20的關鍵字將轉給新IP節點。顯然，為了能在系統中轉發查詢報文，每個IP節點要了解并維護環上相鄰IP節點的標志和IP地址，并用這些信息構成自身的路由表。有了這張表，就可以在環上任意兩點間進行尋路。

圓環中每個IP節點只要維護它在環上的后繼節點的標志和IP地址就可以完成簡單的資源定位過程。對特定關鍵字的查詢報文可以通過后繼節點指針在圓環上傳遞，直到到達這樣一個節點：關鍵字的標志落在該節點標志和它的后繼節點標志之間。這里的后繼節點就是存儲目標對(Sreq，Saddr)的節點區域，在該非結構化P2P區域內查找出資源的具體位置。

圖3給出了一個簡單的依次查詢的示意圖。首先，節點6發起的查找關鍵字57的請求，通過后繼節點依次傳遞，最后定位到存儲有關鍵字57的節點58。在這種簡單查詢方式中，每個節點需要維護的狀態信息很少，但查詢速度太慢。若網絡中有N個節點，查詢的代價就為O(N)數量級，在網絡規模很大時，這樣的速度是不能接受的。

為了加快查詢搜索速度，圓環必須使用改進的DHT查詢算法。改進查詢過程是：任何一個IP節點收到查詢關鍵字Sreq的請求時，首先檢查Sreq是否落在該節點標志和它的后繼節點標志之間，如果是的話，這個后繼節點就是存儲目標對(Sreq，Saddr)的節點；否則，IP節點將查找它的指針表，找到表中節點標志符最大但不超過Sreq的第一個節點，并將這個查詢請求轉發給該節點。通過重復這個過程，最終可以定位到Sreq的后繼節點，即存儲有目標(Sreq，Saddr)對的IP節點。

為此，每個IP節點需要維護一個路由表，稱為指針表(search table)。如果關鍵字和ID號用m位二進制位數表示，那么指針表中最多含有m個表項。節點n的指針表中第i項是圓環上標志大于或等于n+2i-1的第一個節點(比較是以2m為模進行的)。例如，s=successor(n+2i-1)( 1≤i≤m)，則稱節點s為節點n的第i個指針，記為n．search[i]，如n．search [1]就是節點n的后繼節點。指針表中每一項既包含相關節點的標志，又包含該節點的IP地址(和端口號)。

圖4給出了ID節點6的指針表。從圖中可以看出，節點12是環上緊接在(6+20) mod 26=7之后的第一個節點，所以節點6的第一個指針是節點12；同理，因為節點43是環上緊接在(6+25) mod 26=38之后的第一個節點，所以節點6的第6個指針是節點43。維護指針表使得每個節點只需要知道網絡中一小部分節點的信息，而且離它越近的節點，它就知道越多的信息。但是，對于任意一個關鍵字Sreq，節點通常無法根據自身的指針表確定其后繼節點。例如，圖中的節點6就不能確定關鍵字34的后繼節點，因為環上34的后繼節點是36，而節點36并沒有出現在節點6的指針表中。

為了應對系統的變化，每個IP節點都周期性地運行探測協議來檢測新加入的IP節點或失效IP節點，從而更新自己的指針表和指向后繼節點的指針。新IP節點n加入時，將通過系統中現有的IP節點來初始化自己的指針表。也就是說，新IP節點n將要求已知的系統中某節點為它查找指針表中的各個表項。在其他IP節點運行探測協議后，新節點n將被反映到相關IP節點的指針表和后繼節點指針中。這時，系統中一部分關鍵字的后繼節點將變為新IP節點n，而先前的后繼節點要將這部分關鍵字轉移到新IP節點下屬的SP節點網絡中。當IP節點n失效時，需要啟用節點n下性能最好的SP節點來繼承節點n的全部功能。這就要求存在若干個SP節點作為上級IP節點的備份，如果IP節點的備份更新失敗，所有指針表中含有n的IP節點都必須把它替換成n的后繼節點。為了保證IP節點n的失效不影響系統中正在進行的查詢過程，每個IP節點都維護一張包括r個最近后繼節點的后繼列表。如果某個IP節點注意到它的后繼節點失效了，它就用其后繼列表中第一個正常IP節點替換失效節點。

4實驗模擬

本實驗通過構造一個虛擬的small－world網絡[15]來完成資源發現系統的實現過程，如圖5所示。具體實現原理為：利用五臺PC機的性能優劣來擔任各種節點的角色，每個節點通過一個端口號來實現它的工作性能。實驗中，D、E屬高性能機，可以模擬IP節點；B、C屬中性能機，可以模擬SP節點；A屬低性能機，將擔任VO節點的角色；各個節點都將提供相關的資源。本實驗中，五臺PC機實現局域網內互聯。D和E節點將開啟兩個端口，模擬兩個節點;B和C節點將開啟四個端口，模擬出四個SP節點，分別為B1、B2、C1和C2;A開啟四個端口，充當四個節點的角色，分別為A1、A2、A3和A4。

各節點的CPU與內存資源設置如下：IP節點要求主頻≥2．0 GHz，內存≥512 MB;SP節點要求主頻≥300 MHz，內存≥64 MB；VO節點要求主頻≥100 MHz，內存≥32 MB。

仿真過程如下：節點通過運行在每個仿真機上的節點狀態監測進程獲取節點運行參數，以10 s為一個周期從本節點收集。采樣結果通過一定的映射規則計算得出，D、E節點賦值為1，可充當IP節點；B1、B2、C1和C2節點賦值為2，可作為SP節點;A1、A2、A3和A4賦值為3，為VO節點。通過比較，采集SP節點到IP節點的連接情況，依次將SP節點加入IP節點，得到10次CPU、存儲量和帶寬綜合平均值，如表1所示。

資源要求的實現過程如下：假如由A1提交新資源K1，通過DHT相關監聽函數取得函數關鍵字，此處選用SHA－1哈希算法。計算結果將K1分配給E。SP層采用隨機算法將K1分配給C2存儲。當A2在系統中提交資源查詢請求時，在C2的哈希表中得知K1的存在，將結果返回給DHT相關監聽函數，查找得出K1的E節點位置，并提出資源請求。E節點將C2地址返回， C2提供A1地址連接。至此，完成資源查找。

5結束語

P2P系統中資源發現機制的可用性和有效性取決于其是否適應P2P系統的高度動態性和查詢的高效性。本文提出的IndexPeer模型采用三層半結構化索引網絡，充分考慮了P2P系統中節點性能差異，按節點的處理能力分配職能，克服了結構化P2P網絡的缺點。頂層的結構較穩定，修改代價較小，下層節點采用非結構化網絡，可自由加入和退出，能很好地適應P2P系統的高度動態性。

參考文獻：

［1］ PARAMESWARAN M，SUSARLA A，WHINSTON A B. P2P networking: an information sharing alternative[J]. Computer， 2001，34(7):31－38.

[2]ANDROUTSELLIS－TEOTOKIS S，SPINELLIS D. A survey of peer－to－peer content distribution technologies [J]. ACM Computing Surveys，2004，36(4):335－371.

[3]LOO B T，HUEBSCH R，STOICA I，et al. The case for a hybrid P2P search infrastructure[C]//Proc of the 3rd International Workshop on Peer－to－Peer Systems. Heidelberg:Springer－Verlag， 2004:141－150．

[4]李運娣，馮勇．基于DHT的P2P搜索定位技術研究[J]．計算機應用研究，2006，23(10):226－228.

[5]GUPTA I，BIRMAN K，LINGA P，et al． Kelips: building an efficient and stable P2P DHT through increased memory and background overhead [C]//Proc of the 2nd International Workshop on Peer－to－Peer Systems．Berlin: Springer－Verlag， 2003:160－169．

[6]LI Jin－yang，STRIBLING J，MORRIS R，et al． A performance vs cost framework for evaluating DHT design tradeoffs under churn [C]//Proc of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies.Piscataway: IEEE Press， 2005:225－235．

[7]楊峰，李鳳霞，余宏亮，等.一種基于分布式哈希表的混合對等發現算法[J]．軟件學報，2007，18(3): 714－721.

[8]RATNASAMY S，SHENKER S，STOICAI. Routing algorithms for DHTs: some open questions[C]//Proc of the 1st International Workshop on Peer－to－Peer Systems．Heidelberg: Springer－Verlag， 2002:45－52.

[9]施曉秋.非集中式P2P 系統中資源搜索與現存問題分析[J].計算機工程，2007，33(5): 91－93.

[10]BALAKRISHNAN H，KAASHOEK M F，KARGER D，et al. Looking up data in P2P systems[J]． Communications of the ACM，2003，46(2):43－48.

[11]ZHU Ying－wu，HU Yi－ming．Enhancing search performance on Gnutella－like P2P [J]． IEEE Trans on Parallel and Distributed Systems，2006，17(12):1482－1495.

[12]CLARKE I，SANDBERG O，WILEY B，et al．Freenet: a distributed anonymous information storage and retrieval system[C]//Proc of the ICSI Workshop on Design Issues in Anonymity and Unobservability. Berkeley: International Computer Science Institute， 2000:311－320．

[13]馮國富， 毛鶯池， 陸桑璐，等．PeerRank:一種無結構P2P資源發現策略[J]．軟件學報， 2006，17(5): 1098－1106．

[14]GODFREY B，LAKSHMINARAYNAN K，SURANA S，et al．Load ba－lancing in dynamic structured P2P systems[C]//Proc ofthe 23rd Annual Joint Conference of the IEEE Computer and Communications Societies.Piscataway: IEEE Press， 2004:2253－2262．

[15] ZHANG H，GOEL A，GOVINDAN R．Using the small－world model to improve Freenet performance[C]//Proc of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies.New York: IEEE Press，2002:40－49.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文