Chrod算法是P2P中的四大算法之一，是有MIT（麻省理工學(xué)院）于2001年提出顶籽，其他三大算法分別是：

1. CAN
2. Pastry
3. Tapestry

Chord的目的是提供一種能在P2P網(wǎng)絡(luò)快速定位資源的的算法莺掠，Cord并不關(guān)心資源是如何存儲的揩尸，只是從算法層面研究資源的取得姑曙，因此Chord的API就簡單到只有一個set酸些、get尚蝌。

Chord是什么遭庶？

Chord是一個算法承匣，也是一個協(xié)議蓖乘。作為一個算法，Chord可以從數(shù)學(xué)的角度嚴(yán)格證明其正確性和收斂性韧骗；作為一個協(xié)議嘉抒，Chord詳細(xì)定義了每個環(huán)節(jié)的消息類型。當(dāng)然袍暴，Chord之所以受追捧些侍，還有一個主要原因就是Chord足夠簡單，3000行的代碼就足以實(shí)現(xiàn)一個完整的Chord政模。
Chord還可以被作為一個一致性哈希岗宣、分布式哈希（DHT）的實(shí)現(xiàn)。

覆蓋網(wǎng)絡(luò)（overlay network）

覆蓋網(wǎng)絡(luò)是指這樣一種網(wǎng)絡(luò)：構(gòu)建在其他網(wǎng)絡(luò)之上淋样、網(wǎng)絡(luò)節(jié)點(diǎn)之間通過虛擬或邏輯連接在一起耗式，比如云計(jì)算、分布式系統(tǒng)都是覆蓋網(wǎng)絡(luò)习蓬，因?yàn)槠涠紭?gòu)建于TCP/IP之上纽什，且節(jié)點(diǎn)之間有聯(lián)系。Chord也是構(gòu)建于覆蓋網(wǎng)絡(luò)躲叼。

結(jié)構(gòu)化與非結(jié)構(gòu)化網(wǎng)絡(luò)

非結(jié)構(gòu)化的P2P網(wǎng)絡(luò)是指網(wǎng)絡(luò)節(jié)點(diǎn)之間不存在組織關(guān)系芦缰，節(jié)點(diǎn)之間完全是對等的，比如第一代P2P網(wǎng)絡(luò)Napster枫慷，這類網(wǎng)絡(luò)結(jié)構(gòu)清晰让蕾、簡單，但查找沒有多大的優(yōu)化余地或听，經(jīng)常采用全局或分區(qū)泛洪查找探孝，查找時間長、且結(jié)果難以保證（有可能在找到前就超時）誉裆。
結(jié)構(gòu)化的P2P網(wǎng)絡(luò)與非結(jié)構(gòu)化恰好相反顿颅，我們認(rèn)為網(wǎng)絡(luò)在邏輯上存在一個人為設(shè)計(jì)的結(jié)構(gòu)，比如Chord假定網(wǎng)絡(luò)是一個環(huán)足丢，Kadelima則假定為一顆二叉樹粱腻，所有的節(jié)點(diǎn)均為樹的葉子節(jié)點(diǎn)庇配。有了這些邏輯結(jié)構(gòu)，就給我們資源查找引入了更多的算法和思路绍些。

分布式哈希表（DHT）

DHT的主要想法是把網(wǎng)絡(luò)上資源的存取像Hashtable一樣捞慌，可以簡單而快速地進(jìn)行put、get柬批，該思想的誕生主要是受第一代P2P（Napster）網(wǎng)絡(luò)的影響啸澡。與一致性哈希相比，DHT更強(qiáng)調(diào)的是資源的存取氮帐，而不管資源是否是一致性的嗅虏。與一致性哈希相同的是，DHT也只是一個概念揪漩，具體細(xì)節(jié)留給各實(shí)現(xiàn)旋恼。
當(dāng)前這些P2P實(shí)現(xiàn)可以被作為DHT的具體實(shí)現(xiàn)，再次再列舉一些有代表性的實(shí)現(xiàn)：

• Chord
• CAN
• Tapestry
• Pastry
• Apache Cassandra
• Kadelima
• P-Grid
• BitTorrent DHT

Chord實(shí)現(xiàn)原理

Chord通過把Node和Key映射到相同的空間而保證一致性哈希奄容，為了保證哈希的非重復(fù)性冰更，Chord選擇SHA-1作為哈希函數(shù)，SHA-1會產(chǎn)生一個2¹⁶⁰的空間昂勒，每項(xiàng)為一個16字節(jié)（160bit）的大整數(shù)蜀细。我們可以認(rèn)為這些整數(shù)首尾相連形成一個環(huán)，稱之為Chord環(huán)戈盈。整數(shù)在Chord環(huán)上按大小順時針排列奠衔，Node（機(jī)器的IP地址和Port）與Key（資源標(biāo)識）都被哈希到Chord環(huán)上，這樣我們就假定了整個P2P網(wǎng)絡(luò)的狀態(tài)為一個虛擬的環(huán)塘娶，因此我們說Chord是結(jié)構(gòu)化的P2P網(wǎng)絡(luò)归斤。
下面有幾個定義：

