瞭解一致性哈希演算法_ZenDei技術網路在線

一、背景 1.1 使用場景一致性哈希演算法一般用於解決分散式系統當中的熱點問題，用於提升分散式系統的可擴展性與健壯性。 1.2 解決的問題一般用於分散式緩存系統當中的緩存擊穿問題，簡單哈希在服務節點數量產生變化的時候，其緩存命中率很低，從而導致大量介面直接請求資料庫，造成緩存擊穿的情況。例如我們 ...

一、背景

1.1 使用場景

一致性哈希演算法一般用於解決分散式系統當中的熱點問題，用於提升分散式系統的可擴展性與健壯性。

1.2 解決的問題

一般用於分散式緩存系統當中的緩存擊穿問題，簡單哈希在服務節點數量產生變化的時候，其緩存命中率很低，從而導致大量介面直接請求資料庫，造成緩存擊穿的情況。

例如我們有 10 台緩存伺服器，我們可以對請求關鍵字 (key) 進行哈希操作，將其值對 10 取模，得到的結果即伺服器的索引。

伺服器信息=hash(key) % 10

但是一旦增加/減少了一臺伺服器，其所有緩存數據的位置都會發生相應的改變。例如原本 Id 為 2 的用戶信息，取模的結果為 hash(2)%10=4 ，當增加了一臺伺服器之後 hash(2)%11=? ，這裡的緩存位置就被改變了，這個時候就需要一致性哈希來解決問題了。

一致性哈希可以解決的問題：

提高緩存命中率。
緩存數據應該均勻地分配在各個伺服器中。

二、原理

註意：

由於粗心，將伺服器 C 的 IP 地址也設置成了 192.168.100.102，其 IP 應該是 192.168.100.103。

創建一個環，這個哈希環有 2^32 個節點。
求出伺服器的哈希值，並將其與哈希環的節點數量取模，根據得到的位置，把服務分配在一個哈希環當中。
根據存儲數據的鍵，求出其哈希值，也將其映射在哈希環上。
根據鍵在哈希環的位置，順時針查找第一個服務節點，將數據存儲到對應的伺服器當中。
如果增加了一臺新的伺服器 D，僅會影響 D 之前的區間數據。
當我們需要獲得某個緩存數據在哪個伺服器的時候，僅需要對這個數據的關鍵字取其 Hash 值，並對 2^32 取模，找到它下一個節點即是數據所對應的伺服器節點。

2.1 新的問題

使用上述方案的確可以解決由於服務 節點增加/減少 造成的緩存擊穿，這是節點分佈位置均衡的情況。如果節點的在哈希環上 分佈位置不均勻 ，就會造成下圖這種極端情況。

上圖中，黃色的小點代表緩存的數據，A、B、C 並沒有均勻地分佈在哈希環上。可以看到 C -> A 區間是最大的，這就會造成大部分數據都會存放到 A 節點當中，導致 伺服器雪崩 的情況發生。

2.2 使用虛擬節點解決問題

由於伺服器節點可能存在分佈不均的問題，我們可以將一些虛擬節點放在哈希環上，這些虛擬節點其實是映射的真實伺服器的地址。

從下圖來看，黑底白字的伺服器節點 A、B、C 只是真實節點的三個副本，虛擬節點 B -> C 區間的內容，實際上是存放到真實 C 節點的。我們就可以通過增加虛擬節點來解決伺服器節點分佈不均的問題。

三、實現

這裡的 DEMO 我們使用的是 C# + .NET Core 進行實現，在這個 DEMO 當中演示了基於一致性哈希演算法的緩存的

using System;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Text;

/*
 * 一致性哈希演算法的 DEMO，主要用於演示一致性哈希演算法的實現與實際應用。
 */

namespace ConsistentHashing.Startup
{
    public class NodeInfo
    {
        public string IPAddress { get; set; }
    }

    public class VirtualNodeInfo
    {
        public string NodeName { get; set; }

        public NodeInfo RealNodeInfo { get; set; }
    }

    public class ConsistentHashing
    {
        // 哈希環的大小
        private readonly int _ringCount;
        // 每個物理節點對應的虛擬節點數量
        private readonly int _virtualNodeCount;

        // 哈希環
        public readonly VirtualNodeInfo[] HashRing;

