了解一致性哈希算法

释放双眼,带上耳机,听听看~!

一、背景

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 非线程安全,在实际项目使用当中应该考虑线程同步的问题。

人已赞赏
随笔日记

vue 组件使用中的细节点

2020-11-9 4:01:09

随笔日记

SpringCloud学习系列之五-----配置中心(Config)和消息总线(Bus)完美使用版

2020-11-9 4:01:11

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索