• 我們稱Chord環(huán)上的每個節(jié)點(diǎn)為標(biāo)志符
• 如果某個Node映射到了某個標(biāo)志符，則繼續(xù)稱該標(biāo)準(zhǔn)符為Node

• 按順時針刁岸，節(jié)點(diǎn)前面的成為前繼(predecessor),節(jié)點(diǎn)后面的成為后繼（successor)脏里；同理，第一個predecessor稱之為直接前繼虹曙，第一個successor稱之為直接后繼
  如圖：

  
  
  
  

  紅色點(diǎn)為Node迫横，藍(lán)色為標(biāo)志符。上面只是部分節(jié)點(diǎn)和標(biāo)志符酝碳，以節(jié)點(diǎn)N1為例說明其Finger表中的successor：

把Node和Key都映射到一個值域感覺是把狗和貓放在一起衡量矾踱，雖然有點(diǎn)怪，但這樣可以保證一致性哈希疏哗，具體可以參考前文呛讲。
很顯然，分布在Chord環(huán)上的Node數(shù)遠(yuǎn)遠(yuǎn)小于標(biāo)志符數(shù)（2¹⁶⁰是一個無法衡量的天文數(shù)字），這樣Chord環(huán)上的Node就會很稀疏地分布在Chord環(huán)上圣蝎，理論上應(yīng)該是隨機(jī)分布刃宵，但如前面一致性哈希的討論，如果節(jié)點(diǎn)數(shù)量不多徘公，分布肯定是不均勻的，可以考慮增加虛擬節(jié)點(diǎn)來增加其平衡性哮针，如果在節(jié)點(diǎn)較多（比如大型的P2P網(wǎng)絡(luò)有上百萬的機(jī)器）就不必引入虛擬節(jié)點(diǎn)关面。
很顯然，任何查找只要沿Chord環(huán)一圈結(jié)果肯定可以找到十厢，這樣的時間復(fù)雜度是O(N)等太，N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，但對一個上百萬節(jié)點(diǎn)蛮放，且節(jié)點(diǎn)經(jīng)常加入缩抡、退出的P2P網(wǎng)絡(luò)來說，O(N)是不可忍受的包颁，因此Chord提出了下面非線性查找的算法：

1. 每個節(jié)點(diǎn)都維護(hù)一個Finger表瞻想，該表長度為m（m就是位數(shù)，在Chord中為160）娩嚼，該表的第 i 項(xiàng)存放節(jié)點(diǎn) n 的第(n+2ⁱ-1) mod 2^m 個successor(1<=i<=m)
2. 每個節(jié)點(diǎn)都維護(hù)一個predecessor和successor列表蘑险，該列表的作用是能快速定位前繼和后繼，并能周期性檢測前繼和后繼的健康狀態(tài)
3. 就是說存放的successor是按2的倍數(shù)等比遞增岳悟，自所以取模是因?yàn)樽詈蟮墓?jié)點(diǎn)的successor是開始的幾個節(jié)點(diǎn)佃迄，比如最大的一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)定義為第一個節(jié)點(diǎn)
4. 資源Key存儲在下面的Node上：沿Chord環(huán)，hash(Node)>=hash(key)的第一個Node贵少，我們稱這個Node為這個Key的successor
5. 給定一個Key呵俏，按下面的步驟查找其對應(yīng)的資源位于哪個節(jié)點(diǎn)，也就是查找該Key的successor：（假如查找是在節(jié)點(diǎn)n上進(jìn)行）

• 查看Key的哈希是否落在節(jié)點(diǎn)n和其直接successor之間滔灶，若是結(jié)束查找普碎，n的successor即為所找
• 在 n 的Finger表中，找出與hash(Key)距離最近且<hash(Key)的n的successor宽气，該節(jié)點(diǎn)也是Finger表中最接近Key的predecessor随常，把查找請求轉(zhuǎn)發(fā)到該節(jié)點(diǎn)
• 繼續(xù)上述過程，直至找到Key對應(yīng)的節(jié)點(diǎn)

從直覺上來說萄涯，上次查找過程應(yīng)該是指數(shù)收斂的绪氛，類似二分法的查找，收斂速度應(yīng)該是很快的涝影；反過來枣察，查找時間或路由復(fù)雜度應(yīng)該是對數(shù)即的，在下面我們會證明這一點(diǎn)。
下圖表明了節(jié)點(diǎn)N1查找節(jié)點(diǎn)N53的過程序目，還是非潮酆郏快的：

Chord收斂性證明

對一個算法而言，收斂性是至關(guān)重要的猿涨，如果沒有收斂性做保證握童，在程序上化再多的心思也是徒勞。在證明之前叛赚，我們再強(qiáng)調(diào)3點(diǎn)：

