共计 2508 个字符,预计需要花费 7 分钟才能阅读完成。
本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore
微信公众号:贝塔学 Java
前言
在之前写了两篇对于缓存的文章《万字长文聊缓存(上)- http 缓存》《万字长文聊缓存(下)- 利用级缓存》,谈到缓存不说一下一致性 Hash 算法那就是在耍流氓。
分布式缓存集群的拜访模型
当初通常应用 Redis 来做分布式缓存,上面咱们就以 Redis 为例:
如果以后咱们零碎的业务倒退很快,须要缓存的数据很多,所以咱们做了一个由三组主从复制的 redis 组成的高可用的 redis 集群,如何将申请路由的不同的 redis 集群上,这是咱们须要思考的,罕用的路由算法:
随机算法:每次将申请随机的发送到其中一组 Redis 集群中,这种算法的益处是申请会被平均的散发到每组 Redis 集群上;毛病也很显著,因为随机散发申请,为了进步缓存的命中率,所以同一份数据须要在每组集群中都存在,这样就会造成了数据的冗余,节约了存储空间
Hash 算法 :针对随机算法的问题,咱们能够思考 Hash 算法,举例:
当初有三组 redis 集群,咱们能够对每次缓存 key 的 hash 值取模,公式:index=hash(key) % 3
,index 的值就对应着 3 组集群,这样就能够保障同一个申请每次都被散发到同一个 redis 集群上,无需对数据做冗余,完满的解决了方才随机算法的毛病;
然而 hash 算法也有毛病:对于容错性和伸缩性反对很差,举例:当咱们三组 redis 集群中其中一组节点宕机了,那么此时的 redis 集群中可用的数量变成了 2,公式变成了index=hash(key) % 2
,所有数据缓存的节点地位就产生了变动,造成缓存的命中率直线降落;
同理,当咱们须要扩大一组新的 redis 机器,计算的公式index=hash(key) % 4
,大量的 key 会被从新定位到其余服务器,也会造成缓存的命中率降落。
为了解决 hash 算法容错性和伸缩性的问题,一致性 hash 算法由此而生~
一致性哈希算法
具体的算法过程
- 先结构一个长度为 2^32- 1 的整数环(称为一致性 hash 环),而后给每组 redis 集群命名,依据名字的 hash 值计算出每组集群应该放在什么地位
- 依据缓存数据的 key 计算出 hash 值,计算出进去的 hash 值同样也散布在一致性 hash 环上; 如果当初有 5 个数据须要缓存对应的 key 别离为 key1、key2、key3、key4、key5,计算 hash 值之后的分部如下图
- 而后顺着 hash 环顺时针方向查找 reids 集群,把数据寄存到最近的集群上
最初所有 key4、key5 寄存在了集群 2,key1、key3 寄存在了集群 1,key2 寄存在了集群 3
容错性
还是持续沿用下面的例子,咱们来看下一致性哈希算法的容错性如何呢?如果其中 集群 1 跪了,那么影响的数据只有 key1 和 key3,其余数据寄存的地位不受影响;当再次缓存 key1、key3 的时候依据顺时针查找,会把数据寄存到集群 3 下面
伸缩性
如果咱们须要在以后的根底上再增加一组 redis 集群 4,依据名字 hash 之后的地位在集群 1 和集群 2 之间
新加 redis 集群 4 之后影响的只有 key1 数据,其余数据不受影响。
数据歪斜问题
通过容错性、伸缩性的验证证实了一致性哈希算法的确能解决 Hash 算法的问题,然而当初的算法就是完满的吗?让咱们持续来看方才容错性的例子,退出集群 1 跪了,那么原来落在集群 1 上的所有数据会间接落在集群 3 下面,如果说每组 redis 集群的配置都是一样的,那么集群 3 的压力会增大,数据分布不平均造成数据歪斜问题。
怎么搞呢?
歪果仁的脑子就是好使,给的解决方案就是加一层虚构层,如果每组集群都调配了 2 个虚构节点
集群 | 虚构节点 |
---|---|
集群 1 | vnode1, vnode2 |
集群 2 | vnode3, vnode4 |
集群 3 | vnode5, vnode6 |
接下来就是把虚构节点放入到一致性 hash 环上,在缓存数据的时候依据顺时针查找虚构节点,在依据虚构节点的和理论集群的对应关系把数据寄存到 redis 集群,这样数据就会平均的散布到各组集群中。
这时候如果有一组 redis 集群呈现了问题,那么这组集群下面的 key 会绝对平均的摊派到其余集群上。
从下面的后果来看,只有每组集群对应的虚构节点越多,那么各个物理集群的数据分布越平均,当新减少或者缩小物理集群影响也会最小,然而如果虚构节点太多会影响查找的性能,太少数据又会不平均,那么多少适合呢?依据一些大神的教训给出的倡议是 150 个虚构节点。
一致性 Hash 算法 Java 版实现
实现思路:在每次增加物理节点的时候,依据物理节点的名字生成虚构节点的名字,把虚构节点的名字求 hash 值,而后把 hash 值作为 key,物理节点作为 value 寄存到 Map 中;这里咱们抉择应用 TreeMap,因为须要 key 是程序的存储;在计算数据 key 须要寄存到哪个物理节点时,先计算出 key 的 hash 值,而后调用 TreeMap.tailMap()返回比 hash 值大的 map 子集,如果子集为空就须要把 TreeMap 的第一个元素返回,如果不为空,那么取子集中的第一个元素。
不扯废话,间接上代码,No BB . Show me the code
外围代码:
测试代码:
- 测试删除节点 node3,比照命中率影响了多少 增加如下代码:
执行后果:
- 测试增加节点 node5,比照命中率影响了多少 增加如下代码:
执行后果:
其余应用场景
看上图,在 Nginx 申请的散发过程中,为了让利用本地的缓存命中率最高,咱们心愿依据申请的 URL 或者 URL 参数将雷同的申请转发到同一个应用服务器中,这个时候也能够抉择应用一致性 hash 算法。具体配置能够参考官网文档:
https://www.nginx.com/resources/wiki/modules/consistent_hash/
写到最初(点关注,不迷路)
文中或者会存在或多或少的有余、谬误之处,有倡议或者意见也十分欢送大家在评论交换。
最初,白嫖不好,创作不易 ,心愿敌人们能够 点赞评论关注 三连,因为这些就是我分享的全副能源起源????
原创不易 转载请注明出处:https://mp.weixin.qq.com/s/eCxGPqrfIeFY_E_CnFRfMw