未完待續(xù)

一、引出

假設(shè)有 100W 的數(shù)據(jù)，100 個存儲節(jié)點，如何分配呢？
通常的方法是哈希，數(shù)據(jù)存儲到第 個節(jié)點上。
可是，當新增或刪除節(jié)點時，需要對所有的數(shù)據(jù)重新映射，可能發(fā)生大規(guī)模的數(shù)據(jù)遷移。這對于分布式系統(tǒng)而言，是一個很嚴重的問題。

一致性哈希算法就是為了解決這個問題產(chǎn)生的，即『當slot數(shù)發(fā)生變化時，能夠盡量少的移動數(shù)據(jù)』

維基百科：一致哈希是一種特殊的哈希算法。在使用一致哈希算法后，哈希表槽位數(shù)（大?。┑母淖兤骄恍枰獙?K/n個關(guān)鍵字重新映射，其中K是關(guān)鍵字的數(shù)量， n是槽位數(shù)量。然而在傳統(tǒng)的哈希表中，添加或刪除一個槽位的幾乎需要對所有關(guān)鍵字進行重新映射。

二、實現(xiàn)

基本實現(xiàn)

實現(xiàn)原理：
1）將 0~最大正整數(shù)形成一個環(huán)
2）計算每個節(jié)點的哈希值，即 hash(node)，并落入環(huán)上某個位置
3）計算數(shù)據(jù)的哈希值，即 hash(key)，并落入環(huán)上某個位置。
4）數(shù)據(jù)在環(huán)上的位置順時針找離它最近的節(jié)點，作為該數(shù)據(jù)的存儲節(jié)點

可理解成：每個節(jié)點負責某個范圍內(nèi)的哈希值的數(shù)據(jù)。比如，當哈希值在 [hash(node1), hash(node2)] 內(nèi)的數(shù)據(jù)，落入 node2。

當節(jié)點變化，僅影響該節(jié)點順時針方向的下一個節(jié)點，具體情況如下：

• 當刪除一個節(jié)點時，該節(jié)點上的數(shù)據(jù)遷移到該節(jié)點順時針方向的下一節(jié)點上
• 當新增一個節(jié)點時，該節(jié)點順時針方向的下一節(jié)點部分數(shù)據(jù)遷移到該節(jié)點上。

改進一：加入虛擬節(jié)點

目的：為了使得每個節(jié)點的負載盡量均衡

參考文獻

[1] 一致性Hash原理_憧憬的專欄-CSDN博客
[2] 一致性哈希算法的理解與實踐 | Yikun
[3] 一致性hash算法及java實現(xiàn)Java青魚入云的博客-CSDN博客