对于最近看到的哈希算法，而后还有一致性哈希算法，本文针对网上收集到的材料做一个整顿，不便前面回顾一致性哈希算法的常识，这就是本篇文章《一文彻底读懂一致性哈希算法》的由来；

一致性 hash 算法是 1997 年麻省理工学院提出，是一种非凡的 hash 算法，目标是解决分布式缓存的问题。在移除或者增加一个服务器时，可能尽可能小的扭转已存在的服务申请与解决申请服务器之间的映射关系。一致性 hash 解决了简略 hash 算法在分布式 hash 表（Distributed Hash Table，DHT）中存在的动静伸缩问题。

简介

​ 一致性哈希算法是 1997 年在论文《Consistent hashing and random trees》中被提出的，在分布式系统中利用十分宽泛。一致性哈希是一种哈希算法，简略的说就是在移除或者增加一个服务器时，此算法可能尽可能小的扭转已存在的服务申请与解决申请服务器之间的映射关系，尽可能满足枯燥性的要求，在一般分布式集群中，服务申请鱼解决申请服务器之间能够一一对应，也就是说固定服务申请与解决服务器之间的映射关系，某个申请由固定的服务器去解决。这种形式无奈对整个零碎进行负载平衡，可能会造成某些服务器过于忙碌始终无奈解决新来的申请，而另一些服务器则过于闲暇，整体零碎的资源利用率低，并且当分布式集群中的某个服务器宕机，会间接导致某些服务申请无奈解决。

​ 进一步的改良能够利用 hash 算法对服务申请进行解决服务器之间的关系进行映射，以达到动态分配的目标。通过 hash 算法对服务申请进行转换，转换后的后果对服务器节点值进行取模计算，取模后的值就是服务申请对应的申请解决服务器。这种办法能够应答节点生效的状况，当某个分布式集群节点宕机，服务申请能够通过 hash 算法重新分配到其余可用的服务器上。防止了无奈解决申请的状况呈现。

​ 但这种办法的缺点也很显著，如果服务器中保留有服务申请对应的数据，那么如果从新计算申请的 hash 值，会造成大量的申请被重定位到不同的服务器而造成申请所要的数据有效，这种状况在分布式系统中是十分蹩脚的。一个设计良好的分布式系统应该具备良好的枯燥性，即服务器的增加与移除不会造成大量的哈希重定位，而一致性哈希恰好能够解决这个问题。

​ 一致性哈希算法将整个哈希值空间映射一个虚构的圆环，整个哈希空间的取值范畴为 0～2^32-1. 整个空间按顺时针方向组织。0～2^32- 1 在零点方向重合。接下来应用如下算法对申请进行映射，将服务申请应用哈希算法算出对应的 hash 值，而后依据 hash 值的地位沿圆环顺时针查找，第一台遇到的服务器就是所对应的解决申请服务器。当减少一台新的服务器，受影响的数据仅仅是新增加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其它都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具备较好的容错性和可扩展性。

场景形容

​ 假如咱们有三台缓存服务器，用于缓存图片，咱们为这三台缓存服务器设置编号为 0，1，2 号服务器，当初对申请过去的图片平均的缓存在这三台服务器上，以便它们均摊缓存图片的申请，假如有三万张图片须要缓存，也就是每台服务器均匀缓存一万张左右。如果咱们以没有任何法则的把三万张图片均匀的缓存在三台服务器上，也能满足咱们的需要，然而如果这样做的话，当咱们拜访某一张图片时，则最差须要遍历三台服务器，从三万个缓存中找到咱们所须要的缓存，这样的话其实也就失去了缓存的意义，并没有改善用户的体验。那么咱们能够怎么做呢，原始的做法就是对图片的名称进行哈希（假如图片名称是惟一的），将 hash 后的后果进行与服务器数量的取模操作，通过取模后的后果来决定缓存该存在哪台服务器上，那么咱们能够应用如下公式来决定图片应该存在哪台服务器上

hash（图片名称）%N

​ 因为图片的名称是不反复，所以当咱们对一个图片名称做雷同的哈希计算时，失去的后果应该是不变的，如果咱们有三台服务器，应用哈希后的后果就是对三进行取余，那么余数肯定是 0，1，2 三个中的一个，没错，正好与咱们的服务器编号一样了，所以如果求余的后果是 0，那么咱们就能够把图片缓存在 0 号服务器上，相同，如果取余的后果是 1，那就是缓存在 1 号服务器上。那么当咱们拜访任意一个图片时，只须要对图片名称进行上述的操作即可晓得图片缓存在哪个服务器上，如果图片在对应的服务器上不存在，则证实对应的图片没缓存，也就不须要再去其它的服务器上查问了，通过这样的办法，就能够均匀的把三万张图片扩散的放在三台服务器上，而且当下次访问某张图片时，间接就能判断出以后图片所在的服务器，这样就能满足咱们的需要了，过程能够参考如下图所示

