一、从Web系统的演进说起

单机时代

在当今的互联网项目中，对于缓存的使用已经是”标配“了，我们开发一个平台刚开始访问量很小只需要一个缓存服务器就够用了（系统架构如下图所示）

负载均衡

随着系统的发展，访问量越来越大，这是我们的服务撑不住了，此时我们考虑给系统做负载均衡增加应用服务器来提高系统的并发量，此时缓存还够用，因此几个应用服务器共用一个缓存服务器就好了。

分布式缓存

可是好景不长，随着服务的时间越长，缓存的东西也越来越多，终于有一个天，缓存服务器撑不住了！此时我们考虑增加缓存服务器，并将缓存的数据拆分并缓存到不同的缓存服务器中。（下图中黄色背景的表示被拆分的数据）

这样我们的系统就可以使用处理一定量的高并发和海量数据了。但是问题又来了，我们现在的系统有多个缓存服务器，我们的一个请求下来要到那个缓存服务器中去写\读数据呢？对于这个问题，有一个简单的方法就是使用数据的key的hashCode与缓存服务器结点个数取余。比如：

现在有一个key="java" 求hashCode：key.hashCode()=100

求余：index=100%3 ==> index=1

因此key="java"这个缓存数据就在第1个缓存服务器中

现在系统改进的可以平稳运行了因对日常级别的大流量已经没有问题了，但是突然要搞活动，比如像双11这样的活动，系统的访问量邹增，为了系统能够平稳运行，这时我们考虑给系统增加配置，其中一项就是缓存服务器

增加了缓存服务器之后，我们按照原来的对key的hashCode()取余的思路来计算一下：

现在有一个key="java" 求hashCode：key.hashCode()=100 //hashCode()在一个系统不会改变

取余：index=100%4 ==> index=0 //由于缓存服务器结点增加了，因此问题就在这里

这样一来，原本在第1个服务器中缓存的数据现在计算出来要去第0个服务器中拿，这就会引起错误

通过上面的分析，我们就可以感受到，使用这种简单的hash算法就会导致增加或减少服务结点之后大部分结点之前的数据不可用，因此为了解决这个问题就出现了 一致性hash算法，这个算法原本就是用来解决分布式缓存问题的。

二、一致性hash算法背景

　　一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点问题，初衷和CARP（Common Access Redundancy Protocol，共用地址冗余协议）十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题，使得分布式哈希（DHT，Distributed Hash Table）可以在P2P环境中真正得到应用。

一致性hash算法提出了在动态变化（分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来）的环境中，判定哈希算法好坏的四个定义：

• 平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

• 单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

• 分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

• 负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

三、一致性Hash算法

1、一致性Hash算法基本原理

其实，一致性哈希算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性哈希算法是对2^32取模，什么意思呢？我们慢慢聊。

首先，我们把二的三十二次方想象成一个圆，一个整数就是一个点，就像钟表一样，钟表的圆可以理解成由60个点组成的圆，而此处我们把这个圆想象成由2^32个点组成的圆，示意图如下：

圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32^-1,也就是说0点左侧的第一个点代表2^32^-1,我们把这个由2^32^个点组成的圆环称为hash环。

有了这个Hash环之后，我们首先按照一定的规则把服务节点通过普通的hash算法把结点记录到hash环的结点上，如下图所示：

之后对数据的key同样做hash运算，拿到key的hash值，那么这个key必然就会在hash环上有一个“落点”,我们不要求它能一次性命中缓存结点，只需要顺着落点顺时针遍历每一个结点，当遍历到下一个缓存结点时就把值发入这个缓存结点后从这个缓存结点获取值。当一个key顺着hash环遍历到2^32^-1时又从0开始遍历，知道找到下一个结点。示意图如下：

了解了一致性Hash算法的基本工作原理之后，我们来看看它是如何解决结点动态改变二造成大规模结点数据不同用的问题的。

我们还是模拟上面的情景，在活动开始之前给系统增加缓存服务器，添加后的示意图：

此时我们可以按照Hash一致性算法的原理分析不难看出：添加结点后可能产生问题的地方就在node3到node4之间，因为这个区间的数原本应该是映射到node1的，但是现在都要映射到node4新节点上去了，不过相对于简单的hash取余，这个方法使得动态增加或减少结点之后数据的可用性提升了不少。

2、一致性Hash算法改进

至此问题基本解决，使用Hash一致性算法可以很轻松的解决分布式缓存带来的问题。然而，我们的分析还只是一种过于理想化的模型，即服务节点均匀的分布在Hash环的4周，假如结点没有均匀分布呢？我们来看看下面的示意图：

当结点没有均匀分布时，一旦添加新的结点，仍然会有大部分数据会失效，这肯定不行啊！那么与上面办法解决这个问题呢？目前常用的解决办法就是使用虚拟结点来解决服务节点分布不均匀的问题 ，具体原理是：

给每个真实的物理结点增加一组虚拟结点，将虚拟结点也放置到Hash环上，这样当一个key遍历到虚拟结点了也就表示找到了真实的物理结点。还是用示意图来说明：

通过示意图可以直观的看出来，增加虚拟结点之后，我们人为的让有限的物理结点均匀分布了，这样一来当添加新结点之后受影响的数据很少。

通过分析我们不难得出结论：对于每个物理节点对应的虚拟节点越多，各个物理节点之间的负载越均衡，新加入物理服务器对原有的物理服务器的影响越保持一致（这就是一致性Hash这个名称的由来)。 那么在实践中，一台物理服务器虚拟为多少个虚拟服务器节点合适呢？太多会影响性能，太少又会导致负载不均衡，一般说来，经验值是150，当然根据集群规模和负载均衡的精度需求，这个值应该根据具体情况具体对待。

参考资料：

• [1] https://www.bilibili.com/video/BV1yb411u7bz/?spm_id_from=trigger_reload
• [2] https://www.cnblogs.com/lpfuture/p/5796398.html
• [3] https://blog.csdn.net/zhaohong_bo/article/details/90519123?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
• [4] https://blog.csdn.net/jiankunking/article/details/85111367