借 redis cluster 集群,聊一聊集群中数据分布算法

Redis Cluster 集群中涉及到了数据分布问题,因为 redis cluster 是多 master 的结构,每个 master 都是可以提供存储服务的,这就会涉及到数据分布的问题,在新的 redis 版本中采用的是虚拟槽分区技术来解决数据分布的问题,关于什么是虚拟槽分区技术我们后面会详细的介绍。在集群中除了虚拟槽分区技术之外,还有几种数据分布的算法,比如哈希算法,一致性哈希算法,这篇文章我们就来一起聊一聊这几种数据分布算法。

因为是集群,所以我们需要一个大前提,在这篇文章中假设 redis cluster 集群中有三台 master,我们需要存储的数据集为:[{id:1,"name":"1"},{id:2,name:"2"},{id:3,name:"3"},{id:4,name:"4"},{id:5:"name":"5"},{id:6,"name":"6"}],在这个大前提下,我们来聊一聊集群中的数据分布算法。

哈希算法

哈希算法在分布式架构中应用广泛,不仅仅是数据存储,还有负载均衡等应用上有用的比较多,哈希算法的思想非常简单,也许你知道 HashMap 的哈希函数,哈希算法跟 HashMap 一样,也是通过一个哈希函数得到某一个数字,然后根据数字找到相应的服务器。哈希算法的哈希函数比较简单,一般是根据某个key的值或者key 的哈希值与当前可用的 master节点数取模,根据取模的值获取具体的服务器。哈希算法服务结构模型图如下图所示:

哈希算法结构模型图

用我们前面假设的数据,利用哈希算法来实验一把,加深我们对哈希算法在分布式中的应用的理。我们假设哈希算法中的哈希函数为“id % master 节点数”,结果为 0 的数据存放到 server1 服务器上,结果为 1 的数据存放到 server2 服务器上,结果为 2 的数据存放到 server3 服务器上。

所以经过哈希算法之后,id=3、id=6 的数据与 master 节点数取模为 0 (3%3=0,6%3=0),所以这两个数据会存放到 server1 服务器 ,以此类推,id=1、id=4 的数据将存放到 server2 服务器中,id=2、id=5 的数据将存放到 server3 上,这时候服务器存储数据如下图所示:

服务器存储数据

这就是哈希算法在分布式中的作用,比较简单,可以看出只要你哈希函数设计的好,数据在各个服务器上是比较均匀分布的,但是哈希算法有一个致命的缺点:扩展性特别的差,比如我们的集群中,服务器server3 宕机了,这时候集群中可用的机器只有两台了,这样哈希函数就变成了id % 2了,这就会导致一个问题,所有的数据需要重新计算,找到新的存储节点,每次有服务器宕机或者添加机器时,都需要进行大量的数据迁移,这会使得系统的可用性、稳定性变差。

一致性哈希算法

一致性哈希算法可以说是哈希算法的升级版,解决了哈希算法扩展性差的问题,一致性哈希算法跟哈希算法不一样,一致性哈希算法会将服务器和数据都通过哈希函数映射到一个首尾相连的哈希环上,存储节点映射可以根据 ip 地址来进行哈希取值,数据映射到哈希环上后按照顺时针的方向查找存储节点,即从数据映射在环上的位置开始,顺时针方向找到的第一个存储节点,那么他就存储在这个节点上

我们使用一致性哈希算法来存储我们的数据,我画了一张图来模拟一致性哈希算法可能出现的结果:

一致性算法模拟存储图

我们先来解读一下这张图,按照一致性哈希算法的规则,数据沿着顺时针的方向查找数据,那么 id=4 的数据存放在 server1 服务器,id=2 的数据存放在服务器 server2 上,id=3、id=1、id=5、id=6 的数据都存放在服务器 server3 上,如果你比较敏感的话,也许你就会发现一致性哈希算法的不足之处, 从图中可以看出,我们六条数据分布不均匀,并不是每台服务器存储 2 条数据,而且差距好像还有点大,这里我们就要来说一说一致性哈希算法的缺点:一致性哈希算法会会造成数据分布不均匀的问题或者叫做数据倾斜问题,就像我们图中那样,数据分布不均匀可能会造成某一个节点的负载过大,从而宕机。造成数据分布不均匀有以下两种情况:

  • 第一:哈希函数的原因,经过哈希函数之后服务器在哈希环上的分布不均匀,服务器之间的间距不相等,这样就会导致数据不均匀。
  • 第二:某服务器宕机了,后继节点就需要承受原本属于宕机机器的数据,这样也会造成数据不均匀。

