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

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 { get; set; }
            public override string NodeName
            {
                get => IP;
            }
        }

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

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

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

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

//虛擬環節點的總數量，預設為100
int ringNodeCount;
//每個物理節點對應的虛擬節點數量
int virtualNodeNumber;
//雜湊環，這裡用陣列來儲存
public VirtualNode[] nodes = null;
public ConsistentHash(int _ringNodeCount = 100, int _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(200, 5);
            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

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

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

●程式員修仙之路–設計一個實用的執行緒池

●程式員修仙之路–資料結構之CXO讓我做一個計算器

●程式猿修仙之路–資料結構之設計高效能訪客記錄系統

●程式猿修仙之路–演演算法之快速排序到底有多快

●程式猿修仙之路–資料結構之你是否真的懂陣列？

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

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

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

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

長按識別二維碼關註

聽說轉發文章

會給你帶來好運

已推薦到看一看

你的朋友可以在“發現”-“看一看”看到你認為好看的文章。

取消
推薦

我知道了

已取消，“好看”想法已同步刪除

知道了