精选文章 图解一致性哈希算法,全网(小区局域网)最通俗易懂

图解一致性哈希算法,全网(小区局域网)最通俗易懂

作者:程序员资源社区 时间: 2020-08-03 12:10:00
程序员资源社区 2020-08-03 12:10:00

好久不见小伙伴们,最近都快忙晕了,后端技术学堂差点停课,不过还是抽时间写了这篇文章带大家一起学习一致性哈希算法。

很多同学应该都知道什么是哈希函数,在后端面试和开发中会遇到「一致性哈希」,那么什么是一致性哈希呢?名字听起来很厉害的样子,其实原理并不复杂,这篇文章带你彻底搞懂一致性哈希!

进入主题前,先来一场紧张刺激的模拟面试吧。

模拟面试

图解一致性哈希算法,全网(小区局域网)最通俗易懂1

面试官:看你简历上写参与了一个大型项目,用到了分布式缓存集群,那你说说你们是怎么做缓存负载均衡?

萌新 :这个我知道,我们用的是轮询方式,第一个key 给第一个存储节点,第二个 key 给第二个,以此类推。

面试官:还有其他解决方案吗?

萌新:可以用哈希函数,把请求打散随机分配到缓存集群内机器。

面试官:考虑过这种哈希方式负载均衡的扩展性和容错性吗?

萌新:...

面试官:回去等通知吧。

以上如有雷同,算你抄我的。

什么是哈希

数据结构中我们学习过哈希表也称为散列表,我们来回顾下散列表的定义。

散列表,是根据键直接访问在指定储存位置数据的数据结构。通过计算一个关于键的函数也称为哈希函数,将所需查询的数据映射到表中一个位置来访问记录,加快查找速度。这个映射函数称做「散列函数」,存放记录的数组称做散列表。

散列函数能使对一个数据序列的访问过程更加迅速有效,是一种空间换时间的算法,通过散列函数数据元素将被更快定位。

下图示意了字符串经过哈希函数映射到哈希表的过程。没错,输入字符串是用脸滚键盘打出来的:)

图解一致性哈希算法,全网(小区局域网)最通俗易懂2
哈希示意图.png

常见的哈希算法有MD5、CRC 、MurmurHash 等算法,简单介绍一下。

MD5算法

MD5消息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hash value),MD5算法将数据(如一段文字)运算变为另一固定长度值,是散列算法的基础原理。由美国密码学家 Ronald Linn Rivest设计,于1992年公开并在 RFC 1321 中被加以规范。

CRC算法

循环冗余校验(Cyclic Redundancy Check)是一种根据网络数据包或电脑文件等数据,产生简短固定位数校验码的一种散列函数,由 W. Wesley Peterson 于1961年发表。生成的数字在传输或者存储之前计算出来并且附加到数据后面,然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误,因此获得广泛应用。

MurmurHash

MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。由 Austin Appleby 在2008年发明,并出现了多个变种,与其它流行的哈希函数相比,对于规律性较强的键,MurmurHash的随机分布特征表现更良好。

这个算法已经被很多开源项目使用,比如libstdc++ (4.6版)、Perl、nginx (不早于1.0.1版)、Rubinius、 libmemcached、maatkit、Hadoop等。

常见散列方法

  • 直接定址法:取关键字或关键字的某个线性函数值为散列地址,这个线性函数的定义多种多样,没有标准。

  • 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。

  • 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的,取的位数由表长决定。

  • 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。

  • 取模法:取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(key) = key % p(p<= M),不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对 p 的选择很重要,一般取素数或 m,若 p 选择不好,容易产生冲突。

缓存系统负载均衡

在分布式集群缓存的负载均衡实现中,比如 memcached 缓存集群,需要把缓存数据的 key 利用哈希函数散列,这样缓存数据能够均匀分布到各个分布式存储节点上,要实现这样的负载均衡一般可以用哈希算法来实现。下图演示了这一分布式存储过程:

