一致性Hash(Consistent Hashing)原理剖析

     在業(yè)務(wù)開發(fā)中，我們常把數(shù)據(jù)持久化到數(shù)據(jù)庫中。如果需要讀取這些數(shù)據(jù)，除直接從數(shù)據(jù)庫中讀取外，為了減輕數(shù)據(jù)庫的訪問壓力和提高訪問速度，我們更多地引入緩存來對數(shù)據(jù)進行存取。讀取數(shù)據(jù)的進程1般為：

圖1：加入緩存的數(shù)據(jù)讀取進程

對散布式緩存，不同機器上存儲不同對象的數(shù)據(jù)。為了實現(xiàn)這些緩存機器的負載均衡，可使用式子1來定位對象緩存的存儲機器：

m = hash(o) mod n ——式子1

其中，o為對象的名稱，n為機器的數(shù)量，m為機器的編號，hash為1hash函數(shù)。圖2中的負載均衡器(load balancer)正是使用式子1來將客戶端對不同對象的要求分派到不同的機器上履行，例如，對對象o，經(jīng)過式子1的計算，得到m的值為3，那末所有對對象o的讀取和存儲的要求都被發(fā)往機器3履行。

圖2：如何利用Hash取模實現(xiàn)負載均衡

式子1在大部份時候都可以工作得很好，但是，當機器需要擴容或機器出現(xiàn)宕機的情況下，事情就比較辣手了。

當機器擴容，需要增加1臺緩存機器時，負載均衡器使用的式子變成：

m = hash(o) mod (n + 1) ——式子2

當機器宕機，機器數(shù)量減少1臺時，負載均衡器使用的式子變成：

m = hash(o) mod (n - 1) ——式子3

我們以機器擴容的情況為例，說明簡單的取模方法會致使甚么問題。假定機器由3臺變成4臺，對象o1由式子1計算得到的m值為2，由式子2計算得到的m值卻可能為0，1，2，3(1個 3t + 2的整數(shù)對4取模，其值可能為0，1，2，3，讀者可以自行驗證)，大約有75%(3/4)的可能性出現(xiàn)緩存訪問不命中的現(xiàn)象。隨著機器集群范圍的擴大，這個比例線性上升。當99臺機器再加入1臺機器時，不命中的幾率是99%(99/100)。這樣的結(jié)果明顯是不能接受的，由于這會致使數(shù)據(jù)庫訪問的壓力陡增，嚴重情況，還可能致使數(shù)據(jù)庫宕機。

1致性hash算法正是為了解決此類問題的方法，它可以保證當機器增加或減少時，對緩存訪問命中的幾率影響減至很小。下面我們來詳細說1下1致性hash算法的具體進程。

1致性Hash環(huán)

1致性hash算法通過1個叫作1致性hash環(huán)的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。這個環(huán)的出發(fā)點是0，終點是2^32 - 1，并且出發(fā)點與終點連接，環(huán)的中間的整數(shù)按逆時針散布，故這個環(huán)的整數(shù)散布范圍是[0, 2^32⑴]，以下圖3所示：

圖3：1致性Hash環(huán)

將對象放置到Hash環(huán)

假定現(xiàn)在我們有4個對象，分別為o1，o2，o3，o4，使用hash函數(shù)計算這4個對象的hash值(范圍為0 ~ 2^32⑴):

hash(o1) = m1

hash(o2) = m2

hash(o3) = m3

hash(o4) = m4

把m1，m2，m3，m4這4個值放置到hash環(huán)上，得到以下圖4：

圖4：放置了對象的1致性Hash環(huán)

將機器放置到Hash環(huán)

使用一樣的hash函數(shù)，我們將機器也放置到hash環(huán)上。假定我們有3臺緩存機器，分別為 c1，c2，c3，使用hash函數(shù)計算這3臺機器的hash值：

hash(c1) = t1

hash(c2) = t2

hash(c3) = t3

把t1，t2，t3 這3個值放置到hash環(huán)上，得到以下圖5：

圖5：放置了機器的1致性Hash環(huán)

為對象選擇機器

將對象和機器都放置到同1個hash環(huán)后，在hash環(huán)上順時針查找距離這個對象的hash值最近的機器，即是這個對象所屬的機器。

例如，對對象o2，順序針找到最近的機器是c1，故機器c1會緩存對象o2。而機器c2則緩存o3，o4，機器c3則緩存對象o1。

