理論

一致性哈希算法是一種常用的分布式算法，其主要用途是在分布式系統中，將數據根據其鍵（key）進行散列（hash），然后將散列結果映射到環上，再根據數據節點的數量，將環劃分為多個區間，每個節點負責處理環上一定區間范圍內的數據。

普通哈希的問題

分布式集群中，對機器的添加刪除，或者機器故障后自動脫離集群這些操作是集群管理最基本的功能。如果采用常用的hash(object)%N取模的方式，在節點進行添加或者刪除后，需要重新進行遷移改變映射關系，否則可能導致原有的數據無法找到。

舉個栗子

隨著業務和流量的增加，假如我們的Redis查詢服務節點擴展到了3個，為了將查詢請求進行均衡，每次請求都在相同的Redis中，使用hv = hash(key) % 3的方式計算，對每次查詢請求都通過hash值計算，得出來0、1 、2的值分別對應服務節點的編號，計算得到的hv的值就去對應的節點處理。

圖片

但是這里有個問題，服務增減是需要對此時的key進行重新計算，比如減少一個服務的時候，此時需要按 hv = hash(key) % 2計算，而增加一個服務節點的時候需要按hv = hash(key) % 4計算，而這種取模基數的變化會改變大部分原來的映射關系，導致數據查詢不到。

圖片

這個時候只能進行數據遷移，真是太麻煩了，而一致性哈希算法顯然是一個更好選擇！

一致性hash算法

一致性哈希同樣使用了取模的方式，不同的是對 2^32 這個固定的值進行取模運算。

在使用一致哈希算法后，哈希表槽位數（大小）的改變平均只需要對 K/n 個關鍵字重新映射，其中K是關鍵字的數量， n是槽位數量，而不需要對所有的映射關系進行重新映射！

Hsh環

我們可以把一致哈希算法是對 2^32 進行取模運算的結果值虛擬成一個圓環，環上的刻度對應一個 0~2^32 - 1 之間的數值，如下圖：

圖片

節點入環

下圖我們三個節點（A/B/C）經過哈希計算，放入下面環中，一般我們會根據服務器的IP或者唯一別名進行哈希計算。

圖片

那數據是如何進行關系映射呢，同樣key值經過哈希之后，結果映射到哈希環上，然后將結果值按順時針方向找到離自己最近的節點上，將value存儲到那個節點上。

如下圖：

圖片

k1、k2、k3經過哈希計算后在哈希環的位置，順時針方向找到離自己最近的節點，比如k1最近的節點是A，節點A就是存儲 k1數據value的節點。

新增節點

新增加點D，節點的數量增加到了四個，而此時k2最近的節點是D，所以會遷移到D，k1和k3不受影響

圖片

刪除節點

刪除節點B之后，存儲在B節點上的k2，將會重新映射找到離它最近的節點C，此時k2的數據存儲在C節點上，k1、k3不受影響。

圖片

不平衡問題

我們通過新增節點和刪除節點，知道了該方式會影響該節點的順時針的后一個節點，其他節點不受影響。

但是因為生成哈希值的分布并不是均勻的，如下圖新增k4、k5，如果節點B宕機了，k2和k4也遷移到節點C，導致那么大部分請求就落到節點C了，如果數量更多呢，此時會導致節點C壓力陡增，這樣就不均衡了！

圖片

那如何解決這個問題呢？

那就是通過 虛擬節點

虛擬節點

虛擬節點 可以理解為是作為實際節點的一個copy，多個虛擬節點映射一個實際節點，因為在哈希環上節點越多就分布的越均勻，即使我們現實中不會有那么多真實節點。

圖片

上圖中三個真實節點A、B、C，映射了9個虛擬節點，如果key值經過哈希落到臨近A-1、A-2、A-3的虛擬節點，那么最終都將映射到真實節點A，你想如果虛擬節點再多點，是不是就會更均衡了！

假設真實節點A被移除，A對應虛擬節點也會移除，但是多虛擬節點方式可以映射更多真實節點，讓剩余的節點更好得去承擔節點變化的請求壓力！

如下圖：

圖片

這里簡單講解一下，圖中真實節點A被移除，那么對應的虛擬節點移除，那么此時k1的重新映射到C-1、k3重新映射到B-3，也就是說被遷移到真實節點B和C，由此可見節點被移除會被更均衡的分散到其他節點上。

圖中只簡單列舉了幾個虛擬節點，虛擬節點越多，相對會越均衡。

好了，今天關于一致性哈希算法的介紹就到這了！