歡迎光臨
每天分享高質量文章

程式員修神之路–分散式快取的一條明路(附程式碼)

菜菜呀,由於公司業務不斷擴大,線上分散式快取伺服器扛不住了呀

程式員主力 Y總

如果加硬體能解決的問題,那就不需要修改程式

菜菜

我是想加伺服器來解決這個問題,但是有個問題呀

程式員主力 Y總

???

菜菜

你忘了去年分散式快取伺服器也擴容過一次,很多請求都穿透了,DB差點扛不住呀,這次再擴容DB估計就得掛了

程式員主力 Y總

為什麼會有這麼多請求穿透呢?公司的快取策略是什麼?

菜菜

很簡單,根據快取資料key的雜湊值然後和快取伺服器個數取模,即:伺服器資訊=hash(key)%伺服器數量

程式員主力 Y總

這樣的話,增加一臺伺服器,豈不是大部分的快取幾乎都命中不了了?

菜菜

給你半天,把這個機制最佳化一下,你要加油呀

程式員主力 Y總

工資能不能漲一點?

菜菜

將來公司發達了,給你發股票……

程式員主力 Y總

心想:呸!!

菜菜
又是一個沒有開工紅包的公司!!!
 

問題分析

        過以上對話,各位是否能夠猜到所有快取穿透的原因呢?回答之前我們先來看一下快取策略的具體程式碼:

 

快取伺服器IP=hash(key)%伺服器數量

        

    這裡還要多說一句,key的取值可以根據具體業務具體設計。比如,我想要做負載均衡,key可以為呼叫方的伺服器IP;獲取使用者資訊,key可以為使用者ID;等等。

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

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

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

1. 儘量提高快取的命中率(轉移的資料最少)

2. 快取資料儘量平均分配

 

解決方案

        透過以上的分析我們明白了,造成大量快取失效的根本原因是公式分母的變化,如果我們把分母保持不變,基本上可以減少大量資料被移動

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

 

快取伺服器IP=hash(key)%N (N為常數)

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

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

         以上就是簡單雜湊策略帶來的問題(簡單取餘的雜湊策略可以抽象為連續的陣列元素,按照下標來訪問的場景)

 為瞭解決以上問題,業界早已有解決方案,那就是一致性雜湊

 

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

一致性雜湊具體的特點,請各位百度,這裡不在詳細介紹。至於解決問題的思路這裡還要強調一下:

1.  首先求出伺服器(節點)的雜湊值,並將其配置到環上,此環有2^32個節點。

2.  採用同樣的方法求出儲存資料的鍵的雜湊值,並對映到相同的圓上。

3.  然後從資料對映到的位置開始順時針查詢,將資料儲存到找到的第一個伺服器上。如果超過2^32仍然找不到伺服器,就會儲存到第一臺伺服器上

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

    透過上圖我們可以發現發生變化的只有如黃色部分所示。刪除伺服器情況類似。

    透過以上介紹,一致性雜湊正是解決我們目前問題的一種方案。解決方案千萬種,能解決問題即為好

最佳化方案

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

但是現實往往是這樣:

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

        如上圖,雜湊環上不再是實際的伺服器資訊,而是伺服器資訊的對映資訊,比如:ServerA-1,ServerA-2 都對映到伺服器A,在環上是伺服器A的一個複製品。這種解決方法是利用數量來達到均勻分佈的目的,隨之需要的記憶體可能會稍微大一點,算是空間換取設計的一種方案。

擴充套件閱讀

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

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

3.  如果你度娘過你就會發現,網上很多介紹虛擬雜湊環節點個數為2^32(2的32次方),千篇一律。難道除了這個個數就不可以嗎?在菜菜看來,這個數目完全必要這麼大,只要符合我們的業務需求,滿足業務資料即可。

4.  一致性雜湊用到的雜湊函式,不止要保證比較高的效能,還要保持雜湊值的儘量平均分佈,這也是一個工業級雜湊函式的要求,一下程式碼實體的雜湊函式其實不是最佳的,有興趣的同學可以最佳化一下。

