图解一致性哈希算法,看这文就够了!

2020-08-04 19:11 栏目:经验之谈 来源:网络整理 查看()

许多学生应该知道什么是哈希函数,他们在后端的面试和开发中会遇到“一致哈希”,那么什么是一致哈希呢?这个名字听起来很有力,但原理并不复杂。这篇文章将帮助你彻底理解一致哈希!

在进入主题之前,让我们进行一次激动人心的模拟面试。

1.模拟面试

记者:鉴于你参与了一个大型项目,并在简历中使用了分布式缓存集群,你如何实现缓存负载平衡?

孟新:我知道这个。我们使用轮询,第一个密钥给第一个存储节点,第二个密钥给第二个存储节点,依此类推。

记者:还有其他解决办法吗?

孟新:哈希函数可以用来将请求随机分配给缓存集群中的机器。

记者:你考虑过这种哈希负载平衡的可伸缩性和容错性吗?

孟新:

记者:回去等通知。

如果以上相似,你可以复制我的。

2.什么是杂凑

我们了解到哈希表在数据结构中也称为哈希表。让我们回顾一下哈希表的定义。

哈希表是一种数据结构,它根据密钥直接访问指定存储位置中的数据。通过计算关于键的函数,也称为散列函数,要查询的数据被映射到表中的某个位置以访问记录,这加快了搜索速度。这种映射函数称为“哈希函数”,存储记录的数组称为哈希表。

哈希函数可以使数据序列的访问过程更快、更有效。这是一种空时算法,通过哈希函数可以更快地定位数据元素。

下图说明了通过哈希函数将字符串映射到哈希表的过程。没错,输入字符串是用你的脸滚动键盘输入的:)

图解一致性哈希算法,看这文就够了!

常见的哈希算法包括MD5、循环冗余校验、混合哈希等。对此进行了简要介绍。

MD5算法

MD5消息摘要算法是一种广泛使用的加密散列函数,可以产生128位(16字节)的散列值。MD5算法将数据(如一段文本)转换成另一个固定长度的值,这是哈希算法的基本原理。由美国密码学家罗纳德林里弗斯特设计,于1992年出版,并在RFC 1321中规范。

循环冗余校验算法

循环冗余校验是一种哈希函数,它根据网络数据包或计算机文件等数据生成短的固定位数校验码。它是由韦斯利彼得森在1961年出版的。生成的数字在传输或存储之前被计算并附加到数据上,然后接收器检查以确定数据是否已经改变。由于该功能易于与二进制计算机硬件一起使用,易于进行数学分析,尤其擅长检测传输信道干扰引起的误差,因此得到了广泛的应用。

MurmurHash

MurmurHash是一个未加密的哈希函数,适用于一般的哈希检索操作。由奥斯汀艾波在2008年发明,有许多变体。与其他流行的哈希函数相比,murHash具有更好的随机分布特性,密钥具有很强的规律性。

该算法已经被许多开源项目使用,如lib stdc(4.6版)、Perl、nginx(不早于1.0.1版)、Rubinius、libmemcached、maatkit、Hadoop等。

常见的哈希方法

直接地址法:将关键字或关键字的线性函数值作为哈希地址。这个线性函数的定义是多种多样的,没有标准。

数字分析方法:假设关键字是基于R的数字,并且哈希表中可能出现的关键字是预先已知的,哈希地址可以由几个数字的关键字组成。

Square方法:将关键字square的中间数字作为哈希地址。通常,在选择哈希函数时,您可能不知道所有的关键字,也可能不适合选择哪个关键字,但是数字平方后的中间位数与数字的每个位数相关,因此随机分布的关键字获得的哈希地址也是随机的,取的位数由表的长度决定。

折叠方法:将关键字分成若干个位数相同的部分(最后一部分的位数可以不同),然后将这些部分的叠加和(不包括进位)作为哈希地址。

模块化方法:将关键字除以不大于哈希表长度m的数字p后的余数作为哈希地址。即hash(key)=key% p(p=M),它不仅可以直接对关键字进行模运算,还可以对关键字进行模运算,如折叠和平方运算。选择P是非常重要的,一般取质数或m。如果P选择得不好,很容易发生冲突。

3.缓存系统的负载平衡

在分布式集群缓存(如memcached cache cluster)的负载均衡实现中,缓存数据的密钥需要通过哈希函数进行哈希运算,以便缓存数据能够均匀分布到所有分布式存储节点。为了实现这种负载平衡,通常可以使用哈希算法。下图说明了这个分布式存储过程:

