一致性hash算法java版实现(代码片段)

Silently9527 Silently9527     2022-12-10     223

关键词:

前言

在之前写了两篇关于缓存的文章《万字长文聊缓存(上)- 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算法由此而生~

一致性哈希算法

具体的算法过程

  1. 先构造一个长度为2^32-1的整数环(称为一致性hash环),然后给每组redis集群命名,根据名字的hash值计算出每组集群应该放在什么位置

  1. 根据缓存数据的key计算出hash值,计算出出来的hash值同样也分布在一致性hash环上; 假如现在有5个数据需要缓存对应的key分别为key1、key2、key3、key4、key5,计算hash值之后的分部如下图

  1. 然后顺着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个虚拟节点

集群虚拟节点
集群1vnode1, vnode2
集群2vnode3, vnode4
集群3vnode5, 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

核心代码:

测试代码:

  1. 测试删除节点node3,对比命中率影响了多少 添加如下代码:

执行结果:

  1. 测试添加节点node5,对比命中率影响了多少 添加如下代码:

执行结果:

其他使用场景

看上图,在Nginx请求的分发过程中,为了让应用本地的缓存命中率最高,我们希望根据请求的URL或者URL参数将相同的请求转发到同一个应用服务器中,这个时候也可以选择使用一致性hash算法。具体配置可以参考官方文档:
https://www.nginx.com/resources/wiki/modules/consistent_hash/


写到最后(点关注,不迷路)

文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。

最后,白嫖不好,创作不易,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源

算法技术专题如何用java实现一致性hash算法(consistenthashing)(上)(代码片段)

一致性hash的历史【ConsistentHashing算法】早在1997年就在论文Consistenthashingandrandomtrees中被提出,目前在cache系统中应用越来越广泛;一致性hash的目的一致性哈希算法是分布式系统中常用的算法,一致性哈希算法解决了普... 查看详情

手撸一致性hash算法(java实现)(代码片段)

正文在下面,先打个广告:一、一致性Hash(ConsistentHashing)原理剖析引入一致性哈希算法是分布式系统中常用的算法。一致性哈希算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量... 查看详情

对一致性hash算法,java代码实现的深入研究

一致性Hash算法关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了详细的解读。算法的具体原理这里再次贴... 查看详情

对一致性hash算法,java代码实现的深入研究

一致性Hash算法关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法和一致性Hash算法的算法原理做了详细的解读。算法的具体原理这里再次贴... 查看详情

对一致性hash算法,java代码实现的深入研究

原文:http://www.cnblogs.com/xrq730/p/5186728.html一致性Hash算法关于一致性Hash算法,在我之前的博文中已经有多次提到了,MemCache超详细解读一文中"一致性Hash算法"部分,对于为什么要使用一致性Hash算法、一致性Hash算法的算法原理做了... 查看详情

一致性hash算法实现(伪码)(代码片段)

一致性Hash算法原理参考此博客,介绍的比较详细:https://www.cnblogs.com/lpfuture/p/5796398.html预设场景:所有请求过来,会根据一致性hash算法,选择一个服务器转发出去,一致性hash算法获取到的是服务器的ip。假定节点存储结构如下... 查看详情

简陋版一致性hash算法实现

1publicfunctionhashAction(){2$server_list=range(14,114);3$server_slot=$this->hashAri($server_list);4$key_list=range(1,100000);5$key_slot=$this->hashAri($key_list);67//分配位子8$result=$this->hash 查看详情

一致性hash算法原理总结(代码片段)

作者:kylinkzhang,腾讯CSIG后台开发工程师一致性Hash算法是解决分布式缓存等问题的一种算法,本文介绍了一致性Hash算法的原理,并给出了一种实现和实际运用的案例;一致性Hash算法背景考虑这么一种场景ÿ... 查看详情

一致性hash算法深入探究(代码片段)

...hash,打破了原始的设计初衷,怎么解决呢?一致性h 查看详情

一致性hash算法原理,java实现,及用途

学习记录:一致性Hash算法原理及java实现:https://blog.csdn.net/suifeng629/article/details/81567777一致性Hash算法介绍,原理,及使用场景:https://blog.csdn.net/cbmljs/article/details/88021598纯转载,侵删 查看详情

基于murmurhash+list实现一致性hash(代码片段)

一致性Hash原理这里不再介绍了,下面是一个简单版的实现方案。1、MurmurHashUtilspackagecom.jane.pos.sync.utils;importjava.io.UnsupportedEncodingException;importjava.math.BigDecimal;importjava.nio.ByteBuffer;importjava.nio.ByteOrder; 查看详情

架构实践使用golang实现一致性hash算法代码

【架构实践】使用golang实现一致性Hash算法代码文章目录【架构实践】使用golang实现一致性Hash算法代码分布式系统中的一致性Hash算法具体是什么?再详细一点讲讲一致性Hash算法存在的一些问题一致性Hash算法都有哪些实际的应用... 查看详情

一致性hash算法及java实现

一致性hash算法是分布式中一个常用且好用的分片算法、或者数据库分库分表算法。现在的互联网服务架构中,为避免单点故障、提升处理效率、横向扩展等原因,分布式系统已经成为了居家旅行必备的部署模式,所以也产出了... 查看详情

一致性hash算法consistenthashing(代码片段)

一致性hash算法ConsistentHashing对于原有hash算法hash%nso...1.话不多说直接上代码,原理或详解自行百度即可importcn.pheker.utils.UtilElapsedTime;importcn.pheker.utils.UtilLogger;importcn.pheker.utils.UtilMD5;importjava.util.*;/***<pre 查看详情

mongodb多数据源实现(代码片段)

...源对应每个MongoDB集合都支持自定义分片算法提供默认的一致性hash算法实现,解决使用一致性hash分片算法时可能存在的多数据源数据倾斜问题提供默认的一致性hash分片算法实现,对于MongoDB集合可以采用一致性hash算法来... 查看详情

dubbo协调一致性哈希算法在项目中的应用(代码片段)

下面的算法是对Dubbo源码中协调一致性Hash算法改进后在项目中做负载均衡使用:注意:1.Dubbo的一致性Hash算法实现逻辑:   对每个一个注册的服务名,创建一个选择器(ConsistentHashSelector),这个选择器中维护了一个hash环,这个Hash环... 查看详情

缓存架构中分布式一致性hash应用解析(代码片段)

前言本篇文章会从什么是分布式一致性hash算法、hash算法在Memcached、Redis中的应用、以及Java本地缓存与分布式缓存绝佳组合、剖析从浏览器缓存到数据库缓存等;然后去解析一致性hash算法的应用。以及我们在项目应用中,... 查看详情

基础算法一致性hash算法(代码片段)

hash这个词对我们来说并不陌生,以缓存服务器来说,一般会在线上配置好几台服务器,然后根据hash来决定请求哪台缓存服务,比如常见的就是取模方式hash(key)%num来获取目标机器。假设现在有3台缓存服务器,... 查看详情