在了解一致性哈希算法之前，最好先了解一下緩存中的一個(gè)應(yīng)用場(chǎng)景，了解了這個(gè)應(yīng)用場(chǎng)景之后，再來(lái)理解一致性哈希算法，就容易多了，也更能體現(xiàn)出一致性哈希算法的優(yōu)點(diǎn)，那么，我們先來(lái)描述一下這個(gè)經(jīng)典的分布式緩存的應(yīng)用場(chǎng)景。

場(chǎng)景描述

假設(shè)，我們有三臺(tái)緩存服務(wù)器，用于緩存圖片，我們?yōu)檫@三臺(tái)緩存服務(wù)器編號(hào)為0號(hào)、1號(hào)、2號(hào)，現(xiàn)在，有3萬(wàn)張圖片需要緩存，我們希望這些圖片被均勻的緩存到這3臺(tái)服務(wù)器上，以便它們能夠分?jǐn)偩彺娴膲毫ΑＲ簿褪钦f(shuō)，我們希望每臺(tái)服務(wù)器能夠緩存1萬(wàn)張左右的圖片，那么，我們應(yīng)該怎樣做呢？如果我們沒(méi)有任何規(guī)律的將3萬(wàn)張圖片平均的緩存在3臺(tái)服務(wù)器上，可以滿足我們的要求嗎？可以！但是如果這樣做，當(dāng)我們需要訪問(wèn)某個(gè)緩存項(xiàng)時(shí)，則需要遍歷3臺(tái)緩存服務(wù)器，從3萬(wàn)個(gè)緩存項(xiàng)中找到我們需要訪問(wèn)的緩存，遍歷的過(guò)程效率太低，時(shí)間太長(zhǎng)，當(dāng)我們找到需要訪問(wèn)的緩存項(xiàng)時(shí)，時(shí)長(zhǎng)可能是不能被接受的，也就失去了緩存的意義，緩存的目的就是提高速度，改善用戶體驗(yàn)，減輕后端服務(wù)器壓力，如果每次訪問(wèn)一個(gè)緩存項(xiàng)都需要遍歷所有緩存服務(wù)器的所有緩存項(xiàng)，想想就覺(jué)得很累，那么，我們?cè)撛趺崔k呢？原始的做法是對(duì)緩存項(xiàng)的鍵進(jìn)行哈希，將hash后的結(jié)果對(duì)緩存服務(wù)器的數(shù)量進(jìn)行取模操作，通過(guò)取模后的結(jié)果，決定緩存項(xiàng)將會(huì)緩存在哪一臺(tái)服務(wù)器上，這樣說(shuō)可能不太容易理解，我們舉例說(shuō)明，仍然以剛才描述的場(chǎng)景為例，假設(shè)我們使用圖片名稱作為訪問(wèn)圖片的key，假設(shè)圖片名稱是不重復(fù)的，那么，我們可以使用如下公式，計(jì)算出圖片應(yīng)該存放在哪臺(tái)服務(wù)器上。

hash（圖片名稱）% N

因?yàn)閳D片的名稱是不重復(fù)的，所以，當(dāng)我們對(duì)同一個(gè)圖片名稱做相同的哈希計(jì)算時(shí)，得出的結(jié)果應(yīng)該是不變的，如果我們有3臺(tái)服務(wù)器，使用哈希后的結(jié)果對(duì)3求余，那么余數(shù)一定是0、1或者2，沒(méi)錯(cuò)，正好與我們之前的服務(wù)器編號(hào)相同，如果求余的結(jié)果為0， 我們就把當(dāng)前圖片名稱對(duì)應(yīng)的圖片緩存在0號(hào)服務(wù)器上，如果余數(shù)為1，就把當(dāng)前圖片名對(duì)應(yīng)的圖片緩存在1號(hào)服務(wù)器上，如果余數(shù)為2，同理，那么，當(dāng)我們?cè)L問(wèn)任意一個(gè)圖片的時(shí)候，只要再次對(duì)圖片名稱進(jìn)行上述運(yùn)算，即可得出對(duì)應(yīng)的圖片應(yīng)該存放在哪一臺(tái)緩存服務(wù)器上，我們只要在這一臺(tái)服務(wù)器上查找圖片即可，如果圖片在對(duì)應(yīng)的服務(wù)器上不存在，則證明對(duì)應(yīng)的圖片沒(méi)有被緩存，也不用再去遍歷其他緩存服務(wù)器了，通過(guò)這樣的方法，即可將3萬(wàn)張圖片隨機(jī)的分布到3臺(tái)緩存服務(wù)器上了，而且下次訪問(wèn)某張圖片時(shí)，直接能夠判斷出該圖片應(yīng)該存在于哪臺(tái)緩存服務(wù)器上，這樣就能滿足我們的需求了，我們暫時(shí)稱上述算法為HASH算法或者取模算法，取模算法的過(guò)程可以用下圖表示。

