不會一致性hash演算法,勸你簡歷別寫搞過負載均衡

語言: CN / TW / HK

大家好,我是小富~

個人公眾號:程式設計師內點事,歡迎學習交流

這兩天看到技術群裡,有小夥伴在討論一致性hash演算法的問題,正愁沒啥寫的題目就來了,那就簡單介紹下它的原理。下邊我們以分散式快取中經典場景舉例,面試中也是經常提及的一些話題,看看什麼是一致性hash演算法以及它有那些過人之處。

構建場景

假如我們有三臺快取伺服器編號node0node1node2,現在有3000萬個key,希望可以將這些個key均勻的快取到三臺機器上,你會想到什麼方案呢?

我們可能首先想到的方案,是取模演算法hash(key)% N,對key進行hash運算後取模,N是機器的數量。key進行hash後的結果對3取模,得到的結果一定是0、1或者2,正好對應伺服器node0node1node2,存取資料直接找對應的伺服器即可,簡單粗暴,完全可以解決上述的問題。

hash的問題

取模演算法雖然使用簡單,但對機器數量取模,在叢集擴容和收縮時卻有一定的侷限性,因為在生產環境中根據業務量的大小,調整伺服器數量是常有的事;而伺服器數量N發生變化後hash(key)% N計算的結果也會隨之變化。

比如:一個伺服器節點掛了,計算公式從hash(key)% 3變成了hash(key)% 2,結果會發生變化,此時想要訪問一個key,這個key的快取位置大概率會發生改變,那麼之前快取key的資料也會失去作用與意義。

大量快取在同一時間失效,造成快取的雪崩,進而導致整個快取系統的不可用,這基本上是不能接受的,為了解決優化上述情況,一致性hash演算法應運而生~

那麼,一致性雜湊演算法又是如何解決上述問題的?

一致性hash

一致性hash演算法本質上也是一種取模演算法,不過,不同於上邊按伺服器數量取模,一致性hash是對固定值2^32取模。

IPv4的地址是4組8位2進位制陣列成,所以用2^32可以保證每個IP地址會有唯一的對映

hash環

我們可以將這2^32個值抽象成一個圓環⭕️(不得意圓的,自己想個形狀,好理解就行),圓環的正上方的點代表0,順時針排列,以此類推,1、2、3、4、5、6……直到2^32-1,而這個由2的32次方個點組成的圓環統稱為hash環

那麼這個hash環和一致性hash演算法又有什麼關係嘞?我們還是以上邊的場景為例,三臺快取伺服器編號node0node1node2,3000萬個key

伺服器對映到hash環

這個時候計算公式就從hash(key)% N 變成了hash(伺服器ip)% 2^32,使用伺服器IP地址進行hash計算,用雜湊後的結果對2^32取模,結果一定是一個0到2^32-1之間的整數,而這個整數對映在hash環上的位置代表了一個伺服器,依次將node0node1node2三個快取伺服器對映到hash環上。

物件key對映到hash環

接著在將需要快取的key物件也對映到hash環上,hash(key)% 2^32,伺服器節點和要快取的key物件都對映到了hash環,那物件key具體應該快取到哪個伺服器上呢?

物件key對映到伺服器

從快取物件key的位置開始,沿順時針方向遇到的第一個伺服器,便是當前物件將要快取到的伺服器

因為被快取物件與伺服器hash後的值是固定的,所以,在伺服器不變的條件下,物件key必定會被快取到固定的伺服器上。根據上邊的規則,下圖中的對映關係:

  • key-1 -> node-1
  • key-3 -> node-2
  • key-4 -> node-2
  • key-5 -> node-2
  • key-2 -> node-0

如果想要訪問某個key,只要使用相同的計算方式,即可得知這個key被快取在哪個伺服器上了。

一致性hash的優勢

我們簡單瞭解了一致性hash的原理,那它又是如何優化叢集中新增節點和縮減節點,普通取模演算法導致的快取服務,大面積不可用的問題呢?

