支持節(jié)點異常的Chord算法研究

袁 赟，張英杰

（1.湖南大學 計算機與通信學院，湖南 長沙 410082；2.邵陽學院 信息工程系，湖南 邵陽 422000）

支持節(jié)點異常的Chord算法研究

袁 赟1,2，張英杰1

（1.湖南大學 計算機與通信學院，湖南 長沙 410082；2.邵陽學院 信息工程系，湖南 邵陽 422000）

Chord算法是典型的分布式P2P協(xié)議，在資源定位和查找上具有優(yōu)越的性能，但對于節(jié)點異常機制的處理不夠完善.本文在研究Chord算法的基礎(chǔ)上，改進了Chord算法對于節(jié)點異常機制的處理能力，能夠有效支持節(jié)點的異常離開且不影響環(huán)上資源共享.實驗證明本文算法在中小規(guī)模的集群應(yīng)用中具有較好的性能.

P2P；Chord；分布式哈希；網(wǎng)絡(luò)拓撲；網(wǎng)絡(luò)協(xié)議

1 引言

P2P技術(shù)的核心思想是，在整個網(wǎng)絡(luò)中由每一個參與網(wǎng)絡(luò)的peer之間自由地提供資源和服務(wù). P2P中的peer取代了中心服務(wù)器，構(gòu)成分布式的網(wǎng)絡(luò)，在此網(wǎng)絡(luò)中的每一個參與者既是資源（服務(wù)和內(nèi)容）提供者(Server)，又是資源（服務(wù)和內(nèi)容）獲取者(Client)[1]，它改變了原來的計算機網(wǎng)絡(luò)結(jié)構(gòu)的C/S或B/S結(jié)構(gòu)，變得平民化，體現(xiàn)一種自由、平等、互聯(lián)的思想.

在P2P技術(shù)中，最基本、最核心的問題是如何在網(wǎng)絡(luò)中高效準確的定位資源節(jié)點，從而進行各種信息和數(shù)據(jù)交互.目前，P2P技術(shù)采用分布式哈希表(Distributed Hash Table，簡稱DHT)來實現(xiàn)完全分布式的結(jié)構(gòu)化網(wǎng)絡(luò)拓撲[2].

Chord項目是美國麻省理工學院(MIT)開展的P2P分布式系統(tǒng)項目之一[3].它的目標是提供一個適合于P 2P環(huán)境的分布式資源發(fā)現(xiàn)服務(wù)，它通過使用D H T技術(shù)使得對于一個發(fā)現(xiàn)指定對象的服務(wù)，每個節(jié)點只需要維護一個O(logN)長度的路由表. Chord的主要貢獻是提出了一個分布式查找算法協(xié)議，該協(xié)議可將指定的關(guān)鍵字(Key)映射到對應(yīng)的節(jié)點(Node).

與Chord算法類似的采用DHT技術(shù)的P 2P系統(tǒng)還有由加州大學伯克利分校提出的CAN[4]和由位于英國劍橋的微軟研究院和萊斯(Rice)大學提出的Pastry[5].在節(jié)點數(shù)量非常大時，CAN的平均查詢跳數(shù)要比Chord增加得更快，并且CAN查詢過程中需要的運算量也要高于Chord.與Chord和CAN相比，Pastry引入了葉子節(jié)點和鄰居節(jié)點集合的概念.在應(yīng)用層能夠及時準確地獲得這兩個集合的節(jié)點信息時，可以大大加快路由查找的速度，同時降低因路由引起的網(wǎng)絡(luò)傳輸開銷.不過在動態(tài)變化的P 2P網(wǎng)絡(luò)中如何理想地做到這一點的確有很大的難度.

