JAVA面試又被問一致性hash算法？

我來給大家講講一致性hash算法，如果有理解錯誤的地方，也請大家留言指正。

單臺服務(wù)器

就拿Redis來舉例吧，我們經(jīng)常會用Redis做緩存，把一些數(shù)據(jù)放在上面，以減少數(shù)據(jù)的壓力。

當(dāng)數(shù)據(jù)量少，訪問壓力不大的時候，通常一臺Redis就能搞定，為了高可用，弄個主從也就足夠了；

多臺服務(wù)器數(shù)據(jù)分布的問題

當(dāng)數(shù)據(jù)量變大，并發(fā)量也增加的時候，把全部的緩存數(shù)據(jù)放在一臺機器上就有些吃力了，畢竟一臺機器的資源是有限的，通常我們會搭建集群環(huán)境，讓數(shù)據(jù)盡量平均的放到每一臺Redis中，比如我們的集群中有三臺Redis。

那么如何把數(shù)據(jù)盡量平均地放到這三臺Redis中呢？最簡單的就是求余算法：hash(key)%N，在這里N=3。

看起來非常地美好，因為依靠這樣的方法，我們可以讓數(shù)據(jù)平均存儲到三臺Redis中，當(dāng)有新的請求過來的時候，我們也可以定位數(shù)據(jù)會在哪臺Redis中，這樣可以精確地查詢到緩存數(shù)據(jù)。

但是注意了，如果要增加一臺Redis，或者三臺中的一臺Redis發(fā)生了故障變成了兩臺，那么這個求余算法就會變成：hash(key)%4或者hash(key)%2；那么可以想象一下，當(dāng)前大部分緩存的位置都會是錯誤的，極端情況下，所有的緩存的位置都要發(fā)生改變，這樣會造成【緩存雪崩】。

一致性hash算法

一致性hash算法可以很好地解決這個問題，它的大概過程是：

把0作為起點，2^32-1作為終點，畫一條直線，再把起點和終點重合，直線變成一個圓，方向是順時針從小到大。0的右側(cè)第一個點是1，然后是2，以此類推。

對三臺服務(wù)器的IP或其他關(guān)鍵字進行hash后對2^32取模，這樣勢必能落在這個圈上的某個位置，記為Node1、Node2、Node3（圖1）。

然后對數(shù)據(jù)key進行相同的操作，勢必也會落在圈上的某個位置；然后順時針行走，可以找到某一個Node，這就是這個key要儲存的服務(wù)器（圖2）。

如果增加一臺服務(wù)器或者刪除一臺服務(wù)器，只會影響部分小部分數(shù)據(jù)（圖3）。

如果節(jié)點太少或分布不均勻的時候，容易造成數(shù)據(jù)傾斜，也就是被數(shù)據(jù)會集中在某一臺服務(wù)器上（圖4）。

為了解決數(shù)據(jù)傾斜問題，一致性Hash算法提出了【虛擬節(jié)點】，會對每一個服務(wù)節(jié)點計算多個哈希，然后放到圈上的不同位置（圖5）。

原諒我的小學(xué)生字體，下一次我一定好好地畫一畫圖，電腦上畫的那種。

我將持續(xù)分享Java開發(fā)、架構(gòu)設(shè)計、程序員職業(yè)發(fā)展等方面的見解，希望能得到你的關(guān)注。