先來看看擴容的場景,假如業務量激增,系統需要進行擴容增加一臺伺服器node-4,剛好node-4被對映到node-1node-2之間,沿順時針方向物件對映節點,發現原本快取在node-2上的物件key-4key-5被重新對映到了node-4上,而整個擴容過程中受影響的只有node-4node-1節點之間的一小部分資料。

反之,假如node-1節點宕機,沿順時針方向物件對映節點,快取在node-1上的物件key-1被重新對映到了node-4上,此時受影響的資料只有node-0node-1之間的一小部分資料。

從上邊的兩種情況發現,當叢集中伺服器的數量發生改變時,一致性hash算只會影響少部分的資料,保證了快取系統整體還可以對外提供服務的。

資料偏斜問題

前邊為了便於理解原理,畫圖中的node節點都很理想化的相對均勻分佈,但理想和實際的場景往往差別很大,就比如辦了個健身年卡的我,只去過健身房兩次,還只是洗了個澡。

想要健身的你

在伺服器節點數量太少的情況下,很容易因為節點分佈不均勻而造成資料傾斜問題,如下圖被快取的物件大部分快取在node-4伺服器上,導致其他節點資源浪費,系統壓力大部分集中在node-4節點上,這樣的叢集是非常不健康的。

解決資料傾斜的辦法也簡單,我們就要想辦法讓節點對映到hash環上時,相對分佈均勻一點。

一致性Hash演算法引入了一個虛擬節點機制,即對每個伺服器節點計算出多個hash值,它們都會對映到hash環上,對映到這些虛擬節點的物件key,最終會快取在真實的節點上。

虛擬節點的hash計算通常可以採用,對應節點的IP地址加數字編號字尾 hash(10.24.23.227#1) 的方式,舉個例子,node-1節點IP為10.24.23.227,正常計算node-1的hash值。

  • hash(10.24.23.227#1)% 2^32

假設我們給node-1設定三個虛擬節點,node-1#1node-1#2node-1#3,對它們進行hash後取模。

  • hash(10.24.23.227#1)% 2^32
  • hash(10.24.23.227#2)% 2^32
  • hash(10.24.23.227#3)% 2^32

下圖加入虛擬節點後,原有節點在hash環上分佈的就相對均勻了,其餘節點壓力得到了分攤。

但需要注意一點,分配的虛擬節點個數越多,對映在hash環上才會越趨於均勻,節點太少的話很難看出效果

引入虛擬節點的同時也增加了新的問題,要做虛擬節點和真實節點間的對映,物件key->虛擬節點->實際節點之間的轉換。

一致性hash的應用場景

一致性hash在分散式系統中應該是實現負載均衡的首選演算法,它的實現比較靈活,既可以在客戶端實現,也可以在中介軟體上實現,比如日常使用較多的快取中介軟體memcachedredis叢集都有用到它。

memcached的叢集比較特殊,嚴格來說它只能算是偽叢集,因為它的伺服器之間不能通訊,請求的分發路由完全靠客戶端來的計算出快取物件應該落在哪個伺服器上,而它的路由演算法用的就是一致性hash。

還有redis叢集中hash槽的概念,雖然實現不盡相同,但思想萬變不離其宗,看完本篇的一致性hash,你再去理解redis槽位就輕鬆多了。

其它的應用場景還有很多:

  • RPC框架Dubbo用來選擇服務提供者
  • 分散式關係資料庫分庫分表:資料與節點的對映關係
  • LVS負載均衡排程器
  • .....................

總結

簡單的闡述了下一致性hash,如果有不對的地方大家可以留言指正,任何技術都不會十全十美,一致性Hash演算法也是有一些潛在隱患的,如果Hash環上的節點數量非常龐大或者更新頻繁時,檢索效能會比較低下,而且整個分散式快取需要一個路由服務來做負載均衡,一旦路由服務掛了,整個快取也就不可用了,還要考慮做高可用。

不過話說回來,只要是能解決問題的都是好技術,有點副作用還是可以忍受的。