分布式缓存一致性hash算法

在设计分布式缓存集群的时候,需要考虑集群的伸缩性,也就是当向集群中增加服务器的时候,要尽量减小对集群的影响,而一致性hash算法就是用来解决集群伸缩性。 当服务器不多,并且不考虑扩容的时候,可直接使用简单的路由算法,用服务器数除缓存数据KEY的hash值,余数作为服务器下标即可。

但是当业务发展,网站缓存服务需要扩容时就会出现问题,比如3台缓存服务器要扩容到4台,就会导致75%的数据无法命中,当100台服务器中增加一台,不命中率会到达99%(n/(n+1)),这显然是不能接受的。

在设计分布式缓存集群的时候,需要考虑集群的伸缩性,也就是当向集群中增加服务器的时候,要尽量减小对集群的影响,而一致性hash算法就是用来解决集群伸缩性。

一致性hash算法通过构造一个长度为2^32的整数环,根据节点名的hash值将缓存服务器节点放置在这个环上,然后计算要缓存的数据的key的hash值,顺时针找到最近的服务器节点,将数据放到该服务器上。

有Node0,Node1,Node2三个节点,假设Node0的hash值是1024,key1的hash值是500,key1在环上顺时针查找,最近的节点就是Node0。 当服务器集群又开始扩容,新增了Node3节点,从三个节点扩容到了四个节点。

Node3加到了Node2和Node1之间,除了Node2到Node3之间原本是Node1的数据无法再命中,其它的数据不受影响,3台扩容到4台可命中率高达75%, 而且集群越大,影响越小,100台服务器增加一台,命中率可达到99%。

查找不小于查找树的最小值是用的二叉查找树实现的。 但是这样子还是会存在一个问题,就是负载不均衡的问题,当Node3加到Node2和Node1之间时,原本会访问Node1的缓存数据有50%的概率会缓存到Node3上了,这样Node0和Node2的负载会是Node1和Node3的两倍。

要解决一致性hash算法带来的负载不均衡问题,可通过将每台物理服务器虚拟成一组虚拟缓存服务器,将虚拟服务器的hash值放置在hash环上,KEY在环上先找到虚拟服务器节点,然后再映射到实际的服务器上。

这样在Node0,1,2虚拟节点都已存在的情况下,将Node3的多个虚拟节点分散到它们中间,多个虚拟的Node3节点会影响到其它的多个虚拟节点,而不是只影响其中一个,这样将命中率不会有变化,但是负载却更加均衡了而且虚拟节点越多越均衡。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏令仔很忙

考试系统--底层框架发布时遇到的问题解决方案(Window7 IIS6.0)(三)

考试系统--底层框架发布时遇到的问题解决方案(Window7 IIS6.0)(二)

13410
来自专栏前端小叙

vue报错集锦

1、vue报错: 没安装 less-loader css-loader style-loader        可能的很大原因:没安装less 2、vuex报错...

45960
来自专栏腾讯云TStack专栏

对象存储,了解一下

? 对象存储,通常指 S3 (Simple Storage Service) 服务,由AWS提供公有云服务,而 Ceph 也可以提供兼容 S3 协议的对象存储...

93320
来自专栏Python中文社区

Python多进程抓取全国邮政编码和长途区号

由于Python设计的限制(就是咱们常用的CPython)最多只能用满1个CPU核心。Python提供了非常好用的多进程包multiprocessing,你只需...

28790
来自专栏小尘哥的专栏

springboot中使用tk.mybatis代码生成器

tk.mybatis是对mybatis的进一步封装,它对基本的单表的增删改查又做了进一步封装,springboot中的使用之前已经写过了,如果没用过,请参考我之...

35620
来自专栏程序员同行者

vue moment库格式化处理后端传的日期

日期时间格式前端和后端都可以处理,我比较推荐前端来处理(定制化高),下面我就介绍下两种处理的方式

90510
来自专栏北京马哥教育

rsync - Linux下进行文件同步命令

rsync是Linux下进行文件同步到一个命令,可以同步两台计算机到文件与目录,利用查找文件中到不同块以减少数据传输。也可以在一台电脑到不同目录间同步,比如可以...

61360
来自专栏hbbliyong

错误提示之(MVC3.0):HTTP 404。您正在查找的资源(或者它的一个依赖项)可能已被移除,或其名称已更改,或暂时不可用。请检查以下 URL 并确保其拼写正确 MVC误设起始页

MVC3.0框架开发项目: 有时在程序运行的时候会出现“HTTP 404。您正在查找的资源(或者它的一个依赖项)可能已被移除,或其名称已更改,或暂时不可用。请检...

44160
来自专栏Laoqi's Linux运维专列

Saltstack 远程操作(grains,pillar)服务安装+配置管理

25170
来自专栏个人分享

Redis简介及3.0.2编译安装

Redis是一个key-value存储系统。和Memcached类似,它支持存储的value类型相对更多,包括string(字符串)、list(链表)、set(...

10220

扫码关注云+社区

领取腾讯云代金券