前面我们提到过一致性哈希算法解决了哈希算法中扩展性差的问题,这个怎么理解呢?我们来看看,在一致性哈希算法中当有存储节点加入或者退出时,只会影响应该该节点的后继节点,举个例子说明一下,例如我们要在服务器server3 和服务 server2 之间加入了一个服务器存储节点 server4,只会对服务器server3 造成影响,原本存储到服务器server3 上的数据有一部分会落入到服务器 server4 上,对服务器 server1 和 server2 并没有任何影响,这样就不会进行大量的数据迁移,扩展性就变强了。

带有限负载的一致性哈希算法

因为一致性哈希算法的数据分布不均匀的问题,Google 在 2017 年提出了带有限负载的一致性哈希算法来解决这个问题,带有限负载的一致性哈希算法思想比较简单,给每个存储节点设置了一个存储上限值来控制存储节点添加或移除造成的数据不均匀,当数据按照一致性哈希算法找到相应的存储节点时,要先判断该存储节点是否达到了存储上限;如果已经达到了上限,则需要继续寻找该存储节点顺时针方向之后的节点进行存储。

我们利用带有限负载的一致性哈希算法来改进上面的数据存储,我们限定每台服务器节点存储的数据上限为 2 ,数据插入的顺序就按照 ID 大小的顺序,同样我也画了一张模拟图:

带有限负载的一致性哈希算法

一起来分析一下这张图,因为我们的添加顺序是按照 id 大小的顺序,所以前四个数据都没有问题,这时候的服务器都没有超过最高负载数量,id=5 的数据落在了服务器server2 和服务器server3 之间,本应该是存储在服务器server3 上,但是由于此时的服务器server3 上已经存储了 id=1、id=3 的数据达到了最高限定,因此 id=5 的数据会沿着顺时针的方向继续往下寻找服务器,下一个服务器就是server1,此时的服务器server1 就存储了 id=4 的数据并没有达到上限,所以 id=5 的数据就会存储在服务器server1,id=6 的数据同样的道理。这样就利用带有限负载的一致性哈希算法解决了一致性哈希算法中数据分布不均匀的问题。

带虚拟节点的一致性哈希算法

带有限负载的一致性哈希算法也有一个问题,那就是每台服务器的性能配置可能存在不一样,如果规定数量过小的话,对于配置高的服务器来说有点浪费,这是因为服务器之间可能存在差异,叫做服务器之间的异构性,为了解决服务器之间的异构性问题,引入了一种叫做带虚拟节点的一致性哈希算法,带虚拟节点的一致性哈希算法核心思想是:根据每个节点的性能为每个节点划分不同数量的虚拟节点,并将这些虚拟节点映射到哈希环中,然后再按照一致性哈希算法进行数据映射和存储

为了演示带虚拟节点的一致性哈希算法,我们先做一个假设服务器server3是配置最差的,所以我们以服务器server3 为基准,服务器server2 是服务器server3 的两倍,服务器server1 是服务器server3 的三倍,有了这个前提之后,我们就可以来建立虚拟节点,我们假设服务器server3 的虚拟节点为服务器server3_1,服务器server2 就有两个虚拟节点服务器server2_1、服务器server2_2,服务器server1 有三个虚拟节点 服务器server1_1、服务器server1_2、服务器server1_3。我还是跟前面一样画了一张模拟图:

落到虚拟节点上的数据都会存到对应的物理服务器上,所以通过带虚拟节点的一致性哈希算法后,数据存储结果为:数据id=2、id=3、id=5 的数据都会存储到服务器server1 上,id=1 的数据将会存储到服务器server2 上,数据 id=4、id=6 都会存放到服务器server3上。

虚拟节点可以让配置好的服务器存储更多的数据,这样就解决了系统异构性的问题,同时由于大量的虚拟节点的存在

