Chord協定

Chord協定使用一致性哈希作為哈希算法。在一致性哈希協定中並沒有定義具體的算法，在Chord協定中將其規定為SHA-1。

Chord在2001年由麻省理工學院提出(參見0)，其核心思想就是要解決在P2P套用中遇到的基本問題：如何在P2P網路中找到存有特定數據的節點。Chord專門為P2P套用設計，因此考慮了在P2P套用中可能遇到的特殊問題，這些內容將在路由的部分進行討論。
哈希算法
Chord使用一致性哈希作為哈希算法。在一致性哈希協定中並沒有定義具體的算法，在Chord協定中將其規定為SHA-1。
路由算法
Chord在一致性哈希的基礎上提供了最佳化的路由算法：
在Chord中，每個節點同樣需要存儲m個其他節點的信息，這些信息的集合被稱為查詢表(Finger Table)。一致性哈希中的節點同樣具有這樣的表格，但在Chord中，表格中的節點不再是直接相鄰的節點，它們的間距(ID間隔)將成2i 的關係排列(i 表示表中的數組下標)。這樣形成的節點之間路由關係實際上就是折半查找算法需要的排列關係。
在查詢的過程中，查詢節點將請求傳送到與鍵值最接近的節點上。收到查詢請求的節點如果發現自身存儲了被查詢的信息，可以直接回應查詢節點(這與一致性哈希完全相同)；如果被查詢的信息不在本地，就根據查詢表將請求轉發到與鍵值最接近的節點上。這樣的過程一直持續到找到相應的節點為止。不難看出，查詢過程實際上就是折半查找的過程。
經過Chord的最佳化後，查詢需要的跳數由O ( N)減少到O(log(N))。這樣即使在大規模的P2P網路中(例如N=100,000,000)，查詢的跳數也僅為O(8)，每個節點僅需存儲27個(log2100000000)其他節點的信息。
Chord還考慮到多個節點同時加入系統的情況並對節點加入/退出算法作了最佳化。
Chord算法本身具有如下優點：
負載平衡
這一優點來自於一致性哈希，也就是一致性哈希中提到的平衡性。所有的節點以同等的機率分擔系統負荷，從而可以避免某些節點負載過大的情況。
分布性
Chord是純分散式系統，節點之間完全平等並完成同樣的工作。這使得Chord具有很高的魯棒性，可以抵禦DoS攻擊。
可擴展性
Chord協定的開銷隨著系統規模(結點總數N)的增加而按照O(logN)的比例增加。因此Chord可以用於大規模的系統。
可用性
Chord協定要求節點根據網路的變化動態的更新查詢表，因此能夠及時恢復路由關係，使得查詢可以可靠地進行。
命名的靈活性
Chord並未限制查詢內容的結構，因此套用層可以靈活的將內容映射到鍵值空間而不受協定的限制。
Chord在CFS系統中得到了套用，具體的介紹可參見[8]