是一个集中式单点缓存系统，不具备集群功能。此操作主要由客户端完成。

所以说到分布式，肯定会提到客户端。看下图：

简单来说，这里的客户端做了一个路由功能，负责将不同的请求转发到对应的机器（实例）。

那么客户端如何确定将特定请求转发到哪台机器？

在上面的场景中，我们可以在每次访问数据时根据缓存key计算出hash值一致性hash算法php开源，然后根据实际的机器数量来定位我们想要的机器（这里只是举例，实际环境往往更复杂），

而且，在存储数据和获取数据时，同一台机器定位。它会满足我们的需求吗？

是的，正常情况下可以满足我们的需求，为什么是正常的？

因为在实际生产环境中肯定会出现一些意外情况。比如上面三台机器中的一台突然宕机了，或者我想加一台，会不会出现这个问题？起来了？

由于机器数量的变化，所有原来的缓存无法正确定位，无法再使用。这在一些高并发系统中往往是致命的。

有没有更好的方法可以在机器宕机的情况下进行平滑升级并尽可能保持正常运行？

这个当然有，就是我们接下来要讲的一致性哈希算法。

当我第一次看到一致性哈希算法这个词时，我脑海中的第一反应就是上面的实现。事实上，事实并非如此。更准确地说，一致性哈希算法是一个全局概念模型，是集群部署中的一个很好的解决方案。

一致性哈希算法()早在1997年就已经提出，目前在很多服务器中被广泛使用，目前比较流行。

它的最终目标是在移除或添加机器时最小化对现有键映射关系的影响。

以下是其实现原理的细目分类，网上已经有详细说明。

考虑到通常的hash算法是映射到一个32位的key值，也就是0~2^32-1次幂的数值空间；我们可以把这个空间看作是第一个（0）尾（2^32-1）个连接环，如下图1所示。

接下来考虑4个对象~，hash函数计算出的hash值key在环上的分布如图2所示。

hash() = key1;

…………

hash() = key4;

基本思路

是将对象映射到相同的哈希值空间，并使用相同的哈希算法。

假设当前有3个单元A、B、C，则映射结果如图3所示，将它们排列在对应的hash值的hash空间中。

hash(A) = 键 A;

…………

hash(C) = 键 C;

说到这里，顺便提一下哈希计算。一般的方法可以使用机器的IP地址或机器名作为hash输入。

既然对象和对象都通过相同的哈希算法映射到哈希值空间，接下来要考虑的是如何将对象映射到它。

在这个环形空间中，如果从对象的key值开始顺时针方向，直到遇到一个，那么就将对象存储在this上，因为对象的hash值和hash值是固定的，所以这个必须是唯一的和确定的。你没有找到对象的映射方法吗？ ！

继续上面的例子（见图3），那么按照上面的方法，对象就会被存储在A上；并对应于 C；对应B;

前面说过，先hash再计算余数的方法带来的最大问题是不能满足单调性。当有变化时，就会失败，这会对后端服务器造成巨大的影响。现在让我们来分析和分析算法。 .

删除

考虑假设 B 挂断了电话。根据上面提到的映射方法，只有那些沿着 B 逆时针遍历直到下一个（C）的对象才会受到影响，这些对象原本是映射到 B 上的那些对象。

所以这里我们只需要改变对象，重新映射到C；见下图

添加

考虑添加一个新的D，假设在这个循环的hash空间中，D在对象和之间进行映射。此时，唯一受影响的将是那些沿 D 逆时针遍历直到下一个 (B) 的对象（它们是最初映射到 C 的对象的一部分）。将这些对象重新映射到 D。

所以这里我们只需要改变对象，重新映射到D即可；见下图

另一个考虑Hash算法的指标是()一致性hash算法php开源，定义如下：

平衡

平衡意味着可以将哈希结果尽可能分配到所有的缓冲区，从而可以使用所有的缓冲区空间。

哈希算法不保证绝对平衡。如果对象较少，则无法均匀映射对象。例如，在上面的例子中，当只部署了A和C时，4个对象中，A只存储，C存储，和；分布很不均匀。

为了解决这种情况，引入了“虚拟节点”的概念，可以定义如下：

“虚拟节点”（node）是哈希空间中一个实际节点的副本（），一个实际节点对应几个“虚拟节点”，这个对应的数字也变成了“副本数”，“虚拟节点” “ ”在哈希空间中按哈希值排列。

仍然以仅部署A和C的情况为例，如图4所示，分布并不均匀。现在我们引入虚拟节点，将“复制次数”设置为2，即总共会有4个“虚拟节点”，A1、A2代表A； C1、C2代表C；假设一个更理想的情况，见下图

此时对象与“虚拟节点”的映射关系为：

-> A2; -> A1; -> C1; -> C2;

所以对象和被映射到A，和被映射到C；平衡得到了很大的改善。

引入“虚拟节点”后，映射关系从{ -> node}转化为{ -> node}。查询对象时的映射关系如图所示。

“虚拟节点”的hash计算可以采用在对应节点的IP地址加上数字后缀的方法。例如，假设A的IP地址为202.168.14.241。

在引入“虚拟节点”之前，计算A的hash值：

Hash("202.168.14.241");

引入“虚拟节点”后，计算“虚拟节点”点A1和A2的hash值：

Hash("202.168.14.241#1"); // A1

Hash("202.168.14.241#2"); // A2

基本原则是这些。具体分布的理论分析应该很复杂，但一般不使用。

上面有java版本的例子，可以参考。

转载了一个PHP版本的实现代码。

C 语言版本

查看本文的一致性哈希算法：