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

背景

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

垂直拆分和水平拆分

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

image

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

image

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

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

大碗捞针

大海捞针

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

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

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

固定哈希

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

image

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

一致性哈希

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

一致性哈希是一个钟表

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

image

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

image

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

为了应对上面的问题，我们引入了虚拟节点的概念，我们通过对每个机器映射出多个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

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

image

自定义计算方式

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

$ip = \begin{cases} ip[userid \% 32],\quad userid\ not\ in\ big\ users \\ ip[9999], \quad userid\ in\ big\ users \end{cases}$

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

reference

[1] 分布式系统中一致性哈希算法
[2] 大型网站系统与Java中间件开发实践
[3] 一致哈希-维基百科