在分布式系統(tǒng)中架構(gòu)中我們經(jīng)常提到一致性哈希算法，那么什么是一致性哈希算法，為什么需要一致性哈希算法呢？

1、為什么需要一致性哈希算法

    假設(shè)現(xiàn)在有三臺(tái)緩存服務(wù)器（緩存服務(wù)器A、緩存服務(wù)器B、緩存服務(wù)器C），現(xiàn)在將數(shù)據(jù)預(yù)熱到這三臺(tái)服務(wù)器，我們可以使用負(fù)載均衡的方法將數(shù)據(jù)緩存到服務(wù)器上，如下圖所示：

    通過負(fù)載均衡的方式可以把數(shù)據(jù)均勻的分發(fā)到三臺(tái)緩存服務(wù)器上，在讀取緩存的熱點(diǎn)數(shù)據(jù)就存在一定的困難（因?yàn)椴磺宄?shù)據(jù)被緩存在那臺(tái)服務(wù)器上），讀取數(shù)據(jù)的過程如下所示：

    通過輪詢緩存服務(wù)器的方式讀取緩存的熱點(diǎn)數(shù)據(jù)，此時(shí)效率就非常的低了，接口的響應(yīng)時(shí)間也會(huì)變長，從而導(dǎo)致用戶的體驗(yàn)非常差。

    負(fù)載均衡的方案致命的缺點(diǎn)是無法快速的定位數(shù)據(jù)在哪臺(tái)服務(wù)器上，導(dǎo)致需要輪詢服務(wù)器來獲取數(shù)據(jù)，為了解決這個(gè)痛點(diǎn)便提出使用Hash算法。Hash算法的預(yù)熱數(shù)據(jù)的流程如下圖：

    將數(shù)據(jù)的key計(jì)算一個(gè)hash值，然后將這個(gè)hash值和服務(wù)器的臺(tái)數(shù)取模，取模之后的結(jié)果就決定當(dāng)前的數(shù)據(jù)存放在哪臺(tái)服務(wù)器上。獲取數(shù)據(jù)的流程如下：

    讀取數(shù)據(jù)的時(shí)候，將數(shù)據(jù)key同樣方式獲取hash值，然后將hash值與服務(wù)器的臺(tái)數(shù)取模來定位數(shù)據(jù)在哪臺(tái)服務(wù)器上。但是hash法也存在一個(gè)嚴(yán)重的缺陷，假設(shè)現(xiàn)在增加/減少服務(wù)器數(shù)據(jù)量，如下圖所示：

    我們繼續(xù)使用：hash（key）% 服務(wù)器數(shù)量，來定位數(shù)據(jù)在哪臺(tái)服務(wù)器就存在問題了，因?yàn)榉?wù)器數(shù)量變化導(dǎo)致原先數(shù)據(jù)定位不準(zhǔn)，如下所示：

    假設(shè)現(xiàn)在有大量的請(qǐng)求打進(jìn)來，由于命中緩存服務(wù)上沒有數(shù)據(jù)，請(qǐng)求都落到了資源服務(wù)器上，由于資源服務(wù)器瞬間壓力過大可能會(huì)導(dǎo)致服務(wù)崩潰。

    hash隨著服務(wù)器的數(shù)量變化（增加或減少），定位服務(wù)上的緩存的數(shù)據(jù)位置也會(huì)變動(dòng)，就會(huì)導(dǎo)致無法獲取數(shù)據(jù)的問題。為了解決這個(gè)問題便提出了一致性hash算法。

2、一致性hash和虛擬節(jié)點(diǎn)

    一致性hash算法是對(duì)2^32方取模，從0-2^32方計(jì)數(shù)形成一個(gè)圓環(huán)，我們稱這個(gè)圓環(huán)為hash環(huán)。

    通過hash(服務(wù)器的ip) % 2^32 = X；通過這個(gè)X值可以定位服務(wù)器在圓環(huán)上的位置。

    如何確定數(shù)據(jù)存放在哪個(gè)服務(wù)器上呢？如下圖所示：

    如上的數(shù)據(jù)A，我們可以使用hash(數(shù)據(jù)A) % 2^32 = LA；通過LA可以定位數(shù)據(jù)A在圓環(huán)上的位置，然后順時(shí)針方便找距離數(shù)據(jù)A最近的服務(wù)器，發(fā)現(xiàn)是服務(wù)器A，那么我們將數(shù)據(jù)A存放到服務(wù)器A上。同理數(shù)據(jù)B也是存放在服務(wù)器上A上。

    讀取數(shù)據(jù)也是同樣按照hash算法取模的方式來定位服務(wù)器，通過這樣的方式可以很快地定位數(shù)據(jù)在哪臺(tái)服務(wù)器上。如下所示：

    假設(shè)現(xiàn)在服務(wù)器C下線了，如下所示：

    此時(shí)數(shù)據(jù)A定位是沒有問題，數(shù)據(jù)C從原先的服務(wù)器C上定位到服務(wù)器A上，數(shù)據(jù)C是無法獲取到的。換句話講，雖然服務(wù)器C下線了，但是只是部分?jǐn)?shù)據(jù)異常，不會(huì)使得整個(gè)服務(wù)集群數(shù)據(jù)錯(cuò)亂，數(shù)據(jù)異常的部分如下所示：

    假設(shè)現(xiàn)在增加了一臺(tái)機(jī)器D，那么也只會(huì)導(dǎo)致部分?jǐn)?shù)據(jù)出現(xiàn)錯(cuò)亂，如下圖所示：

    此時(shí)我們只需要將錯(cuò)亂的這一部分?jǐn)?shù)據(jù)遷移到服務(wù)器D上可以實(shí)現(xiàn)數(shù)據(jù)的同步了。理想狀態(tài)下，一致性hash是很完美的，但是在極端的情況下由于離散型差的問題導(dǎo)致服務(wù)器都集中分布在一起，如下圖所示：

此時(shí)數(shù)據(jù)又剛好落在服務(wù)器C和服務(wù)器A之間的區(qū)域上，如下圖所示：

    這樣就導(dǎo)致所有的數(shù)據(jù)壓力都到了服務(wù)器A上，服務(wù)器B和服務(wù)器C就是一個(gè)擺設(shè)了作用了。如果服務(wù)器A掛了，那么整個(gè)緩存就失效了，這個(gè)就是hash環(huán)的傾斜問題。為了解決hash環(huán)傾斜問題，于是便引入了虛擬節(jié)點(diǎn)，也就是把真實(shí)的服務(wù)器通過虛擬化的方式復(fù)制一些節(jié)點(diǎn)出來成為虛擬虛擬節(jié)點(diǎn)。如下圖所示：

    通過虛擬節(jié)點(diǎn)的加入就不會(huì)導(dǎo)致所有的數(shù)據(jù)都到一臺(tái)機(jī)器中，同時(shí)虛擬節(jié)點(diǎn)越多，緩存數(shù)據(jù)越均勻。

總結(jié)：

（1）一致性hash常用于負(fù)載均衡、分布式緩存分區(qū)、數(shù)據(jù)庫分庫分表等場(chǎng)景。

（2）為防止服務(wù)器上的數(shù)據(jù)傾斜問題，通常增加虛擬節(jié)點(diǎn)的方式來讓數(shù)據(jù)更加均勻的分布在機(jī)器上。