一緻性哈希算法

普通的哈希算法使用取餘操作：hash(o) mod n，其中 n 代表機器的數量。如果在集群中新增加一個節點時，計算公式會變為：hash(o) mod (n 1)；在集群中删除一個機器時，計算公式變為：hash(o) mod (n-1)。所以當集群中機器數量有所變化時，幾乎所有的 Object 的哈希值都會改變。一緻性哈希可以保證當從集群中删除一台機器時，僅僅保存在該機器上的 Object 的值會變化；當集群中增加一台機器時，也僅僅是非常小的一部分 Object 的哈希值會發生改變。

一緻性哈希算法的實現原理其實很簡單，它也是使用取模的方式，隻是剛才描述的取模法是對機器的數量進行取模，而一緻性哈希算法是對2^32取模，hash(o) mod 2^32 什麼意思呢？我們慢慢聊。

其将整個哈希值空間組織成一個虛拟的圓環，比如某哈希函數H的值空間為0-2^32-1（即哈希值是一個32位無符号整形），那麼整個哈希空間環看起來就像下圖所示：

将機器映射到環中

一緻性哈希算法是數據分布的方式，而數據最終是需要存到機器中的，所以我們首先需要将機器映射到環中。假設我們有四台機器 Node1、Node2、Node3 以及 Node4，我們使用機器名或者 ip 計算這些機器的哈希值，然後分别映射到環中去，看起來就像下面一樣：

将數據映射到環中

我們使用相同的哈希函數計算需要存儲數據的哈希值，假設現在我們有四份數據 data1、data2、data3 以及 data4，我們需要将這些數據映射到環中去，這樣看起來像下面圖一樣：

在這個哈希環中，數據存儲的機器是按照順時針方向遇到的第一個節點就是這個數據存儲的節點，所以圖中：

• 數據 data2 存儲在節點 Node1 上；
• 數據 data3 存儲在節點 Node4 上；
• 數據 data1 存儲在節點 Node2 上；
• 數據 data4 存儲在節點 Node3 上。

添加節點在分布式環境中，添加或減少節點是很常見的操作。現在我們往上面的哈希環添加一個節點 Node5，同樣使用相同的哈希函數計算這個節點在哈希環的位置，假設計算的結果如下：

添加節點 Node5 之後，原本存儲在 Node4 上的數據 data3 就轉移到 Node5 了，其他數據分配不變。相比于普通的哈希添加節點會導緻大量映射失效，一緻性哈希可以很好的處理這種情況。如果增加一台服務器，則受影響的數據僅僅是新服務器到其環空間中前一台服務器（即沿着逆時針方向行走遇到的第一台服務器）之間數據，其它數據也不會受到影響。

删除節點

如果哈希環中有節點出現故障，需要從哈希空間中移除，那麼影響的數據也是有限的。假設節點 Node1 出現故障需要移除，新的哈希空間的數據映射如下：

Node1 節點移走之後，數據 data2 就轉移到 Node4 節點上了。所以如果從環中删除節點，受影響的數據僅僅是此服務器到其環空間中前一台服務器（即沿着逆時針方向行走遇到的第一台服務器）之間數據，其它不會受到影響。

虛拟節點

上述最基本的一緻性哈希算法有很明顯缺點，随機分布方式使得難均勻的分布哈希值域；尤其在動态增加節點後，即使原先的分布均勻也很難保證繼續均勻 即hash環的偏斜。由此帶來另一個較為嚴重的缺點，當一個節異常時，該節點的壓力全部轉移到相鄰的一個節點，當加入一個新節點時，隻能為一個相鄰節點分攤壓力。

為此一個改進方法是引入虛拟節點（virtual node），虛拟節點是實際節點在哈希空間的複制品（ replica ），一實際個節點（機器）對應了若幹個虛拟節點，這個對應個數也成為複制個數，虛拟節點在哈希空間中以哈希值排列。

為了表述方便，假設我們有2個節點，4份數據，在引入虛拟節點之前節點和數據分布如下：

可以看見節點 Node2 管理的數據有 data1、data3 和 data4；而節點 Node1 僅僅隻管理數據 data2。這就造成了數據分布不均勻的情況。如果我們通過引入虛拟節點，并且假定複制個數為3，則哈希之後的情況如下：

其中 Node1_1、Node1_2 和 Node1_3 是 Node1 虛拟出來的節點；同理Node2_1、Node2_2 和 Node2_3 是 Node2 虛拟出來的節點。通過添加虛拟節點之後，各個節點管理的數據已經比較均勻了。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!