傳統(tǒng)哈希算法的局限性

在分布式系統(tǒng)中，通常使用多個節(jié)點來保存數(shù)據(jù)，以提高并發(fā)能力和容量，那么如果決定數(shù)據(jù)保存到哪個節(jié)點上呢？一般的做法是通過一個哈希函數(shù)對數(shù)據(jù)key進行計算，然后對節(jié)點數(shù)量取模，從而得到數(shù)據(jù)分配的節(jié)點：
node_id = hash(key) % N
但是這種做法在節(jié)點數(shù)量N變化的時候，大部分key的計算的節(jié)點都會重新分配。如果是應用在分布式緩存，就會導致大規(guī)模的緩存失效，引起緩存雪崩。

一致性哈希算法

原理

一致性哈希算法將哈?？臻g分配到哈希環(huán)的數(shù)據(jù)結(jié)構(gòu)上，取值范圍0~2^32-1，并且起點與終點相連。

1. 將服務器通過哈希函數(shù)（以IP或者主機名作為key）放置到環(huán)上
2. 對數(shù)據(jù)key使用相同的哈希函數(shù)，落到哈?？臻g上的某個點，如果該點不是服務器節(jié)點的位置，則順時針向前尋找，直到碰到第一個服務器節(jié)點，將數(shù)據(jù)分配到該節(jié)點。

新增節(jié)點

新增了節(jié)點S4，那么影響的只是哈?？臻gS3到S4之間的數(shù)據(jù)，如原來key4是分配到節(jié)點S1，現(xiàn)在分配到了S4。

下線節(jié)點

節(jié)點S2下線，只影響哈?？臻gS1到S2之間的數(shù)據(jù)，如原來key2分配到了S2，現(xiàn)在分配到了S3。

虛擬節(jié)點優(yōu)化

當服務節(jié)點比較少的時候會出現(xiàn)分配不平衡的問題，造成大量數(shù)據(jù)集中到一個節(jié)點上，如下圖所示：

大部分的哈?？臻g都會分配到S1上，少量分配到S2上。
為了解決這種數(shù)據(jù)傾斜問題，一致性哈希引入了虛擬節(jié)點機制：對每一個服務器節(jié)點計算多個哈希，每個計算結(jié)果都防止一個此服務器對應的虛擬節(jié)點。具體做法可以在服務器IP后面加上編號再計算哈希值。

特點

• 良好的伸縮性。一致性哈希算法保證了增加或減少服務器時，數(shù)據(jù)存儲的改變最少，比傳統(tǒng)的哈希算法大大節(jié)省了數(shù)據(jù)移動的開銷。
• 更好的適應數(shù)據(jù)增長。當數(shù)據(jù)不斷增長，部分虛擬節(jié)點可能包含很多數(shù)據(jù)，造成數(shù)據(jù)分配不平衡，此時可以將包含數(shù)據(jù)多的虛擬節(jié)點分裂，這種分裂僅僅是將原有的虛擬節(jié)點一分為二，不需要對全部數(shù)據(jù)重新哈希劃分。

參考

【1】 圖解一致性哈希算法
【2】一致性Hash算法詳解