        public ConsistentHashing(int ringCount = int.MaxValue, int virtualNodeCount = 3)
        {
            _ringCount = ringCount;
            _virtualNodeCount = virtualNodeCount;
            HashRing = new VirtualNodeInfo[_ringCount];
        }

        public NodeInfo GetNode(string key)
        {
            var pos = Math.Abs(GetStandardHashCode(key) % _ringCount);
            // 順時針查找最近的節點
            return GetFirstNodeInfo(pos).RealNodeInfo;
        }

        /// <summary>
        /// 向哈希環上添加虛擬節點。
        /// </summary>
        public void AddNode(NodeInfo info)
        {
            for (int index = 0; index < _virtualNodeCount; index++)
            {
                // 哈希環上沒有物理節點，只有虛擬節點
                var virtualNodeName = $"{info.IPAddress}#{index}";
                var hashIndex = Math.Abs(GetStandardHashCode(virtualNodeName) % _ringCount);
                
                // 搜索空的哈希環位置
                var emptyIndex = GetEmptyNodeIndex(hashIndex);

                if (emptyIndex == -1)
                {
                    break;
                }
                
                HashRing[emptyIndex] = new VirtualNodeInfo{NodeName = virtualNodeName,RealNodeInfo = info};
            }
        }

        public void RemoveNode(NodeInfo info)
        {
            // 構建虛擬節點的 KEY
            var virtualNames = new List<string>();
            for (int i = 0; i < _virtualNodeCount; i++)
            {
                virtualNames.Add($"{info.IPAddress}#{i}");
            }

            for (int i = 0; i < HashRing.Length; i++)
            {
                if(HashRing[i] == null) continue;
                if (virtualNames.Contains(HashRing[i].NodeName)) HashRing[i] = null;
            }
        }

        /// <summary>
        /// 計算指定 KEY 的 HASH 值
        /// </summary>
        private int GetStandardHashCode(string key)
        {
            var sha1 = SHA256.Create();
            var hashValue = sha1.ComputeHash(Encoding.UTF8.GetBytes(key));
            return BitConverter.ToInt32(hashValue);
        }

        /// <summary>
        /// 迴圈遍歷哈希環，尋找空節點的索引，防止覆蓋存在的節點信息。
        /// </summary>
        private int GetEmptyNodeIndex(int startFindIndex)
        {
            while (true)
            {
                if (HashRing[startFindIndex] == null)
                {
                    return startFindIndex;
                }

                var nextIndex = GetNextNodeIndex(startFindIndex);
                // 說明已經遍歷了整個哈希環，說明沒有空的節點了。
                if (startFindIndex == nextIndex)
                {
                    return -1;
                }

                startFindIndex = nextIndex;
            }
        }

        /// <summary>
        /// 根據指定的索引，獲得哈希環的下一個索引。這裡需要註意的是，因為哈希環是一個環形，當
        /// 當前位置為環的末尾時，應該從 0 開始查找。
        /// </summary>
        private int GetNextNodeIndex(int preIndex)
        {
            if (preIndex == HashRing.Length - 1) return 0;

            return ++preIndex;
        }

        private VirtualNodeInfo GetFirstNodeInfo(int currentIndex)
        {
            VirtualNodeInfo nodeInfo = null;
            int nextIndex = currentIndex;
            while (nodeInfo == null)
            {
                nodeInfo = HashRing[GetNextNodeIndex(nextIndex)];
                nextIndex += 1;
            }
            
            return nodeInfo;
        }
    }

    internal class Program
    {
        private static void Main(string[] args)
        {
            var consistentHashing = new ConsistentHashing(400,10);
            consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.101"});
            consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.102"});
            consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.103"});
            consistentHashing.AddNode(new NodeInfo {IPAddress = "192.168.1.104"});

            foreach (var node in consistentHashing.HashRing)
            {
                Console.WriteLine(node?.NodeName ?? "NULL");
            }

            // 存放 Id 為 15 的緩存伺服器
            var nodeInfo = consistentHashing.GetNode("15");
            
            // 刪除節點測試
            consistentHashing.RemoveNode(new NodeInfo {IPAddress = "192.168.1.103"});
        }
    }
}

以上 DEMO 非線程安全，在實際項目使用當中應該考慮線程同步的問題。