一致性Hash

• 2020 年 8 月 12 日
• 筆記
• 分散式

緣起

我有一個圖片存取服務，為了快速獲取圖片，我架起了3台快取伺服器，用簡單的Hash映射決定圖片存儲在哪台快取上。比如:

f(x) % 3 = 0 存儲在s0上

f(x) % 3 = 1 存儲在s1上

f(x) % 3 = 2存儲在s2上

某天，快取負載過高，需要擴容1台，快取數量由3變為4，那麼按獲取圖片按公式：f(x) % n,很多會請求失敗，這樣會直接訪問後台服務，給後台服務造成很大的壓力，可能造成雪崩。

是否有這樣的演算法，解決分散式快取中，解決簡單Hash隨快取伺服器伸縮，造成大面積快取失效的問題

快取穿透

介紹 

一致性哈希演算法在1997年由麻省理工學院提出，是一種特殊的哈希演算法，目的是解決分散式快取的問題，解決了簡單哈希演算法在分散式哈希表中存在的動態伸縮等問題

原理

引入Hash環

假如有3個節點，三個節點位於環的不同位置

具體的值，根據Hash值取余環的大小，順時針方向找到最近的節點就是具體的存儲節點

比如：f(x1)存儲在Node1, f(x2)存儲在node2， f(x3)存儲在Node0

此時，如果加入了節點Node4，那麼原來指向Node2的紅色箭頭部分，快取會失效，變成存儲在Node4

如：f(x2)存儲在Node4

可以看到的效果是：當快取伺服器數量發生伸縮時，只有部分快取失效

實現

圓環大小：2³²，由來：整數4B=4*8bit(32位無符號整形)，值從0~2³² -1

每個節點位置：hash(ip) % 2³²

存儲的key位置：hash(key) % 2³²

使用場景

在分散式系統中一致性hash起著不可忽略的地位，無論是分散式快取，還是分散式Rpc框架的負載均衡策略都有所使用。

優缺點

優點:在分散式快取中

• 冗餘少
• 負載均衡
• 過渡平滑
• 存儲均衡
• 關鍵詞單調

缺點：可能存在Hash偏斜，如

解決策略

虛擬節點