漫畫：分散式緩存伺服器扛不住了怎麼辦？

問題分析

通過以上對話，各位是否能夠猜到所有緩存穿透的原因呢？回答之前我們先來看一下緩存策略的具體代碼：

這裡還要多說一句，key的取值可以根據具體業務具體設計。比如，我想要做負載均衡，key可以為調用方的伺服器IP；獲取用戶信息，key可以為用戶ID......等等。

在伺服器數量不變的情況下，以上設計沒有問題。但是要知道，程序員的現實世界是悲慘的，唯一不變的就是業務一直在變。我本無奈，只能靠技術來改變這種狀況。

假如我們現在伺服器的數量為10，當我們請求key為6的時候，結果是4，現在我們增加一台伺服器，伺服器數量變為11，當再次請求key為6的伺服器的時候，結果為5。不難發現，不光是key為6的請求，幾乎大部分的請求結果都發生了變化，這就是我們要解決的問題，這也是我們設計分散式緩存等類似場景時候主要需要注意的問題。

我們終極的設計目標是，在伺服器數量變動的情況下：

盡量提高緩存的命中率（轉移的數據最少）；

緩存數據盡量平均分配。

解決方案

通過以上的分析我們明白了，造成大量緩存失效的根本原因是公式分母的變化，如果我們把分母保持不變，基本上可以減少大量數據被移動

如果基於公式：緩存伺服器IP=hash(key)%伺服器數量，我們保持分母不變，基本上可以改善現有情況。我們選擇緩存伺服器的策略會變為：

N的數值選擇，可以根據具體業務選擇一個滿足情況的值。比如：我們可以肯定將來伺服器數量不會超過100台，那N完全可以設定為100。那帶來的問題呢？

目前的情況可以認為伺服器編號是連續的，任何一個請求都會命中一個伺服器，還是以上作為例子，我們伺服器現在無論是10還是增加到11，key為6的請求總是能獲取到一台伺服器信息，但是現在我們的策略公式分母為100，如果伺服器數量為11，key為20的請求結果為20，編號為20的伺服器是不存在的。

以上就是簡單哈希策略帶來的問題（簡單取余的哈希策略可以抽象為連續的數組元素，按照下標來訪問的場景）。

為了解決以上問題，業界早已有解決方案，那就是一致性哈希。

一致性哈希演算法在1997年由麻省理工學院的Karger等人在解決分散式Cache中提出的，設計目標是為了解決網際網路中的熱點(Hot spot)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡單哈希演算法帶來的問題，使得DHT可以在P2P環境中真正得到應用。

一致性哈希具體的特點，這裡不在詳細介紹。至於解決問題的思路這裡還要強調一下：

首先求出伺服器（節點）的哈希值，並將其配置到環上，此環有2^32個節點。

採用同樣的方法求出存儲數據的鍵的哈希值，並映射到相同的圓上。

然後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個伺服器上。如果超過2^32仍然找不到伺服器，就會保存到第一台伺服器上。

當增加新的伺服器的時候會發生什麼情況呢？

通過上圖我們可以發現發生變化的只有如黃色部分所示，刪除伺服器情況類似，一致性哈希正是解決我們目前問題的一種方案。

解決方案千萬種，能解決問題即為好。

優化方案

到目前為止方案都看似完美，但現實是殘酷的。以上方案雖好，但還存在瑕疵。假如我們有3台伺服器，理想狀態下伺服器在哈希環上的分配如下圖：

但是現實往往是這樣：

這就是所謂的哈希環偏斜。分布不均勻在某些場景下會依次壓垮伺服器，實際生產環境一定要注意這個問題。為了解決這個問題，虛擬節點應運而生。

如上圖，哈希環上不再是實際的伺服器信息，而是伺服器信息的映射信息，比如：ServerA-1,ServerA-2 都映射到伺服器A，在環上是伺服器A的一個複製品。這種解決方法是利用數量來達到均勻分布的目的，隨之需要的內存可能會稍微大一點，算是空間換取設計的一種方案。

反思

1. 既然是哈希就會有哈希衝突，那多個伺服器節點的哈希值相同該怎麼辦呢？我們可以採用散列表定址的方案：從當前位置順時針開始查找空位置，直到找到一個空位置。如果未找到，那麼你的哈希環是不是該擴容了，或者你的分母參數是不是太小了呢？

2. 在實際的業務中，增加伺服器或者減少伺服器的操作要比查找伺服器少的多，所以我們存儲哈希環的數據結構的查找速度一定要快，具體說來本質是：自哈希環的某個值起，能快速查找第一個不為空的元素。

3. 網上很多介紹虛擬哈希環節點個數為2^32(2的32次方)，千篇一律。難道除了這個個數就不可以嗎？在我看來，這個數目完全必要這麼大，只要符合我們的業務需求，滿足業務數據即可。

4. 一致性哈希用到的哈希函數，不止要保證比較高的性能，還要保持哈希值的盡量平均分布，這也是一個工業級哈希函數的要求，一下代碼實例的哈希函數其實不是最佳的，有興趣的同學可以優化一下。

5. 有些語言自帶的GetHashCode（）方法應用於一致性哈希是有問題的，例如C#。程序重啟之後同一個字元串的哈希值是變動的，所有需要一個更加穩定的字元串轉int的哈希演算法。

一致性哈希解決的本質問題是：相同的key通過相同的哈希函數，能正確路由到相同的目標——像我們平時用的資料庫分表策略、分庫策略、負載均衡、數據分片等都可以用一致性哈希來解決。

理論結合實際才是真諦（NetCore代碼）

以下代碼經過少許修改可直接應用於中小項目生產環境。

測試程序所用節點信息：

以下為一致性哈希核心代碼：

測試生成的節點：

輸出結果（還算比較均勻）：

測試一下性能：

輸出結果（調用10萬次耗時657毫秒）：

作者：菜菜，一個奔走在通往互聯網更高之路的工程師，熱衷於互聯網技術。目前就職於某互聯網教育公司，應用服務端主要負責人。擁有10年 互聯網開發經驗，熱衷於高性能、高並發、分散式技術領域的研究，主要工作語言為C#和Golang。

聲明：本文為作者投稿，版權歸其個人所有，責編郭芮。

【End】

熱 文推 薦

你點的每個「在看」，我都認真當成了喜歡

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！