在数据迁移时数据会落到不同的物理机上,这样就减小了数据迁移时某台服务器的分担压力,能够保证系统的稳定性。

虚拟槽分区

虚拟槽分区是 redis cluster 中默认的数据分布技术,虚拟槽分区巧妙地使用了哈希空间,使用分散度良好的哈希函数把所有数据映射到一个固定范围的整数集合中,这个整数定义为槽(slot),而且这个槽的个数一般远远的大于节点数。

在 redis cluster 中有16384(0~16383)个槽,会将这些槽平均分配到每个 master 上,在存储数据时利用 CRC16 算法,具体的计算公式为:slot=CRC16(key)/16384 来计算 key 属于哪个槽。在我们的集群环境中,一个 key 的存储或者查找过程,可能如下图所示:

虚拟槽分区解耦了数据与节点的关系,通过引入槽,让槽成为集群内数据管理和迁移的基本单位,简化了节点扩容和收缩难度,你只需要关注数据在哪个槽,并不需要关心数据在哪个节点上。所以虚拟槽分区可以说比较好的兼容了数据均匀分布和扩展性的问题。

以上就是我要分享关于集群中数据分布的技术,希望本文的内容对大家的学习或者工作能带来一定的帮助,感谢大家的支持

最后

目前互联网上很多大佬都有数据分布相关文章,如有雷同,请多多包涵了。原创不易,码字不易,还希望大家多多支持。若文中有所错误之处,还望提出,谢谢。

原文发布于微信公众号 -平头哥的技术博文(id:pingtouge_java) 作者:平头哥,学会伺机而动,实现弯道超车 ZjYyMjU2OWMyMTA3?x-oss-process=image/format,png)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java后端技术栈cwnait

你知道12306 的架构到底有多牛逼吗?

尤其是春节期间,大家不仅使用 12306,还会考虑“智行”和其他的抢票软件,全国上下几亿人在这段时间都在抢票。

6430
来自专栏二的十次方

redis 的持久化有哪几种方式?

持久化主要是做灾难恢复、数据恢复,也可以归类到高可用的一个环节中去,比如你 redis 整个挂了,然后 redis 就不可用了,你要做的事情就是让 redis ...

5710
来自专栏可能是东半球最正规的API社区

xue微xue微深入地聊一聊PHP session

大家好,我今天打算换一个新的出场方式。所以,我打算从下面倒计时后开始重新打招呼,你们就假装开头这句话我没写配合一下,谢谢。

7220
来自专栏二的十次方

集群部署时的分布式 session 如何实现?

session 是啥?浏览器有个 cookie,在一段时间内这个 cookie 都存在,然后每次发请求过来都带上一个特殊的 jsessionid cookie,...

8100
来自专栏玩转JavaEE

Spring Boot2 系列教程(三十)Spring Boot 整合 Ehcache

用惯了 Redis ,很多人已经忘记了还有另一个缓存方案 Ehcache ,是的,在 Redis 一统江湖的时代,Ehcache 渐渐有点没落了,不过,我们还是...

9930
来自专栏Java架构学习路线

面试还搞不懂redis,快看看这40道面试题(含答案和思维导图)

34、一个 Redis 实例最多能存放多少的 keys?List、Set、Sorted Set他们最多能存放多少元素?

7030
来自专栏二的十次方

CAP原则

CAP原则是NOSQL数据库的基石。Consistency(一致性)。 Availability(可用性)。

8430
来自专栏Java后端技术栈cwnait

SpringBoot 并发登录人数控制

通常系统都会限制同一个账号的登录人数,多人登录要么限制后者登录,要么踢出前者,Spring Security 提供了这样的功能,本文讲解一下在没有使用Secur...

8430
来自专栏架构之美

如何设计真正高性能高并发分布式系统(万字长文)

“世间可称之为天经地义的事情没几样,复杂的互联网架构也是如此,万丈高楼平地起,架构都是演变而来,那么演变的本质是什么?”

11820
来自专栏架构之美

构建企业级业务高可用的延时消息中

扫库的方案一般体量不大时可以使用,当业务发展到一定规模后就不再适用。对IM消息重发秒级别的定时需求,只能增加扫库的频率,但过于频繁的扫库很可能会将数据库拖垮。显...

7310

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励