本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore
微信公衆号：貝塔學Java
前言
在之前寫了兩篇關于緩存的文章《萬字長文聊緩存（上）- http緩存》《萬字長文聊緩存（下）- 應用級緩存》，談到緩存不說一下一緻性Hash算法那就是在耍流氓。
分布式緩存叢集的通路模型
現在通常使用Redis來做分布式緩存，下面我們就以Redis為例：
假如目前我們系統的業務發展很快，需要緩存的資料很多，是以我們做了一個由三組主從複制的redis組成的高可用的redis叢集，如何将請求路由的不同的redis叢集上，這是我們需要考慮的，常用的路由算法：
随機算法：每次将請求随機的發送到其中一組Redis叢集中，這種算法的好處是請求會被均勻的分發到每組Redis叢集上；缺點也很明顯，由于随機分發請求，為了提高緩存的命中率，是以同一份資料需要在每組叢集中都存在，這樣就會造成了資料的備援，浪費了存儲空間
Hash算法：針對随機算法的問題，我們可以考慮Hash算法，舉例：
現在有三組redis叢集，我們可以對每次緩存key的hash值取模，公式：
index=hash(key) % 3
，index的值就對應着3組叢集，這樣就可以保證同一個請求每次都被分發到同一個redis叢集上，無需對資料做備援，完美的解決了剛才随機算法的缺點；
但是hash算法也有缺點：對于容錯性和伸縮性支援很差，舉例：當我們三組redis叢集中其中一組節點當機了，那麼此時的redis叢集中可用的數量變成了2，公式變成了
index=hash(key) % 2
， 所有資料緩存的節點位置就發生了變化，造成緩存的命中率直線下降；
同理，當我們需要擴充一組新的redis機器，計算的公式
index=hash(key) % 4
，大量的key會被重新定位到其他伺服器，也會造成緩存的命中率下降。
為了解決hash算法容錯性和伸縮性的問題，一緻性hash算法由此而生~
一緻性雜湊演算法
具體的算法過程
- 先構造一個長度為2^32-1的整數環（稱為一緻性hash環），然後給每組redis叢集命名，根據名字的hash值計算出每組叢集應該放在什麼位置
- 根據緩存資料的key計算出hash值，計算出出來的hash值同樣也分布在一緻性hash環上; 假如現在有5個資料需要緩存對應的key分别為key1、key2、key3、key4、key5，計算hash值之後的分部如下圖
- 然後順着hash環順時針方向查找reids叢集，把資料存放到最近的叢集上
最後所有key4、key5存放在了叢集2，key1、key3存放在了叢集1，key2存放在了叢集3
容錯性
還是繼續沿用上面的例子，我們來看下一緻性雜湊演算法的容錯性如何呢？假如其中 叢集1 跪了，那麼影響的資料隻有key1和key3，其他資料存放的位置不受影響；當再次緩存key1、key3的時候根據順時針查找，會把資料存放到叢集3上面
伸縮性
如果我們需要在目前的基礎上再添加一組redis叢集4，根據名字hash之後的位置在叢集1和叢集2之間
新加redis叢集4之後影響的隻有key1資料，其他資料不受影響。
資料傾斜問題
經過容錯性、伸縮性的驗證證明了一緻性雜湊演算法确實能解決Hash算法的問題，但是現在的算法就是完美的嗎？讓我們繼續來看剛才容錯性的例子，加入叢集1跪了，那麼原來落在叢集1上的所有資料會直接落在叢集3上面，如果說每組redis叢集的配置都是一樣的，那麼叢集3的壓力會增大，資料分布不均勻造成資料傾斜問題。
怎麼搞呢？
歪果仁的腦子就是好使，給的解決方案就是加一層虛拟層，假如每組叢集都配置設定了2個虛拟節點
| 叢集 | 虛拟節點 |
|---|---|
| 叢集1 | vnode1, vnode2 |
| 叢集2 | vnode3, vnode4 |
| 叢集3 | vnode5, vnode6 |
接下來就是把虛拟節點放入到一緻性hash環上，在緩存資料的時候根據順時針查找虛拟節點，在根據虛拟節點的和實際叢集的對應關系把資料存放到redis叢集，這樣資料就會均勻的分布到各組叢集中。
這時候如果有一組redis叢集出現了問題，那麼這組叢集上面的key會相對均勻的分攤到其他叢集上。
從上面的結果來看，隻要每組叢集對應的虛拟節點越多，那麼各個實體叢集的資料分布越均勻，當新增加或者減少實體叢集影響也會最小，但是如果虛拟節點太多會影響查找的性能，太少資料又會不均勻，那麼多少合适呢？根據一些大神的經驗給出的建議是 150 個虛拟節點。
一緻性Hash算法Java版實作
實作思路：在每次添加實體節點的時候，根據實體節點的名字生成虛拟節點的名字，把虛拟節點的名字求hash值，然後把hash值作為key，實體節點作為value存放到Map中；這裡我們選擇使用TreeMap，因為需要key是順序的存儲；在計算資料key需要存放到哪個實體節點時，先計算出key的hash值，然後調用TreeMap.tailMap()傳回比hash值大的map子集，如果子集為空就需要把TreeMap的第一個元素傳回，如果不為空，那麼取子集中的第一個元素。
> 不扯廢話，直接上代碼，No BB . Show me the code
核心代碼：
測試代碼：
- 測試删除節點node3，對比命中率影響了多少 添加如下代碼：
執行結果：
- 測試添加節點node5，對比命中率影響了多少 添加如下代碼：
執行結果：
其他使用場景
看上圖，在Nginx請求的分發過程中，為了讓應用本地的緩存命中率最高，我們希望根據請求的URL或者URL參數将相同的請求轉發到同一個應用伺服器中，這個時候也可以選擇使用一緻性hash算法。具體配置可以參考官方文檔:
https://www.nginx.com/resources/wiki/modules/consistent_hash/
寫到最後（點關注，不迷路）
文中或許會存在或多或少的不足、錯誤之處，有建議或者意見也非常歡迎大家在評論交流。
最後，白嫖不好，創作不易，希望朋友們可以點贊評論關注三連，因為這些就是我分享的全部動力來源🙏
原創不易 轉載請注明出處：https://mp.weixin.qq.com/s/eCxGPqrfIeFY_E_CnFRfMw