【學術之門之P2P算法研讀】P2P中的Chord算法

P2P的一個常見問題是如何高效的定位節點，也就是說，一個節點怎樣高效的知道在網絡中的哪個節點包含它所尋找的資料，如下圖：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131301145633.png"></a>

對此，有三種比較典型的來解決這個問題。

Napster：使用一個中心伺服器接收所有的查詢，伺服器告知去哪下載下傳其所需要的資料。存在的問題是中心伺服器單點失效導緻整個網絡癱瘓。

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131301333652.png"></a>

Gnutella：使用消息洪泛（message flooding）來定位資料。一個消息被發到系統内每一個節點，直到找到其需要的資料為止。當然，使用生存時間（TTL）來限制網絡内轉發消息的數量。存在的問題是消息數與節點數成線性關系，導緻網絡負載較重。

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131301511704.png"></a>

SN型：現在大多數采用所謂超級節點（Super Node），SN儲存網絡中節點的索引資訊，這一點和中心伺服器類型一樣，但是網内有多個SN，其索引資訊會在這些SN中進行傳播，是以整個系統的崩潰幾率就會小很多。盡管如此，網絡還是有崩潰的可能。

現在的研究結果中，Chord、Pastry、CAN和Tapestry等常用于建構結構化P2P的分布式哈希表系統（Distributed Hash Table，DHT）。

DHT的主要思想是：首先，每條檔案索引被表示成一個(K, V)對，K稱為關鍵字，可以是檔案名（或檔案的其他描述資訊）的哈希值，V是實際存儲檔案的節點的IP位址（或節點的其他描述資訊）。所有的檔案索引條目(即所有的（K, V）對)組成一張大的檔案索引哈希表，隻要輸入目标檔案的K值，就可以從這張表中查出所有存儲該檔案的節點位址。然後，再将上面的大檔案哈希表分割成很多局部小塊，按照特定的規則把這些小塊的局部哈希表分布到系統中的所有參與節點上，使得每個節點負責維護其中的一塊。這樣，節點查詢檔案時，隻要把查詢封包路由到相應的節點即可（該節點維護的哈希表分塊中含有要查找的(K,V)對）。

這裡介紹的Chord算法就是解決網絡内節點定位問題的一種P2P協定。它通過多個節點跳轉找到我們所查找的資源：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131302127507.png"></a>

我們先看看它是如何進行的，随後再總結其特點和操作特征，以及一些實作。

1.Chord裡面的基本要素

節點ID：NID（node identifier），表示一個實體機器，m位的一個數字（m要足夠大以保證不同節點的NID相同的幾率小的可以忽略不計），由節點機器的IP位址通過哈希操作得到。

資源ID；KID（key identifiers），原為鍵ID，其實際表示一個資源（因為Key與一個資源value哈希綁定），故在本文中統稱資源ID（這樣比較直覺），m位的一個數字（m要足夠大以保證不同資源的KID相同的幾率小的可以忽略不計），由Key通過哈希操作得到。

常哈希函數：較之一般哈希函數，節點的加入和離開對整個系統影響最小，另外還有一些優勢在此不贅述。在Chord中使用SHA-1來進行常哈希計算。

Chord環：Chord Ring，NID和KID被配置設定到一個大小為2^m的環上，用于資源配置設定（給某一個節點）和節點分布，以及資源定位（注：在這個環上的ID為0--2^m-1）。首先我們說資源配置設定，資源被配置設定到NID&gt;=KID的節點上，這個節點成為k的後繼節點，是環上從k起順時針方向的第一個節點，記為successor(k)。而節點分布則順時針将節點N由大到小放在這個環上。例如下邊這幅圖：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131302302244.png"></a>

這是一個m=6的環，其中有10個節點，5個資源，K10的後繼節點為N14，也就是說K10被配置設定給了N14。

2.Chord資源定位（Key Location）

資源定位是Chord協定的核心功能，為了便于了解，我們先介紹一個簡單的資源定位方法，然後再介紹這個可伸縮的資源定位方法。

簡單方法：

考慮如下場景：節點n尋找KID為id的資源，此時節點n首先問詢是否在下一個節點上（find_successor），這要看資源k的KID是否在該節點NID和下一個節點的NID之間，若在則說明資源k被配置設定給了下一個節點，若不在則在下一個節點上發起同樣的查詢，問詢下下一個點是否有該資源。如此疊代下去，用僞代碼定義這個操作：

n.find_successor(id)

if (id є (n; successor])

return successor;

else

// 将查詢沿着環進行下去

return successor.find_successor(id);

例如下圖：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/20120113130247494.png"></a>

節點N8尋找K54這個資源，N8.find_successor(K54)發現下一個節點N14不合符54є (8; 14]，于是N14發起同樣的搜尋，然後一跳一跳後直到節點N56滿足54є (51; 56]，于是得知資源K54在N56這個節點上。

在一個有N個節點的環上，這樣的查找方法顯然在最壞的時候要查找N次才能得到所需資源的位置，查找次數與節點個數成線性關系。顯然，這樣的效率不給力，是以Chord使用了可伸縮資源定位的方式來提高效率。

可伸縮方法：

在每個節點N上都維護了最多有m項（m為ID的位數）的路由表（稱為finger table），用來定位資源。這個表的第i項是該節點的後繼節位置，至少包含到2^(i-1)後的位置。還是延續上邊的例子：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131303096132.png"></a>

