多服务器的Redis分布式模式，一致的哈希算法

一致性哈希和随机树早在1997年就提出了一致性哈希算法，并在缓存系统中得到越来越广泛的应用.

例如，如果您有N个缓存服务器（以下称为缓存），然后如何将对象映射到N个缓存，则可能会使用类似于以下内容的通用方法来计算对象的哈希值，然后平均映射到N个缓存；

哈希（对象）％N

一切正常，然后考虑以下两种情况；

1缓存服务器m关闭（在实际应用中必须考虑这种情况），以便映射到缓存m的所有对象都将无效，该怎么办，您需要从缓存中删除缓存mredis一致性哈希算法，此时缓存为N-1，映射公式变为hash（object）％（N-1）;

2由于访问增加，需要添加缓存. 此时，缓存为N + 1，映射公式变为hash（object）％（N + 1）;

1和2是什么意思？这意味着几乎所有缓存都突然失效. 对于服务器来说，这是一场灾难，类似洪水的访问将直接冲向后台服务器；

让我们再次考虑第三个问题. 由于硬件功能越来越强大，因此您可能需要向以后添加的节点添加更多的工作. 显然，上述哈希算法无法完成.

有什么办法可以改变这种情况，这是一致的哈希值...

对哈希算法的一种度量是单调性，其定义如下:

单调性意味着如果已经通过哈希将某些内容分配给了相应的缓冲区，则会向系统添加新的缓冲区. 散列的结果应确保可以将原始分配的内容映射到新缓冲区，但不能映射到旧缓冲区集中的其他缓冲区.

不难看出，上述简单的哈希算法hash（object）％N难以满足单调性要求.

一致性哈希是一种哈希算法. 简而言之，在删除/添加缓存时，它可以将现有的键映射关系更改为尽可能小的以满足新的单调要求.

在这里，我们将分五个步骤简要说明一致性哈希算法的基本原理.

考虑到通常的哈希算法是将值映射到键值32，键值是0〜2 ^ 32-1幂的值空间；我们可以将此空间视为第一（0）个尾部（2 ^ 32-1），相连的圆如下图1所示.

图1环形哈希空间

接下来考虑四个对象object1〜object4. 由散列函数计算出的散列值键在环上的分布如图2所示.

hash（object1）= key1;

……

hash（object4）= key4;

图2 4个对象的键值分布

一致性哈希的基本思想是将对象和缓存都映射到相同的哈希值空间，并使用相同的哈希算法.

假设当前有3个A，B和C缓存，那么它们的映射结果将如图3所示，它们以具有对应的哈希值的方式排列在哈希空间中.

hash（cache A）= key A;

……

哈希（缓存C）=密钥C；

图3缓存和对象键值分布

顺便说一下redis一致性哈希算法，对于缓存的哈希计算，一般方法可以使用缓存计算机的IP地址或计算机名称作为哈希输入.

现在，缓存和对象已通过相同的哈希算法映射到哈希值空间中，接下来要考虑的是如何将对象映射到缓存.

在这个环形空间中，如果您从对象的键值开始沿顺时针方向直到遇到缓存，则将对象存储在缓存中，因为对象和缓存的哈希值是固定的，因此，此缓存必须唯一且确定. 您没有找到对象和缓存之间的映射方法吗？ ！

继续上面的示例（参见图3），然后根据上述方法，对象object1将存储在高速缓存A上； object2和object3对应于高速缓存C； object4对应于缓存B；

如前所述，哈希和余数方法带来的最大问题是它不能满足单调性. 当高速缓存更改时，高速缓存将失败，这将对后台服务器造成巨大影响. 现在让我们对其进行分析. 一致性哈希算法分析.

3.5.1删除缓存

考虑缓存B挂起的假设. 根据上述映射方法，只有那些沿缓存B逆时针移动直到下一个缓存（缓存C）的对象才会受到影响，这些对象最初映射到缓存B上的那些对象.

因此，仅需要更改object4，并且需要将其重新映射到缓存C；参见图4.

图4删除缓存B后的缓存图

3.5.2添加缓存

让我们考虑添加一个新的缓存D的情况. 假设在此循环哈希空间中，缓存D映射在对象object2和object3之间. 此时，仅影响沿缓存D逆时针移动直到下一个缓存（缓存B）的那些对象（它们是最初映射到缓存C的对象的一部分），并且这些对象将重新映射到缓存D随便去吧.

因此，仅需要更改object2并将其重新映射到缓存D；参见图5.

图5添加缓存D后的映射关系

另一个考虑哈希算法的指标是Balance，其定义如下:

余额

平衡性意味着散列的结果可以尽可能地分配给所有缓冲区，以便可以使用所有缓冲区空间.

哈希算法不能保证绝对平衡. 如果缓存较少，则无法将对象均匀地映射到缓存. 例如，在上面的示例中，当仅部署高速缓存A和高速缓存C时，在对象中有4个，高速缓存A仅存储object1，而高速缓存C存储object2，object3和object4. 分布非常不均匀.

为解决这种情况，一致性哈希引入了“虚拟节点”的概念，其定义如下:

“虚拟节点”是哈希空间中实际节点的副本. 实际节点对应于几个“虚拟节点”，并且对应的编号成为“副本数”. “虚拟节点”通过哈希值在哈希空间中排列.

仍然以仅部署缓存A和缓存C的情况为例，我们在图4中看到缓存分布不均匀. 现在我们介绍虚拟节点并将“副本数”设置为2，这意味着总共将有4个“虚拟节点”，缓存A1，缓存A2代表缓存A；缓存C1，缓存C2代表缓存C；假设情况更理想，请参见图6.

图6引入“虚拟节点”后的映射关系

此时，对象与“虚拟节点”之间的映射关系为:

objec1->缓存A2； objec2->缓存A1; objec3->缓存C1; obje->缓存C2;

因此，对象object1和object2映射到缓存A，而object3和object4映射到缓存C；平衡已大大改善.

引入“虚拟节点”后，映射关系从{对象->节点}更改为{对象->虚拟节点}. 查询对象所在的缓存时的映射关系如图7所示.

图7查询对象所在的缓存

“虚拟节点”的哈希计算可以使用相应节点的IP地址加上数字后缀. 例如，假设缓存A的IP地址为202.168.14.241.

在引入“虚拟节点”之前，计算缓存A的哈希值:

Hash（“ 202.168.14.241”）;

引入“虚拟节点”后，在“虚拟节点”处计算缓存A1和缓存A2的哈希值:

Hash（“ 202.168.14.241#1”）; //缓存A1

Hash（“ 202.168.14.241#2”）; //缓存A2

一致性哈希的基本原理就是这些. 具体分布等理论分析应该非常复杂，但通常不使用.

上面有一个Java版本示例，您可以参考它.

转载了PHP版本的实现代码.

C语言版本

发件人:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-251001-1.html