现在“分布式”的概念越来越广泛,分布式db、分布式cache等,在设计的过程免不了牵扯到哈希算法。接下来介绍下一致性哈希算法。
首先举个栗子:比如我们开发一个网站,随着网站的规模和受众度的增加,使得我们不得不想出一些解决有效的方案来解决数据读写压力,于是我们引入了缓存机制。比如memcached、redis等可能都会成为我们的选择,不过关于这些选择我们该怎么使用确实不得不考虑的问题。
方案一、可以在web服务器前面增加三个甚至更多的缓存服务器,类似如下的结构
,采用最简单的策略机制:通过随机方式获取到对应的缓存服务器,这样的话就存在可能如下问题:1.数据冗余,同一份数据存在不同的服务器上; 2、缓存数据命中率低,比如可能数据已经缓存过,本次请求由于是随机到对应的缓存服务器,会导致数据不能命中。不能够保证同一个key的数据存放在同一台缓存服务器上,所以该策略不能空间上还是时间上都是比较低效的
方案二:为了解决针对方案一中存在的问题,那么我们可能会想到使用哈希算法,来保证相同的key的请求发送到相同的缓存服务器上,比如hash(k)%3 这样 就可以保证对相同的key缓存请求转到同一台缓存服务器,与此同时问题也随之而来,一旦我们增加节点或者减少节点的时候,hash计算要重新计算了,会导致key数据的冗余、命中率低的问题;意味着这样的设计容错性、可扩展性差,也意味着我们需要实现hash一致性计算
方案三、一致性哈希算法
1、概念:一致性哈希算法就是将整个哈希值组织成一个虚拟的圆环,这样的话,安装顺时针方向这个哈希值范围的首值和末值重合;
2、使用:首先我们使用电脑的ip或者主机名称执行Hash,将其定位到圆环中对应的位置;
然后对于key同样执行hash,也将其定位到圆环中的位置
最后,沿着顺时针方向,逐一找到每一个key通过hash后,靠近的第一个服务器的hash,那么就将 这个key归属于这个缓存服务器;
减少节点:只需要将原属于该节点的key按照逆时针方向,找到第一个临近的缓存服务器(前一个缓存服务 器);而其他正常 的缓存服务器及其关联的key则不需要进行任何改变
增加节点:同样采用逆时针方向,找到第一个临近的缓存服务器,这两个范围内的数据就隶属于新增的缓 存服务器。
这样的话,无论使用增加、还是减少节点,真正受到影响的数据都是很小的一部分,同样容错性和可扩展 都得到了很好的完善。
在使用第三种解决方案时,有一个问题值得我们深思,一旦整个圆环节点很少的时候 ,就可能存在节点分布不均匀,数据大量的集中某一台缓存服务器中,针对于此种情况,可以通过使用虚拟节点的方式来解决
这样可以对同一个节点执行多个hash,这样就形成了分布较为均匀的分布,注意虚拟节点格式 缓存服务器编号#自定义编号 比如cache server 1 #1 这样就代表隶属于server 1的一个分支;如此类推。在实际使用过程,建议使用超过32个虚拟节点,使得节点分布更加均匀些,可以很好解决服务节点较少,数据倾斜的问题。
相关推荐
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
一致性哈希算法
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
哈希算法 基于C# 实现的一致性哈希算法
#资源达人分享计划#
运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
#资源达人分享计划#
一致性哈希算法用来解决分布式系统中热点接入与删除管理,是目前公认的最有效的算法,该文档图文并茂,详细解释了这一算法。
#资源达人分享计划#
白话解析:一致性哈希算法1
#资源达人分享计划#
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性哈希算法应用及优化(最简洁明了的教程)
基于NIO-EPOOL模型netty实现的具备一致性哈希算法的NAT端口映射器
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
其次介绍了系统的实现流程,阐明了系统的关键技术:利用录音服务器对其镜像端口的SIP报文进行解析获得媒体流并解码、采用一致性哈希算法的内存数据库作为解码数据的缓存机制、利用Ckafka技术在两者之间构建实时数据...
ufire-springcloud-platform 学习微服-基于一致性哈希算法实现websocket分布式扩展的尝试。