商城网站策划,代理记帐,佛山市专注网站建设平台,沈阳企业网站制作公司这两天看到技术群里#xff0c;有小伙伴在讨论一致性hash算法的问题#xff0c;正愁没啥写的题目就来了#xff0c;那就简单介绍下它的原理。下边我们以分布式缓存中经典场景举例#xff0c;面试中也是经常提及的一些话题#xff0c;看看什么是一致性hash算法以及它有那些…这两天看到技术群里有小伙伴在讨论一致性hash算法的问题正愁没啥写的题目就来了那就简单介绍下它的原理。下边我们以分布式缓存中经典场景举例面试中也是经常提及的一些话题看看什么是一致性hash算法以及它有那些过人之处。 构建场景
假如我们有三台缓存服务器编号node0、node1、node2现在有3000万个key希望可以将这些个key均匀的缓存到三台机器上你会想到什么方案呢
我们可能首先想到的方案是取模算法hashkey% N对key进行hash运算后取模N是机器的数量。key进行hash后的结果对3取模得到的结果一定是0、1或者2正好对应服务器node0、node1、node2存取数据直接找对应的服务器即可简单粗暴完全可以解决上述的问题。 hash的问题
取模算法虽然使用简单但对机器数量取模在集群扩容和收缩时却有一定的局限性因为在生产环境中根据业务量的大小调整服务器数量是常有的事而服务器数量N发生变化后hashkey% N计算的结果也会随之变化。 比如一个服务器节点挂了计算公式从hashkey% 3变成了hashkey% 2结果会发生变化此时想要访问一个key这个key的缓存位置大概率会发生改变那么之前缓存key的数据也会失去作用与意义。
大量缓存在同一时间失效造成缓存的雪崩进而导致整个缓存系统的不可用这基本上是不能接受的为了解决优化上述情况一致性hash算法应运而生~
那么一致性哈希算法又是如何解决上述问题的
一致性hash
一致性hash算法本质上也是一种取模算法不过不同于上边按服务器数量取模一致性hash是对固定值2^32取模。
“ IPv4的地址是4组8位2进制数组成所以用2^32可以保证每个IP地址会有唯一的映射 hash环
我们可以将这2^32个值抽象成一个圆环⭕️不得意圆的自己想个形状好理解就行圆环的正上方的点代表0顺时针排列以此类推1、2、3、4、5、6……直到2^32-1而这个由2的32次方个点组成的圆环统称为hash环。 那么这个hash环和一致性hash算法又有什么关系嘞我们还是以上边的场景为例三台缓存服务器编号node0、node1、node23000万个key。
服务器映射到hash环
这个时候计算公式就从hashkey% N 变成了hash服务器ip% 2^32使用服务器IP地址进行hash计算用哈希后的结果对2^32取模结果一定是一个0到2^32-1之间的整数而这个整数映射在hash环上的位置代表了一个服务器依次将node0、node1、node2三个缓存服务器映射到hash环上。 对象key映射到hash环
接着在将需要缓存的key对象也映射到hash环上hashkey% 2^32服务器节点和要缓存的key对象都映射到了hash环那对象key具体应该缓存到哪个服务器上呢 对象key映射到服务器
“ 从缓存对象key的位置开始沿顺时针方向遇到的第一个服务器便是当前对象将要缓存到的服务器。 因为被缓存对象与服务器hash后的值是固定的所以在服务器不变的条件下对象key必定会被缓存到固定的服务器上。根据上边的规则下图中的映射关系 key-1 - node-1 key-3 - node-2 key-4 - node-2 key-5 - node-2 key-2 - node-0 如果想要访问某个key只要使用相同的计算方式即可得知这个key被缓存在哪个服务器上了。
一致性hash的优势
我们简单了解了一致性hash的原理那它又是如何优化集群中添加节点和缩减节点普通取模算法导致的缓存服务大面积不可用的问题呢
先来看看扩容的场景假如业务量激增系统需要进行扩容增加一台服务器node-4刚好node-4被映射到node-1和node-2之间沿顺时针方向对象映射节点发现原本缓存在node-2上的对象key-4、key-5被重新映射到了node-4上而整个扩容过程中受影响的只有node-4和node-1节点之间的一小部分数据。 反之假如node-1节点宕机沿顺时针方向对象映射节点缓存在node-1上的对象key-1被重新映射到了node-4上此时受影响的数据只有node-0和node-1之间的一小部分数据。 从上边的两种情况发现当集群中服务器的数量发生改变时一致性hash算只会影响少部分的数据保证了缓存系统整体还可以对外提供服务的。
数据偏斜问题
前边为了便于理解原理画图中的node节点都很理想化的相对均匀分布但理想和实际的场景往往差别很大就比如办了个健身年卡的我只去过健身房两次还只是洗了个澡。 想要健身的你
在服务器节点数量太少的情况下很容易因为节点分布不均匀而造成数据倾斜问题如下图被缓存的对象大部分缓存在node-4服务器上导致其他节点资源浪费系统压力大部分集中在node-4节点上这样的集群是非常不健康的。 解决数据倾斜的办法也简单我们就要想办法让节点映射到hash环上时相对分布均匀一点。
一致性Hash算法引入了一个虚拟节点机制即对每个服务器节点计算出多个hash值它们都会映射到hash环上映射到这些虚拟节点的对象key最终会缓存在真实的节点上。
虚拟节点的hash计算通常可以采用对应节点的IP地址加数字编号后缀 hash10.24.23.227#1) 的方式举个例子node-1节点IP为10.24.23.227正常计算node-1的hash值。 hash10.24.23.227#1% 2^32
假设我们给node-1设置三个虚拟节点node-1#1、node-1#2、node-1#3对它们进行hash后取模。 hash10.24.23.227#1% 2^32 hash10.24.23.227#2% 2^32 hash10.24.23.227#3% 2^32
下图加入虚拟节点后原有节点在hash环上分布的就相对均匀了其余节点压力得到了分摊。 “ 但需要注意一点分配的虚拟节点个数越多映射在hash环上才会越趋于均匀节点太少的话很难看出效果 引入虚拟节点的同时也增加了新的问题要做虚拟节点和真实节点间的映射对象key-虚拟节点-实际节点之间的转换。 一致性hash的应用场景
一致性hash在分布式系统中应该是实现负载均衡的首选算法它的实现比较灵活既可以在客户端实现也可以在中间件上实现比如日常使用较多的缓存中间件memcached和redis集群都有用到它。
memcached的集群比较特殊严格来说它只能算是伪集群因为它的服务器之间不能通信请求的分发路由完全靠客户端来的计算出缓存对象应该落在哪个服务器上而它的路由算法用的就是一致性hash。 还有redis集群中hash槽的概念虽然实现不尽相同但思想万变不离其宗看完本篇的一致性hash你再去理解redis槽位就轻松多了。
其它的应用场景还有很多 RPC框架Dubbo用来选择服务提供者 分布式关系数据库分库分表数据与节点的映射关系 LVS负载均衡调度器 .....................
总结
简单的阐述了下一致性hash如果有不对的地方大家可以留言指正任何技术都不会十全十美一致性Hash算法也是有一些潜在隐患的如果Hash环上的节点数量非常庞大或者更新频繁时检索性能会比较低下而且整个分布式缓存需要一个路由服务来做负载均衡一旦路由服务挂了整个缓存也就不可用了还要考虑做高可用。
不过话说回来只要是能解决问题的都是好技术有点副作用还是可以忍受的。
