一致性哈希算法深度解析：原理、虛擬節點與分佈式緩存架構實戰

傳統取模算法的災難性缺陷

分佈式緩存集群N台節點，路由算法hash(key) % N。當節點變動：

• 節點下線：N→N-1，近100%鍵值重新映射，緩存雪崩直擊後端DB
• 節點上線：N→N+1，同理導致大面積失效
• 異構硬件：無法按性能權重分配負載

這是單調性違背：新增節點應盡量保持原有映射不變，僅影響必要範圍。

一致性哈希核心原理：環形哈希空間

步驟1：構建2^32環形空間

將哈希值空間[0, 2^32-1]首尾相連成環。

步驟2：對象映射到環上

對象object1~4經hash()得到key1~4，順時針分布於環上。

步驟3：緩存節點映射到環上

節點A、B、C用IP/主機名哈希得到keyA、keyB、keyC，同樣分布於環上。

步驟4：順時針尋找最近節點

從對象key出發順時針，遇到的第一個節點即為歸屬節點。
示例：object1→A、object2、3→C、object4→B。

步驟5：節點變動影響範圍最小化

• 移除B：僅object4（B逆時針到C間）重映射到C
• 新增D（位於object2、3間）：僅object2重映射到D

結論：僅影響逆時針方向下一個節點間的對象，完美滿足單調性。

虛擬節點：解決小集群負載不均

少量物理節點（如2台）在環上分布稀疏，導致對象極不均勻（一台存90%）。

引入虛擬節點（VNode）

• 每個物理節點對應K個虛擬節點（副本數），如K=2時：A1、A2、C1、C2
• 虛擬節點哈希計算：hash("IP#1")、hash("IP#2")
• 對象→虛擬節點→物理節點，雙層映射

效果：虛擬節點越多（典型100-200），負載分佈越均勻，新增/移除節點時數據遷移量越平滑。

工程落地關鍵點

• 哈希函數選擇：FNV1a、MurmurHash、Ketama算法（Memcached客戶端標準）
• 虛擬節點數：建議150-200，平衡內存佔用與均勻度
• 客戶端實現：避免中心化調度，客戶端本地計算路由，無單點故障
• 權重支持：高性能機器配置更多虛擬節點（如K=300 vs K=100）

一致性哈希是分佈式系統擴縮容平滑、負載均衡、去中心化的基石算法，Redis Cluster、Dynamo、Cassandra、Kubernetes Service Proxy均採用其變體。