Chord算法在資源查詢和服務(wù)發(fā)現(xiàn)中具有優(yōu)越的性能，但由于Chord算法完全分布式的結(jié)構(gòu)，使得Chord算法在實際的應(yīng)用系統(tǒng)使用中具有一定的缺陷[6].在當前流行的各種P2P應(yīng)用系統(tǒng)中，都不可避免的采用了結(jié)構(gòu)化-半結(jié)構(gòu)化的網(wǎng)路拓撲. Chord算法所采用的節(jié)點異常機制不能較好的支持節(jié)點異常后的環(huán)上數(shù)據(jù)維護及資源共享.在本文中，我們提出基于Chord的改進算法，在一定程度上改善了Chord算法對于網(wǎng)絡(luò)不穩(wěn)定時節(jié)點異常機制的管理和數(shù)據(jù)的備份，有效提高了Chord算法的性能，使得Chord算法更適合于大規(guī)模系統(tǒng)應(yīng)用.

2 Chord工作原理概述

基于Chord算法的系統(tǒng)中，所有節(jié)點在邏輯上按照由標識符哈希出來的KEY的大小組成一個環(huán)（見圖1），數(shù)據(jù)同樣有標識符哈希后的KEY并且存放在和自己KEY最近的節(jié)點上.當在某一個節(jié)點上輸入查詢請求時，如果節(jié)點的KEY小于數(shù)據(jù)的KEY，則向該節(jié)點知道的下一個節(jié)點傳遞請求，下一個節(jié)點如果擁有該文件則返回結(jié)果，否則按前面的方式繼續(xù)轉(zhuǎn)發(fā)給下一個節(jié)點.其中每個Chord節(jié)點只需要知道關(guān)于部分節(jié)點和到達它們的路由信息（Finger表）.Chord路由查找過程有兩個重要特性：每個節(jié)點都只需要知道一部分節(jié)點的信息，而且離它越近的節(jié)點，它就知道越多的關(guān)于它們上面的數(shù)據(jù)信息；每個節(jié)點的路由表只有部分節(jié)點的路由信息并且不能確定任意一個KEY的確切位置，只能知道下一跳的節(jié)點.圖1所示為Chord節(jié)點維護的指向表，其中0、1、3的位置上有節(jié)點.每個節(jié)點上維護一張表，以順時針方向，會在O(logN)內(nèi)找到任何一個節(jié)點.

圖1 Chord環(huán)及節(jié)點Finger表

Chord路由表具有如下特點：每個節(jié)點只保存很少的其它節(jié)點信息，并且根據(jù)計算s t a r t下標的算法（見表1），對離它越遠的節(jié)點所知越少，也就是說指向表中節(jié)點的分布越來越疏，成指數(shù)式遞增.Chord節(jié)點不能從自己的路由表中看出對象k的后繼，只能查找到節(jié)點的后繼.

表1 Chord節(jié)點n的路由表各項屬性及其定義

3 支持節(jié)點異常的Chord算法

3.1 改進算法概述

在Chord算法的描述中，對于節(jié)點異常離開情況的辦法是：每個節(jié)點定時更新后繼，與此同時，每個節(jié)點在網(wǎng)絡(luò)中查找Finger表中某一隨機項的真正對應(yīng)節(jié)點，來保證Finger表的最新.這里存在三個問題，一是節(jié)點后繼和Finger表中對同一節(jié)點的路由當出現(xiàn)不一致的情況時，系統(tǒng)將不能正常工作；二是隨機取Finger表中的某一項來更新，無法保證每一項都有公平相等的被取到的機會；三是在更新Finger表示需要調(diào)用find Succ ESS orBy KEY函數(shù)在系統(tǒng)中定位某一項對應(yīng)的節(jié)點，因此即使在網(wǎng)絡(luò)空閑的情況下，也會充斥的大量的查找后繼的消息，這很容易導致網(wǎng)絡(luò)擁塞.另外，在Chord的算法描述中，并沒有提供實現(xiàn)數(shù)據(jù)冗余備份的細節(jié).

