題幹與適用場景
實作把字串 key 路由到實體節點的雜湊環。API 是 addNode(nodeId, weight)、removeNode(nodeId) 與 getNode(key)。節點產生 weight × V 個虛擬 token，使用確定性的 64 位元雜湊；查找 key 順時針遇到的第一個存活 token。空環回傳空節點。假設更新由呼叫端序列化，重點是可執行資料結構而非完整成員服務。
面試官考察點
PracHub 將此題記錄為 DoorDash Software Engineer 技術面試，要求三個 API、虛擬節點、碰撞處理與複雜度；Glassdoor 的近期公開面試紀錄也提到修復 round-robin 負載平衡器並實作一致性雜湊。MIT 原論文將 balance 與 monotonicity 視為核心性質：負載大致均衡，新增桶時不移動本可保留的 key。
回答前需要澄清的問題
- node ID 是否穩定且唯一？移除必須精確找到該實體節點的 token。
- weight 是否為正整數？本文假設是；小數容量需另做 token 預算歸一化。
- 更新是否與查找並行？若並行，發佈不可變快照；範例假設更新序列化。
- 是否要求副本？基礎 API 只回傳一個 owner，多副本是後續限制。
- 雜湊函式是否給定？練習假設確定且近似均勻，生產仍需評估碰撞與對抗輸入。
30 秒回答框架
「我保存按 (tokenHash, virtualTokenId, nodeId) 排序的記錄。新增節點插入 weight × V 個確定 token，刪除節點只刪除它擁有的 token。查找時二分找到第一個不小於 key hash 的 token，越過末尾就回到零。核心不變量是每個 token 只屬於一個存活節點、每個 key 歸屬順時針第一個 token。查找 O(log M)，更新取決於容器；我會測試碰撞、環回、重複更新、刪除、空環和重映射。」
分步深入解答
1. 表示與不變量
用排序陣列保存 (hash, tokenId, nodeId)，再用 nodeId → tokens 反向索引精確刪除。維持四個不變量：token 按 (hash, tokenId) 排序；每個 token 指向註冊節點；key 歸屬順時針第一個 token；token 由穩定 node ID、索引和 token 數生成。第二排序鍵讓雜湊碰撞仍確定。
2. 確定產生虛擬節點
對節點 n 與索引 i 雜湊 n + "#" + i，產生 weight × V 個索引。weight 越大，期望擁有區間越多。V 與權重策略應隨環快照保存；修改它們會造成預期外的重映射。
3. 實作 API
from bisect import bisect_left
class ConsistentHashRing:
def __init__(self, virtuals_per_weight, hash64):
self.v = virtuals_per_weight
self.hash64 = hash64
self.tokens = [] # (hash, token_id, node_id)
self.by_node = {}
def add_node(self, node_id, weight=1):
if weight <= 0 or node_id in self.by_node:
raise ValueError("invalid or duplicate node")
owned = []
for i in range(weight * self.v):
token_id = f"{node_id}#{i}"
owned.append((self.hash64(token_id), token_id, node_id))
self.by_node[node_id] = owned
self.tokens.extend(owned)
self.tokens.sort()
def remove_node(self, node_id):
owned = self.by_node.pop(node_id, None)
if owned is None:
return False
owned_ids = {token_id for _, token_id, _ in owned}
self.tokens = [t for t in self.tokens if t[1] not in owned_ids]
return True
def get_node(self, key):
if not self.tokens:
return None
h = self.hash64(key)
i = bisect_left(self.tokens, (h, "", ""))
return self.tokens[i if i < len(self.tokens) else 0][2]重複節點視為呼叫錯誤，刪除不存在節點回傳 false。生產實作可先建立新快照再原子發佈，避免讀者看到半更新狀態。
4. 複雜度與重映射
令 M = V × sum(weight)。查找 O(log M)，每次額外空間 O(1)，陣列實作更新為 O(M + K log M)，其中 K 是變更節點 token 數；平衡樹可降為 O(K log M)，總空間 O(M)。節點加入只影響其虛擬 token 前方區間，移除後這些區間轉移到下一個順時針 owner；這是相比 hash % N 的優勢。虛擬節點不能解決單一熱點 key。
高品質示範回答
「我用排序的 (hash, tokenId, nodeId) 記錄和反向索引實作。新增節點生成穩定的 weight × V 個虛擬 token，刪除時精確刪除它們，查找用 lower-bound 並處理環回。碰撞以 tokenId 決定順序。排序陣列查找 O(log M)，更新 O(M + K log M)；平衡樹可讓更新 O(K log M)。我會測試空環、單節點、環回、重複 ID、碰撞、權重分布、刪除和節點變更後的 key 重映射比例。」
常見錯誤
- 使用
hash(key) % N→ 節點數變化會大規模重映射 → 查找順時針 token。 - 假設不會碰撞 → 相同 hash 的 owner 不穩定 → 用確定 tokenId 打破平手。
- 每次重啟隨機產生 token → 所有 key 意外遷移 → 從穩定 node ID 和索引產生。
- 只按名稱前綴刪除 → 相似 ID 可能誤刪 → 維護反向索引。
- 聲稱虛擬節點消除熱點 → 單一熱門 key 仍只有一個 owner → 把副本或熱點處理列為獨立需求。
- 忽略空環和重複 → 邊界不變量失效 → 先定義回傳值和錯誤行為。
追問及應對
如何回傳三個副本？
從 owner 順時針掃描，收集不同實體 node ID；跳過同一節點的其他虛擬 token。存活節點不足時回傳可用集合並明確短缺。
如何測試分布？
產生固定 key 集合，統計各節點占比及最大最小比，加入與移除節點後重複測試；固定雜湊種子讓回歸可重現。
節點容量變更怎麼辦？
先刪舊 token，再按新 weight 增加 token，並一次發佈快照；監控變更期間負載。
什麼時候 modulo 更簡單？
成員固定或可接受全量重平衡時，modulo 更短；成員常變且重映射成本重要時，才值得一致性雜湊的複雜度。