一致性hash算法是什么？

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

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

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

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

一致性hash算法

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

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

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

image

1. 如何讓key和緩存節(jié)點(diǎn)對(duì)應(yīng)起來呢？很簡(jiǎn)單，每一個(gè)key的順時(shí)針方向最近節(jié)點(diǎn)，就是key所歸屬的緩存節(jié)點(diǎn)。所以圖中key1存儲(chǔ)于node1，key2，key3存儲(chǔ)于node2，key4存儲(chǔ)于node3。

image

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

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

image

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

image

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

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

image

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

image

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

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

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

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

image

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

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

image

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

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

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

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

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

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

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

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

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