Chord協議

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並未限制查詢內容的結構，因此應用層可以靈活的將內容映射到鍵值空間而不受協議的限制。 ^[1]