但是，使用上述HASH算法進(jìn)行緩存時(shí)，會(huì)出現(xiàn)一些缺陷，試想一下，如果3臺(tái)緩存服務(wù)器已經(jīng)不能滿足我們的緩存需求，那么我們應(yīng)該怎么做呢？沒(méi)錯(cuò)，很簡(jiǎn)單，多增加兩臺(tái)緩存服務(wù)器不就行了，假設(shè)，我們?cè)黾恿艘慌_(tái)緩存服務(wù)器，那么緩存服務(wù)器的數(shù)量就由3臺(tái)變成了4臺(tái)，此時(shí)，如果仍然使用上述方法對(duì)同一張圖片進(jìn)行緩存，那么這張圖片所在的服務(wù)器編號(hào)必定與原來(lái)3臺(tái)服務(wù)器時(shí)所在的服務(wù)器編號(hào)不同，因?yàn)槌龜?shù)由3變?yōu)榱?，被除數(shù)不變的情況下，余數(shù)肯定不同，這種情況帶來(lái)的結(jié)果就是當(dāng)服務(wù)器數(shù)量變動(dòng)時(shí)，所有緩存的位置都要發(fā)生改變，換句話說(shuō)，當(dāng)服務(wù)器數(shù)量發(fā)生改變時(shí)，所有緩存在一定時(shí)間內(nèi)是失效的，當(dāng)應(yīng)用無(wú)法從緩存中獲取數(shù)據(jù)時(shí)，則會(huì)向后端服務(wù)器請(qǐng)求數(shù)據(jù)，同理，假設(shè)3臺(tái)緩存中突然有一臺(tái)緩存服務(wù)器出現(xiàn)了故障，無(wú)法進(jìn)行緩存，那么我們則需要將故障機(jī)器移除，但是如果移除了一臺(tái)緩存服務(wù)器，那么緩存服務(wù)器數(shù)量從3臺(tái)變?yōu)?臺(tái)，如果想要訪問(wèn)一張圖片，這張圖片的緩存位置必定會(huì)發(fā)生改變，以前緩存的圖片也會(huì)失去緩存的作用與意義，由于大量緩存在同一時(shí)間失效，造成了緩存的雪崩，此時(shí)前端緩存已經(jīng)無(wú)法起到承擔(dān)部分壓力的作用，后端服務(wù)器將會(huì)承受巨大的壓力，整個(gè)系統(tǒng)很有可能被壓垮，所以，我們應(yīng)該想辦法不讓這種情況發(fā)生，但是由于上述HASH算法本身的緣故，使用取模法進(jìn)行緩存時(shí)，這種情況是無(wú)法避免的，為了解決這些問(wèn)題，一致性哈希算法誕生了。

?

我們來(lái)回顧一下使用上述算法會(huì)出現(xiàn)的問(wèn)題。

問(wèn)題1：當(dāng)緩存服務(wù)器數(shù)量發(fā)生變化時(shí)，會(huì)引起緩存的雪崩，可能會(huì)引起整體系統(tǒng)壓力過(guò)大而崩潰（大量緩存同一時(shí)間失效）。

問(wèn)題2：當(dāng)緩存服務(wù)器數(shù)量發(fā)生變化時(shí)，幾乎所有緩存的位置都會(huì)發(fā)生改變，怎樣才能盡量減少受影響的緩存呢？

?

其實(shí)，上面兩個(gè)問(wèn)題是一個(gè)問(wèn)題，那么，一致性哈希算法能夠解決上述問(wèn)題嗎？

我們現(xiàn)在就來(lái)了解一下一致性哈希算法。

? ?

一致性哈希算法的基本概念

