一致性哈希算法
普通的哈希算法使用取余操作：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 虛擬出來的節點。通過添加虛擬節點之后，各個節點管理的數據已經比較均勻了。
