摸不熟一致性hash算法？勸你簡歷別寫搞過負載均衡
點擊關(guān)注公眾號，Java干貨及時送達
這兩天看到技術(shù)群里，有小伙伴在討論一致性hash算法的問題，正愁沒啥寫的題目就來了，那就簡單介紹下它的原理。下邊我們以分布式緩存中經(jīng)典場景舉例，面試中也是經(jīng)常提及的一些話題，看看什么是一致性hash算法以及它有那些過人之處。
構(gòu)建場景
假如我們有三臺緩存服務(wù)器編號node0、node1、node2，現(xiàn)在有3000萬個key，希望可以將這些個key均勻的緩存到三臺機器上，你會想到什么方案呢？
我們可能首先想到的方案，是取模算法hash（key）% N，對key進行hash運算后取模，N是機器的數(shù)量。key進行hash后的結(jié)果對3取模，得到的結(jié)果一定是0、1或者2，正好對應(yīng)服務(wù)器node0、node1、node2，存取數(shù)據(jù)直接找對應(yīng)的服務(wù)器即可，簡單粗暴，完全可以解決上述的問題。
hash的問題
取模算法雖然使用簡單，但對機器數(shù)量取模，在集群擴容和收縮時卻有一定的局限性，因為在生產(chǎn)環(huán)境中根據(jù)業(yè)務(wù)量的大小，調(diào)整服務(wù)器數(shù)量是常有的事；而服務(wù)器數(shù)量N發(fā)生變化后hash（key）% N計算的結(jié)果也會隨之變化。
比如：一個服務(wù)器節(jié)點掛了，計算公式從hash（key）% 3變成了hash（key）% 2，結(jié)果會發(fā)生變化，此時想要訪問一個key，這個key的緩存位置大概率會發(fā)生改變，那么之前緩存key的數(shù)據(jù)也會失去作用與意義。
大量緩存在同一時間失效，造成緩存的雪崩，進而導(dǎo)致整個緩存系統(tǒng)的不可用，這基本上是不能接受的，為了解決優(yōu)化上述情況，一致性hash算法應(yīng)運而生~
那么，一致性哈希算法又是如何解決上述問題的？
一致性hash
一致性hash算法本質(zhì)上也是一種取模算法，不過，不同于上邊按服務(wù)器數(shù)量取模，一致性hash是對固定值2^32取模。
“IPv4的地址是4組8位2進制數(shù)組成，所以用2^32可以保證每個IP地址會有唯一的映射
hash環(huán)
我們可以將這2^32個值抽象成一個圓環(huán)??（不得意圓的，自己想個形狀，好理解就行），圓環(huán)的正上方的點代表0，順時針排列，以此類推，1、2、3、4、5、6……直到2^32-1，而這個由2的32次方個點組成的圓環(huán)統(tǒng)稱為hash環(huán)。
那么這個hash環(huán)和一致性hash算法又有什么關(guān)系嘞？我們還是以上邊的場景為例，三臺緩存服務(wù)器編號node0、node1、node2，3000萬個key。
服務(wù)器映射到hash環(huán)
這個時候計算公式就從hash（key）% N 變成了hash（服務(wù)器ip）% 2^32，使用服務(wù)器IP地址進行hash計算，用哈希后的結(jié)果對2^32取模，結(jié)果一定是一個0到2^32-1之間的整數(shù)，而這個整數(shù)映射在hash環(huán)上的位置代表了一個服務(wù)器，依次將node0、node1、node2三個緩存服務(wù)器映射到hash環(huán)上。
對象key映射到hash環(huán)
接著在將需要緩存的key對象也映射到hash環(huán)上，hash（key）% 2^32，服務(wù)器節(jié)點和要緩存的key對象都映射到了hash環(huán)，那對象key具體應(yīng)該緩存到哪個服務(wù)器上呢？
對象key映射到服務(wù)器
“從緩存對象key的位置開始，沿順時針方向遇到的第一個服務(wù)器，便是當前對象將要緩存到的服務(wù)器。
因為被緩存對象與服務(wù)器hash后的值是固定的，所以，在服務(wù)器不變的條件下，對象key必定會被緩存到固定的服務(wù)器上。根據(jù)上邊的規(guī)則，下圖中的映射關(guān)系：
key-1 -> node-1key-3 -> node-2key-4 -> node-2key-5 -> node-2key-2 -> node-0
如果想要訪問某個key，只要使用相同的計算方式，即可得知這個key被緩存在哪個服務(wù)器上了。
一致性hash的優(yōu)勢
我們簡單了解了一致性hash的原理，那它又是如何優(yōu)化集群中添加節(jié)點和縮減節(jié)點，普通取模算法導(dǎo)致的緩存服務(wù)，大面積不可用的問題呢？
先來看看擴容的場景，假如業(yè)務(wù)量激增，系統(tǒng)需要進行擴容增加一臺服務(wù)器node-4，剛好node-4被映射到node-1和node-2之間，沿順時針方向?qū)ο笥成涔?jié)點，發(fā)現(xiàn)原本緩存在node-2上的對象key-4、key-5被重新映射到了node-4上，而整個擴容過程中受影響的只有node-4和node-1節(jié)點之間的一小部分數(shù)據(jù)。
反之，假如node-1節(jié)點宕機，沿順時針方向?qū)ο笥成涔?jié)點，緩存在node-1上的對象key-1被重新映射到了node-4上，此時受影響的數(shù)據(jù)只有node-0和node-1之間的一小部分數(shù)據(jù)。
從上邊的兩種情況發(fā)現(xiàn)，當集群中服務(wù)器的數(shù)量發(fā)生改變時，一致性hash算只會影響少部分的數(shù)據(jù)，保證了緩存系統(tǒng)整體還可以對外提供服務(wù)的。
數(shù)據(jù)偏斜問題
前邊為了便于理解原理，畫圖中的node節(jié)點都很理想化的相對均勻分布，但理想和實際的場景往往差別很大，就比如辦了個健身年卡的我，只去過健身房兩次，還只是洗了個澡。
在服務(wù)器節(jié)點數(shù)量太少的情況下，很容易因為節(jié)點分布不均勻而造成數(shù)據(jù)傾斜問題，如下圖被緩存的對象大部分緩存在node-4服務(wù)器上，導(dǎo)致其他節(jié)點資源浪費，系統(tǒng)壓力大部分集中在node-4節(jié)點上，這樣的集群是非常不健康的。
解決數(shù)據(jù)傾斜的辦法也簡單，我們就要想辦法讓節(jié)點映射到hash環(huán)上時，相對分布均勻一點。
一致性Hash算法引入了一個虛擬節(jié)點機制，即對每個服務(wù)器節(jié)點計算出多個hash值，它們都會映射到hash環(huán)上，映射到這些虛擬節(jié)點的對象key，最終會緩存在真實的節(jié)點上。
虛擬節(jié)點的hash計算通常可以采用，對應(yīng)節(jié)點的IP地址加數(shù)字編號后綴 hash（10.24.23.227#1) 的方式，舉個例子，node-1節(jié)點IP為10.24.23.227，正常計算node-1的hash值。
hash（10.24.23.227#1）% 2^32
假設(shè)我們給node-1設(shè)置三個虛擬節(jié)點，node-1#1、node-1#2、node-1#3，對它們進行hash后取模。
hash（10.24.23.227#1）% 2^32hash（10.24.23.227#2）% 2^32hash（10.24.23.227#3）% 2^32
下圖加入虛擬節(jié)點后，原有節(jié)點在hash環(huán)上分布的就相對均勻了，其余節(jié)點壓力得到了分攤。
“但需要注意一點，分配的虛擬節(jié)點個數(shù)越多，映射在hash環(huán)上才會越趨于均勻，節(jié)點太少的話很難看出效果
引入虛擬節(jié)點的同時也增加了新的問題，要做虛擬節(jié)點和真實節(jié)點間的映射，對象key->虛擬節(jié)點->實際節(jié)點之間的轉(zhuǎn)換。
一致性hash的應(yīng)用場景
一致性hash在分布式系統(tǒng)中應(yīng)該是實現(xiàn)負載均衡的首選算法，它的實現(xiàn)比較靈活，既可以在客戶端實現(xiàn)，也可以在中間件上實現(xiàn)，比如日常使用較多的緩存中間件memcached和redis集群都有用到它。
memcached的集群比較特殊，嚴格來說它只能算是偽集群，因為它的服務(wù)器之間不能通信，請求的分發(fā)路由完全靠客戶端來的計算出緩存對象應(yīng)該落在哪個服務(wù)器上，而它的路由算法用的就是一致性hash。
還有redis集群中hash槽的概念，雖然實現(xiàn)不盡相同，但思想萬變不離其宗，看完本篇的一致性hash，你再去理解redis槽位就輕松多了。
其它的應(yīng)用場景還有很多：
RPC框架Dubbo用來選擇服務(wù)提供者分布式關(guān)系數(shù)據(jù)庫分庫分表：數(shù)據(jù)與節(jié)點的映射關(guān)系 LVS負載均衡調(diào)度器.....................
總結(jié)
簡單的闡述了下一致性hash，如果有不對的地方大家可以留言指正，任何技術(shù)都不會十全十美，一致性Hash算法也是有一些潛在隱患的，如果Hash環(huán)上的節(jié)點數(shù)量非常龐大或者更新頻繁時，檢索性能會比較低下，而且整個分布式緩存需要一個路由服務(wù)來做負載均衡，一旦路由服務(wù)掛了，整個緩存也就不可用了，還要考慮做高可用。
?
往 期 推 薦
4、Windows重要功能被閹割，全球用戶怒噴數(shù)月后微軟終于悔改
點分享
點收藏
點點贊
點在看
