Chord 算法完整實現詳解：從單機版到叢集版

背景

Chord 是最經典的 DHT（分散式雜湊表）實現，基於一致性雜湊 + Finger 表實現 O(log N) 路由。本文詳細剖析單機版與叢集版核心實現邏輯。

單機版核心資料結構

ChordNode

• `nodeId`：業務標識
• `ChordKey`：SHA-1 雜湊值，決定在環上位置（0 ~ 2¹⁶⁰-1）
• `successor`、`predecessor`：順時針後繼/前驅
• `FingerTable`：m 條記錄（m=160），第 i 條 = `key + 2ⁱ` 順時針第一個節點

Finger 表可視為：以本節點為起點，按 2 的冪等比切分環，每段記錄最近後繼，構成全域二分路由表。

建立環與加入節點流程

1. 建立種子節點：每個節點初始化時視自己為唯一節點，`succ = pred = self`，Finger 全指向自己。
2. 加入現有環：新節點 Nₖ 透過已知節點 N₀ `join`：
   1. N₀ 協助查找 Nₖ 的後繼 Nₛᵤ꜀ = N₀.findSuccessor(Nₖ.key)
   2. 確認 Nₖ 與 Nₛᵤ꜀ 關係：Nₖ.pred = Nₛᵤ꜀.pred；Nₛᵤ꜀.pred = Nₖ；Nₖ.pred.succ = Nₖ
   3. 刷新所有受影響節點的 Finger 表（掃描各節點 Finger，更新指向 Nₖ 的項）

關鍵圖解

圖中展示 N₀ 協助 Nₖ 找後繼、調整前驅後繼鏈、更新 Finger 表的完整過程。

叢集版架構

• 節點分布於多 JVM，透過 RMI/Socket/Local 通訊。
• 核心類 `ChordImpl` 包含：`NodeImpl`（本地節點代理）、`Entries`（資料 K/V）、`References`（前驅、後繼列表、資料引用）、線程池、雜湊函數。

關鍵操作實現

findSuccessor(key)

1. 無後繼 → 唯一節點，回傳自己。
2. key 在 (self, succ] 間 → 回傳 succ（可選 ping 檢活）。
3. 否則找最接近 key 的前驅節點，遞歸呼叫其 `findSuccessor`。

create() 建立新環

初始化 Entries/References/LocalNode，啟動三大定時任務：

• StabilizeTask：週期性穩固後繼關係（檢查 succ.pred 是否為自己）
• FixFingerTask：隨機採樣 key 更新 Finger 表
• CheckPredecessorTask：ping 前驅，失聯則清除

join(bootstrapURL) 加入現有環

1. 初始化本地資料結構。
2. 透過 Proxy 連接 bootstrap 節點。
3. 呼叫遠端 `findSuccessor` 獲取後繼。
4. 呼叫遠端 `notifyAndCopyEntries` 取得前驅、後繼列表、Entries 引用。
5. 根據引用列表計算正確前驅（可能需多輪 `notifyAndCopyEntries` 修正）。
6. 啟動定時任務與通訊監聽。

leave() 離開

關閉線程池，通知前驅後繼更新指標，斷開連線。

資料操作

`insert/retrieve/remove` 皆先 `findSuccessor(key)` 定位節點，再呼叫該節點對應方法。

命令行工具展示

oc> create -names n1
oc> create -names n2_n3 -bootstraps n1
oc> refs -node n1   # 顯示 Finger 表、後繼列表、前驅
oc> joinN           # 加入遠端叢集

支援本地/遠端混合操作，適合除錯與教學。

總結

Chord = 一致性雜湊 + Finger 表。單機版專注記憶體資料結構維護；叢集版增加網路通訊、容錯、定時穩定機制。核心難點在於節點加入/離開時前驅後繼與 Finger 表的正確收斂。