关于后端:一文详解分布式缓存附代码

又是一个没有动工红包的公司！！！

通过以上对话，各位是否可能猜到所有缓存穿透的起因呢？答复之前咱们先来看一下缓存策略的具体代码

缓存服务器 IP=hash(key)% 服务器数量

这里还要多说一句，key 的取值能够依据具体业务具体设计。比方，我想要做负载平衡，key 能够为调用方的服务器 IP；获取用户信息，key 能够为用户 ID；等等。

在服务器数量不变的状况下，以上设计没有问题。然而要晓得，程序员的事实世界是悲惨的，惟一不变的就是业务始终在变。我本无奈，只能靠技术来扭转这种情况。

如果咱们当初服务器的数量为 10，当咱们申请 key 为 6 的时候，后果是 4，当初咱们减少一台服务器，服务器数量变为 11，当再次申请 key 为 6 的服务器的时候，后果为 5. 不难发现，不光是 key 为 6 的申请，简直大部分的申请后果都产生了变动，这就是咱们要解决的问题，这也是咱们设计分布式缓存等相似场景时候次要须要留神的问题。

咱们终极的设计指标是：在服务器数量变动的状况下

尽量进步缓存的命中率（转移的数据起码）
缓存数据尽量平均分配

通过以上的剖析咱们明确了，造成大量缓存生效的根本原因是公式分母的变动，如果咱们把分母放弃不变，基本上能够缩小大量数据被挪动

分母不变计划

如果基于公式：缓存服务器 IP=hash(key)% 服务器数量咱们放弃分母不变，基本上能够改善现有状况。咱们抉择缓存服务器的策略会变为：

缓存服务器 IP=hash(key)%N（N 为常数）
N 的数值抉择，能够依据具体业务抉择一个满足状况的值。比方：咱们能够必定未来服务器数量不会超过 100 台，那 N 齐全能够设定为 100。那带来的问题呢？

目前的状况能够认为服务器编号是间断的，任何一个申请都会命中一个服务器，还是以上作为例子，咱们服务器当初无论是 10 还是减少到 11，key 为 6 的申请总是能获取到一台服务器信息，然而当初咱们的策略公式分母为 100，如果服务器数量为 11，key 为 20 的申请后果为 20，编号为 20 的服务器是不存在的。

以上就是简略哈希策略带来的问题（简略取余的哈希策略能够形象为间断的数组元素，依照下标来拜访的场景）

为了解决以上问题，业界早已有解决方案，那就是 一致性哈希。

一致性哈希算法在 1997 年由麻省理工学院的 Karger 等人在解决分布式 Cache 中提出的，设计指标是为了解决因特网中的热点 (Hot spot) 问题，初衷和 CARP 非常相似。一致性哈希修改了 CARP 应用的简略哈希算法带来的问题，使得 DHT 能够在 P2P 环境中真正失去利用。

一致性哈希具体的特点，请各位百度，这里不在具体介绍。至于解决问题的思路这里还要强调一下:

首先求出服务器（节点）的哈希值，并将其配置到环上，此环有 2^32 个节点。
采纳同样的办法求出存储数据的键的哈希值，并映射到雷同的圆上。
而后从数据映射到的地位开始顺时针查找，将数据保留到找到的第一个服务器上。如果超过 2^32 依然找不到服务器，就会保留到第一台服务器上

当减少新的服务器的时候会产生什么状况呢？

通过上图咱们能够发现发生变化的只有如黄色局部所示。删除服务器状况相似。

通过以上介绍，一致性哈希正是解决咱们目前问题的一种计划。解决方案千万种，能解决问题即为好。

到目前为止计划都看似完满，但事实是残暴的。以上计划虽好，但还存在瑕疵。如果咱们有 3 台服务器，现实状态下服务器在哈希环上的调配如下图：

然而事实往往是这样：

这就是所谓的哈希环偏斜。散布不平均在某些场景下会顺次压垮服务器，理论生产环境肯定要留神这个问题。为了解决这个问题，虚构节点应运而生。

如上图，哈希环上不再是理论的服务器信息，而是服务器信息的映射信息，比方：ServerA-1,ServerA-2 都映射到服务器 A，在环上是服务器 A 的一个复制品。这种解决办法是利用数量来达到均匀分布的目标，随之须要的内存可能会略微大一点，算是空间换取设计的一种计划。

既然是哈希就会有哈希抵触，那多个服务器节点的哈希值雷同该怎么办呢？咱们能够采纳散列表寻址的计划：从以后地位顺时针开始查找空地位，直到找到一个空地位。如果未找到，菜菜认为你的哈希环是不是该扩容了，或者你的分母参数是不是太小了呢。
在理论的业务中，减少服务器或者缩小服务器的操作要比查找服务器少的多，所以咱们存储哈希环的数据结构的查找速度肯定要快，具体说来实质是：自哈希环的某个值起，能疾速查找第一个不为空的元素。
如果你度娘过你就会发现，网上很多介绍虚构哈希环节点个数为 2^32(2 的 32 次方)，千篇一律。难道除了这个个数就不能够吗？在菜菜看来，这个数目完全必要这么大，只有合乎咱们的业务需要，满足业务数据即可。
一致性哈希用到的哈希函数，不止要保障比拟高的性能，还要放弃哈希值的尽量均匀散布，这也是一个工业级哈希函数的要求，一下代码实例的哈希函数其实不是最佳的，有趣味的同学能够优化一下。
有些语言自带的 GetHashCode（）办法利用于一致性哈希是有问题的，例如 c#。程序重启之后同一个字符串的哈希值是变动的。所有须要一个更加稳固的字符串转 int 的哈希算法。

一致性哈希解决的实质问题是：雷同的 key 通过雷同的哈希函数，能正确路由到雷同的指标。像咱们平时用的数据库分表策略，分库策略，负载平衡，数据分片等都能够用一致性哈希来解决。

以下代码通过少许批改可间接利用于中小我的项目生产环境

 // 实在节点的信息
    public abstract class NodeInfo
    {public abstract string NodeName { get;}
    }

测试程序所用节点信息：

    class Server : NodeInfo
        {public string IP { get; set;}
            public override string NodeName
            {get => IP;}
        }

以下为一致性哈希外围代码：

 /// <summary>
    /// 1. 采纳虚构节点形式  2. 节点总数能够自定义  3. 每个物理节点的虚构节点数能够自定义
    /// </summary>
    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 < virtualNodeNumber)
                {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 < virtualNodeNumber)
            {lstRemoveNodeName.Add($"{nodeName}#{virtualNodeIndex}");
                virtualNodeIndex++;
            }
            // 从索引为 0 的地位循环一遍，把所有的虚构节点都删除
            int startFindIndex = 0;
            lock (objLock)
            {while (startFindIndex < nodes.Length)
                {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 < h.nodes.Length; 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 毫秒）：

以上代码实有优化空间

哈希函数
很多 for 循环的长期变量

有趣味优化的同学能够留言哦!!

更多精彩文章

分布式大并发系列

架构设计系列

趣学算法和数据结构系列

设计模式系列

关于后端:一文详解分布式缓存附代码

问题剖析

解决方案

分母不变计划

优化计划

扩大浏览

实践结合实际才是真谛(NetCore 代码)

测试生成的节点

测试一下性能

写在最初

Just My Socks（注册教程内含优惠码）

关于后端:一文详解分布式缓存附代码

问题剖析

解决方案

分母不变计划

优化计划

扩大浏览

实践结合实际才是真谛(NetCore 代码)

测试生成的节点

测试一下性能

写在最初

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）