• Key存放在Key的successor節(jié)點(diǎn)上（滿足：hash(Node)>=hash(Key)）
• 節(jié)點(diǎn)n的第i項(xiàng)存放的是第(n+2ⁱ-1)個successor
• 查找是根據(jù)最近原則澡绩，當(dāng)前節(jié)點(diǎn)沒有存放Key則從Finger表中尋找與hash(Key)距離最近的Node繼續(xù)這個過程

這里要區(qū)分是Key的successor還是節(jié)點(diǎn)n的successor，同時要注意最近匹配原則俺附。
假如節(jié)點(diǎn)n的Finger表中的第i個successor與Key的距離最近肥卡，則滿足：Key處在第i項(xiàng)與第i+1項(xiàng)中間

記第i項(xiàng)為J,第i+1項(xiàng)為P

• J<hash(Key)
• P>hash(Key)

而：

J = n + 2i-1

P = n + 2i

節(jié)點(diǎn)n與Key的距離應(yīng)該處在n與J和P的中間，即 J-n<n - hash(Key)<P - n

1. 2i-1<n - hash(Key)<2i

2. 而J與Key的距離最大為J與P的距離 J-hash(Key) <P - J = 2i-1

也就是說J與Key的距離事镣，小于n與Key的距離步鉴，并且該距離小于n與Key距離的一半，這樣我們保證每次迭代璃哟，與Key的距離都會收斂氛琢，并且至少按2的指數(shù)收斂，也就是折半查找沮稚。

至此艺沼，我們理論證明了Chord的收斂性。

深入Chord算法

其實(shí)Chord算法可以完全轉(zhuǎn)換為一個數(shù)學(xué)問題：
在Chord環(huán)上任意標(biāo)記個點(diǎn)作為Node集合蕴掏，任意指定Node T障般，從任意的Node N開始根據(jù)Chord查找算法都能找到節(jié)點(diǎn)T。
為什么能這么轉(zhuǎn)換呢盛杰？因?yàn)橹灰业搅薑ey的直接前繼挽荡，也就算找到了Key，所有問題轉(zhuǎn)化為一個在Chord環(huán)上通過Node找Node的問題即供。這樣定拟，這個題就馬上變的很神奇，假如我們把查找的步驟記錄為路徑逗嫡，又轉(zhuǎn)化為任意2個節(jié)點(diǎn)之間存在一條最短路徑青自，而Chord算法其實(shí)就是構(gòu)造了這樣一條最短路徑，那這樣的路徑會不會不存在呢驱证？不會的延窜，因?yàn)镃hord本身是一個環(huán)，最差情況可以通過線性查找保證其收斂性抹锄。
從最短路徑的角度來看逆瑞，Chord只是對已存在線性路徑的改進(jìn)荠藤，根據(jù)這個思路，我們完全可以設(shè)計(jì)出其他的最短路徑算法获高。從算法本來來看哈肖，保證算法收斂或正確性的前提是每個Node要正確地維護(hù)其后繼節(jié)點(diǎn)，但在一個大型的P2P網(wǎng)絡(luò)中念秧，會有節(jié)點(diǎn)的頻繁加入淤井、退出，如果沒有額外的工作出爹，很難保證每個節(jié)點(diǎn)有正確的后繼庄吼。

Chord冗余性：

所謂冗余性是指Chord的Finger表中存在無用項(xiàng)，那些處在Node N和其successor之間的項(xiàng)均無意義严就，因?yàn)檫@些項(xiàng)所代表的successor不存在。比如在N1的Finger表中的第1～5項(xiàng)均不存在器罐，故都指向了N18梢为，至少第1～4項(xiàng)為冗余信息。
一般說來轰坊，假如Chord環(huán)的大小為2^m铸董，節(jié)點(diǎn)數(shù)為2ⁿ，假如節(jié)點(diǎn)平均分布在Chord環(huán)上肴沫，則任一節(jié)點(diǎn)N的Finger表中的第i項(xiàng)為冗余的條件為：N+2 ^{i - 1}<N + 2^m/2ⁿ =>2ⁱ-1<2 ^m-n =>i <m-n+1粟害，即當(dāng)i <m-n+1時才有冗余。
冗余度為：(m-n+1)/m=1-（n-1)/m,一般說來m >>n,所以Chord會存在很多的冗余信息颤芬。假如悲幅，網(wǎng)絡(luò)上有1024個節(jié)點(diǎn)，即n=10,則冗余度為:1-(10-1)/160≈94%站蝠。所以很多論文都指出這一點(diǎn)汰具，并認(rèn)為會造成冗余查詢，降低性能菱魔。其實(shí)不然留荔，因?yàn)檫@些冗余信息是分布在多個Node的Finger表，如果采取適當(dāng)?shù)穆酚伤惴ɡ骄耄瑢β酚捎?jì)算不會有任何影響聚蝶。
至此，我們已經(jīng)完整地討論了Chord算法及其核心思想藻治，接下來要討論的是Chord的具體實(shí)施碘勉。

原文鏈接：http://blog.csdn.net/chen77716/article/details/6059575