此时应用了下面的哈希算法之后还会有什么问题呢，试想一下，如果三台缓存服务器曾经不能满足咱们的缓存需要，那么咱们是不是要减少一台，那么缓存服务器的数量就由 3 台变成 4 台了，此时如果依然采纳上述办法对同一张图片进行缓存，那么这张图片所在的服务器编号必然与原来三台服务器时产生的后果不统一，这种状况带来的结果就是当缓存服务器数量产生变动时，所有缓存的地位都要产生扭转，换句话说，当服务器数量产生扭转时，所有缓存在肯定工夫内是生效的，当申请无奈从缓存中读取到数据时，则会向后端服务器发送申请，同理，假如三台服务器其中有一台服务器产生了故障，无奈进行缓存，那么咱们就须要将故障机器移除，此时响应的缓存服务器数量也是产生了变动，以前缓存的图片也就失去了意义，此时大量图片缓存生效，造成缓存雪崩，此时缓存无奈在分担压力，后端服务器将接受压力，整个零碎也就有可能被压垮，所以咱们要想方法不让这种状况产生，然而因为上述哈希算法自身的缘故，应用取模算法进行缓存时，这种状况是不可避免的，为了解决这些问题，一致性哈希算法也就应运而生了。

所以咱们来回顾下应用上述哈希算法会产生的问题：

• 当缓存服务器数量发生变化时，引起缓存大量生效，缓存雪崩，可能会使后端服务器压力变大而解体
• 当缓存服务器数量发生变化时，简直所有的缓存地位都会发生变化，那咱们怎样才能缩小受影响的缓存呢

其实，这两个问题都能够应用一致性哈希算法解决，当初咱们持续深刻理解一下一致性哈希算法

概念

​ 首先，一致性哈希算法是采纳取模的办法，只是，方才的取模算法是对服务器数量进行取模，那么咱们只有不对服务器数量进行取模，而对一个常量进行取模不就能够了吗，所以一致性哈希算法是对 2^32 进行取模，咱们把 0 - 2 的 32 次方设想成一个圆，就像钟表一样的圆，钟表的圆能够设想是圆上有 60 个点，而咱们的这个圆是由 2^32 个点组成的圆，示意图如下

​ 圆的正上方的点代表 0，0 点右侧第一个点代表 1，左侧第一个点代表 2^32-1，咱们把 0 -2^32- 1 之间的圆环称之为 hash 环

上面，跟我一起看下一致性哈希算法是怎么在这个圆上来体现的

首先咱们还是有三台服务器，别离是服务器 A，服务器 B，服务器 C，那么在咱们的生产环境中，咱们对这三台服务器的 ip 地址进行哈希，用哈希后的后果对 2^32 进行取模运算，失去的后果就是服务器的地位

hash（服务器 IP 地址）% 2^32

通过这个公式计算的后果必定是 0 -2^32- 1 之间的一个数，咱们就用这个数代表服务器 A

而后咱们用同样的办法，计算出服务器 B，和服务器 C 的地位，示意如下

假如三台服务器通过计算之后的地位如上图所示（现实状况下是这个样子，然而事实往往很有情）

好了，到这里，咱们曾经把服务器与 hash 环绑定到了一起，上面就是把数据绑定到 hash 环上，那么咱们上面就用同样的办法把须要缓存的对象放到 hash 环上

还是依照方才的例子，对三万张图片进行缓存，此时咱们还是应用如下公式

hash（图片名称）% 2^32

第一张图片映射的后果如下图所示（假如）

那么它是如何决定到哪台服务器下来呢，下面的图片会被缓存到服务器 A 上，为什么会这样呢？因为从图片的地位开始，沿顺时针方向遇到的第一个服务器就是服务器 A，所以上图会被缓存到服务器 A 上，如下图所示

所以一致性哈希算法就是通过这种办法来判断对象该存储在哪台服务器上的，也就是将缓存服务器与缓存的对象绑定到 hash 环上之后，从被缓存的对象开始，顺时针方向遇到的第一台服务器就是缓存对象要存储的服务器，因为缓存对象对服务器 hash 后的值是固定的，所以在服务器不变的状况下，一张图片必定会缓存在固定的服务器上，所以当下次形式该图片时，只有在次应用同样的哈希算法计算，即可获取出该图片在哪台服务器上，而后间接去对应的服务器上获取即可。

方才的示例是一张图片，上面演示一下多张图片的，

