了解一致性hash原理，这篇文章就够了

旧城等待， 2023-09-27 09:07 127阅读 0赞

在理解一致性hash算法之前，让我们来看一个在缓存中最经典的案例场景，理解这个运用场景之后，我们再去理解一致性hash算法就更容易了，在这个过程中我们还能体会一致性hash算法的优势之处，好了，让我们来描述一下这个经典的分布式缓存案例。

## 1、场景描述 ##

假设，我们有三台缓存服务器用来缓存图片，我们给这三台服务器一次命名为服务器1、服务器2、服务器3，然后呢，我们有3万张图片需要缓存，我们希望这3万张图片均匀的分布在这三台服务器上，这样就可以让三台服务器均摊压力。换句话说，就是想每台服务器上存一万张图片，我们该怎么做呢？如果我们没有任何的规则限制，我们可以将三张图片依次落在3台服务器上（从第一张图片开始放的是1，下一张就放2，再下一张就放3，一直这样循环，直到把3万张图片放完），这样能满足要求吗，当然可以！但是如果你这样做，当你需要读取图片时，你需要遍历三个服务器，每次都要遍历一万次，直到找到为止，这个过程效率就太低了~时间太长了，当我们命中缓存的时间过长，以至于不能满足要求，这个缓存动作就失去意义了，缓存的目的是为了提高查询效率，改善用户体验，减轻后端服务的压力；如果每次查询数据时都要遍历所有的服务器上的所以缓存，想到这个就心累，那我们该怎么办呢？

最先想到的方法是通过对关键字进行hash取值，然后将hash值对服务器数量进行取模，通过取模的结果决定将这个缓存项放到哪个服务器，这个可能不太那么好理解，举个栗子，我们还是以上面那个存图片的场景为例，假设我用图片名作为key来定位图片，假设图片名不重复，我们通过以下公司，就可以推断这个图片将被放置到哪个服务器上。

> **hash（ Image name ）% N**

因为图片名称是不重复的，所以当我们通过相同的hash运算，同一张图片名称得到的结果是一样的，如果我们有三台服务器，我们将hash值对3求余，那么余数必然是0、1、2，是吧，这不就对应到了我们的服务器编号了！如果余数是0，这对应的缓存项就落在0号服务器上，如果余数是1，对应的缓存项就落在2号服务器上，如果余数是2，同理。

这样我们访问任何一张图片时，只要再进行一下如上运算，就能知道我们要访问的图片在哪个服务器上，我们只需要直接去那个服务器上找，如果对应的服务器上没有，就说明这个图片还没有被缓存，无需再去其他服务器上找了，这样的话，我们就能将3万张图片随机放到3台服务器上，当我们需要访问时，也能直接定位图片应该在哪个服务器上，为了便于理解，我们将上诉方法称之为HASH算法或者叫取模算法，这个取模算法的流程如下所示：

![9b230fa270c7517efa9970b26efae25d.png][]

但是呢，我们使用这个HASH算法在缓存场景时，会有些问题，试想一下，如果这三台缓存服务器不足以支撑我们的缓存业务，我们该怎么办？是的没错，这个很简单，再加两台不就完事了！假设我们添加一台缓存服务器，那么问题来了，之前我们求余的基数是3，现在变成了4；如果我们使用相同的方法缓存相同的图片，在增加服务器前后，相同的图片应该对应相同的缓存服务器，但现在肯定不同了，因为除数由3变成了4，除数变了，余数肯定也变了；这样造成的结果就是，当服务器数量发生变化时，所有的缓存位置都必须更改((也就是根据新的服务器数量进行重新定位))，换句话说，当服务器数量发生改变时，所有的缓存将在一定时间内不可用(在重新计算位置)。当运用程序无法从缓存中取到数据时，所有的请求都打到后台服务，同理，假设三台服务器中有一台挂了，无法缓存，我们需要将这台服务器移除，但如果你移除它，那可用服务器数量就有3台变成了2台，如果你想访问图片，这个时候图片的位置必然发生改变，由于大量的缓存同时失效，那缓存也就失去了意义，造成缓存雪崩。此时前端缓存已经无法承受访问压力，后端服务器将承担极大的压力，整个系统可能奔溃。

因此，我们应该尽量避免这种情况的发生，但由于HASH算法的局限性，当我们用取模策略时，这个是不可避免的，为了解决这些问题，一致性哈希算法应运而生。

让我们总结一下上述算法存在的问题：

**问题1：当缓存服务器数量发生改变时，会导致缓存雪崩，可能会引起整个系统因压力过大而崩溃(大量缓存同时失效)**

**问题2：当服务器数量发生改变时，几乎所有的缓存位置都要发生改变，怎么样才能将缓存的影响降到最低(原来的缓存位置不动)？**

实际上，上面两个问题是同一个问题，一致性hash就能解决上述问题。

现在让我们来看看一致性hash算法。

## 2、均匀Hash的基本概念 ##