圖6：在1致性Hash環(huán)上為對象選擇機器

處理機器增減的情況

對線上的業(yè)務(wù)，增加或減少1臺機器的部署是常有的事情。

例如，增加機器c4的部署并將機器c4加入到hash環(huán)的機器c3與c2之間。這時候，只有機器c3與c4之間的對象需要重新分配新的機器。對我們的例子，只有對象o4被重新分配到了c4，其他對象仍在原有機器上。如圖7所示：

圖7：增加機器后的1致性Hash環(huán)的結(jié)構(gòu)

如上文前面所述，使用簡單的求模方法，當新添加機器后會致使大部份緩存失效的情況，使用1致性hash算法后這類情況則會得到大大的改良。前面提到3臺機器變成4臺機器后，緩存命中率只有25%(不命中率75%)。而使用1致性hash算法，理想情況下緩存命中率則有75%，而且，隨著機器范圍的增加，命中率會進1步提高，99臺機器增加1臺后，命中率到達99%，這大大減輕了增加緩存機器帶來的數(shù)據(jù)庫訪問的壓力。

再例如，將機器c1下線(固然，也有多是機器c1宕機)，這時候，只有原有被分配到機器c1對象需要被重新分配到新的機器。對我們的例子，只有對象o2被重新分配到機器c3，其他對象仍在原有機器上。如圖8所示：

圖8：減少機器后的1致性Hash環(huán)的結(jié)構(gòu)

虛擬節(jié)點

上面提到的進程基本上就是1致性hash的基本原理了，不過還有1個小小的問題。新加入的機器c4只分擔(dān)了機器c2的負載，機器c1與c3的負載并沒有由于機器c4的加入而減少負載壓力。如果4臺機器的性能是1樣的，那末這類結(jié)果其實不是我們想要的。

為此，我們引入虛擬節(jié)點來解決負載不均衡的問題。

將每臺物理機器虛擬為1組虛擬機器，將虛擬機器放置到hash環(huán)上，如果需要肯定對象的機器，先肯定對象的虛擬機器，再由虛擬機器肯定物理機器。

說得有點復(fù)雜，其實進程也很簡單。

還是使用上面的例子，假設(shè)開始時存在緩存機器c1，c2，c3，對每一個緩存機器，都有3個虛擬節(jié)點對應(yīng)，其1致性hash環(huán)結(jié)構(gòu)如圖9所示：

圖9：機器c1，c2，c3的1致性Hash環(huán)結(jié)構(gòu)

假定對對象o1，其對應(yīng)的虛擬節(jié)點為c11，而虛擬節(jié)點c11對象緩存機器c1，故對象o1被分配到機器c1中。

新加入緩存機器c4，其對應(yīng)的虛擬節(jié)點為c41，c42，c43，將這3個虛擬節(jié)點添加到hash環(huán)中，得到的hash環(huán)結(jié)構(gòu)如圖10所示：

圖10：機器c1，c2，c3，c4的1致性Hash環(huán)結(jié)構(gòu)

新加入的緩存機器c4對應(yīng)1組虛擬節(jié)點c41，c42，c43，加入到hash環(huán)后，影響的虛擬節(jié)點包括c31，c22，c11(順時針查找到第1個節(jié)點)，而這3個虛擬節(jié)點分別對應(yīng)機器c3，c2，c1。即新加入的1臺機器，同時影響到原本的3臺機器。理想情況下，新加入的機器同等地分擔(dān)了原有機器的負載，這正是虛擬節(jié)點帶來的好處。而且新加入機器c4后，只影響25%(1/4)對象分配，也就是說，命中率依然有75%，這跟沒有使用虛擬節(jié)點的1致性hash算法得到的結(jié)果是相同的。

總結(jié)

1致性hash算法解決了散布式環(huán)境下機器增加或減少時，簡單的取模運算沒法獲得較高命中率的問題。通過虛擬節(jié)點的使用，1致性hash算法可以均勻分擔(dān)機器的負載，使得這1算法更具現(xiàn)實的意義。正因如此，1致性hash算法被廣泛利用于散布式系統(tǒng)中。

參考資料

https://en.wikipedia.org/wiki/Consistent_hashing

https://www.codeproject.com/articles/56138/consistent-hashing

《大型網(wǎng)站技術(shù)架構(gòu)——核心原理與安全分析》，李智慧著，電子工業(yè)出版社

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