一致性hash算法是什么？

一致性hash算法，是麻省理工學院1997年提出的一種算法，目前主要應用于分布式緩存當中。
一致性hash算法可以有效地解決分布式存儲結(jié)構(gòu)下動態(tài)增加和刪除節(jié)點所帶來的問題。
在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了一致性hash算法，可以說一致性hash算法是分布式系統(tǒng)負載均衡的首選算法。

傳統(tǒng)hash算法的弊端

常用的算法是對hash結(jié)果取余數(shù) (hash() mod N)：對機器編號從0到N-1，按照自定義的hash算法，對每個請求的hash值按N取模，得到余數(shù)i，然后將請求分發(fā)到編號為i的機器。但這樣的算法方法存在致命問題，如果某一臺機器宕機，那么應該落在該機器的請求就無法得到正確的處理，這時需要將宕掉的服務器使用算法去除，此時候會有(N-1)/N的服務器的緩存數(shù)據(jù)需要重新進行計算；如果新增一臺機器，會有N /(N 1)的服務器的緩存數(shù)據(jù)需要進行重新計算。對于系統(tǒng)而言，這通常是不可接受的顛簸（因為這意味著大量緩存的失效或者數(shù)據(jù)需要轉(zhuǎn)移）。

傳統(tǒng)求余做負載均衡算法，緩存節(jié)點數(shù)由3個變成4個，緩存不命中率為75%。計算方法：窮舉hash值為1-12的12個數(shù)字分別對3和4取模，然后比較發(fā)現(xiàn)只有前3個緩存節(jié)點對應結(jié)果和之前相同，所以有75%的節(jié)點緩存會失效，可能會引起緩存雪崩。

一致性hash算法

1. 首先，我們將hash算法的值域映射成一個具有2³² 次方個桶的空間中，即0~（2³²）-1的數(shù)字空間?，F(xiàn)在我們可以將這些數(shù)字頭尾相連，組合成一個閉合的環(huán)形。

2. 每一個緩存key都可以通過Hash算法轉(zhuǎn)化為一個32位的二進制數(shù)，也就對應著環(huán)形空間的某一個緩存區(qū)。我們把所有的緩存key映射到環(huán)形空間的不同位置。

3. 我們的每一個緩存節(jié)點也遵循同樣的Hash算法，比如利用IP或者主機名做Hash，映射到環(huán)形空間當中，如下圖

image

1. 如何讓key和緩存節(jié)點對應起來呢？很簡單，每一個key的順時針方向最近節(jié)點，就是key所歸屬的緩存節(jié)點。所以圖中key1存儲于node1，key2，key3存儲于node2，key4存儲于node3。

image

1. 當緩存的節(jié)點有增加或刪除的時候，一致性哈希的優(yōu)勢就顯現(xiàn)出來了。讓我們來看看實現(xiàn)的細節(jié)：

• 增加節(jié)點
  當緩存集群的節(jié)點有所增加的時候，整個環(huán)形空間的映射仍然會保持一致性哈希的順時針規(guī)則，所以有一小部分key的歸屬會受到影響。

image

有哪些key會受到影響呢？圖中加入了新節(jié)點node4，處于node1和node2之間，按照順時針規(guī)則，從node1到node4之間的緩存不再歸屬于node2，而是歸屬于新節(jié)點node4。因此受影響的key只有key2。

image

最終把key2的緩存數(shù)據(jù)從node2遷移到node4，就形成了新的符合一致性哈希規(guī)則的緩存結(jié)構(gòu)。

• 刪除節(jié)點
  當緩存集群的節(jié)點需要刪除的時候（比如節(jié)點掛掉），整個環(huán)形空間的映射同樣會保持一致性哈希的順時針規(guī)則，同樣有一小部分key的歸屬會受到影響。

image

有哪些key會受到影響呢？圖中刪除了原節(jié)點node3，按照順時針規(guī)則，原本node3所擁有的緩存數(shù)據(jù)就需要“托付”給node3的順時針后繼節(jié)點node1。因此受影響的key只有key4。

image

最終把key4的緩存數(shù)據(jù)從node3遷移到node1，就形成了新的符合一致性哈希規(guī)則的緩存結(jié)構(gòu)。

說明：這里所說的遷移并不是直接的數(shù)據(jù)遷移，而是在查找時去找順時針的后繼節(jié)點，因緩存未命中而刷新緩存。

計算方法：假設節(jié)點hash散列均勻（由于hash是散列表，所以并不是很理想），采用一致性hash算法，緩存節(jié)點從3個增加到4個時，會有0-33%的緩存失效，此外新增節(jié)點不會環(huán)節(jié)所有原有節(jié)點的壓力。

一致性hash算法的結(jié)果相比傳統(tǒng)hash求余算法已經(jīng)進步很多，但可不可以改進一下呢？或者如果出現(xiàn)分布不均勻的情況怎么辦？比如下圖這樣，按順時針規(guī)則，所有的key都歸屬于統(tǒng)一個節(jié)點。

image

一致性hash算法 虛擬節(jié)點

為了優(yōu)化這種節(jié)點太少而產(chǎn)生的不均衡情況。一致性哈希算法引入了虛擬節(jié)點的概念。
所謂虛擬節(jié)點，就是基于原來的物理節(jié)點映射出N個子節(jié)點，最后把所有的子節(jié)點映射到環(huán)形空間上。

image

虛擬節(jié)點越多，分布越均勻。使用一致性hash算法 虛擬節(jié)點這種情況下，緩存節(jié)點從3個變成4個，緩存失效率為25%，而且每個節(jié)點都平均的承擔了壓力。

一致性hash算法 虛擬節(jié)點的實現(xiàn)

原理理解了，實現(xiàn)并不難，主要是一些細節(jié)：

1. hash算法的選擇。Java代碼不要使用hashcode函數(shù)，這個函數(shù)結(jié)果不夠散列，而且會有負值需要處理。
   這種計算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默認的MemCache推薦的一致性Hash算法，用別的Hash算法也可以，比如FNV1_32_HASH算法的計算效率就會高一些。

2. 數(shù)據(jù)結(jié)構(gòu)的選擇。根據(jù)算法原理，我們的算法有幾個要求：

• 要能根據(jù)hash值排序存儲

• 排序存儲要被快速查找 （List不行）

• 排序查找還要能方便變更 （Array不行）

另外，由于二叉樹可能極度不平衡。所以采用紅黑樹是最穩(wěn)妥的實現(xiàn)方法。Java中直接使用TreeMap即可。