本文轉載自微信公眾號「程序員內點事」，作者程序員內點事。轉載本文請聯系程序員內點事公眾號。

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

構建場景

假如我們有三臺緩存服務器編號node0、node1、node2，現在有3000萬個key，希望可以將這些個key均勻的緩存到三臺機器上，你會想到什么方案呢?

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

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算法又有什么關系嘞?我們還是以上邊的場景為例，三臺緩存服務器編號node0、node1、node2，3000萬個key。

服務器映射到hash環

這個時候計算公式就從hash(key)% N 變成了hash(服務器ip)% 2^32，使用服務器IP地址進行hash計算，用哈希后的結果對2^32取模，結果一定是一個0到2^32-1之間的整數，而這個整數映射在hash環上的位置代表了一個服務器，依次將node0、node1、node2三個緩存服務器映射到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-1和node-2之間，沿順時針方向對象映射節點，發現原本緩存在node-2上的對象key-4、key-5被重新映射到了node-4上，而整個擴容過程中受影響的只有node-4和node-1節點之間的一小部分數據。

反之，假如node-1節點宕機，沿順時針方向對象映射節點，緩存在node-1上的對象key-1被重新映射到了node-4上，此時受影響的數據只有node-0和node-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#1、node-1#2、node-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在分布式系統中應該是實現負載均衡的首選算法，它的實現比較靈活，既可以在客戶端實現，也可以在中間件上實現，比如日常使用較多的緩存中間件memcached和redis集群都有用到它。

memcached的集群比較特殊，嚴格來說它只能算是偽集群，因為它的服務器之間不能通信，請求的分發路由完全靠客戶端來的計算出緩存對象應該落在哪個服務器上，而它的路由算法用的就是一致性hash。

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

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

• RPC框架Dubbo用來選擇服務提供者
• 分布式關系數據庫分庫分表：數據與節點的映射關系
• LVS負載均衡調度器
• .....................

總結

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

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