图解一致性哈希算法,全网(小区局域网)最通俗易懂3
分布式缓存散列存储示意图

普通哈希算法负载均衡

前面我们介绍过各种散列方法,不管是选择上述哪种散列方法,在这个应用场景下,都是要把缓存数据利用哈希函数均匀的映射到服务器集群上,我们就选择简单的「取模法」来说明这个过程。

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

哈希计算公式:key % 节点总数 = Hash节点下标
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
5 % 3 = 2
6 % 3 = 0
图解一致性哈希算法,全网(小区局域网)最通俗易懂4
缓存哈希实例

每个连接都均匀的分散到了三个不同的服务器节点上,看起来很完美!

但是,在分布式集群系统的负载均衡实现上,这种模型有两个问题:

1. 扩展能力差

为了动态调节服务能力,服务节点经常需要扩容缩容。打个比方,如果是电商服务,双十一期间的服务机器数量肯定要比平常大很多,新加进来的机器会使原来计算的哈希值不准确,为了达到负载均衡的效果,要重新计算并更新哈希值,对于更新后哈希值不一致的缓存数据,要迁移到更新后的节点上去。

假设新增了 1 个服务器节点,由原来的 3 个服务节点变成 4 个节点编号 [0 - 3],哈希映射情况如下:

哈希计算公式:key % 节点总数 = Hash节点下标
1 % 4 = 1
2 % 4 = 2
3 % 4 = 3
4 % 4 = 0
5 % 4 = 1
6 % 4 = 2

可以看到后面三个缓存 key :4、5、6 对应的存储节点全部失效了,这就需要把这几个节点的缓存数据迁移到更新后的节点上 (费时费力) ,也就是由原来的节点 [1, 2, 0] 迁移到节点 [0, 1, 2],迁移后存储示意图如下:

图解一致性哈希算法,全网(小区局域网)最通俗易懂5
缓存哈希扩展性示意图

2. 容错能力不佳

线上环境服务节点虽然有各种高可用性保证,但还是是有宕机的可能,即使没有宕机也有缩容的需求。不管是宕机和缩容都可以归结为服务节点删除的情况,下面分析下服务节点删除对负载均衡哈希值的影响。

假设删除 1 个服务器节点,由最初的 3 个服务节点变成 2 个,节点编号 [0 - 1],哈希映射情况如下:

哈希计算公式:key % 节点总数 = Hash节点下标
1 % 2 = 1
2 % 2 = 0
3 % 2 = 1
4 % 2 = 0
5 % 2 = 1
6 % 2 = 0

下图展示普通哈希负载均衡算法在一个节点宕机时候,导致的的缓存数据迁移分布情况:

图解一致性哈希算法,全网(小区局域网)最通俗易懂6
缓存哈希容错性示意图

如图所见,在这个例子中,仅仅删除了一个服务节点,也导致了哈希值的大面积更新,哈希值的更新也是意味着节点缓存数据的迁移(缓存数据表示心好累)。

一致性哈希算法负载均衡

正是由于普通哈希算法实现的缓存负载均衡存在扩展能力和容错能力差问题,所以我们引入一致性哈希算法,那么什么是一致性哈希呢?先来看下wiki上对一致性Hash的定义

一致哈希由 MIT 的 David Karger 及其合作者提出,现在这一思想已经扩展到其它领域。在这篇1997年发表的学术论文中介绍了一致哈希如何应用于用户易变的分布式Web服务中。一致哈希也可用于实现健壮缓存来减少大型Web应用中系统部分失效带来的负面影响。

这篇描述一致性哈希的论文发表于1997年,阅读无障碍的同学可以直接看看大佬的论文理解更深刻,附上论文下载链接:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879

图解一致性哈希算法,全网(小区局域网)最通俗易懂7
一致性hash论文