实际上，一致性哈希算法用的也是取模方法，只不过这个取模方法不是对服务器数量取模，而是对2^32取模，这是什么意思呢？听我娓娓道来。

首先，让我们把2^32想象成一个圆，就像一个圆钟，钟上的圆可以看成由60个点组成的圆，而我们想象的这个圆可以看成由2^32个点组成的，示意图如下：

![97346f2268d5c342842e53fdf751454c.png][]

圆圈的正上方那个点表示0，第一个点的右边，一次是1、2、3、4、5、6……一直到2的32次方减一，我们把这个由2的32次方个点组成的东西称为哈希环。

一致性hash算法与上述的环有什么关系呢？我们继续讨论，还是以上面的场景为例，假设我们有三台服务器，分别为服务器A、服务器B、服务器C，众所周知，在生产环境，这三台服务器必然有自己的IP地址，我们就它们各种的IP进行hash运算，将得到的结果与2^32进行取模，就像下面这个公式描述的一样：

> **hash（ The server A Of IP Address ） % 2^32**

经过上述公式的运算，结果必然落在0-2^32-1之间，我们把这个点在哈希环上的位置映射为服务器所在的位置，示意图如下：

![21310e52fbb7c10facfe284f337f034f.png][]

同理，我们可以对服务器B、服务器C进行相同的hash映射

> **hash（ The server B Of IP Address ） % 2^32**
> 
> **hash（ The server C Of IP Address ） % 2^32**

通过上述方法，我们可以将服务器B和服务C映射到哈希环上，示意图如下：

![282acde83f654ffd015503228608ba08.png][]

现在假设三台服务器都映射到环上了，如上图所示(当然，这是最理想的情况，我们后面在讨论)

很好，截止到目前，我们使用上述方法，已经将缓存服务器映射到哈希环上了，我们也可以使用相同的方法，将需要缓存的对象映射到哈希环上。

> 假设我们需要用缓存服务器来缓存图片，还是通过图片名称来作为查询图片的key，我们可以使用相同的方法将图片映射到哈希环上。

> **hash（ Image name ） % 2^32**

这个映射关系如下，环上橙色的点就是

![0092593baf2142af8cdb2d325eb6e4b1.png][]

很好，现在服务器和图片都映射到哈希环了，那我们的图片该缓存到哪个服务器上呢？上述图片将会被缓存在服务器A，这是为什么呢？因为从这个图片的位置开始，顺时针往前移动，最先遇到的点是服务器A，因此这个图片将缓存在服务器A上，如下图所示：

![d62ed0584f0ab7f40db8a5c8a3fa51d6.png][]

明白了吧，这就是一致性哈希算法的原理，通过将服务器和待缓存对象都映射到哈希环上，从而确定待缓存对象应该缓存到哪个服务器上；从缓存对象在环上的位置开始算，顺时针方向第一个遇到的服务器，将缓存当前对象。由于被缓存对象和服务器hash后的值是固定的，因此，只要服务器数量不变，一个图片对应的缓存服务器也一定是固定不变的。随后如果你想获取这张图片，只需要同相同的算法再算一遍，就可以确定这张图片在哪个服务器上，直接到相应的服务器上去获取相应的图片。

上面的栗子中只有一张图片，假设有四张图片，示意图如下：

![c26c13cc706ea4fe369298f060385065.png][]

如上图所示，图片1、图片2将落在服务器A上，图片3将落在服务器B上，图书4将落在服务器C上。

## 3、一致性哈希算法的优势 ##

老铁们，通过上面的描述，我想你应该理解了一致性哈希算法的原理了，不过，一致性哈希算法怎么就解决了我们上面提到的两个问题呢？我们说过，如果我们只是简单的对服务器数量求余，当服务器数量发生改变时，将会发生缓存雪崩，进而很可能造成系统奔溃，那么我们用这个一致性哈希算法，这个问题就能避免吗？让我们再来推导一次，答案自会揭晓。

假设，服务器B宕机了，现在我们需要将服务器B退役，我们将上图中的服务器B从哈希环中移除，示意图如下

![7af9cb7338ff1ca058b5a0c8dc67a3f6.png][]

在服务器B被移除前，图片3应该落在服务器B上的，现在服务器B下线了，根据一致性哈希算法的的顺时针法则，图片3将被缓存到服务器C上；因为从图片3的位置出发，顺时针走第一个遇到的服务器节点是C，简而言之，当服务器因宕机下线后，图片3的缓存位置将发生改变

![a4891b04b84cb918a3193ef17de1186a.png][]

但是呢，图片4仍然将缓存在服务器C上，图片1、图片2也将保持原位置不变缓存在服务器A上，它们的位置在服务器B移除前后都保持不变，这就是一致性哈希算法的优势。如果你使用之前的hash算法，当服务器数量发生变化时，所有的缓存都将失效，作为对比，如果你使用一致性哈希算法，同样是服务器数量发生变化，并不是所有的缓存都失效，仅仅是一部分缓存失效，前端的缓存将持续的承担流量压力，而不是将压力全部转移给后端服务。

