了解一致性哈希算法

用途

一致性哈希算法是为了解决普通哈希算法的热点问题,当使用普通哈希算法来切割数据到不同的缓存服务器时。 一旦缓存服务器的数量产生变化,客户端向缓存服务器请求相应的数据就不会命中,转而请求具体的数据库服务器,从而造成 缓存击穿

下面我们来看一下使用普通哈希算法时所带来的问题,假如我们拥有 10 台缓存服务器,那么我们在存放数据的时候可以对缓存数据项的 Key 进行哈希操作,取得其散列值,并将其与服务器数量进行取模运算,就可以得到一个服务器下标的数字。

服务器信息 = Hash(Key) % 10

例如我针对字符串 “140” 进行 SHA256 散列操作,得到 762818267,对 10 取模运算结果是 7 号服务器。但如果增加了一台服务器,那么就会变成对 11 取模,,其结果就是 2 号服务器,得到的位置完全不正确,造成取缓存的时候肯定不会命中。

原理

注意:

由于画图的时候粗心将服务器 C 的 IP 地址写成了 192.168.100.102,其真实 IP 应该是 192.168.100.103,阅读文章的时候请注意这个区别。

1.创建一个环,这个哈希环有 2^32 个节点。

image-20190326121534703

2.求出服务器的哈希值,并将其与哈希环节点的数量取模,得到的值即是服务器节点在哈希环上的位置。

image-20190326122549456

3.根据要存储的数据项键值,求出其哈希值,与哈希环节点数量取模,得到在哈希环的位置。

image-20190326130204253

4.根据数据项在哈希环的位置,顺时针查找遇到的第一个服务器节点,将数据项存放到该服务器。

image-20190326140049779

5.如果增加了一台服务器 D,只会影响 D 之前区间的数据。

image-20190326141821117

上述情况仅适用于服务节点在哈希环上分布均匀的情况,如果哈希环上服务器节点的 分布位置不均匀,则会导致某个区间内的数据项的大量数据存放在一个服务器节点中。如下图,A 缓存服务器就会接收大量请求,当该服务器崩溃掉之后,B 服务器,C 服务器会依次崩溃,这样就会造成 服务器雪崩效应,整个缓存服务器集群都会瘫痪。

image-20190326143407844

这种时候,我们可以引入虚拟节点来解决该问题。例如我们拥有 A、B、C 三台服务器,我们在哈希环上创建哈希服务器的时候,可以为其创建 N 个虚拟节点,这些虚拟节点都是指向真实服务器的 IP,这样我们在哈希环上的服务器节点分布就会很均匀。

image-20190326143734935

实现

在这里我们基于 C# 与 .NET Core 编写一个 DEMO 代码,用来演示上述情况,这里的代码仅作演示使用,如果要应用到生产环境,请注意线程同步问题。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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"});
        }
    }
}
Built with Hugo
主题 StackJimmy 设计