一句话概括一致性哈希:就是普通取模哈希算法的改良版,哈希函数计算方法不变,只不过是通过构建环状的 Hash 空间代替普通的线性 Hash 空间。具体做法如下:

首先,选择一个足够大的Hash空间(一般是 0 ~ 2^32)构成一个哈希环。

图解一致性哈希算法,全网(小区局域网)最通俗易懂8
一致性哈希环

然后,对于缓存集群内的每个存储服务器节点计算 Hash 值,可以用服务器的 IP 或 主机名计算得到哈希值,计算得到的哈希值就是服务节点在 Hash 环上的位置。

图解一致性哈希算法,全网(小区局域网)最通俗易懂9
节点哈希

最后,对每个需要存储的数据 key 同样也计算一次哈希值,计算之后的哈希也映射到环上,数据存储的位置是沿顺时针的方向找到的环上的第一个节点。下图举例展示了节点存储的数据情况,我们下面的说明也是基于目前的存储情况来展开。

图解一致性哈希算法,全网(小区局域网)最通俗易懂10
image

原理讲完了,来看看为什么这样的设计能解决上面普通哈希的两个问题

扩展能力提升

前面我们分析过,普通哈希算法当需要扩容增加服务节点的时候,会导致原油哈希映射大面积失效。现在,我们来看下一致性哈希是如何解决这个问题的。

如下图所示,当缓存服务集群要新增一个节点node3时,受影响的只有 key3 对应的数据 value3,此时只需把 value3 由原来的节点 node0 迁移到新增节点 node3 即可,其余节点存储的数据保持不动

图解一致性哈希算法,全网(小区局域网)最通俗易懂11
一致性哈希-扩展节点

容错能力提升

普通哈希算法当某一服务节点宕机下线,也会导致原来哈希映射的大面积失效,失效的映射触发数据迁移影响缓存服务性能,容错能力不足。一起来看下一致性哈希是如何提升容错能力的。

如下图所示,假设 node2 节点宕机下线,则原来存储于 node2 的数据 value2 和 value5 ,只需按顺时针方向选择新的存储节点 node0 存放即可,不会对其他节点数据产生影响。一致性哈希能把节点宕机造成的影响控制在顺时针相邻节点之间,避免对整个集群造成影响

图解一致性哈希算法,全网(小区局域网)最通俗易懂12
一致性哈希-删除节点

一致性哈希优化

存在的问题

上面展示了一致性哈希如何解决普通哈希的扩展和容错问题,原理比较简单,在理想情况下可以良好运行,但在实际使用中还有一些实际问题需要考虑,下面具体分析。

数据倾斜

试想一下若缓存集群内的服务节点比较少,就像我们例子中的三个节点,而哈希环的空间又有很大(一般是 0 ~ 2^32),这会导致什么问题呢?

可能的一种情况是,较少的服务节点哈希值聚集在一起,比如下图所示这种情况 node0 、node1、node2 聚集在一起,缓存数据的 key 哈希都映射到 node2 的顺时针方向,数据按顺时针寻找存储节点就导致全都存储到 node0 上去,给单个节点很大的压力!这种情况称为数据倾斜

图解一致性哈希算法,全网(小区局域网)最通俗易懂13
一致性哈希-数据倾斜

节点雪崩

数据倾斜和节点宕机都可能会导致缓存雪崩。

图解一致性哈希算法,全网(小区局域网)最通俗易懂14
雪崩

拿前面数据倾斜的示例来说,数据倾斜导致所有缓存数据都打到 node0 上面,有可能会导致 node0 不堪重负被压垮了,node0 宕机,数据又都打到 node1 上面把 node1 也打垮了,node1 也被打趴传递给 node2,这时候故障就像像雪崩时滚雪球一样越滚越大

还有一种情况是节点由于各种原因宕机下线。比如下图所示的节点 node2 下线导致原本在node2 的数据压到 node0 , 在数据量特别大的情况下也可能导致节点雪崩,具体过程就像刚才的分析一样。