图解一致性哈希算法,看这文就够了!

4.常见哈希算法的负载均衡

我们之前已经介绍了各种散列方法。无论选择哪种哈希方法,在这个应用场景中,缓存的数据都应该使用哈希函数均匀地映射到服务器集群,所以我们选择一个简单的“模方法”来说明这个过程。

假设有3个服务器节点号[0-2]和6个缓存键值对号[1-6],哈希映射完成后,三个缓存数据的映射如下:

图解一致性哈希算法,看这文就够了!

每个连接平均分布到三个不同的服务器节点,看起来很完美!

然而,这种模型在分布式集群系统的负载平衡中有两个问题:

1.膨胀能力差

为了动态调整服务能力,服务节点经常需要扩展和收缩容量。例如,如果是电子商务服务,在双十一期间服务机器的数量肯定会比平时多得多,新增加的机器会使原来计算的哈希值不准确。为了达到负载平衡的效果,应该重新计算和更新哈希值,并将哈希值不一致的缓存数据迁移到更新的节点。

假设添加了一个新的服务器节点,它从原来的三个服务节点变为四个节点编号[0-3]。哈希映射如下:

哈希计算公式:关键字%节点总数=哈希节点下标

1 % 4=1

2 % 4=2

3 % 4=3

4 % 4=0

5 % 4=1

6 % 4=2

可以看出,对应于以下三个缓存键:4、5和6的存储节点都是无效的,因此有必要将这些节点的缓存数据迁移到更新的节点(费时费力),即从原始节点[1,2,0]迁移到节点[0,1,2]。迁移后的存储图如下:

图解一致性哈希算法,看这文就够了!

2.容错能力差

尽管在线环境服务节点有各种高可用性保证,但仍然存在停机的可能性,即使没有停机,也需要减少容量。停机时间和容量减少都可以归因于服务节点的删除。服务节点删除对负载平衡哈希值的影响分析如下。

假设删除了一个服务器节点,将原来的三个服务节点改为两个,节点号为[0-1],哈希映射如下:

哈希计算公式:关键字%节点总数=哈希节点下标

1 % 2=1

2 % 2=0

3 % 2=1

4 % 2=0

5 % 2=1

6 % 2=0

下图显示了当节点停机时,由通用哈希负载平衡算法导致的缓存数据迁移分布:

图解一致性哈希算法,看这文就够了!

从图中可以看出,在本例中,只删除了一个服务节点,这也导致了哈希值的大规模更新,哈希值的更新也意味着节点缓存数据的迁移(缓存数据表示心脏非常疲劳)。

5.一致性哈希算法负载均衡

正是由于普通哈希算法实现的缓存负载均衡的可扩展性和容错性差,我们引入了一致性哈希算法。什么是一致哈希?让我们首先看看维基上一致哈希的定义

统一哈希是由麻省理工学院的大卫卡尔格和他的合作者提出的,现在这个想法已经扩展到其他领域。在这篇发表于1997年的学术论文中,本文介绍了一致哈希算法如何应用于具有可变用户的分布式网络服务。一致哈希还可以用来实现健壮的缓存,以减少大型网络应用程序中部分系统故障的负面影响。

这篇描述一致散列的论文发表于1997年。阅读无障碍的学生可以直接看大榭的论文,有更深的理解。附上论文的下载链接:http://citeseerx.ist.psu.edu/viewdoc/summary? doi=10 . 1 . 1 . 147 . 1879

图解一致性哈希算法,看这文就够了!

用一句话来概括一致性哈希:它是普通模哈希算法的改进版本,哈希函数的计算方法不变,只是通过构造循环哈希空间来代替普通的线性哈希空间。具体做法如下:

首先,选择一个足够大的哈希空间(一般为0 ~ 2 32)来形成一个哈希环。

图解一致性哈希算法,看这文就够了!

然后,为缓存群集中的每个存储服务器节点计算哈希值,哈希值可以通过使用服务器的IP或主机名来计算,并且计算出的哈希值是服务节点在哈希环上的位置。

图解一致性哈希算法,看这文就够了!

最后,为每个要存储的数据密钥计算一次哈希值,并且计算的哈希值也被映射到环。数据存储位置是沿顺时针方向找到的环上的第一个节点。下图说明了节点存储的数据,我们下面的描述也基于当前的存储情况。

图解一致性哈希算法,看这文就够了!

