Chord算法
轉自：http://blog.csdn.net/wangxiaoqin00007/article/details/7374833
雖然網上搜索CHord，一搜一大堆，但大多講得不太清楚明白。今天發現一篇blog，圖文并茂，邏輯清楚且易懂，特意轉載收藏。
?
P2P的一個常見問題是如何高效的定位節點，也就是說，一個節點怎樣高效的知道在網絡中的哪個節點包含它所尋找的數據，如下圖：
對此，有三種比較典型的來解決這個問題。
Napster：使用一個中心服務器接收所有的查詢，服務器告知去哪下載其所需要的數據。存在的問題是中心服務器單點失效導致整個網絡癱瘓。
Gnutella：使用消息洪泛（message flooding）來定位數據。一個消息被發到系統內每一個節點，直到找到其需要的數據為止。當然，使用生存時間（TTL）來限制網絡內轉發消息的數量。存在的問題是消息數與節點數成線性關系，導致網絡負載較重。
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協議。它通過多個節點跳轉找到我們所查找的資源：
我們先看看它是如何進行的，隨后再總結其特點和操作特征，以及一些實現。
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>=KID的節點上，這個節點成為k的后繼節點，是環上從k起順時針方向的第一個節點，記為successor(k)。而節點分布則順時針將節點N由大到小放在這個環上。例如下邊這幅圖：
這是一個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);
例如下圖：
節點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)后的位置。還是延續上邊的例子：
節點N8的路由表中，左邊那一欄包含了N8+1到N8+32（2^5-1）的位置，右邊那一欄每個位置對應的實際存在的節點。比如N8+1-N14，表示在N8后的第一個位置上的資源由N14來負責。這樣記錄有以下優勢：
每個節點只包含全網中一小部分節點的信息。
每個節點對于臨近節點負責的位置知道的更多，比如N8節點對于N14負責的位置知道3處，而對N21負責的位置只知道1處。
路由表通常不包含直接找到后繼節點的信息，往往需要詢問其他節點來完成。
當在某個節點上查找資源時，首先判斷其后繼節點是不是就持有該資源，若沒有則直接從該節點的路由表從最遠處開始查找，看哪一項離持有資源的節點最近（發現后跳轉），若沒有則說明本節點自身就有要尋找的資源。如此迭代下去。
例如：節點N8尋找K54這個資源
首先，在N8上查找后繼節點為N14，發現K54并不符合54? (8; 14]的要求，那么直接在N8的路由表上查找符合這個要求的表項（由遠及近查找），此時N8的路由表為：
我們發現路由表中最遠的一項N8+32--N42滿足42? (8; 54]，則說明N42這個點離持有K54這個資源的節點最近（因為N42在該路由表中離N8這個節點最遠），那么此時跳到N42這個節點上繼續查找。N42的后繼節點為N48，不符合54? (42; 48]的要求，說明N48不持有資源54，此時，開始在N42的路由表上查找：
N42節點的路由表為：
我們由遠及近開始查找，發現N42+8--N51滿足51? (42; 54]，則說明N51這個點離持有K54這個資源的節點最近，那么此時跳到N51這個節點上繼續查找。N51節點的后繼節點為N56，符合54? (51; 56]，此時定位完成，N56持有資源節點K54。
用偽代碼表示：
// 查詢節點n后繼節點。?
n.find_successor(id)?
if (id ? (n; successor])?
return successor;?
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(): 修改路由表。
具體的，例如：
這是原先的結構：
現在N26節點要加入系統，首先它指向其后繼N32，然后通知N32，N32接到通知后將N26標記為它的前序節點（predecessor）。如下圖：
然后N26修改路由表，如下圖：
下一次N21運行stabilize()詢問其后繼節點N32的前序節點是不是還是自己，此時發現N32的前序節點已經是N26：
于是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
轉載于:https://www.cnblogs.com/z-sm/p/5058176.html
總結
- 上一篇： 内存区划分；内存分配；堆、栈概念分析；动
- 下一篇： 黑马程序员_java基础笔记(15)..