其實(shí)，一致性哈希算法也是使用取模的方法，只是，剛才描述的取模法是對(duì)服務(wù)器的數(shù)量進(jìn)行取模，而一致性哈希算法是對(duì)2^32取模，什么意思呢？我們慢慢聊。

?

首先，我們把二的三十二次方想象成一個(gè)圓，就像鐘表一樣，鐘表的圓可以理解成由60個(gè)點(diǎn)組成的圓，而此處我們把這個(gè)圓想象成由2^32個(gè)點(diǎn)組成的圓，示意圖如下：

圓環(huán)的正上方的點(diǎn)代表0，0點(diǎn)右側(cè)的第一個(gè)點(diǎn)代表1，以此類推，2、3、4、5、6……直到2^32-1,也就是說(shuō)0點(diǎn)左側(cè)的第一個(gè)點(diǎn)代表2^32-1?

我們把這個(gè)由2的32次方個(gè)點(diǎn)組成的圓環(huán)稱為hash環(huán)。

?

那么，一致性哈希算法與上圖中的圓環(huán)有什么關(guān)系呢？我們繼續(xù)聊，仍然以之前描述的場(chǎng)景為例，假設(shè)我們有3臺(tái)緩存服務(wù)器，服務(wù)器A、服務(wù)器B、服務(wù)器C，那么，在生產(chǎn)環(huán)境中，這三臺(tái)服務(wù)器肯定有自己的IP地址，我們使用它們各自的IP地址進(jìn)行哈希計(jì)算，使用哈希后的結(jié)果對(duì)2^32取模，可以使用如下公式示意。

hash（服務(wù)器A的IP地址） % ?2^32

通過(guò)上述公式算出的結(jié)果一定是一個(gè)0到2^32-1之間的一個(gè)整數(shù)，我們就用算出的這個(gè)整數(shù)，代表服務(wù)器A，既然這個(gè)整數(shù)肯定處于0到2^32-1之間，那么，上圖中的hash環(huán)上必定有一個(gè)點(diǎn)與這個(gè)整數(shù)對(duì)應(yīng)，而我們剛才已經(jīng)說(shuō)明，使用這個(gè)整數(shù)代表服務(wù)器A，那么，服務(wù)器A就可以映射到這個(gè)環(huán)上，用下圖示意

同理，服務(wù)器B與服務(wù)器C也可以通過(guò)相同的方法映射到上圖中的hash環(huán)中

hash（服務(wù)器B的IP地址） % ?2^32

hash（服務(wù)器C的IP地址） % ?2^32

通過(guò)上述方法，可以將服務(wù)器B與服務(wù)器C映射到上圖中的hash環(huán)上，示意圖如下

假設(shè)3臺(tái)服務(wù)器映射到hash環(huán)上以后如上圖所示（當(dāng)然，這是理想的情況，我們慢慢聊）。

?

好了，到目前為止，我們已經(jīng)把緩存服務(wù)器與hash環(huán)聯(lián)系在了一起，我們通過(guò)上述方法，把緩存服務(wù)器映射到了hash環(huán)上，那么使用同樣的方法，我們也可以將需要緩存的對(duì)象映射到hash環(huán)上。

?

假設(shè)，我們需要使用緩存服務(wù)器緩存圖片，而且我們?nèi)匀皇褂脠D片的名稱作為找到圖片的key，那么我們使用如下公式可以將圖片映射到上圖中的hash環(huán)上。

hash（圖片名稱） % ?2^32

映射后的示意圖如下，下圖中的橘黃色圓形表示圖片

好了，現(xiàn)在服務(wù)器與圖片都被映射到了hash環(huán)上，那么上圖中的這個(gè)圖片到底應(yīng)該被緩存到哪一臺(tái)服務(wù)器上呢？上圖中的圖片將會(huì)被緩存到服務(wù)器A上，為什么呢？因?yàn)閺膱D片的位置開(kāi)始，沿順時(shí)針?lè)较蛴龅降牡谝粋€(gè)服務(wù)器就是A服務(wù)器，所以，上圖中的圖片將會(huì)被緩存到服務(wù)器A上，如下圖所示。

