一致性哈希算法

avatar 2020年08月16日18:14:46 1 106 views

在了解一致性哈希算法之前,最好先了解一下缓存中的一个应用场景。

场景描述

假设,我们有三台缓存服务器,用于缓存图片。

我们为这三台缓存服务器编号为0号、1号、2号,现在,有3万张图片需要缓存,我们希望这些图片被均匀的缓存到这3台服务器上,以便它们能够分摊缓存的压力。

也就是说,我们希望每台服务器能够缓存1万张左右的图片,那么,我们应该怎样做呢?

假设我们使用图片名称作为访问图片的key,假设图片名称是不重复的,那么,我们可以使用如下公式,计算出图片应该存放在哪台服务器上。

hash(图片名称)% N

但是,使用上述HASH算法进行缓存时,会出现一些缺陷。

试想一下,如果现在我们新增一台服务器或者减少一台服务器,之前的图片缓存位置肯定会有很多发生变化。

由于大量缓存在同一时间失效,造成了缓存的雪崩

为了解决这些问题,一致性哈希算法诞生了。

 

一致性哈希算法的基本概念

其实,一致性哈希算法也是使用取模的方法,只是,刚才描述的取模法是对服务器的数量进行取模,而一致性哈希算法是对2^32取模

首先,我们把二的三十二次方想象成一个圆,就像钟表一样,示意图如下:

假设我们有3台缓存服务器,服务器A、服务器B、服务器C,我们使用它们各自的IP地址进行哈希计算,使用哈希后的结果对2^32取模。

可以使用如下公式示意:

hash(服务器A的IP地址) %  2^32

hash(服务器B的IP地址) %  2^32

hash(服务器C的IP地址) %  2^32

我们需要使用缓存服务器缓存图片,我们仍然使用图片的名称作为找到图片的key,那么我们使用如下公式可以将图片映射到上图中的hash环上。

hash(图片名称) %  2^32

映射后的示意图如下,下图中的橘黄色圆形表示图片

那么上图中的这个图片到底应该被缓存到哪一台服务器上呢?上图中的图片将会被缓存到服务器A上,为什么呢?因为从图片的位置开始,沿顺时针方向遇到的第一个服务器就是A服务器。所以,上图中的图片将会被缓存到服务器A上,如下图所示:

假设有四张图片需要缓存,示意图如下:

1号、2号图片将会被缓存到服务器A上,3号图片将会被缓存到服务器B上,4号图片将会被缓存到服务器C上。

 

一致性哈希算法的优点

如果简单的对服务器数量进行取模,那么当服务器数量发生变化时,会产生缓存的雪崩,从而很有可能导致系统崩溃,那么使用一致性哈希算法,能够避免这个问题吗?

假设,服务器B出现了故障,我们现在需要将服务器B移除,那么,我们将上图中的服务器B从hash环上移除即可,移除服务器B以后示意图如下。


图片3的位置会发生改变

图片1、2还是缓存在 A 服务器,图片 4 还是缓存在 C 服务器

也就是说使用一致性哈希算法时,服务器的数量如果发生改变,并不是所有缓存都会失效,而是只有部分缓存会失效。这也就是其优点。

 

hash环的偏斜

在介绍一致性哈希的概念时,我们理想化的将3台服务器均匀的映射到了hash环上。

但是现实中有时候并不是这么理想,如下图:

A、B、C 三台服务器分布严重不均匀

导致图片 1、2、3、4、6 都缓存在 A 服务器

图片 5 缓存在 B 服务器

 

虚拟节点

话接上文,由于我们只有3台服务器,当我们把服务器映射到hash环上的时候,很有可能出现hash环偏斜的情况。

当hash环偏斜以后,缓存往往会极度不均衡的分布在各服务器上。

如果想要均衡的将缓存分布到3台服务器上,最好能让这3台服务器尽量多的、均匀的出现在hash环上。

但是,真实的服务器资源只有3台,我们怎样凭空的让它们多起来呢,没错,就是凭空的让服务器节点多起来。

既然没有多余的真正的物理服务器节点,我们就只能将现有的物理节点通过虚拟的方法复制出来,这些由实际节点虚拟复制而来的节点被称为"虚拟节点",加入虚拟节点以后的hash环如下:

"虚拟节点"是"实际节点"(实际的物理服务器)在hash环上的复制品,一个实际节点可以对应多个虚拟节点。

 

从上图可以看出,A、B、C三台服务器分别虚拟出了一个虚拟节点。当然,如果你需要,也可以虚拟出更多的虚拟节点。

引入虚拟节点的概念后,缓存的分布就均衡多了,上图中,1号、3号图片被缓存在服务器A中,5号、4号图片被缓存在服务器B中,6号、2号图片被缓存在服务器C中。

如果你还不放心,可以虚拟出更多的虚拟节点,以便减小hash环偏斜所带来的影响,虚拟节点越多,hash环上的节点就越多,缓存被均匀分布的概率就越大。

 

 

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

avatar 登录者:匿名
您需要登录才能评论,可以选择注册或者QQ快速登录

     

已通过评论:1   待审核评论数:0
  1. avatar 小白

    一楼,抱楼主大腿