一致性Hash介紹及使用場景

一、概述
當(dāng)單個節(jié)點（緩存服務(wù)器等）的能力達到上限，一般需要增加節(jié)點來打破瓶頸。在分布式系統(tǒng)中，擴容縮容操作極為常見。為了保證數(shù)據(jù)的均勻，一般情況會采用對key值hash，然后取模的方式，然后根據(jù)結(jié)果，確認(rèn)數(shù)據(jù)落到哪臺節(jié)點上。如：hash(key)%N，這的確實現(xiàn)了初步的分布式，數(shù)據(jù)均勻分散到了各個節(jié)點上，流量請求也均勻的分散到了各個節(jié)點；但出現(xiàn)以下情況：

某臺服務(wù)器突然宕機。服務(wù)器從N變?yōu)镹-1臺。

容量達到上限或者請求處理達到上限，需要增加服務(wù)器，假定增加1臺，則服務(wù)器從N變?yōu)镹+1

上面的情況帶來的問題：增加或者刪除服務(wù)器的時候，意味著大部分的數(shù)據(jù)都會失效。這個是比較致命的一點。如果頻繁進行重Hash操作顯然是不可取的，一是消耗太大，而是可能引發(fā)服務(wù)的中斷。

所以，增刪機器時，希望大部分key依舊在原有的服務(wù)器上保持不變。

這就需要一致性hash算法。

二、一致性hash
一致性Hash算法（Consistent Hashing）是一種hash算法，它能夠在Hash輸出空間發(fā)生變化時，引起最小的變動。以我們的例子來講，增加或者移除一臺服務(wù)器時，對原有的服務(wù)器和用戶之間的映射關(guān)系產(chǎn)生的影響最小。

好的一致性Hash算法應(yīng)該能夠滿足以下要求：

平衡性：這是Hash算法的基本要求，是指哈希的結(jié)果均勻地分配在整個輸出空間中。

單調(diào)性：當(dāng)發(fā)生數(shù)據(jù)節(jié)點變動時，對于相同的數(shù)據(jù)始終映射到相同的緩沖節(jié)點中或者新增加的緩沖節(jié)點中，避免無法找到原來的數(shù)據(jù)。

穩(wěn)定性：當(dāng)出現(xiàn)節(jié)點壞掉或熱點訪問而需要動態(tài)擴容時，盡量減少數(shù)據(jù)的移動。顯然一般的Hash方法不滿足這一點。

2.1 一致性hash
一致性哈希將整個哈希輸出空間設(shè)置為一個環(huán)形區(qū)域，將整個哈希值空間組織成一個虛擬的圓環(huán)。而且這個哈希值空間的大小為 [0, 2^32-1]。

服務(wù)器分布在環(huán)形的固定點上。

key經(jīng)過計算，也映射到環(huán)形上。

順時針尋找下一個節(jié)點。

假設(shè)我們有3臺服務(wù)器，把服務(wù)器通過hash算法，加入到上述的環(huán)中。一般情況下是根據(jù)機器的IP地址或者唯一的計算機別名進行哈希。

c1=hash(cache1) %  2^32;
c2=hash(cache2) %  2^32;
c3=hash(cache3) %  2^32;
假設(shè)我們現(xiàn)在有key1,key2,key3,key4 4個key值，我們通過一定的hash算法，將其對應(yīng)到上面的環(huán)形hash空間中。

k1=hash(key1) %  2^32;
k2=hash(key2) %  2^32;
k3=hash(key3) %  2^32;
k4=hash(key4) %  2^32;


一致性hash的尋址方案如下：








2.2 為什么要取模2^32
一致性hash算法是允許對任意一個數(shù)字取模的。但是，如果數(shù)字太小，擴容時服務(wù)器數(shù)量大于該數(shù)字，就會存在環(huán)空間節(jié)點重復(fù)。所以一般選擇一個固定大的數(shù)來取模運算（2^32=4294947297（最大的非符號整形數(shù)，也是ip地址的數(shù)值空間））。

2.3 為什么需要想象成環(huán)形
只有環(huán)形可以覆蓋所有hash值，不然就必須在首或者尾存在節(jié)點。

從0-2^32，不用環(huán)形，如果2^32-1上沒有節(jié)點，那2^32-1這個數(shù)據(jù)就沒地方存放。

從2^32-0，不用環(huán)形，如果0上沒有節(jié)點，那0這個數(shù)據(jù)就沒地方存放。

用環(huán)形，首尾沒有節(jié)點，也可以找到下一個。

2.4 虛擬節(jié)點
上面的簡單的一致性hash的方案在某些情況下但依舊存在問題：一個節(jié)點宕機之后，數(shù)據(jù)需要落到距離他最近的節(jié)點上，會導(dǎo)致下個節(jié)點的壓力突然增大，可能導(dǎo)致雪崩，整個服務(wù)掛掉。

可以用虛擬節(jié)點解決，用實際節(jié)點虛擬復(fù)制而來的節(jié)點被稱為”虛擬節(jié)點”，將虛擬節(jié)點分散在環(huán)上，并映射到實際節(jié)點上。

這個就解決之前的問題，某個節(jié)點宕機之后，存儲及流量壓力并沒有全部轉(zhuǎn)移到某臺機器上，而是分散到了多臺節(jié)點上。解決了節(jié)點宕機可能存在的雪崩問題。當(dāng)物理節(jié)點多的時候，虛擬節(jié)點多，這個的雪崩可能就越小。







作者：碼農(nóng)編程進階筆記

歡迎關(guān)注微信公眾號 ：碼農(nóng)編程進階筆記