一、引出

假設有 100W 的數(shù)據(jù)儡毕，100 個存儲節(jié)點也切，如何分配呢？
通常的方法是哈希腰湾，數(shù)據(jù)存儲到第 $hash(key)\%100$ 個節(jié)點上雷恃。
可是，當新增或刪除節(jié)點時费坊，需要對所有的數(shù)據(jù)重新映射倒槐，可能發(fā)生大規(guī)模的數(shù)據(jù)遷移。這對于分布式系統(tǒng)而言附井，是一個很嚴重的問題讨越。

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

維基百科：一致哈希是一種特殊的哈希算法把跨。在使用一致哈希算法后，哈希表槽位數(shù)（大芯淼瘛）的改變平均只需要對 K/n個關鍵字重新映射节猿，其中K是關鍵字的數(shù)量， n是槽位數(shù)量漫雕。然而在傳統(tǒng)的哈希表中，添加或刪除一個槽位的幾乎需要對所有關鍵字進行重新映射峰鄙。

二浸间、實現(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é)點負責某個范圍內的哈希值的數(shù)據(jù)。比如狭瞎，當哈希值在 [hash(node1), hash(node2)] 內的數(shù)據(jù)细移，落入 node2。

$插圖（構建環(huán)）熊锭，參考文獻[1][3]$

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

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

$插圖（刪除/新增節(jié)點），參考文獻[1][3]$

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

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

參考文獻

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

最后編輯于：2020.09.12 10:44:39

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者