了解一致性哈希算法

一、背景

1.1 使用场景

一致性哈希算法一般用于解决分布式系统当中的热点问题，用于提升分布式系统的可扩展性与健壮性。

1.2 解决的问题

一般用于分布式缓存系统当中的缓存击穿问题，简单哈希在服务节点数量产生变化的时候，其缓存命中率很低，从而导致大量接口直接请求数据库，造成缓存击穿的情况。

例如我们有 10 台缓存服务器，我们可以对请求关键字 (key) 进行哈希操作，将其值对 10 取模，得到的结果即服务器的索引。

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

但是一旦增加/减少了一台服务器，其所有缓存数据的位置都会发生相应的改变。例如原本 id 为 2 的用户信息，取模的结果为 hash(2)%10=4 ，当增加了一台服务器之后 hash(2)%11=? ，这里的缓存位置就被改变了，这个时候就需要一致性哈希来解决问题了。

一致性哈希可以解决的问题：

1. 提高缓存命中率。
2. 缓存数据应该均匀地分配在各个服务器中。

二、原理

注意：

由于粗心，将服务器 c 的 ip 地址也设置成了 192.168.100.102，其 ip 应该是 192.168.100.103。

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

   

2. 求出服务器的哈希值，并将其与哈希环的节点数量取模，根据得到的位置，把服务分配在一个哈希环当中。

   

3. 根据存储数据的键，求出其哈希值，也将其映射在哈希环上。

   

4. 根据键在哈希环的位置，顺时针查找第一个服务节点，将数据存储到对应的服务器当中。

   

5. 如果增加了一台新的服务器 d，仅会影响 d 之前的区间数据。

   

6. 当我们需要获得某个缓存数据在哪个服务器的时候，仅需要对这个数据的关键字取其 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 非线程安全，在实际项目使用当中应该考虑线程同步的问题。