背景

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

垂直拆分和程度拆分

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

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

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

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

所以咱们须要将 DB/redis 扩大为多台。

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

置信后面的介绍曾经阐明了程度拆分的必要性，当初的问题就是如何拆分，按何种规定 将不同的数据归类到不同的 mysql 库 /mysql 表 /redis 机器上。上面咱们以 userid 作为 key 为例。

固定哈希

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

这么做的益处是 逻辑简略 ，置信这也是很多公司 db 业务的分库分表办法，如果可能保障用户的 id 可能 均匀分布 在每个分片上。
毛病是伸缩性差，当须要新增服务时，新机器基本路由不到；当须要下线服务时，因为固定哈希必然会导致申请到该服务的申请失败。

一致性哈希

一致性哈希带来的最大变动就是把节点对应的哈希值变成了一个范畴，能够将一致性哈希设想成一个环形的钟表，当初咱们在 12 点、4 点、8 点钟反向别离有三台机器，这时候咱们算出 hash(key) 之后就去找离它最近的机器节点

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

一致性哈希尽管可能稳固的将申请切换到新机器，然而它也有一些小缺点。因为 hash 取模算法失去的后果是随机的，咱们并不能保障各个服务节点能平均的调配到哈希环上，这就导致了经典的 热点问题，又叫数据歪斜问题，例如如图状况会导致 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

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

自定义计算形式

如上文所述，笔者所在的公司后期的分库规定是固定哈希，然而随后联合业务理论体现来看有局部用户（称为小户）访问量是小用户的 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] 统一哈希 - 维基百科