【綜述】從一致性哈希演算法到緩存集群實現

03-17

一致性哈希（consistent hashing）演算法

讓我們先稍微複習一下一致性哈希演算法。

因為一般的哈希演算法（CRC16 /32）無法滿足單調性，所以需要一種能在緩存節點數量發生變化的情況下，最小化數據移動量的哈希演算法。

構建一個哈希環（hash ring）（2的32次方-1）
計算緩存對象的哈希值放入
計算緩存節點（ip或者主機名）的哈希值放入
從緩存對象所在的位置順時針查找最近的緩存節點位置

因為一致性哈希演算法無法滿足平衡性，所以需要引入虛擬節點的概念，通過為緩存節點創建N個虛擬節點（例如為ip或者主機名加上%N後綴），使緩存對象更均勻的分布在哈希環上。

哈希槽（部分哈希）演算法

哈希槽（hashing slot）或者部分哈希（part hashing）演算法是基於一般哈希演算法上發展而來的。

規劃槽的數量（常見1024（codis）或者16383（redis-cluster））
每個槽對應一個可重複的緩存節點
計算緩存對象的哈希值放入槽對應的節點

通過預先規劃和變動槽對應的緩存節點，就能滿足單調性和平衡性。

緩存集群

redis作為目前主流的緩存解決方案，在其集群使用中也廣泛的使用了一致性哈希演算法和哈希槽演算法。目前redis自身的replication已經非常成熟，沒有必要採用其他方案。

redis cluster

redis從3.0開始的原生cluster方案，採用了哈希槽演算法實現，支持reshard，請求未命中的任一緩存節點會重定向客戶端到可用的緩存節點，性能較差。

server-side shard/proxy

官方推薦的twemproxy已經長期未更新，採用了一致性哈希演算法實現。而且可運維性差（不支持reshard）。以codis為代表的伺服器端shard方案，採用了哈希槽演算法實現，完全代理了客戶端的訪問，接入簡便，伺服器端可以做各種運維（reshard，promote等），採用pipeline，性能中等。

client-side shard

一般採用一致性哈希演算法計算key來確定放入客戶端配置的緩存節點，可運維性差，但是性能較好。進一步可以採用加入zk來實現高可用的和進一步的動態reshard，演算法也建議修改成哈希槽，可參考如何實現高可用的redis集群。

proxy + redis cluster

優酷的方案，通過一個nginx作為反向代理實現client-side shard的功能，通過proxy計算hash slot所在的緩存節點，直接代理訪問，性能較高，可運維性強，但需要較多的代碼開發。優酷土豆的Redis服務平台化之路

參考文獻

優酷土豆的Redis服務平台化之路

每天進步一點點--五分鐘理解一致性哈希演算法(consistent hashing)

一致性哈希演算法的理解與實踐

如何實現高可用的redis集群

Redis cluster tutorial - Redis