理論

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

普通哈希的問題

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

舉個(gè)栗子

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

圖片

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

圖片

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

一致性hash算法

一致性哈希同樣使用了取模的方式，不同的是對(duì) 2^32 這個(gè)固定的值進(jìn)行取模運(yùn)算。

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

Hsh環(huán)

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

圖片

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

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

圖片

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

如下圖：

圖片

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

新增節(jié)點(diǎn)

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

圖片

刪除節(jié)點(diǎn)

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

圖片

不平衡問題

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

但是因?yàn)樯晒Ｖ档姆植疾⒉皇蔷鶆虻?，如下圖新增k4、k5，如果節(jié)點(diǎn)B宕機(jī)了，k2和k4也遷移到節(jié)點(diǎn)C，導(dǎo)致那么大部分請(qǐng)求就落到節(jié)點(diǎn)C了，如果數(shù)量更多呢，此時(shí)會(huì)導(dǎo)致節(jié)點(diǎn)C壓力陡增，這樣就不均衡了！

圖片

那如何解決這個(gè)問題呢？

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

虛擬節(jié)點(diǎn)

虛擬節(jié)點(diǎn) 可以理解為是作為實(shí)際節(jié)點(diǎn)的一個(gè)copy，多個(gè)虛擬節(jié)點(diǎn)映射一個(gè)實(shí)際節(jié)點(diǎn)，因?yàn)樵诠－h(huán)上節(jié)點(diǎn)越多就分布的越均勻，即使我們現(xiàn)實(shí)中不會(huì)有那么多真實(shí)節(jié)點(diǎn)。

圖片

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

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

如下圖：

圖片

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

圖中只簡(jiǎn)單列舉了幾個(gè)虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)越多，相對(duì)會(huì)越均衡。

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