图片 1，图片 2 会缓存在服务器 A 上，图片 3 缓存在服务器 B 上，图片 4 缓存在服务器 C 上

一致性哈希的长处

​ 通过下面的形容，我想大家应该可能晓得一致性哈希的原理了，所以大家考虑一下，一致性哈希能够解决下面的两个问题吗，首先还是第一个问题，当服务器数量产生变动时，缓存会大量同一时间生效造成缓存雪崩，从而有可能引发零碎的解体，那么应用一致性哈希算法可能防止这个问题吗，上面咱们来看一下

假如服务器 B 呈现故障，当初咱们须要把服务器 B 移除掉，那么咱们从 hash 环上移除服务器 B 之后如下所示

在服务器 B 没有故障未被移除时，图片 3 应该是缓存在服务器 B 上，可是当服务器 B 有了故障被移除后，图片 3 依照顺时针方向遇到的第一个服务器就变成了服务器 C，所以此时图片 3 就被缓存在服务器 C 中，也就是说，如果服务器 B 呈现故障，图片 3 的缓存地位会发生变化

此时，图片 4 依然会被缓存中服务器 C 中，图片 1 与图片 2 缓存在服务器 A 中，这与服务器 B 移除前后并不会有影响，这也就是哈希算法的长处，如果应用之前的哈希算法，服务器数量发生变化时，所有的缓存对象都会发生变化，而应用一致性哈希算法之后，服务器的数量如果发生变化，并不是所有的缓存都会生效，而只有局部缓存才会生效，所以这种状况下不至于所有的缓存生效，都在同一时间集中到后端服务器上。

hash 环的偏斜

​ 在介绍一致性哈希时，咱们是十分理想化的假如 3 台服务器平均的散布在 hash 环上，如下图所示

然而往往事实不会如此，在理论的应用过程中，服务器有可能会被映射为如下

聪慧的你必定想到如果产生了这种状况，那么缓存的对象可能会集中的缓存中一台服务器上，这也就是 hash 环的歪斜，如下如所示

此时，如图所示，图片 1，图片 3，图片 4，图片 5 都会缓存到服务器 A 上，图片 2 缓存中服务器 B 上，服务器 C 上没有图片，也就是说，服务器资源并没有均匀的被应用，最坏的状况下，如果此时服务器 A 产生故障，那缓存生效的对象也就达到了最大值，极其状况下也有可能造成后端服务器的解体。此时这种状况称之为 hash 环的歪斜，那么怎么避免 hash 环的歪斜呢，一致性 hash 算法应用虚构节点来解决了这个问题，上面咱们来看看

虚构节点

​ 还是依照咱们说的，假如咱们只有三台服务器，当咱们把服务器映射到 hash 环上的时候，很有可能产生 hash 环偏斜的状况，当 hash 环偏斜当前，缓存往往会极度不均衡的散布在各个服务器上，聪慧的你必定想到了，要想平衡的将缓存散布在三台服务器上，那么只有这三台服务器尽可能多的平均的散布在 hash 环不就行了吗，然而实在的服务器资源只有 3 台，咱们怎么凭空让它多起来呢，没错，就是凭空让服务器的节点多起来，既然没有多余的真正的物理服务器节点，咱们只能将现有的物理节点虚构进去，这些由理论节点虚构复制进去的节点被称为“虚构节点”，退出虚构节点之后的 hash 环如下

​ 虚构节点是理论节点在 hash 环上的复制品，一个理论节点能够复制多少虚构节点

​ 从上图能够看出，ABC 三台服务器别离虚构进去一个虚构节点，当然，如果你需要的话也能够虚构出更多的节点，此时为了画图演示，咱们各只虚构出一个节点。减少了虚构节点的概念后，缓存的散布就就平均了很多，上图中，图片 1，图片 3 缓存在服务器 A，图片 2，图片 4 缓存中服务器 B，图片 5 缓存中服务器 C，如果你还不释怀的话，能够虚构出更多的虚构节点，以便缩小 hash 环歪斜带来的影响，虚构节点越多，hash 环的节点越多，缓存被均匀分布的可能就越大。

​ 所以，此时缓存对象曾经平衡的散布在 hash 环上，如果在产生服务器故障，那么受影响的缓存对象就是产生故障的服务器逆时针方向到遇到的第一台服务器之间的数据，受影响的缓存对象大大减少。

好了，一致性哈希算法的原理就总结了这里，如果谬误，欢送赐教

参考链接

• 百度百科
• 维基百科
• 参考博客
• 参考博客
• 参考链接

如果感觉整顿不错的话能够点个关注后续一起成长

回复【面试】获取面试宝典

​