其實不光光是Java面試，其它程式語言的面試過程中往往也會問及一致性Hash演算法問題，不少開發者可能聽說過“一致性Hash”這個術語，但卻不瞭解什麼是一致性Hash，一致性Hash是用來解決什麼問題的。

“Hash演算法”與“一致性Hash演算法”是不同的概念

不少人容易把“Hash演算法”與“一致性Hash演算法”混淆，甚至認為兩者是同個意思。其實，“Hash演算法”與“一致性Hash演算法”是不同的概念，“一致性Hash演算法”是一種特殊的“Hash演算法”！

1、Hash演算法

Hash演算法有很多種說法，如：雜湊函式、雜湊演算法等，它是一種函式，用來把任意長度的內容透過Hash演算法轉換為固定長度的輸出。

常見的Hash演算法有：MD5、SHA1等。MD5都用過，任何長度的字串經過MD5處理後會得到固長的Hash值。

2、一致性Hash演算法

一致性Hash演算法是在Hash演算法基礎上建立和改進的，它是一種分散式演算法，能確保資料的分佈平衡性，常用於負載均衡類的應用。

一致性Hash演算法與普通取模Hash演算法的區別

1、普通取模Hash

普通取模（餘數）Hash演算法很簡單，就是：Hash值 % 節點數 。這種方式，一旦節點數變化了，原先的Hash結果與節點的對映全部失效！

2、一致性Hash演算法

一致性Hash演算法與普通取模Hash演算法不同，它是對 2^32 取模。比如：hash(伺服器IP地址) % 2^32 。

一致性Hash演算法對於節點的增減只需要重新定位環空間的小部分資料，因此具有很好的容錯性和可擴充套件性。

通俗的說就是，一致性Hash演算法可以確保：在增加伺服器節點或移除節點時，對原有伺服器和使用者之間的對映關係影響最小！

一致性Hash演算法的應用場景

現在的網際網路系統業務絕大多數都是分散式的，所以擴容縮容操作較為常見。

一致性Hash演算法的常用場景有：

Redis叢集的應用

分庫分表

用最通俗易懂的方式來解釋下一致性hash演算法；

首先我們要明確的是一般的hash演算法在取模的時候往往跟實際應用有關！

比如說nginx hash的時候，會根據後臺的應用伺服器數量進行取模，比如說後臺有四臺應用，那麼hash（key）%4 =（0,1,2,3）,就能獲取到具體哪一臺的標號，這個時候如果後臺應用需要擴容，那麼hash演算法就要換成hash（key）%6 =（0,1,2,3,4,5），分佈到六臺不同的機器上去請求，看著沒什麼太大問題，但是如果我們把場景切換為資料庫根據業務主鍵business_no進行hash的的分庫分表結構，在切換之後，因為hash演算法的改變，原本的資料落在4，但是hash結果為5，肯定查不到原來的資料，這就出現了資料查詢錯誤問題！

而如果上述問題是出現在redis上，因為資料大量不命中，大量的查詢降落在底層的資料庫上，嚴重的話發生快取雪崩問題，導致資料庫系統乃至整個系統全部雪崩；

下面詳細說下一致性hash演算法（以redis儲存為例），來解決上面遇到的問題：

一致性hash演算法，不管你的應用有多少，都使用2^32（2的32次方）作為取模，並且將0和2^32-1首尾相連，結成一個環，這樣所有使用一致性hash演算法的資料都大機率均勻的落在這個環上；

落在環上面的資料又是怎麼落到不同的redis伺服器上的呢？我們不管是使用redis伺服器的IP也好，域名也好，總之是一個唯一標識，透過計算hash值也落在這個環上(ABCD伺服器節點)，然後規定把落在環上的資料以順時針的方向旋轉，儲存在遇到的第一個節點（伺服器）上，這很好理解； 如下圖所示：

使用了一致性hash之後，我們伺服器的擴充套件也會變得很容易，如果監控到某個節點（D）壓力比較大，則透過計算hash值，在這個節點的逆時針上游加一個伺服器E（A和D之間），如下圖：

這時候如果有請求進來，在整個環上的資料，只有A到E之間的資料獲取不到從而對下層資料庫有影響，而其他的所有資料不會有任何影響，由此可見使用一致性hash擴充套件是十分方便的！

一致性hash存在的問題：

1，雪崩效應：假設我們並沒有上面說的類似的監控，或者某個節點（B）的資料激增，在我們的反應之前，這個時候這個節點出現了宕機，那麼所有的資料請求將迅速落在A上，A不僅承受自己的資料，還要承受B的，肯定也馬上奔潰，最終整個快取系統發生快取雪崩效應！

2，分佈不均勻： 上面的例子對於hash演算法過於理想化了，比如ABCD四臺伺服器的hash值剛好為1,2,3，4也就代表著hash值在（4，2^32-1]這個範圍的所有資料將落在一臺服務上，這也將是災難性的。。。

那麼我們怎麼解決這種資料分佈十分不均勻的情況呢？

解決辦法：最好的辦法就是增加虛擬節點，截圖如下： ABCD對每個伺服器A，B，C，D都新增了一個（也可以是多個）虛擬節點，也就是說現在A節點可以接受B2-A1加上C1到A2的資料，假設A服務宕機了，那麼A1的資料將落在C2（也就是C），A2的資料將落在D1（也就是D）上，也就是說隨著崩潰的伺服器增多，相對應的資料將分散在更多的伺服器，從而防止整個快取系統的持續雪崩效應；

