图解分布式DB/redis的几种路由算法(一致性哈希)

云栖号资讯小哥 2020-08-03

分布式 redis 算法 高并发 微服务 DB HASH

云栖号资讯:【点击查看更多行业资讯
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!


背景

随着应用的越做越大,数据量越来越多,不论是MySQL数据库的单库单表还是单台redis都无法满足高并发的读写操作和大数据量的存储功能,因此有了大家耳熟能详的分库分表。

垂直拆分和水平拆分

垂直拆分,即拆分列,从业务上将原来一个表的信息拆到两个表中,形象的理解为垂直的一把刀切开了表

2

水平拆分,即拆分行,通过某种规则将一个表中的数据拆分到不同的表中,形象的理解为水平的一把刀切开了表

3

当然垂直拆分和水平拆分的概念不是本文要讨论的重点,本文要讨论的是水平拆分的规则。水平拆分的本质其实和分布式系统下微服务的思想不谋而合,微服务的出现笔者前文提到过是因为单个服务承载了太多的业务逻辑,导致出现了诸如代码逻辑庞大复杂、开发人员关系耦合、单点故障等问题。这些问题对于DB和redis同样会有:

  • 当访问请求越来越多时,单机的DB/redis无法分配足够的线程抗住高并发的请求
  • 当数据量越来越大时,从一碗水中找一根针和从一片大海中找一根针的难度和耗时也是不一样的,我们要做的是找到那个碗,然后从碗里捞针

所以我们需要将DB/redis扩展为多台。

几种分布式集群中的路由算法

相信前面的介绍已经说明了水平拆分的必要性,现在的问题就是如何拆分,按何种规则将不同的数据归类到不同的mysql库/mysql表/redis机器上。下面我们以userid作为key为例。

固定哈希

固定哈希很好理解,笔者现在所在的部门数据库的分库分表逻辑就是简单的 (userid % 32) ^ (userid >> 32),取了userid的高32位和低32位进行了与运算。

4

这么做的好处是逻辑简单,相信这也是很多公司db业务的分库分表方法,如果能够保证用户的id能够均匀分布在每个分片上。
缺点是伸缩性差,当需要新增服务时,新机器根本路由不到;当需要下线服务时,由于固定哈希必然会导致请求到该服务的请求失败。

一致性哈希

一致性哈希带来的最大变化就是把节点对应的哈希值变成了一个范围,可以将一致性哈希想象成一个环形的钟表,现在我们在12点、4点、8点钟反向分别有三台机器,这时候我们算出hash(key)之后就去找离它最近的机器节点

5

例如这里hash(key)=2,则找到了4点钟方向的节点

6

一致性哈希虽然能够稳定的将请求切换到新机器,但是它也有一些小缺陷。因为 hash取模算法得到的结果是随机的,我们并不能保证各个服务节点能均匀的分配到哈希环上,这就导致了经典的热点问题,又叫数据倾斜问题,例如如图情况会导致8点钟服务承受了过多的负载。

8

引入虚拟节点的一致性哈希

为了应对上面的问题,我们引入了虚拟节点的概念,我们通过对每个机器映射出多个hash,

hashA = hash("192.168.0.1-A") % 32
hashB = hash("192.168.0.1-B") % 32
hashC = hash("192.168.0.1-C") % 32

从而实现一个机器在环上有多个虚拟节点,如图

1

自定义计算方式

如上文所述,笔者所在的公司前期的分库规则是固定哈希,但是随后结合业务实际表现来看有部分用户(称为大户)访问量是小用户的n倍,和普通用户路由到一个db或redis中势必会影响到普通用户的读写,因此对于这些特殊的户单独做了一个规则路由到分片号为9999的特殊分片。

9

以上这种模式其实就是自定义计算方式。

【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/live

立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK

原文发布时间:2020-08-01
本文作者:ackpotDC
本文来自:“掘金”,了解相关信息可以关注“掘金”

登录 后评论
下一篇
云栖号资讯小编
12031人浏览
2020-07-13
相关推荐
后端架构师技术图谱
5693人浏览
2018-05-07 19:32:00
分布式锁(redis/mysql)
1366人浏览
2018-04-15 23:08:55
Chord算法实现详细
3741人浏览
2014-05-28 18:58:00
数据库拆分的几种方式
861人浏览
2016-05-04 00:22:39
Redis集群及管理讲解
748人浏览
2017-11-10 00:16:00
Hash函数及其应用
1034人浏览
2015-06-12 16:40:00
Redis实践(九)-初识Redis Cluster
1031人浏览
2018-08-12 19:16:00
Java面试
1286人浏览
2018-08-22 11:05:00
Redis Cluster集群的实现原理
3362人浏览
2019-07-30 23:11:30
0
0
0
217