沒(méi)錯(cuò)，一致性哈希算法就是通過(guò)這種方法，判斷一個(gè)對(duì)象應(yīng)該被緩存到哪臺(tái)服務(wù)器上的，將緩存服務(wù)器與被緩存對(duì)象都映射到hash環(huán)上以后，從被緩存對(duì)象的位置出發(fā)，沿順時(shí)針?lè)较蛴龅降牡谝粋€(gè)服務(wù)器，就是當(dāng)前對(duì)象將要緩存于的服務(wù)器，由于被緩存對(duì)象與服務(wù)器hash后的值是固定的，所以，在服務(wù)器不變的情況下，一張圖片必定會(huì)被緩存到固定的服務(wù)器上，那么，當(dāng)下次想要訪問(wèn)這張圖片時(shí)，只要再次使用相同的算法進(jìn)行計(jì)算，即可算出這個(gè)圖片被緩存在哪個(gè)服務(wù)器上，直接去對(duì)應(yīng)的服務(wù)器查找對(duì)應(yīng)的圖片即可。

?

剛才的示例只使用了一張圖片進(jìn)行演示，假設(shè)有四張圖片需要緩存，示意圖如下

1號(hào)、2號(hào)圖片將會(huì)被緩存到服務(wù)器A上，3號(hào)圖片將會(huì)被緩存到服務(wù)器B上，4號(hào)圖片將會(huì)被緩存到服務(wù)器C上。

? ?

一致性哈希算法的優(yōu)點(diǎn)

經(jīng)過(guò)上述描述，我想兄弟你應(yīng)該已經(jīng)明白了一致性哈希算法的原理了，但是話說(shuō)回來(lái)，一致性哈希算法能夠解決之前出現(xiàn)的問(wèn)題嗎，我們說(shuō)過(guò)，如果簡(jiǎn)單的對(duì)服務(wù)器數(shù)量進(jìn)行取模，那么當(dāng)服務(wù)器數(shù)量發(fā)生變化時(shí)，會(huì)產(chǎn)生緩存的雪崩，從而很有可能導(dǎo)致系統(tǒng)崩潰，那么使用一致性哈希算法，能夠避免這個(gè)問(wèn)題嗎？我們來(lái)模擬一遍，即可得到答案。

?

假設(shè)，服務(wù)器B出現(xiàn)了故障，我們現(xiàn)在需要將服務(wù)器B移除，那么，我們將上圖中的服務(wù)器B從hash環(huán)上移除即可，移除服務(wù)器B以后示意圖如下。

在服務(wù)器B未移除時(shí)，圖片3應(yīng)該被緩存到服務(wù)器B中，可是當(dāng)服務(wù)器B移除以后，按照之前描述的一致性哈希算法的規(guī)則，圖片3應(yīng)該被緩存到服務(wù)器C中，因?yàn)閺膱D片3的位置出發(fā)，沿順時(shí)針?lè)较蛴龅降牡谝粋€(gè)緩存服務(wù)器節(jié)點(diǎn)就是服務(wù)器C，也就是說(shuō)，如果服務(wù)器B出現(xiàn)故障被移除時(shí)，圖片3的緩存位置會(huì)發(fā)生改變

?
?

但是，圖片4仍然會(huì)被緩存到服務(wù)器C中，圖片1與圖片2仍然會(huì)被緩存到服務(wù)器A中，這與服務(wù)器B移除之前并沒(méi)有任何區(qū)別，這就是一致性哈希算法的優(yōu)點(diǎn)，如果使用之前的hash算法，服務(wù)器數(shù)量發(fā)生改變時(shí)，所有服務(wù)器的所有緩存在同一時(shí)間失效了，而使用一致性哈希算法時(shí)，服務(wù)器的數(shù)量如果發(fā)生改變，并不是所有緩存都會(huì)失效，而是只有部分緩存會(huì)失效，前端的緩存仍然能分擔(dān)整個(gè)系統(tǒng)的壓力，而不至于所有壓力都在同一時(shí)間集中到后端服務(wù)器上。

?

這就是一致性哈希算法所體現(xiàn)出的優(yōu)點(diǎn)。

? ?

hash環(huán)的偏斜

在介紹一致性哈希的概念時(shí)，我們理想化的將3臺(tái)服務(wù)器均勻的映射到了hash環(huán)上，如下圖所示

但是，理想很豐滿，現(xiàn)實(shí)很骨感，我們想象的與實(shí)際情況往往不一樣。