經過上述的案例，我們能看到一致性hash遵循的原則有下列幾個： ①，平衡性：資料將盡可能的均勻分佈在整個hash環上，

②，單調性：在擴充套件的時候，將保證原來的資料儘量少的落在新的節點上。

一致性hash原理很簡單，但是一致性hash演算法廣泛的用在了諸如redis叢集，資料庫分庫分表等情景當中，良好解決了資料分佈不均，擴充套件困難的難題，是大規模叢集中的優良演算法！

一致性hash演算法，常被應用到分散式叢集快取中。

其原理主要是把節點(做快取的物理主機，如IP)和資料(要快取的具體資料)都做一次雜湊運算，然後把資料快取到雜湊運算後離得最近的節點上去。

此處借個圖

其中，右邊的深藍色的表示節點，橘色的表示資料，然後按順時針方向去尋找最近的節點就可以了……

需要注意的地方有

第一，節點和資料在雜湊運算(取模)過程中用到的除數是一致的。如節點的雜湊運算為hash(伺服器的IP地址)% 2^32，資料的雜湊運算為hash (資料名稱)% 2^32等。

第二，雜湊運算後，所有的結果都分佈在一個雜湊環上。

第三，節點的分佈可能並不是均衡的，所以會加入左邊淺藍色的虛擬節點。

優點

萬一有節點掛掉或者新加節點，不會影響其它的節點和快取資料，原因很簡單，就在那個取模的除數上。

單臺伺服器

就拿Redis來舉例吧，我們經常會用Redis做快取，把一些資料放在上面，以減少資料的壓力。

當資料量少，訪問壓力不大的時候，通常一臺Redis就能搞定，為了高可用，弄個主從也就足夠了；

多臺伺服器資料分佈的問題

當資料量變大，併發量也增加的時候，把全部的快取資料放在一臺機器上就有些吃力了，畢竟一臺機器的資源是有限的，通常我們會搭建叢集環境，讓資料儘量平均的放到每一臺Redis中，比如我們的叢集中有三臺Redis。

那麼如何把資料儘量平均地放到這三臺Redis中呢？最簡單的就是求餘演算法：hash(key)%N，在這裡N=3。

看起來非常地美好，因為依靠這樣的方法，我們可以讓資料平均儲存到三臺Redis中，當有新的請求過來的時候，我們也可以定位資料會在哪臺Redis中，這樣可以精確地查詢到快取資料。

但是注意了，如果要增加一臺Redis，或者三臺中的一臺Redis發生了故障變成了兩臺，那麼這個求餘演算法就會變成：hash(key)%4或者hash(key)%2；那麼可以想象一下，當前大部分快取的位置都會是錯誤的，極端情況下，所有的快取的位置都要發生改變，這樣會造成【快取雪崩】。

一致性hash演算法

一致性hash演算法可以很好地解決這個問題，它的大概過程是：

把0作為起點，2^32-1作為終點，畫一條直線，再把起點和終點重合，直線變成一個圓，方向是順時針從小到大。0的右側第一個點是1，然後是2，以此類推。

對三臺伺服器的IP或其他關鍵字進行hash後對2^32取模，這樣勢必能落在這個圈上的某個位置，記為Node1、Node2、Node3（圖1）。

然後對資料key進行相同的操作，勢必也會落在圈上的某個位置；然後順時針行走，可以找到某一個Node，這就是這個key要儲存的伺服器（圖2）。

如果節點太少或分佈不均勻的時候，容易造成資料傾斜，也就是被資料會集中在某一臺伺服器上（圖4）。

為了解決資料傾斜問題，一致性Hash演算法提出了【虛擬節點】，會對每一個服務節點計算多個雜湊，然後放到圈上的不同位置（圖5）。

原諒我的小學生字型，下一次我一定好好地畫一畫圖，電腦上畫的那種。

環割法（一致性 hash）

環割法的原理如下：

1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字串，例如 SHARD-1-NODE-1，並計算所有 X×N 個字串的所有 hash 值。

2. 將所有計算出來的 hash 值放到一個排序的 Map 中，並將其中的所有元素進行排序。

3. 輸入字串的時候計算輸入字串的 hash 值，檢視 hash 值介於哪兩個元素之間，取小於 hash 值的那個元素對應的分片為資料的分片。

跳躍法（jumpstringhash）

跳躍法的原理如下：

1. 根據公式：

將資料落在每一個節點的機率進行平均分配。

2. 對於輸入的字串進行計算 hash 值，透過判斷每次產生的偽隨機值是否小於當前判定的節點 1/x，最終取捕獲節點編號最大的作為資料的落點。

3. 在實際使用中使用倒數的方法從最大節點值進行反向判斷，一旦當產生的偽隨機值大於 x 則判定此節點 x 作為資料的落點。

資料比較

下面將透過測試對環割法和跳躍法的效能及均衡性進行對比，說明 DBLE 為何使用跳躍法代替了環割法。

資料來源：現場資料 350595 條測試經過：1. 透過各自的測試方法執行對於測試資料的分片任務。2. 測試方法：記錄分片結果的方差；記錄從開始分片至分片結束的時間；記錄分片結果與平均數的最大差值。3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數，所以測試過程只能使用 2 的指數形式進行測試，並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷，取全量長度進行測試。