这就是一致性哈希算法的优势。

## 4、分布不均的哈希环 ##

在介绍一致性哈希算法概念的时候，我们采用的是理想化的方式，假设3台服务器均匀的分布在哈希环上，如下图所示：

![5cf67951ff0f020f22fb1a53f317bde5.png][]

而在实际去情况中，映射关系有可能是这样的

![0cbc04bc118bb0035f47d2eb57e1597c.png][]

这明眼人一眼就能看出，如果映射关系像上图那么的不均匀，一定会导致绝大部分的缓存都落在某个服务器上，如下图所示：

![94f3131dcf12c96a2484d80e3bb37c1f.png][]

如上图所示，图1、2、3、4、6都落在A服务器上，只有图片5落在服务器B上，服务器C干脆就没有任何图片在它上面，这就导致服务器A、B、C没有被合理的充分利用；缓存分布极其不均匀，如果此时服务器A出了问题，将导致大量的缓存不可用，在极端情况下，仍然有可能导致系统崩溃，上图所示的哈希环我们称之为——哈希倾斜，那我们该如何解决哈希倾斜问题呢？一致性哈希算法用“虚拟节点”的方式来解决这个问题，让我们接着往下看。

## 5、虚拟节点 ##

好了，我们继续。因为我们只有3台服务器，当我们把服务器映射到哈希环上时，很有可能就会发生哈希倾斜，一旦发生了哈希倾斜，服务器上的缓存将分布不均；那怎么行呢！如果你想将缓存均匀的分布在3台服务器上，你就必须使这三台服务器尽可能的均匀分布在哈希环上。然而，这真正的服务器只有三台，怎么才能让它们变得更多呢？英雄所见略同，我们就是要无中生有的变出更多的服务器节点。由于没有真实的服务节点，我们只能够通过虚拟方法来复制已存在的物理节点，这些通过实际节点复制而来的节点成为虚拟节点。虚拟节点加入哈希环后的示意图如下：

![dc7e0e01e6ade807307104e174aa982d.png][]

虚拟节点在哈希环上可以看成是实际节点的副本，一个实际节点可以有多个虚拟节点。

如上图所示，服务器A/B/C都可以有一个虚拟节点，当然了，如果你喜欢，你可以创建更多的虚拟节点。在引入虚拟节点之后，缓存分布更均匀了，如上图所示，图片1、3落在服务器A，图片4、5落在服务器B，图片2、6落在服务器C，如果还不放心，你可以创建更多的虚拟节点，以便减少哈希倾斜带来的影响，虚拟节点越多，哈希环上的节点就越多，缓存就分布的越均匀。

[9b230fa270c7517efa9970b26efae25d.png]: https://img-blog.csdnimg.cn/img_convert/9b230fa270c7517efa9970b26efae25d.png
[97346f2268d5c342842e53fdf751454c.png]: https://img-blog.csdnimg.cn/img_convert/97346f2268d5c342842e53fdf751454c.png
[21310e52fbb7c10facfe284f337f034f.png]: https://img-blog.csdnimg.cn/img_convert/21310e52fbb7c10facfe284f337f034f.png
[282acde83f654ffd015503228608ba08.png]: https://img-blog.csdnimg.cn/img_convert/282acde83f654ffd015503228608ba08.png
[0092593baf2142af8cdb2d325eb6e4b1.png]: https://img-blog.csdnimg.cn/img_convert/0092593baf2142af8cdb2d325eb6e4b1.png
[d62ed0584f0ab7f40db8a5c8a3fa51d6.png]: https://img-blog.csdnimg.cn/img_convert/d62ed0584f0ab7f40db8a5c8a3fa51d6.png
[c26c13cc706ea4fe369298f060385065.png]: https://img-blog.csdnimg.cn/img_convert/c26c13cc706ea4fe369298f060385065.png
[7af9cb7338ff1ca058b5a0c8dc67a3f6.png]: https://img-blog.csdnimg.cn/img_convert/7af9cb7338ff1ca058b5a0c8dc67a3f6.png
[a4891b04b84cb918a3193ef17de1186a.png]: https://img-blog.csdnimg.cn/img_convert/a4891b04b84cb918a3193ef17de1186a.png
[5cf67951ff0f020f22fb1a53f317bde5.png]: https://img-blog.csdnimg.cn/img_convert/5cf67951ff0f020f22fb1a53f317bde5.png
[0cbc04bc118bb0035f47d2eb57e1597c.png]: https://img-blog.csdnimg.cn/img_convert/0cbc04bc118bb0035f47d2eb57e1597c.png
[94f3131dcf12c96a2484d80e3bb37c1f.png]: https://img-blog.csdnimg.cn/img_convert/94f3131dcf12c96a2484d80e3bb37c1f.png
[dc7e0e01e6ade807307104e174aa982d.png]: https://img-blog.csdnimg.cn/img_convert/dc7e0e01e6ade807307104e174aa982d.png