節點N8的路由表中，左邊那一欄包含了N8+1到N8+32（2^5-1）的位置，右邊那一欄每個位置對應的實際存在的節點。比如N8+1-N14，表示在N8後的第一個位置上的資源由N14來負責。這樣記錄有以下優勢：

每個節點隻包含全網中一小部分節點的資訊。

每個節點對于臨近節點負責的位置知道的更多，比如N8節點對于N14負責的位置知道3處，而對N21負責的位置隻知道1處。

路由表通常不包含直接找到後繼節點的資訊，往往需要詢問其他節點來完成。

當在某個節點上查找資源時，首先判斷其後繼節點是不是就持有該資源，若沒有則直接從該節點的路由表從最遠處開始查找，看哪一項離持有資源的節點最近（發現後跳轉），若沒有則說明本節點自身就有要尋找的資源。如此疊代下去。

例如：節點N8尋找K54這個資源

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131303205292.png"></a>

首先，在N8上查找後繼節點為N14，發現K54并不符合54є (8; 14]的要求，那麼直接在N8的路由表上查找符合這個要求的表項（由遠及近查找），此時N8的路由表為：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131303329610.png"></a>

我們發現路由表中最遠的一項N8+32--N42滿足42є (8; 54]，則說明N42這個點離持有K54這個資源的節點最近（因為N42在該路由表中離N8這個節點最遠），那麼此時跳到N42這個節點上繼續查找。N42的後繼節點為N48，不符合54є (42; 48]的要求，說明N48不持有資源54，此時，開始在N42的路由表上查找：

N42節點的路由表為：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131303445498.png"></a>

我們由遠及近開始查找，發現N42+8--N51滿足51є (42; 54]，則說明N51這個點離持有K54這個資源的節點最近，那麼此時跳到N51這個節點上繼續查找。N51節點的後繼節點為N56，符合54є (51; 56]，此時定位完成，N56持有資源節點K54。

用僞代碼表示：

// 查詢節點n後繼節點。

else n0 = closest_preceding_node(id);

return n0.find successor(id);

// search the local table for the highest

// predecessor of id

n.closest_preceding_node(id)

for i = m downto 1

if (finger[i] є (n; id))

return finger[i];

return n;

經證明，最多經過O(log N)次查找就能找到一個資源。

3.Chord的節點加入

Chord通過在每個節點的背景周期性的進行stabilization詢問後繼節點的前序節點是不是自己來更新後繼節點以及路由表中的項。

有三個操作：

join(n0) ：n加入一個Chord環，已知其中有一個節點n0.

Stabilize(): n查詢其後繼節點的前序節點P來決定P是否應該是n的後續節點，也就是說當p不是n本身時，說明p是新加入的，此時将n的後繼節點設定為p。

Notify(n0): n0通知n它的存在，若此時n沒有前序節點或，n0比n現有的前序節點更加靠近n，則n将其設定為前序節點。

Fix_fingers(): 修改路由表。

具體的，例如：

這是原先的結構：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131303563164.png"></a>

現在N26節點要加入系統，首先它指向其後繼N32，然後通知N32，N32接到通知後将N26标記為它的前序節點（predecessor）。如下圖：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131304092824.png"></a>

然後N26修改路由表，如下圖：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131304216651.png"></a>

下一次N21運作stabilize()詢問其後繼節點N32的前序節點是不是還是自己，此時發現N32的前序節點已經是N26：

<a href="http://images.cnblogs.com/cnblogs_com/gnuhpc/201201/201201131304323478.png"></a>

于是N21就将後繼節點修改為N26，并通知N26自己已經将其設定為後繼節點，N26接到通知後将N21設定為自己的前序節點。

這個加入操作會帶來兩方面的影響：

1)正确性方面：當一個節點加入系統，而一個查找發生在stabilization結束前，那麼此時系統會有三個狀态：

A.所有後繼指針和路由表項都正确時：對正确性沒有影響。

B.後繼指針正确但表項不正确：查找結果正确，但速度稍慢（在目标節點和目标節點的後繼處加入非常多個節點時）。如下圖：

C.後繼指針和路由表項都不正确：此時查找失敗，Chord上層的軟體會發現資料查找失敗，在一段時間後會進行重試。

總結一下：節點加入對資料查找沒有影響。

2)效率方面：當stabilization完成時，對查找效率的影響不會超過O(log N) 的時間。當stabilization未完成時，在目标節點和目标節點的後繼處加入非常多個節點時才會有性能影響。可以證明，隻要路由表調整速度快于網絡節點數量加倍的速度，性能就不受影響。

4.Chord節點失敗的處理

我們可以看出，Chord依賴後繼指針的正确性以保證整個網絡的正确性。但如圖，若N14, N21, N32同時失效，那麼N8是不會知道N38是它新的後繼節點。為了防止這樣的情況，每個節點都包含一個大小為r的後繼節點清單，一個後續節點失效了就依次嘗試清單中的其他後繼節點。可以證明，在失效幾率為1/2的網絡中，尋找後繼的時間為O(log N) 。

5.Chord的特征和應用

特征：去中心化，高可用度，高伸縮性，負載平衡，命名靈活。

應用：全球檔案系統、命名服務、資料庫請求處理、網際網路級别的資料結構、通信服務、事件通知、檔案共享。

參考文獻：

Chord項目網址：http://pdos.csail.mit.edu/chord/

http://net.chinaunix.net/8/2008/07/28/1231438.shtml

本文轉自gnuhpc部落格園部落格，原文連結：http://www.cnblogs.com/gnuhpc/archive/2012/01/13/2321476.html，如需轉載請自行聯系原作者