在實(shí)際的映射中，服務(wù)器可能會(huì)被映射成如下模樣。

聰明如你一定想到了，如果服務(wù)器被映射成上圖中的模樣，那么被緩存的對(duì)象很有可能大部分集中緩存在某一臺(tái)服務(wù)器上，如下圖所示。

上圖中，1號(hào)、2號(hào)、3號(hào)、4號(hào)、6號(hào)圖片均被緩存在了服務(wù)器A上，只有5號(hào)圖片被緩存在了服務(wù)器B上，服務(wù)器C上甚至沒(méi)有緩存任何圖片，如果出現(xiàn)上圖中的情況，A、B、C三臺(tái)服務(wù)器并沒(méi)有被合理的平均的充分利用，緩存分布的極度不均勻，而且，如果此時(shí)服務(wù)器A出現(xiàn)故障，那么失效緩存的數(shù)量也將達(dá)到最大值，在極端情況下，仍然有可能引起系統(tǒng)的崩潰，上圖中的情況則被稱之為hash環(huán)的偏斜，那么，我們應(yīng)該怎樣防止hash環(huán)的偏斜呢？一致性hash算法中使用"虛擬節(jié)點(diǎn)"解決了這個(gè)問(wèn)題，我們繼續(xù)聊。

? ?

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

話接上文，由于我們只有3臺(tái)服務(wù)器，當(dāng)我們把服務(wù)器映射到hash環(huán)上的時(shí)候，很有可能出現(xiàn)hash環(huán)偏斜的情況，當(dāng)hash環(huán)偏斜以后，緩存往往會(huì)極度不均衡的分布在各服務(wù)器上，聰明如你一定已經(jīng)想到了，如果想要均衡的將緩存分布到3臺(tái)服務(wù)器上，最好能讓這3臺(tái)服務(wù)器盡量多的、均勻的出現(xiàn)在hash環(huán)上，但是，真實(shí)的服務(wù)器資源只有3臺(tái)，我們?cè)鯓討{空的讓它們多起來(lái)呢，沒(méi)錯(cuò)，就是憑空的讓服務(wù)器節(jié)點(diǎn)多起來(lái)，既然沒(méi)有多余的真正的物理服務(wù)器節(jié)點(diǎn)，我們就只能將現(xiàn)有的物理節(jié)點(diǎn)通過(guò)虛擬的方法復(fù)制出來(lái)，這些由實(shí)際節(jié)點(diǎn)虛擬復(fù)制而來(lái)的節(jié)點(diǎn)被稱為"虛擬節(jié)點(diǎn)"。加入虛擬節(jié)點(diǎn)以后的hash環(huán)如下。

"虛擬節(jié)點(diǎn)"是"實(shí)際節(jié)點(diǎn)"（實(shí)際的物理服務(wù)器）在hash環(huán)上的復(fù)制品,一個(gè)實(shí)際節(jié)點(diǎn)可以對(duì)應(yīng)多個(gè)虛擬節(jié)點(diǎn)。

從上圖可以看出，A、B、C三臺(tái)服務(wù)器分別虛擬出了一個(gè)虛擬節(jié)點(diǎn)，當(dāng)然，如果你需要，也可以虛擬出更多的虛擬節(jié)點(diǎn)。引入虛擬節(jié)點(diǎn)的概念后，緩存的分布就均衡多了，上圖中，1號(hào)、3號(hào)圖片被緩存在服務(wù)器A中，5號(hào)、4號(hào)圖片被緩存在服務(wù)器B中，6號(hào)、2號(hào)圖片被緩存在服務(wù)器C中，如果你還不放心，可以虛擬出更多的虛擬節(jié)點(diǎn)，以便減小hash環(huán)偏斜所帶來(lái)的影響，虛擬節(jié)點(diǎn)越多，hash環(huán)上的節(jié)點(diǎn)就越多，緩存被均勻分布的概率就越大。

? ?

好了，一致性哈希算法的原理就總結(jié)到這里，如有錯(cuò)誤，歡迎賜教，如需轉(zhuǎn)載，請(qǐng)標(biāo)注原文鏈接。

原文鏈接：白話解析：一致性哈希算法 consistent hashing

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的白话解析：一致性哈希算法 consistent hashing的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。