哎喲JAVA不錯哦

用最通俗易懂的方式來解釋下一致性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之間），如下圖：

一致性hash存在的問題：

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

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

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

解決辦法：最好的辦法就是增加虛擬節點，截圖如下：

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

②，單調性：在擴展的時候，將保證原來的數據儘量少的落在新的節點上。

③，分散性：相同的內容儘量避免落在不同的節點上去！

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

個人感覺本文中的解釋還算通俗易懂，如果有不明白的朋友，可以私信我，我再解釋下，後期會有更多的技術分享，也請持續關注，謝謝。。。

哎喲JAVA不錯哦

我來給大家講講一致性hash算法，如果有理解錯誤的地方，也請大家留言指正。

單臺服務器

就拿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）。
  

• 如果增加一臺服務器或者刪除一臺服務器，只會影響部分小部分數據（圖3）。
  

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

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

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

我將持續分享Java開發、架構設計、程序員職業發展等方面的見解，希望能得到你的關注。

會點代碼的大叔

舉個應用場景：分佈式存儲

現在互聯網面對的都是海量的數據和海量的用戶，我們為了提高數據的讀取，寫入能力，一般都採用分佈式的方式來存儲數據，比如分佈式緩存。我們有海量的數據需要緩存，所以一臺機器是肯定不夠的，於是我們需要將數據分佈在多臺機器上。

該如何決定哪些數據放在那臺機器上，可以藉助數據分片的思想，採用hash算法對數據取hash值，然後對機器取模，這個最終值就是存儲緩存的機器編號。

但是如果數據增多，原來的10臺機器不夠，需要擴容到13臺機器，那麼原來數據是通過與10來取模的，比如15這個數據，與10取模就是5，現在與13取模就是2。機器的編號完全變了，擴容並不是簡單的增加機器，而是需要重新計算機器上的緩存存儲位置。這無疑是一件很頭疼的問題。

所以，我們需要一種方法，是的新加入機器後，並不需要做大量的數據搬遷，這時候就需要用到一致性hash算法了。

假設我們有k個機器，數據的hash範圍是[0-Max],現在我們將範圍劃分為m個小區間（m要遠大於k）,每個機器負責m/k個區間，當有新機器加入時，我們只需要將某幾個小區間的數據搬運到新的機器上即可，這樣既不用全部搬移數據，也保持了各個機器的數據均衡。

陸垚瑪麗

一致性hash算法，常被應用到分佈式集群緩存中。

其原理主要是把節點(做緩存的物理主機，如IP)和數據(要緩存的具體數據)都做一次哈希運算，然後把數據緩存到哈希運算後離得最近的節點上去。

此處借個圖

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

需要注意的地方有

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

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

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

優點

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

關鍵字: 編程語言 一致性 科技