总之,连锁反应导致的整个缓存集群不可用,就称为节点雪崩

图解一致性哈希算法,全网(小区局域网)最通俗易懂15
一致性哈希-节点雪崩

虚拟节点

那该如何解决上述两个棘手的问题呢?可以通过「虚拟节点」的方式解决。

所谓虚拟节点,就是对原来单一的物理节点在哈希环上虚拟出几个它的分身节点,这些分身节点称为「虚拟节点」。打到分身节点上的数据实际上也是映射到分身对应的物理节点上,这样一个物理节点可以通过虚拟节点的方式均匀分散在哈希环的各个部分,解决了数据倾斜问题

由于虚拟节点分散在哈希环各个部分,当某个节点宕机下线,他所存储的数据会被均匀分配给其他各个节点,避免对单一节点突发压力导致的节点雪崩问题。

下图展示了虚拟节点的哈希环分布,其中左边是没做虚拟节点情况下的节点分布,右边背景色绿色两个的 node0 节点是 node0 节点的虚拟节点;背景色红色的 node1 节点是 node1 的虚拟节点。

图解一致性哈希算法,全网(小区局域网)最通俗易懂16
一致性哈希-虚拟节点

总结一下

本文首先介绍了什么是哈希算法和常见的哈希算法,以及常见散列方式,接着说明基于普通哈希算法的缓存负载均衡实现,并举例说明普通算法的扩展性和容错性方便存在的问题。

为了解决普通算法的扩展性和容错性问题引入一致性哈希算法,图解和举例分析了一致性哈希是如何提高扩展性和容错性。最后粗糙的一致性哈希算法也存在数据倾斜和节点雪崩的问题,讲解了如何利用虚拟节点优化一致性哈希算法,解决数据倾斜和雪崩问题。至此,一致性哈希你学会了吗?

再聊两句(求三连)

一致性哈希这个知识点不难,但是经常会考察到,就像布隆过滤器算法一样,没听过的人觉得很高端,研究一下也就那么一回事,所以知识面要宽才能吊打面试官啊同学们!

感谢各位的阅读,文章的目的是分享对知识的理解,技术类文章我都会反复求证以求最大程度保证准确性,若文中出现明显纰漏也欢迎指出,我们一起在探讨中学习。

如果觉得文章写的还行,对你有所帮助,不要白票 lemon,动动手指点个「在看」或「分享」是对我持续创作的最大支持

图解一致性哈希算法,全网(小区局域网)最通俗易懂17

今天的技术分享就到这里,我们下期再见。

精选好文

30 张图解 | 高频面试知识点总结:面试官问我高并发服务模型哪家强?

面试官:换人!他连进程线程协程这几个特点都说不出

面试都在问的微服务,一文带你彻底搞懂!

面试官:你说对MySQL事务很熟?那我问你10个问题

手把手教你配置VS Code远程开发工具,工作效率提升N倍

带你学够浪:Go基础系列-环境配置和 Hello world

关注我的公众号「后端技术学堂」

带你一起学编程

回复「资源」送你编程学习大礼包

包括3GB的编程「学习资源」

图解一致性哈希算法,全网(小区局域网)最通俗易懂18

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:中国耳机能否把AirPods拉下铁王座,全看一颗“芯”

下一篇:为什么美国程序员不用加班,而中国程序员就只能996?