5.  有些語言自帶的GetHashCode()方法應用於一致性雜湊是有問題的,例如c#。程式重啟之後同一個字串的雜湊值是變動的。所有需要一個更加穩定的字串轉int的雜湊演演算法

 

一致性雜湊解決的本質問題是:相同的key透過相同的雜湊函式,能正確路由到相同的標的。像我們平時用的資料庫分表策略,分庫策略,負載均衡,資料分片等都可以用一致性雜湊來解決。

 

理論結合實際才是真諦(NetCore程式碼)

以下程式碼經過少許修改可直接應用於中小專案生產環境。

 //真實節點的資訊
    public abstract class NodeInfo
    {
        public abstract string NodeName { get; }
    }

測試程式所用節點資訊:

    class Server : NodeInfo
        {
            public string IP { getset; }
            public override string NodeName
            {
                get => IP;
            }
        }

以下為一致性雜湊核心程式碼:

 /// 
    /// 1.採用虛擬節點方式  2.節點總數可以自定義  3.每個物理節點的虛擬節點數可以自定義
    /// 

public class ConsistentHash
{
//雜湊環的虛擬節點資訊
public class VirtualNode
{
public string VirtualNodeName { getset; }
public NodeInfo Node { getset; }
}

//新增元素 刪除元素時候的鎖,來保證執行緒安全,或者採用讀寫鎖也可以
private readonly object objLock = new object();

//虛擬環節點的總數量,預設為100
int ringNodeCount;
//每個物理節點對應的虛擬節點數量
int virtualNodeNumber;
//雜湊環,這裡用陣列來儲存
public VirtualNode[] nodes = null;
public ConsistentHash(int _ringNodeCount = 100int _virtualNodeNumber = 3)
{
if (_ringNodeCount <= 0 || _virtualNodeNumber <= 0)
{
throw new Exception(“_ringNodeCount和_virtualNodeNumber 必須大於0”);
}
this.ringNodeCount = _ringNodeCount;
this.virtualNodeNumber = _virtualNodeNumber;
nodes = new VirtualNode[_ringNodeCount];
}
//根據一致性雜湊key 獲取node資訊,查詢操作請業務方自行處理超時問題,因為多執行緒環境下,環的node可能全被清除
public NodeInfo GetNode(string key)
{
var ringStartIndex = Math.Abs(GetKeyHashCode(key) % ringNodeCount);
var vNode = FindNodeFromIndex(ringStartIndex);
return vNode == null ? null : vNode.Node;
}
//虛擬環新增一個物理節點
public void AddNode(NodeInfo newNode)
{
var nodeName = newNode.NodeName;
int virtualNodeIndex = 0;
lock (objLock)
{
//把物理節點轉化為虛擬節點
while (virtualNodeIndex                 {
var vNodeName = $”{nodeName}#{virtualNodeIndex};
var findStartIndex = Math.Abs(GetKeyHashCode(vNodeName) % ringNodeCount);
var emptyIndex = FindEmptyNodeFromIndex(findStartIndex);
if (emptyIndex 0)
{
// 已經超出設定的最大節點數
break;
}
nodes[emptyIndex] = new VirtualNode() { VirtualNodeName = vNodeName, Node = newNode };
virtualNodeIndex++;

}
}
}
//刪除一個虛擬節點
public void RemoveNode(NodeInfo node)
{
var nodeName = node.NodeName;
int virtualNodeIndex = 0;
List<string> lstRemoveNodeName = new List<string>();
while (virtualNodeIndex             {
lstRemoveNodeName.Add($”{nodeName}#{virtualNodeIndex});
virtualNodeIndex++;
}
//從索引為0的位置迴圈一遍,把所有的虛擬節點都刪除
int startFindIndex = 0;
lock (objLock)
{
while (startFindIndex                 {
if (nodes[startFindIndex] != null && lstRemoveNodeName.Contains(nodes[startFindIndex].VirtualNodeName))
{
nodes[startFindIndex] = null;
}
startFindIndex++;
}
}

}

//雜湊環獲取雜湊值的方法,因為系統自帶的gethashcode,重啟服務就變了
protected virtual int GetKeyHashCode(string key)
{
var sh = new SHA1Managed();
byte[] data = sh.ComputeHash(Encoding.Unicode.GetBytes(key));
return BitConverter.ToInt32(data, 0);

}

#region 私有方法
//從虛擬環的某個位置查詢第一個node
private VirtualNode FindNodeFromIndex(int startIndex)
{
if (nodes == null || nodes.Length <= 0)
{
return null;
}
VirtualNode node = null;
while (node == null)
{
startIndex = GetNextIndex(startIndex);
node = nodes[startIndex];
}
return node;
}
//從虛擬環的某個位置開始查詢空位置
private int FindEmptyNodeFromIndex(int startIndex)
{

while (true)
{
if (nodes[startIndex] == null)
{
return startIndex;
}
var nextIndex = GetNextIndex(startIndex);
//如果索引回到原地,說明找了一圈,虛擬環節點已經滿了,不會新增
if (nextIndex == startIndex)
{
return -1;
}
startIndex = nextIndex;
}
}
//獲取一個位置的下一個位置索引
private int GetNextIndex(int preIndex)
{
int nextIndex = 0;
//如果查詢的位置到了環的末尾,則從0位置開始查詢
if (preIndex != nodes.Length – 1)
{
nextIndex = preIndex + 1;
}
return nextIndex;
}
#endregion
}

測試生成的節點

            ConsistentHash h = new ConsistentHash(2005);
            h.AddNode(new Server() { IP = "192.168.1.1" });
            h.AddNode(new Server() { IP = "192.168.1.2" });
            h.AddNode(new Server() { IP = "192.168.1.3" });
            h.AddNode(new Server() { IP = "192.168.1.4" });
            h.AddNode(new Server() { IP = "192.168.1.5" });

            for (int i = 0; i             {
                if (h.nodes[i] != null)
                {
                    Console.WriteLine($"{i}===={h.nodes[i].VirtualNodeName}");
                }
            }

輸出結果(還算比較均勻):

2====192.168.1.3#4
10====192.168.1.1#0
15====192.168.1.3#3
24====192.168.1.2#2
29====192.168.1.3#2
33====192.168.1.4#4
64====192.168.1.5#1
73====192.168.1.4#3
75====192.168.1.2#0
77====192.168.1.1#3
85====192.168.1.1#4
88====192.168.1.5#4
117====192.168.1.4#1
118====192.168.1.2#4
137====192.168.1.1#1
152====192.168.1.2#1
157====192.168.1.5#2
158====192.168.1.2#3
159====192.168.1.3#0
162====192.168.1.5#0
165====192.168.1.1#2
166====192.168.1.3#1
177====192.168.1.5#3
185====192.168.1.4#0
196====192.168.1.4#2

測試一下效能

            Stopwatch w = new Stopwatch();
            w.Start();
            for (int i = 0; i 100000; i++)
            {
                var aaa = h.GetNode("test1");
            }
            w.Stop();
            Console.WriteLine(w.ElapsedMilliseconds);

輸出結果(呼叫10萬次耗時657毫秒):

657

 

寫在最後
以上程式碼實有最佳化空間

1. 雜湊函式

2. 很多for迴圈的臨時變數

有興趣最佳化的同學可以留言哦!!

 

程式員修仙之路–高效能排序多個檔案

程式員修仙之路–把使用者訪問記錄最佳化到極致

程式員修仙之路–設計一個實用的執行緒池
程式員修仙之路–資料結構之CXO讓我做一個計算器
程式猿修仙之路–資料結構之設計高效能訪客記錄系統
程式猿修仙之路–演演算法之快速排序到底有多快
程式猿修仙之路–資料結構之你是否真的懂陣列?

程式猿修仙之路–演演算法之希爾排序

程式員修仙之路–演演算法之插入排序

程式員修仙之路–演演算法之選擇排序

網際網路之路,菜菜與君一同成長

長按識別二維碼關註

聽說轉發文章

會給你帶來好運

    贊(0)

    分享創造快樂