在原则的最后,让我们看看为什么这个设计可以解决普通散列法的上述两个问题。

扩展能力改进

如前所述,当普通哈希算法需要扩展容量和增加服务节点时,会导致原油哈希映射的大规模失败。现在,让我们看看一致哈希是如何解决这个问题的。

如下图所示,当节点node3被添加到缓存服务集群时,只有与key3对应的数据值3会受到影响。此时,只需将值3从原始节点节点0迁移到新添加的节点节点3,其他节点中存储的数据将保持不变。

图解一致性哈希算法,看这文就够了!

容错能力得到提高

当一个服务节点在一个通用哈希算法失效时离线,它也会导致原始哈希映射的大面积失效。无效映射会触发数据迁移,这会影响缓存服务性能,并且容错能力不足。让我们看看一致性哈希如何提高容错能力。

如下图所示,假设节点2在关闭时离线,只需顺时针选择一个新的存储节点节点0即可存储节点2中原来存储的数据值2和值5,不会影响其他节点的数据。一致哈希可以控制顺时针相邻节点间节点停机的影响,避免对整个集群的影响。

图解一致性哈希算法,看这文就够了!

6.一致性哈希优化

存在的问题

上面展示了一致哈希如何解决普通哈希的扩展和容错问题。原理简单,在理想条件下也能很好地工作。然而,在实际使用中仍有一些实际问题需要考虑,下面将对此进行详细分析。

数据倾斜

想象一下,如果缓存集群中只有几个服务节点,就像我们例子中的三个节点一样,并且哈希环的空间非常大(一般为0 ~ 2 ^ 32),这会导致什么问题?

一种可能的情况是,聚集在一起的服务节点的散列值较少,例如,如下图所示,节点0、节点1和节点2聚集在一起,并且缓存数据的密钥散列被映射到节点2的顺时针方向。顺时针搜索存储节点将导致所有数据都存储在节点0上,这将给单个节点带来很大压力!这种情况称为数据不对称。

图解一致性哈希算法,看这文就够了!

节点雪崩

数据不对称和节点停机都可能导致缓存雪崩。

以前面的数据倾斜为例。数据倾斜导致所有缓存的数据都到达节点0,这可能导致节点0被淹没和挤压,节点0关闭,数据到达节点1并击败节点1传递到节点2。此时,断层就像雪崩中的滚雪球。

在另一种情况下,节点由于各种原因离线。例如,如下图所示,当node2离线时,原本在node2中的数据被压到node0,在数据量非常大的情况下,也可能导致节点雪崩。具体过程就像刚才的分析。

总之,由于连锁反应,整个缓存集群不可用,这被称为节点雪崩。

图解一致性哈希算法,看这文就够了!

虚拟节点

如何解决上述两个棘手的问题?它可以通过“虚拟节点”来解决。

所谓的虚拟节点是将散列环上的几个虚拟角色节点从原来的单个物理节点虚拟化,这些虚拟角色节点被称为“虚拟节点”。事实上,在化身节点上命中的数据也被映射到相应的物理节点,使得物理节点可以通过虚拟节点均匀地分散在散列环的每个部分中,从而解决了数据偏斜的问题。

由于虚拟节点分散在哈希环的各个部分,当一个节点离线时,其存储的数据将平均分布到其他节点,避免了单个节点突然承受压力而导致的节点雪崩。

下图显示了虚拟节点的哈希环分布,左侧为没有虚拟节点的节点分布,右侧两个绿色背景的节点为节点0的虚拟节点;红色背景的节点1是节点1的虚拟节点。

图解一致性哈希算法,看这文就够了!

7.总结

本文首先介绍了什么是哈希算法、常用哈希算法和常用哈希方法,然后阐述了基于常用哈希算法的缓存负载均衡实现,并举例说明了常用算法在可扩展性和容错性方面存在的问题。

为了解决常用算法的可扩展性和容错性问题,引入了一致性哈希算法,并举例说明和分析了如何提高可扩展性和容错性。最后,粗糙一致哈希算法还存在数据倾斜和节点雪崩的问题。本文阐述了如何利用虚拟节点优化一致性哈希算法,解决数据倾斜和雪崩问题。到目前为止,你已经知道了一致的散列吗?

一致性哈希并不难,但人们经常观察到,就像布鲁姆过滤算法一样,从未听说过它的人认为它非常高端,所以研究它也是一样的事情,所以有必要拥有广泛的知识来击败面试官!

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发