因此，本節(jié)對Chord的節(jié)點異常機制進行了改進.同時也提供了對于數(shù)據(jù)冗余備份機制的細節(jié)實現(xiàn).對于節(jié)點異常離開的處理采用一個定時器.每個節(jié)點上的定時器會定時向后繼詢問其是否有響應(yīng).保證了一定的實時性，具有較高的反應(yīng)時間.通過實驗，可以折中計算出系統(tǒng)合適的詢問間隔時間.數(shù)據(jù)冗余備份機制采用節(jié)點將數(shù)據(jù)復制備份在后繼節(jié)點上的方法，這樣若出現(xiàn)異常，數(shù)據(jù)仍在正確的節(jié)點上.

節(jié)點異常是提供災(zāi)難容錯的處理機制.當節(jié)點發(fā)生異常（斷電、斷網(wǎng)等、宕機等），系統(tǒng)需要能及時發(fā)現(xiàn)并且自動更新，及時更新相關(guān)節(jié)點的后繼和前驅(qū).其中需要有一個機制，以防止當一個節(jié)點異常離開時，如何能發(fā)現(xiàn)異常并獲取該節(jié)點上本身儲存的信息.一個設(shè)想是每一個節(jié)點要另外建立維護一個succ ESS or-list后繼表，以保存r(r>1)個succ ESS or.這樣，當一個節(jié)點發(fā)生異常時，依然可以通過succ ESS or-list找到這個節(jié)點的succ ESS or，然后把環(huán)中斷掉的部分接上即可.

3.2 節(jié)點異常機制算法描述

取r=O(logN)，即使節(jié)點失效概率為1/2，整個系統(tǒng)仍能正確定位.在節(jié)點加入環(huán)之后，開啟使用一個定時器.該定時器20秒執(zhí)行一次（具體時間要根據(jù)當前網(wǎng)絡(luò)環(huán)境的穩(wěn)定性測算最優(yōu)值），執(zhí)行任務(wù)如下：

向后繼通信；

若收到后繼發(fā)回的消息，則不處理；

若超時，則設(shè)置變量IF_SUCCESSOR_ACTIVE為false；

將后繼的后繼作為本節(jié)點的后繼，更新相關(guān)前驅(qū)和后繼；

執(zhí)行stabilize()函數(shù)更新環(huán)狀態(tài)；

執(zhí)行fixFingers()函數(shù)更新節(jié)點Finger表；

執(zhí)行update_others()函數(shù)更新其他節(jié)點信息；

將IF_SUCCESSOR_ACTIVE變量設(shè)為true.

更新結(jié)束.

此方法對于異常節(jié)點上的數(shù)據(jù)沒有進行處理.解決方法就是將每個節(jié)點上數(shù)據(jù)都備份在后繼上.優(yōu)化后的算法如下：

向后繼通信；

若收到后繼發(fā)回的消息，則不處理；

若超時，則設(shè)置變量IF_SUCC ESS OR_ACTIVE為false；

將后繼的后繼作為本節(jié)點的后繼，更新相關(guān)前驅(qū)和后繼；

執(zhí)行stabilize()函數(shù)更新環(huán)狀態(tài)；

執(zhí)行fixFingers()函數(shù)更新節(jié)點Finger表；

執(zhí)行update_others()函數(shù)更新其他節(jié)點信息；

將IF_SUCCESSOR_ACTIVE變量設(shè)為true；

將后繼的數(shù)據(jù)再備份到后繼的后繼上.

更新結(jié)束.

此處存在另一個問題，即若后繼已異常離開，但前驅(qū)還未發(fā)現(xiàn)該節(jié)點異常的期間里，以及發(fā)現(xiàn)該節(jié)點異常離開后系統(tǒng)正在更新的這兩個期間里，若要發(fā)生與該節(jié)點有關(guān)的路由和計算的情況時，該如何處理？

