-
例如，如果您有n个缓存服务器，那么如何将对象对象映射到N缓存您可能会使用下面的一般方法来计算对象的哈希值，然后将它映射到n个缓存，然后将n的散列映射到n。
散列（对象）%
一切正常运行，并考虑以下两种情况。
1缓存服务器m关闭（在实际应用中必须考虑这种情况），以便映射到高速缓存M的所有对象都将失败，如何操作，需要从高速缓存m中删除，然后缓存是n-1，映射公式为哈希（对象）%（n-1）；
2由于访问的恶化，当缓存是N + 1站点时，需要添加缓存，映射公式变成哈希（对象）%（n + 1）；
1和2是什么意思这意味着几乎所有的缓存都突然失败了。对于服务器来说，这是一个灾难，大量的访问将直接进入后台服务器。
考虑第三个问题。由于硬件功能越来越强大，您可能希望向后面的节点添加更多节点。显然，上面的哈希算法不能这样做。
改变这种情况的方法是什么，这是一致的散列法…
2散列算法与单调性
哈希算法的一个度量是单调性（单调性），其定义如下：
单调性意味着，如果某些内容通过散列被分配给相应的缓冲区，则将一个新的缓冲区添加到系统中。散列结果应该能够确保原始分配的内容可以映射到新的缓冲区，而不是映射到旧缓冲区中的其他缓冲区。
很容易看出，上面简单的哈希算法哈希（object）n很难满足单调性要求。
3一致散列算法的原理
一致散列是散列算法。简单地说，在删除/添加缓存时，尽可能少地改变现有的密钥映射，尽可能地满足单调性要求。
在以下5个步骤中，简要描述了一致哈希算法的基本原理。
3.1环散列空间
考虑到通常的哈希算法是地图的价值的一个关键值的32，即0 ~ 2 ^ 32-1数值空间力量。我们可以想象的空间作为第一（0）尾（2 ^ 32-1）连接环，如图1所示。
图1环散列空间
3.2映射对象到哈希空间
其次，考虑4个对象，发生~ object4，通过哈希函数计算哈希值的关键是在环如图2所示。
哈希（发生）= key1；
…
（object4）=密钥散列；
图24对象的键值分布
3.3 map缓存到哈希空间
一致哈希的基本思想是将对象和缓存映射到相同的哈希数值空间，并使用相同的哈希算法。
假设当前有一组3个缓存的A、B和C，那么它们的映射结果将如图3所示，它们被排列在哈希空间中，并具有相应的散列值。
散列（缓存A）；
…
散列（缓存C）=键C；
图3缓存和对象的键值分布
顺便提一下，顺便说一下，通过缓存的散列计算，一般方法可以用作高速缓存机器的IP地址或机器名的哈希输入。
3.4映射对象缓存
现在，缓存和对象已被同一散列算法映射到哈希数值空间。接下来，我们需要考虑如何将对象映射到缓存。
在环形空间中，如果从对象的键值沿顺时针方向开始，直到遇到一个缓存，那么对象就存储在缓存中，因为缓存对象和散列值是固定的，因此缓存必须是唯一的和确定的，所以您不找到对象和缓存的映射方法吗！
继续上述示例（参见图3）。根据上述方法，对象object1将被存储在高速缓存和缓存对象；object2对应C；object4对应缓存B.
3.5研究高速缓存的变化
正如我们前面提到的，哈希和余数所造成的最大问题不是单调的，当缓存的变化、缓存失效时，对后端服务器造成很大的影响，现在分析一致哈希算法。
3.5.1删除缓存
考虑一下缓存B被挂起的假设。根据上面提到的映射方法，受影响的对象将只能是那些逆时针遍历缓存B的对象，直到下一个缓存（缓存C），即那些最初映射到缓存B的对象。
所以，在这里，你只需要改变对象object4和映射到缓存C；见图4。
图4缓存b被删除后的缓存映射
3.5.2添加缓存
考虑添加一个新的缓存，假设在这个圆形的哈希空间，缓存D对象object2和对象之间的映射。当时，那些受影响的将是那些对象遍历缓存D逆时针方向旋转，直到下一个缓存（Cache B）。他们也映射到缓存，缓存和映射这些对象D.
所以，在这里，你只需要改变对象object2和映射到缓存D；见图5。
图5添加高速缓存d后的映射关系
4虚拟节点
散列算法的另一个指示符是平衡，定义如下：
平衡
余额意味着散列结果可以在所有缓冲区中尽可能分布，以便可以使用所有缓冲区空间。
哈希算法并不能保证绝对的平衡，如果缓存较少，对象不能被均匀地映射到缓存，例如，在上面的例子中，缓存和缓存只有低于4的目标情况下的部署，缓存和缓存发生只有店，C店object2对象和object4，分布不平衡。
为了解决这种情况，一致散列引入了虚拟节点的概念，可以定义如下：
虚拟节点（虚拟节点）是散列空间（副本）中实际节点的副本，实节点对应多个虚拟节点，对应的数字也是一个拷贝数，虚拟节点在哈希空间中以散列值排列。
例如，在只部署缓存A和缓存C的情况下，我们在图4中看到缓存分配不统一。现在我们引入虚拟节点并将副本的数量设置为2，这意味着总共有4个虚拟节点。缓存A1，缓存A2代表缓存A；缓存C1；缓存C2代表缓存；假设一个理想的情况，见图6。
图6引入虚拟节点后的映射关系
此时，对象与虚拟节点之间的映射关系为：
客观->缓存A2；objec2 ->缓存A1；objec3 ->缓存C1；objec4 ->缓存C2；
所以对象Object1和object2映射到缓存，和对象和object4映射到缓存C；平衡有了很大的提高。
虚拟节点的引入，从对象- { { { }转换到节点对象>虚拟节点}的映射。当对象位于时缓存的映射如图7所示。
图7查询对象所在的缓存
虚拟节点的哈希计算可用于相应节点的IP地址的方式和数字后缀。例如，假定缓存的IP地址是202.168.14.241。
在引入虚拟节点之前，计算缓存A的散列值。
哈希（202.168.14.241）；
在引入虚拟节点后，计算了虚拟节点缓存A1和缓存A2的散列值。
哈希（202.168.14.241 # 1） / /缓存A1；
哈希（202.168.14.241 # 2） / /缓存A2；