理論

一致性哈希算法是一種常用的分布式算法，其主要用途是在分布式系統(tǒng)中，將數(shù)據(jù)根據(jù)其鍵（key）進行散列（hash），然后將散列結(jié)果映射到環(huán)上，再根據(jù)數(shù)據(jù)節(jié)點的數(shù)量，將環(huán)劃分為多個區(qū)間，每個節(jié)點負責處理環(huán)上一定區(qū)間范圍內(nèi)的數(shù)據(jù)。

普通哈希的問題

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

舉個栗子

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

圖片

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

圖片

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

一致性hash算法

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

在使用一致哈希算法后，哈希表槽位數(shù)（大?。┑母淖兤骄恍枰獙?K/n 個關(guān)鍵字重新映射，其中K是關(guān)鍵字的數(shù)量， n是槽位數(shù)量，而不需要對所有的映射關(guān)系進行重新映射！

Hsh環(huán)

我們可以把一致哈希算法是對 2^32 進行取模運算的結(jié)果值虛擬成一個圓環(huán)，環(huán)上的刻度對應(yīng)一個 0~2^32 - 1 之間的數(shù)值，如下圖：

圖片

節(jié)點入環(huán)

下圖我們?nèi)齻€節(jié)點（A/B/C）經(jīng)過哈希計算，放入下面環(huán)中，一般我們會根據(jù)服務(wù)器的IP或者唯一別名進行哈希計算。

圖片

那數(shù)據(jù)是如何進行關(guān)系映射呢，同樣key值經(jīng)過哈希之后，結(jié)果映射到哈希環(huán)上，然后將結(jié)果值按順時針方向找到離自己最近的節(jié)點上，將value存儲到那個節(jié)點上。

如下圖：

圖片

k1、k2、k3經(jīng)過哈希計算后在哈希環(huán)的位置，順時針方向找到離自己最近的節(jié)點，比如k1最近的節(jié)點是A，節(jié)點A就是存儲 k1數(shù)據(jù)value的節(jié)點。

新增節(jié)點

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

圖片

刪除節(jié)點

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

圖片

不平衡問題

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

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

圖片

那如何解決這個問題呢？

那就是通過 虛擬節(jié)點

虛擬節(jié)點

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

圖片

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

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

如下圖：

圖片

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

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

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