我們采用的保障機制為同步處理.將函數(shù)作為一個事務(wù)，避免函數(shù)進行過程中計算機又執(zhí)行另外的函數(shù).但更好的方式是采用消息隊列的機制，構(gòu)造一個消息隊列緩沖池，是一個未來的研究方向.

4 實驗

為了測試本文算法的有效性，我們利用java開發(fā)了一套局域網(wǎng)Chord共享系統(tǒng)，并在局域網(wǎng)內(nèi)的若干臺主機上進行網(wǎng)絡(luò)測試.每個節(jié)點均運行在x86的PC上.

在測試中，選取節(jié)點20異常離開.在節(jié)點20突然失敗離開之前，節(jié)點69的Finger表如圖2.

圖2 節(jié)點20失敗前的節(jié)點69信息

節(jié)點20失敗離開后，其前驅(qū)發(fā)現(xiàn)節(jié)點20異常后，則開啟前文中描述的異常處理算法，更新系統(tǒng)中相關(guān)節(jié)點的節(jié)點信息.更新后節(jié)點69的信息如圖3.

圖3 節(jié)點20失敗后的節(jié)點69信息

從圖2和圖3可以看出，節(jié)點20失敗后，節(jié)點69的Finger表得到了及時的修正，以保證系統(tǒng)繼續(xù)正常的路由轉(zhuǎn)發(fā).同時數(shù)據(jù)也得到了復制和恢復.節(jié)點20上的數(shù)據(jù)根據(jù)SHA-1的一致性哈希規(guī)則重新被分配在節(jié)點69和節(jié)點98上面.這也體現(xiàn)了數(shù)據(jù)冗余備份的作用.經(jīng)過測試，節(jié)點反復的異常離開和加入，均沒有出現(xiàn)宕機、單點等情況.

5 總結(jié)

Chord采用環(huán)狀的拓撲結(jié)構(gòu)，通過一致性哈希函數(shù)將節(jié)點、數(shù)據(jù)對象映射到系統(tǒng)節(jié)點上.每個Chord節(jié)點維護一個很小的路由表，后繼關(guān)系是Chord定位的基礎(chǔ)，路由表可以將定位路徑長度縮短為O(logN)跳即可找到所需節(jié)點.本文在Chord算法基礎(chǔ)上改進了其節(jié)點異常機制，并通過實驗測試，能滿足中小規(guī)模下的集群應(yīng)用，提供文件檢索和下載的服務(wù).并驗證了改進Chord算法良好的魯棒性和穩(wěn)定性.

〔1〕梁達明.P2P網(wǎng)絡(luò)資源定位模型研究[D].杭州：浙江大學，2006.

〔2〕李振宇,謝高崗.基于DHT的P2P系統(tǒng)的負載均衡算法 [J].計算機研究與發(fā)展,2006,43(9): 1579-1585.

〔3〕Ion Stoica,Robert Morris,David Karger,M. Frans Kaashoek,Hari Balakrishnan.Chord:A Scalable Peertopeer Lookup Service for Internet Applications[A].IEEE/ACM Transactions on Networking [C].New York,NY,USA:IEEE eXpress,2001,11(1):17-32.

〔4〕Sylvia Ratnasamy,Paul Francis,Mark Handley, Richard Karp,Scott Shenker“A Scalable Content-Addressable Network”[A].SIGCOMM'01[C]. New York,NY,USA:ACM,2001:161-172.

〔5〕Antony Rowstron, Peter Druschel. Pastry: Scalable,decentralized object location and routing for large-scale peer-to-peer systems[A]. Proceedingsofthe IFIP/ACM International Conferenceon Distributed SystemsPlatforms Heidelberg[C].London,UK:Springer-Verlag, 2001:329-350.

〔6〕J.Cichon,K.Cichon,P.Kobylanski.Node Evaluation in the Chord P2P Systems[A].Fourth International Conference on Dependability of Computer Systems[C].New York,NY,USA: IEEE eXpress,2009:168-175.

TP393.02

A

1673-260X（2010）08-0024-03