您可能感兴趣

  • Next.js 9.5 发布:支持 Webpack 5

    作者 | Next.js 团队 译者 | 王强 策划 | 李俊辰 Next.js 9.5 发布,具体有这些内容。 Next.js 9.5 今天正式发布了,其改进包括: 稳定的增量静态再生 :部署后以毫秒为单位重建静态页面 可自定义的基本路径 :在域的子路径上轻松托管 Next.js 项目 支持重写、重定向和标头 :重写虚拟 URL,重定向旧 URL,向静态页面添加标头 URL 中的可选尾斜杠...

  • 中国耳机能否把AirPods拉下铁王座,全看一颗“芯”

    作者|茜茜 编辑|猛哥 1853年,犹太青年李维斯和当时的许多美国人一样,满怀梦想地踏上了西部淘金之旅。 很遗憾,他去晚了,到处都是人,还被抢地盘的恶棍们给揍了一顿。 李维斯很快从欺辱中恢复过来,他发现淘金人的衣服很容易磨破,而西部到处都是废弃的帐篷,如果把这些帐篷缝制成裤子,肯定抗穿耐磨。就这样,他缝制了世界上第一条牛仔裤。从此开创了他的牛仔裤王国。 世上的事情就是这么不可思议。 150年...

  • 如何基于 Electron 开发跨终端的应用

    自我介绍 欢迎大家来到今天的早早聊跨端跨栈专场,今天我分享的主题是《如何基于 Electron 开发跨终端的应用》。先做一下自我介绍,我叫逯子洋,17 年加入政采云,目前主要负责政采云前端工程化平台敦煌以及政采云电子招投标客户端的建设。这边是我们团队的微信公众号,大家如果想对我们团队有更多的了解,可以关注一下我们的公众号。 首先我们分享的第一块叫端的延展。不知道大家对这张图熟不熟悉,前段时间...

  • JAVA面试(全)

    Java 八大基本数据类型 八大基本类型 Byte,short,long,int,double,float,boolean,char 占用大小及其长度 数据类型 空间(字节B) 取值范围 byte 1 -2^7 ~ 2^7-1 short 2 -2^15~ 2^15-1 char 2 0 ~ 2^16-1 char无需符号位 int 4 -2^31 ~ 2^31-1 float 4 -2^3...

  • 人工智能那么火~如今AI的应用场景都有哪些?

    作者:新智元 链接:https://www.zhihu.com/question/282715644/answer/1329782546 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 【未来5年AI应用报告】谷歌、DeepMind、英伟达科学家支招企业AI应用 ReWork的一份最新AI落地应用报告,阐述了企业该如何使用AI技术。谷歌的Ian GoodFe...

  • 工业界如何解决NER问题?12个trick,与你分享~

    NER是一个已经解决了的问题吗?或许,一切才刚刚开始。 例如,面对下面笔者在工作中遇到的12个关于NER的系列问题,你有什么好的trick呢?不着急,让我们通过本篇文章,逐一解答~ Q1、如何快速有效地提升NER性能(非模型迭代)? Q2、如何在模型层面提升NER性能? Q3、如何构建引入词汇信息(词向量)的NER? Q4、如何解决NER实体span过长的问题? Q5、如何客观看待BERT在...

  • 新职业教育的三节课,凭什么做到今天这样

    历时7天、翻遍15个平台渠道、访谈25位参与课程的从业者、挖掘了136条推文的标题和内容,我们得到了12500字的拆解。可以点击右上角☝:收藏、分享、在看,不用担心看一半,找不到文章。 本文信息公开来源:三节课官方公众号、虎嗅网、36氪、深网、东方财富网、新榜、知乎、简书、增长黑盒、短书··· 我们认为,这可能比任何官方复盘更能诠释:「三节课」是如何在3年内,做到互联网职业教育(Almost...

  • 《重新定义公司》读书笔记

    激励偏向的是事成之后的利益分享,而赋能强调的,是激起创意人的兴趣与动力,给予挑战。唯有发自内心的志趣,才能激发持续的创造,命令则不适用于他们。因此,组织的职能不再是分派任务和监工,而更多的是让员工的专长、兴趣和客户的问题有更好的匹配,这往往要求更多的员工自主性、更高的流动性和更灵活的组织。我们甚至可以说,是员工使用了组织的公共服务,而不是公司雇用了员工。两者的根本关系发生了颠倒。 年少时,第...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。