在大型web应用中,缓存可算是当今的一个标准开发配置了。在大规模的缓存应用中,应运而生了分布式缓存系统。分布式缓存系统的基本原理,大家也有所耳闻。key-value如何均匀的分散到集群中?说到此,最常规的方式莫过于hash取模的方式。比如集群中可用机器适量为N,那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。的确,这种结构是简单的,也是实用的。但是在一些高速发展的web系统中,这样的解决方案仍有些缺陷。随着系统访问压力的增长,缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式,在增加机器节点的这一时刻,大量的缓存命不中,缓存数据需要重新建立,甚至是进行整体的缓存数据迁移,瞬间会给DB带来极高的系统负载,设置导致DB服务器宕机
。那么就没有办法解决hash取模的方式带来的诟病吗?看下文。。。。
一致性哈希(Consistent Hashing):
选择具体的机器节点不在只依赖需要缓存数据的key的hash本身了,而是机器节点本身也进行了hash运算。
(1) hash机器节点
首先求出机器节点的hash值(怎么算机器节点的hash?ip可以作为hash的参数吧。。当然还有其他的方法了),然后将其分布到0~2^32的一个圆环上(顺时针分布)。如下图所示:
图 - 1
集群中有机器:A , B, C, D, E五台机器,通过一定的hash算法我们将其分布到如图 - 1所示的环上。
(2)访问方式
如果有一个写入缓存的请求,其中Key值为K,计算器hash值Hash(K),
Hash(K)
对应于图 - 1环中的某一个点,如果该点对应没有映射到具体的某一个机器节点,那么顺时针查找,直到第一次找到有映射机器的节点,该节点就是确定的目标节点,如果超过了2^32仍然找不到节点,则命中第一个机器节点。比如
Hash(K)
的值介于A~B之间,那么命中的机器节点应该是B节点(如上图 - 1)。
(3)增加节点的处理
如上图 - 1,在原有集群的基础上欲增加一台机器F,增加过程如下:
计算机器节点的Hash值,将机器映射到环中的一个节点,如下图:
增加机器节点F之后,访问策略不改变,依然按照(2)中的方式访问,此时缓存命不中的情况依然不可避免,不能命中的数据是hash(K)在增加节点以前落在C~F之间的数据。尽管依然存在节点增加带来的命中问题,但是比较传统的hash取模的方式,一致性hash已经将不命中的数据降到了最低。
记录在此,方便查阅
- 大小: 11.8 KB
- 大小: 12.2 KB
分享到:
相关推荐
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
一致性哈希算法
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
#资源达人分享计划#
一致性哈希算法的php版,希望能帮到phper了解一致性哈希
#资源达人分享计划#
Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip Mycat一致性哈希分片算法.zip
NULL 博文链接:https://blackbeans.iteye.com/blog/1129256
运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
24一致性哈希:如何高效地均衡负载?1
通过使用nginx uri一致性哈希,将请求分发到10台缓存服务器上,总容量提升10倍,经过一致性哈希,命中率提升至999.9% 特别适合bazel服务相关的环境使用。 完整配置版本,下载后可直接启动使用。 1.sh bazel-remote...
Mycat一致性哈希分片算法1
#资源达人分享计划#
一致性哈希算法应用及优化(最简洁明了的教程)
一致性哈希算法用来解决分布式系统中热点接入与删除管理,是目前公认的最有效的算法,该文档图文并茂,详细解释了这一算法。
基于动态转移的分布式缓存系统一致性哈希算法改进,张昊,张永军,近年来,随着大数据与分布式集群的广泛应用,一致性哈希算法在分布式缓存系统的负载均衡中得到了广泛的应用。一致性哈希算法虽然
#资源达人分享计划#
白话解析:一致性哈希算法1