漫畫:分散式快取伺服器扛不住了怎麼辦?| 技術頭條

問題分析

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

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

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

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

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

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

解決方案

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

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

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

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

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

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

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

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

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

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

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

優化方案

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

但是現實往往是這樣:

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

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

反思

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

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

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

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

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

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

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

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

//真實節點的資訊

publicabstractclassNodeInfo

{

publicabstractstringNodeName { get; }

}

測試程式所用節點資訊:

classServer: NodeInfo

{

publicstringIP { get; set; }

publicoverridestringNodeName

{

get=> IP;

}

}

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

///<summary>

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

///</summary>

publicclassConsistentHash

{

//雜湊環的虛擬節點資訊

publicclassVirtualNode

{

publicstringVirtualNodeName { get; set; }

publicNodeInfo Node { get; set; }

}

//新增元素 刪除元素時候的鎖,來保證執行緒安全,或者採用讀寫鎖也可以

privatereadonlyobjectobjLock = newobject();

//虛擬環節點的總數量,預設為100

intringNodeCount;

//每個物理節點對應的虛擬節點數量

intvirtualNodeNumber;

//雜湊環,這裡用陣列來儲存

publicVirtualNode[] nodes = null;

publicConsistentHash(int_ringNodeCount = 100, int_virtualNodeNumber = 3)

{

if(_ringNodeCount <= 0|| _virtualNodeNumber <= 0)

{

thrownewException( “_ringNodeCount和_virtualNodeNumber 必須大於0”);

}

this.ringNodeCount = _ringNodeCount;

this.virtualNodeNumber = _virtualNodeNumber;

nodes = newVirtualNode[_ringNodeCount];

}

//根據一致性雜湊key 獲取node資訊,查詢操作請業務方自行處理超時問題,因為多執行緒環境下,環的node可能全被清除

publicNodeInfo GetNode(stringkey)

{

varringstartIndex = Math.Abs(GetKeyHashCode(key) % ringNodeCount);

varvNode = FindNodeFromIndex(ringStartIndex);

returnvNode == null? null: vNode.Node;

}

//虛擬環新增一個物理節點

publicvoidAddNode(NodeInfo newNode)

{

varnodeName = newNode.NodeName;

intvirtualNodeIndex = 0;

lock(objLock)

{

//把物理節點轉化為虛擬節點

while(virtualNodeIndex < virtualNodeNumber)

{

varvNodeName = $”{nodeName}#{virtualNodeIndex};

varfindStartIndex = Math.Abs(GetKeyHashCode(vNodeName) % ringNodeCount);

varemptyIndex = FindEmptyNodeFromIndex(findStartIndex);

if(emptyIndex < 0)

{

// 已經超出設定的最大節點數

break;

}

nodes[emptyIndex] = newVirtualNode() { VirtualNodeName = vNodeName, Node = newNode };

virtualNodeIndex++;

}

}

}

//刪除一個虛擬節點

publicvoidRemoveNode(NodeInfo node)

{

varnodeName = node.NodeName;

intvirtualNodeIndex = 0;

List< string> lstRemoveNodeName = newList< string>();

while(virtualNodeIndex < virtualNodeNumber)

{

lstRemoveNodeName.Add( $”{nodeName}#{virtualNodeIndex});

virtualNodeIndex++;

}

//從索引為0的位置迴圈一遍,把所有的虛擬節點都刪除

intstartFindIndex = 0;

lock(objLock)

{

while(startFindIndex < nodes.Length)

{

if(nodes[startFindIndex] != null&& lstRemoveNodeName.Contains(nodes[startFindIndex].VirtualNodeName))

{

nodes[startFindIndex] = null;

}

startFindIndex++;

}

}

}

//雜湊環獲取雜湊值的方法,因為系統自帶的gethashcode,重啟服務就變了

protectedvirtualintGetKeyHashCode(stringkey)

{

varsh = newSHA1Managed();

byte[] data = sh.ComputeHash(Encoding.Unicode.GetBytes(key));

returnBitConverter.ToInt32(data, 0);

}

#region私有方法

//從虛擬環的某個位置查詢第一個node

privateVirtualNode FindNodeFromIndex(intstartIndex)

{

if(nodes == null|| nodes.Length <= 0)

{

returnnull;

}

VirtualNode node = null;

while(node == null)

{

startIndex = GetnextIndex(startIndex);

node = nodes[startIndex];

}

returnnode;

}

//從虛擬環的某個位置開始查詢空位置

privateintFindEmptyNodeFromIndex(intstartIndex)

{

while( true)

{

if(nodes[startIndex] == null)

{

returnstartIndex;

}

varnextIndex = GetNextIndex(startIndex);

//如果索引回到原地,說明找了一圈,虛擬環節點已經滿了,不會新增

if(nextIndex == startIndex)

{

return-1;

}

startIndex = nextIndex;

}

}

//獲取一個位置的下一個位置索引

privateintGetNextIndex(intpreIndex)

{

intnextIndex = 0;

//如果查詢的位置到了環的末尾,則從0位置開始查詢

if(preIndex != nodes.Length – 1)

{

nextIndex = preIndex + 1;

}

returnnextIndex;

}

#endregion

}

測試生成的節點:

ConsistentHash h = newConsistentHash( 200, 5);

h.AddNode( newServer() { IP = “192.168.1.1”});

h.AddNode( newServer() { IP = “192.168.1.2”});

h.AddNode( newServer() { IP = “192.168.1.3”});

h.AddNode( newServer() { IP = “192.168.1.4”});

h.AddNode( newServer() { IP = “192.168.1.5”});

for( inti = 0; i < h.nodes.Length; 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

測試一下效能:

Stopwatchw = newStopwatch();

w.Start();

for( inti = 0; i < 100000; i++)

{

varaaa = h.GetNode( “test1”);

}

w.Stop();

Console.WriteLine(w.ElapsedMilliseconds);

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

657

Comments

comments

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *