1.前言

在"一文讓你徹底明白什麼是一致性哈希"該文中，我們已經瞭解到了什麼是一致性哈希及其的若干問題。還不瞭解的或者需要溫習的請戳以下鏈接進行回味。

原文鏈接：https://www.toutiao.com/i6685547708570141188/

文中最後留下了兩個小問題，最後的兩個小問題將在以下進行詳細美妙的回答。

2.問題回顧

問題1：hash函數是在大樣本的情況下才會均勻，如果現在機器比較少的情況下，hash後機器的位置分佈不均勻怎麼辦？

​

問題2：即使剛開始機器分佈很均勻，但是加機器後也會導致不均勻的情況。

​

如果問題不明白的話，還是請戳“一文讓你徹底明白什麼是一致性哈希”這篇文章。

原文鏈接:https://www.toutiao.com/i6685547708570141188/

3.解決方案

上述問題1提到，如果機器很少的話，他們經過hash之後落在環有可能形成不均勻的情況，會造成負載不均衡的情況，即:

因為hash函數必須在足夠大的樣本裡，hash之後的分佈才會顯得均勻，因此針對問題1，我們引入虛擬節點的概念

將m-1虛擬化m-1-1、m-1-2、m-1-3...... m-1-1000

m-2虛擬化m-2-1、m-2-2、m-2-3.....m-2-1000

m-3虛擬化m-3-1、m-3-2、m-3-3.....m-3-1000，

然後設置一張物理機和虛擬機的對應表，目的是為了找到可以通過物理機找到對應的虛擬機，通過虛擬機找到相對應的物理機，如下。

​

那這樣的話，通過每臺真實的物理機虛擬化後的節點，經過hash，映射到環上，注意，是虛擬節點去搶環上的點，又因為每臺物理機都有等量的虛擬節點，故它們在環上的分佈可以看作是

當數據來的時候，同樣是按照數據找到其在環上的位置，然後通過順時針法則找到離它最近的虛擬節點，然後將該數據存到該虛擬節點所對應的物理機上(通過虛擬節點-物理機對應表尋找)。

​

如圖，環上的節點均為虛擬節點，為簡單起見，假設每臺物理機只有3個虛擬節點，那當數據經過hash後映射到環上是上圖的位置時，順時針找到離它最近的m-1-1，然後通過“虛擬節點-物理機”映射表找到m-1-1對應的m-1物理機進行存儲。

4.加、減機器的數據遷移

同樣的，如果新增一臺m4機器，將它虛擬化成等量的虛擬節點，然後分佈在環上。簡單起見，每個物理機只有3個虛擬節點，實際上是虛擬化成很多很多的，例如上文提到的1000個虛擬節點。

​

所以，原本圖中綠色的數據屬於m-1中的m-1-1部分的，但是現在中間多了個m-4-1，因此，按順時針法則，灰色部分的數據從m-1上的m-1-1虛擬節點轉移到m-4上的m-4-1節點。同樣滿足虛擬節點均勻分佈(即說明每臺物理機都負載均衡)和數據遷移代價低的條件。

​

5.哈希衝突

哈希衝突問題，即兩個虛擬節點在環上發生衝突了，目前的解決方案是兩個虛擬節點分別對應的兩個真實物理機都存同樣一份數據。另外衝突的概率是很小的，是個小概率事件，比如環上的哈希值範圍為0~2^64，即環上總共可以有2^64個點，但是虛擬節點數目遠比這個總數要小，所以發生衝突的可能性比較低，因此可採用以上策略進行解決。

閱讀更多 強子小課堂 的文章

關鍵字: 虛擬機 最後 原文