水平分库分表排雷帖
一、背景
提起分库分表，对于大部分服务器开发来说，其实并不是一个新鲜的名词。随着业务的发展，我们表中的数据量会变的越来越大，字段也可能随着业务复杂度的升高而逐渐增多，我们为了解决单表的查询性能问题，一般会进行分表操作。
同时我们业务的用户活跃度也会越来越高，并发量级不断加大，那么可能会达到单个数据库的处理能力上限。此时我们为了解决数据库的处理性能瓶颈，一般会进行分库操作。不管是分库操作还是分表操作，我们一般都有两种方式应对，一种是垂直拆分，一种是水平拆分。
关于两种拆分方式的区别和特点，互联网上参考资料众多，很多人都写过相关内容，这里就不再进行详细赘述，有兴趣的读者可以自行检索。
此文主要详细聊一聊，我们最实用最常见的水平分库分表方式中的一些特殊细节，希望能帮助大家避免走弯路，找到最合适自身业务的分库分表设计。
【注1】本文中的案例均基于Mysql数据库，下文中的分库分表统指水平分库分表。
【注2】后文中提到到M库N表，均指共M个数据库，每个数据库共N个分表，即总表个数其实为M*N。
二、什么是一个好的分库分表方案？
前期业务数据量级不大，流量较低的时候，我们无需分库分表，也不建议分库分表。但是一旦我们要对业务进行分库分表设计时，就一定要考虑到分库分表方案的可持续性。
那何为可持续性？其实就是：业务数据量级和业务流量未来进一步升高达到新的量级的时候，我们的分库分表方案可以持续使用。
一个通俗的案例，假定当前我们分库分表的方案为10库100表，那么未来某个时间点，若10个库仍然无法应对用户的流量压力，或者10个库的磁盘使用即将达到物理上限时，我们的方案能够进行平滑扩容。
在后文中我们将介绍下目前业界常用的翻倍扩容法和一致性Hash扩容法。
一个良好的分库分表方案，它的数据应该是需要比较均匀的分散在各个库表中的。如果我们进行一个拍脑袋式的分库分表设计，很容易会遇到以下类似问题：
a、某个数据库实例中，部分表的数据很多，而其他表中的数据却寥寥无几，业务上的表现经常是延迟忽高忽低，飘忽不定。
b、数据库集群中，部分集群的磁盘使用增长特别块，而部分集群的磁盘增长却很缓慢。每个库的增长步调不一致，这种情况会给后续的扩容带来步调不一致，无法统一操作的问题。
这边我们定义分库分表最大数据偏斜率为 ：（数据量最大样本 - 数据量最小样本）/ 数据量最小样本。一般来说，如果我们的最大数据偏斜率在5%以内是可以接受的。
三、常见的分库分表方案
顾名思义，该方案根据数据范围划分数据的存放位置。
举个最简单例子，我们可以把订单表按照年份为单位，每年的数据存放在单独的库（或者表）中。如下图所示：
/**
* 通过年份分表
*
* @param orderId
* @return
*/
public static String rangeShardByYear(String orderId) {
int year = Integer.parseInt(orderId.substring(0, 4));
return "t_order_" + year;
}
通过数据的范围进行分库分表，该方案是最朴实的一种分库方案，它也可以和其他分库分表方案灵活结合使用。时下非常流行的分布式数据库：TiDB数据库，针对TiKV中数据的打散，也是基于Range的方式进行，将不同范围内的[StartKey,EndKey)分配到不同的Region上。
下面我们看看该方案的缺点：
-
a、最明显的就是数据热点问题，例如上面案例中的订单表，很明显当前年度所在的库表属于热点数据，需要承载大部分的IO和计算资源。
-
b、新库和新表的追加问题。一般我们线上运行的应用程序是没有数据库的建库建表权限的，故我们需要提前将新的库表提前建立，防止线上故障。
这点非常容易被遗忘，尤其是稳定跑了几年没有迭代任务，或者人员又交替频繁的模块。
-
c、业务上的交叉范围内数据的处理。举个例子，订单模块无法避免一些中间状态的数据补偿逻辑，即需要通过定时任务到订单表中扫描那些长时间处于待支付确认等状态的订单。
这里就需要注意了，因为是通过年份进行分库分表，那么元旦的那一天，你的定时任务很有可能会漏掉上一年的最后一天的数据扫描。
虽然分库分表的方案众多，但是Hash分库分表是最大众最普遍的方案，也是本文花最大篇幅描述的部分。
针对Hash分库分表的细节部分，相关的资料并不多。大部分都是阐述一下概念举几个示例，而细节部分并没有特别多的深入，如果未结合自身业务贸然参考引用，后期非常容易出现各种问题。
在正式介绍这种分库分表方式之前，我们先看几个常见的错误案例。
常见错误案例一：非互质关系导致的数据偏斜问题
public static ShardCfg shard(String userId) {
int hash = userId.hashCode();
// 对库数量取余结果为库序号
int dbIdx = Math.abs(hash % DB_CNT);
// 对表数量取余结果为表序号
int tblIdx = Math.abs(hash % TBL_CNT);
return new ShardCfg(dbIdx, tblIdx);
}
上述方案是初次使用者特别容易进入的误区，用Hash值分别对分库数和分表数取余，得到库序号和表序号。其实稍微思索一下，我们就会发现，以10库100表为例，如果一个Hash值对100取余为0，那么它对10取余也必然为0。
这就意味着只有0库里面的0表才可能有数据，而其他库中的0表永远为空！
类似的我们还能推导到，0库里面的共100张表，只有10张表中(个位数为0的表序号)才可能有数据。这就带来了非常严重的数据偏斜问题，因为某些表中永远不可能有数据，最大数据偏斜率达到了无穷大。
那么很明显，该方案是一个未达到预期效果的错误方案。数据的散落情况大致示意图如下：
事实上，只要库数量和表数量非互质关系，都会出现某些表中无数据的问题。
证明如下：
那么是不是只要库数量和表数量互质就可用用这种分库分表方案呢？比如我用11库100表的方案，是不是就合理了呢？
答案是否定的，我们除了要考虑数据偏斜的问题，还需要考虑可持续性扩容的问题，一般这种Hash分库分表的方案后期的扩容方式都是通过翻倍扩容法，那11库翻倍后，和100又不再互质。
当然，如果分库数和分表数不仅互质，而且分表数为奇数(例如10库101表)，则理论上可以使用该方案，但是我想大部分人可能都会觉得使用奇数的分表数比较奇怪吧。
常见错误案例二：扩容难以持续
如果避开了上述案例一的陷阱，那么我们又很容易一头扎进另一个陷阱，大概思路如下；
我们把10库100表看成总共1000个逻辑表，将求得的Hash值对1000取余，得到一个介于[0，999)中的数，然后再将这个数二次均分到每个库和每个表中，大概逻辑代码如下：
public static ShardCfg shard(String userId) {
// ① 算Hash
int hash = userId.hashCode();
// ② 总分片数
int sumSlot = DB_CNT * TBL_CNT;
// ③ 分片序号
int slot = Math.abs(hash % sumSlot);
// ④ 计算库序号和表序号的错误案例
int dbIdx = slot % DB_CNT ;
int tblIdx = slot / DB_CNT ;
return new ShardCfg(dbIdx, tblIdx);
}
该方案确实很巧妙的解决了数据偏斜的问题，只要Hash值足够均匀，那么理论上分配序号也会足够平均，于是每个库和表中的数据量也能保持较均衡的状态。
但是该方案有个比较大的问题，那就是在计算表序号的时候，依赖了总库的数量，那么后续翻倍扩容法进行扩容时，会出现扩容前后数据不在同一个表中，从而无法实施。
如上图中，例如扩容前Hash为1986的数据应该存放在6库98表，但是翻倍扩容成20库100表后，它分配到了6库99表，表序号发生了偏移。这样的话，我们在后续在扩容的时候，不仅要基于库迁移数据，还要基于表迁移数据，非常麻烦且易错。
看完了上面的几种典型的错误案例，那么我们有哪些比较正确的方案呢？下面将结合一些实际场景案例介绍几种Hash分库分表的方案。
常用姿势一：标准的二次分片法
上述错误案例二中，整体思路完全正确，只是最后计算库序号和表序号的时候，使用了库数量作为影响表序号的因子，导致扩容时表序号偏移而无法进行。
事实上，我们只需要换种写法，就能得出一个比较大众化的分库分表方案。
public static ShardCfg shard2(String userId) {
// ① 算Hash
int hash = userId.hashCode();
// ② 总分片数
int sumSlot = DB_CNT * TBL_CNT;
// ③ 分片序号
int slot = Math.abs(hash % sumSlot);
// ④ 重新修改二次求值方案
int dbIdx = slot / TBL_CNT ;
int tblIdx = slot % TBL_CNT ;
return new ShardCfg(dbIdx, tblIdx);
}
大家可以注意到，和错误案例二中的区别就是通过分配序号重新计算库序号和表序号的逻辑发生了变化。它的分配情况如下：
那为何使用这种方案就能够有很好的扩展持久性呢？我们进行一个简短的证明：
通过上面结论我们知道，通过翻倍扩容后，我们的表序号一定维持不变，库序号可能还是在原来库，也可能平移到了新库中(原库序号加上原分库数)，完全符合我们需要的扩容持久性方案。
【方案缺点】
1、翻倍扩容法前期操作性高，但是后续如果分库数已经是大几十的时候，每次扩容都非常耗费资源。
2、连续的分片键Hash值大概率会散落在相同的库中，某些业务可能容易存在库热点（例如新生成的用户Hash相邻且递增，且新增用户又是高概率的活跃用户，那么一段时间内生成的新用户都会集中在相邻的几个库中）。
常用姿势二：关系表冗余
我们可以将分片键对应库的关系通过关系表记录下来，我们把这张关系表称为"路由关系表"。
public static ShardCfg shard(String userId) {
int tblIdx = Math.abs(userId.hashCode() % TBL_CNT);
// 从缓存获取
Integer dbIdx = loadFromCache(userId);
if (null == dbIdx) {
// 从路由表获取
dbIdx = loadFromRouteTable(userId);
if (null != dbIdx) {
// 保存到缓存
saveRouteCache(userId, dbIdx);
}
}
if (null == dbIdx) {
// 此处可以自由实现计算库的逻辑
dbIdx = selectRandomDbIdx();
saveToRouteTable(userId, dbIdx);
saveRouteCache(userId, dbIdx);
}
return new ShardCfg(dbIdx, tblIdx);
}
该方案还是通过常规的Hash算法计算表序号，而计算库序号时，则从路由表读取数据。因为在每次数据查询时，都需要读取路由表，故我们需要将分片键和库序号的对应关系记录同时维护在缓存中以提升性能。
上述实例中selectRandomDbIdx方法作用为生成该分片键对应的存储库序号，这边可以非常灵活的动态配置。例如可以为每个库指定一个权重，权重大的被选中的概率更高，权重配置成0则可以将关闭某些库的分配。当发现数据存在偏斜时，也可以调整权重使得各个库的使用量调整趋向接近。
该方案还有个优点，就是理论上后续进行扩容的时候，仅需要挂载上新的数据库节点，将权重配置成较大值即可，无需进行任何的数据迁移即可完成。
如下图所示：最开始我们为4个数据库分配了相同的权重，理论上落在每个库的数据概率均等。但是由于用户也有高频低频之分，可能某些库的数据增长会比较快。当挂载新的数据库节点后，我们灵活的调整了每个库的新权重。
该方案似乎解决了很多问题，那么它有没有什么不适合的场景呢？当然有，该方案在很多场景下其实并不太适合，以下举例说明。
a、每次读取数据需要访问路由表，虽然使用了缓存，但是还是有一定的性能损耗。
b、路由关系表的存储方面，有些场景并不合适。例如上述案例中用户id的规模大概是在10亿以内，我们用单库百表存储该关系表即可。但如果例如要用文件MD5摘要值作为分片键，因为样本集过大，无法为每个md5值都去指定关系（当然我们也可以使用md5前N位来存储关系）。
c、饥饿占位问题，如下详叙：
我们知道，该方案的特点是后续无需扩容，可以随时修改权重调整每个库的存储增长速度。但是这个愿景是比较缥缈，并且很难实施的，我们选取一个简单的业务场景考虑以下几个问题。
【业务场景】：以用户存放文件到云端的云盘业务为例，需要对用户的文件信息进行分库分表设计，有以下假定场景：
①假定有2亿理论用户，假设当前有3000W有效用户。
②平均每个用户文件量级在2000个以内
③用户id为随机16位字符串
④初期为10库，每个库100张表。
我们使用路由表记录每个用户所在的库序号信息。那么该方案会有以下问题：
第一、我们总共有2亿个用户，只有3000W个产生过事务的用户。若程序不加处理，用户发起任何请求则创建路由表数据，会导致为大量实际没有事务数据的用户提前创建路由表。
笔者最初存储云盘用户数据的时候便遇到了这个问题，客户端app会在首页查询用户空间使用情况，这样导致几乎一开始就为每个使用者分配好了路由。随着时间的推移，这部分没有数据的"静默"的用户，随时可能开始他的云盘使用之旅而“复苏”，从而导致它所在的库迅速增长并超过单个库的空间容量极限，从而被迫拆分扩容。
解决这个问题的方案，其实就是只针对事务操作(例如购买空间，上传数据，创建文件夹等等)才进行路由的分配，这样对代码层面便有了一些倾入。
第二、按照前面描述的业务场景，一个用户最终平均有2000条数据，假定每行大小为1K，为了保证B+数的层级在3层，我们限制每张表的数据量在2000W，分表数为100的话，可以得到理论上每个库的用户数不能超过100W个用户。
也就是如果是3000W个产生过事务的用户，我们需要为其分配30个库，这样会在业务前期，用户平均数据量相对较少的时候，存在非常大的数据库资源的浪费。
解决第二个问题，我们一般可以将很多数据库放在一个实例上，后续随着增长情况进行拆分。也可以后续针对将满的库，使用常规手段进行拆分和迁移。
常用姿势三：基因法
还是由错误案例一启发，我们发现案例一不合理的主要原因，就是因为库序号和表序号的计算逻辑中，有公约数这个因子在影响库表的独立性。
那么我们是否可以换一种思路呢？我们使用相对独立的Hash值来计算库序号和表序号。
public static ShardCfg shard(String userId) {
int dbIdx = Math.abs(userId.substring(0, 4).hashCode() % DB_CNT );
int tblIdx = Math.abs(userId.hashCode() % TBL_CNT);
return new ShardCfg(dbIdx, tblIdx);
}
如上所示，我们计算库序号的时候做了部分改动，我们使用分片键的前四位作为Hash值来计算库序号。
这也是一种常用的方案，我们称为基因法，即使用原分片键中的某些基因（例如前四位）作为库的计算因子，而使用另外一些基因作为表的计算因子。该方案也是网上不少的实践方案或者是其变种，看起来非常巧妙的解决了问题，然而在实际生成过程中还是需要慎重。
笔者曾在云盘的空间模块的分库分表实践中采用了该方案，使用16库100表拆分数据，上线初期数据正常。然而当数据量级增长起来后，发现每个库的用户数量严重不均等，故猜测该方案存在一定的数据偏斜。
为了验证观点，进行如下测试，随机2亿个用户id（16位的随机字符串），针对不同的M库N表方案，重复若干次后求平均值得到结论如下：
8库100表
min=248305(dbIdx=2, tblIdx=64), max=251419(dbIdx=7, tblIdx=8), rate= 1.25% √
16库100表
min=95560(dbIdx=8, tblIdx=42), max=154476(dbIdx=0, tblIdx=87), rate= 61.65% ×
20库100表
min=98351(dbIdx=14, tblIdx=78), max=101228(dbIdx=6, tblIdx=71), rate= 2.93%
我们发现该方案中，分库数为16，分表数为100，数量最小行数仅为10W不到，但是最多的已经达到了15W+，最大数据偏斜率高达61%。按这个趋势发展下去，后期很可能出现一台数据库容量已经使用满，而另一台还剩下30%+的容量。
该方案并不是一定不行，而是我们在采用的时候，要综合分片键的样本规则，选取的分片键前缀位数，库数量，表数量，四个变量对最终的偏斜率都有影响。
例如上述例子中，如果不是16库100表，而是8库100表，或者20库100表，数据偏斜率都能降低到了5%以下的可接受范围。所以该方案的隐藏的"坑"较多，我们不仅要估算上线初期的偏斜率，还需要测算若干次翻倍扩容后的数据偏斜率。
例如你用着初期比较完美的8库100表的方案，后期扩容成16库100表的时候，麻烦就接踵而至。
常用姿势四：剔除公因数法
还是基于错误案例一启发，在很多场景下我们还是希望相邻的Hash能分到不同的库中。就像N库单表的时候，我们计算库序号一般直接用Hash值对库数量取余。
那么我们是不是可以有办法去除掉公因数的影响呢？下面为一个可以考虑的实现案例：
public static ShardCfg shard(String userId) {
int dbIdx = Math.abs(userId.hashCode() % DB_CNT);
// 计算表序号时先剔除掉公约数的影响
int tblIdx = Math.abs((userId.hashCode() / TBL_CNT) % TBL_CNT);
return new ShardCfg(dbIdx, tblIdx);
}
经过测算，该方案的最大数据偏斜度也比较小，针对不少业务从N库1表升级到N库M表下，需要维护库序号不变的场景下可以考虑。
常用姿势五：一致性Hash法
一致性Hash算法也是一种比较流行的集群数据分区算法，比如RedisCluster即是通过一致性Hash算法，使用16384个虚拟槽节点进行每个分片数据的管理。关于一致性Hash的具体原理这边不再重复描述，读者可以自行翻阅资料。
这边详细介绍如何使用一致性Hash进行分库分表的设计。
我们通常会将每个实际节点的配置持久化在一个配置项或者是数据库中，应用启动时或者是进行切换操作的时候会去加载配置。配置一般包括一个[StartKey,Endkey)的左闭右开区间和一个数据库节点信息，例如：
示例代码：
private TreeMap<Long, Integer> nodeTreeMap = new TreeMap<>();
@Override
public void afterPropertiesSet() {
// 启动时加载分区配置
List<HashCfg> cfgList = fetchCfgFromDb();
for (HashCfg cfg : cfgList) {
nodeTreeMap.put(cfg.endKey, cfg.nodeIdx);
}
}
public ShardCfg shard(String userId) {
int hash = userId.hashCode();
int dbIdx = nodeTreeMap.tailMap((long) hash, false).firstEntry().getValue();
int tblIdx = Math.abs(hash % 100);
return new ShardCfg(dbIdx, tblIdx);
}
我们可以看到，这种形式和上文描述的Range分表非常相似，Range分库分表方式针对分片键本身划分范围，而一致性Hash是针对分片键的Hash值进行范围配置。
正规的一致性Hash算法会引入虚拟节点，每个虚拟节点会指向一个真实的物理节点。这样设计方案主要是能够在加入新节点后的时候，可以有方案保证每个节点迁移的数据量级和迁移后每个节点的压力保持几乎均等。
但是用在分库分表上，一般大部分都只用实际节点，引入虚拟节点的案例不多，主要有以下原因：
-
a、应用程序需要花费额外的耗时和内存来加载虚拟节点的配置信息。如果虚拟节点较多，内存的占用也会有些不太乐观。
-
b、由于mysql有非常完善的主从复制方案，与其通过从各个虚拟节点中筛选需要迁移的范围数据进行迁移，不如通过从库升级方式处理后再删除冗余数据简单可控。
-
c、虚拟节点主要解决的痛点是节点数据搬迁过程中各个节点的负载不均衡问题，通过虚拟节点打散到各个节点中均摊压力进行处理。
而作为OLTP数据库，我们很少需要突然将某个数据库下线，新增节点后一般也不会从0开始从其他节点搬迁数据，而是前置准备好大部分数据的方式，故一般来说没有必要引入虚拟节点来增加复杂度。
四、常见扩容方案
翻倍扩容法的主要思维是每次扩容，库的数量均翻倍处理，而翻倍的数据源通常是由原数据源通过主从复制方式得到的从库升级成主库提供服务的方式。故有些文档将其称作"从库升级法"。
理论上，经过翻倍扩容法后，我们会多一倍的数据库用来存储数据和应对流量，原先数据库的磁盘使用量也将得到一半空间的释放。如下图所示:
具体的流程大致如下：
①、时间点t1：为每个节点都新增从库，开启主从同步进行数据同步。
②、时间点t2：主从同步完成后，对主库进行禁写。
此处禁写主要是为了保证数据的正确性。若不进行禁写操作，在以下两个时间窗口期内将出现数据不一致的问题：
-
a、断开主从后，若主库不禁写，主库若还有数据写入，这部分数据将无法同步到从库中。
-
b、应用集群识别到分库数翻倍的时间点无法严格一致，在某个时间点可能两台应用使用不同的分库数，运算到不同的库序号，导致错误写入。
③、时间点t3：同步完全完成后，断开主从关系，理论上此时从库和主库有着完全一样的数据集。
④、时间点t4：从库升级为集群节点，业务应用识别到新的分库数后，将应用新的路由算法。
一般情况下，我们将分库数的配置放到配置中心中，当上述三个步骤完成后，我们修改分库数进行翻倍，应用生效后，应用服务将使用新的配置。这里需要注意的是，业务应用接收到新的配置的时间点不一定一致，所以必定存在一个时间窗口期，该期间部分机器使用原分库数，部分节点使用新分库数。这也正是我们的禁写操作一定要在此步完成后才能放开的原因。
⑤、时间点t5：确定所有的应用均接受到库总数的配置后，放开原主库的禁写操作，此时应用完全恢复服务。
⑥、启动离线的定时任务，清除各库中的约一半冗余数据。
为了节省磁盘的使用率，我们可以选择离线定时任务清除冗余的数据。也可以在业务初期表结构设计的时候，将索引键的Hash值存为一个字段。
那么以上述常用姿势四为例，我们离线的清除任务可以简单的通过sql即可实现（需要防止锁住全表，可以拆分成若干个id范围的子sql执行）：
delete from db0.tbl0 where hash_val mod 4 <> 0;
delete from db1.tbl0 where hash_val mod 4 <> 1;
delete from db2.tbl0 where hash_val mod 4 <> 2;
delete from db3.tbl0 where hash_val mod 4 <> 3;
具体的扩容步骤可参考下图：
总结：通过上述迁移方案可以看出，从时间点t2到t5时间窗口呢内，需要对数据库禁写，相当于是该时间范围内服务器是部分有损的，该阶段整体耗时差不多是在分钟级范围内。若业务可以接受，可以在业务低峰期进行该操作。
当然也会有不少应用无法容忍分钟级写入不可用，例如写操作远远大于读操作的应用，此时可以结合canel开源框架进行窗口期内数据双写操作以保证数据的一致性。
该方案主要借助于mysql强大完善的主从同步机制，能在事前提前准备好新的节点中大部分需要的数据，节省大量的人为数据迁移操作。
但是缺点也很明显，一是过程中整个服务可能需要以有损为代价，二是每次扩容均需要对库数量进行翻倍，会提前浪费不少的数据库资源。
我们主要还是看下不带虚拟槽的一致性Hash扩容方法，假如当前数据库节点DB0负载或磁盘使用过大需要扩容，我们通过扩容可以达到例如下图的效果。
下图中，扩容前配置了三个Hash分段，发现[-Inf，-10000）范围内的的数据量过大或者压力过高时，需要对其进行扩容。
主要步骤如下：
①、时间点t1：针对需要扩容的数据库节点增加从节点，开启主从同步进行数据同步。
②、时间点t2：完成主从同步后，对原主库进行禁写。
此处原因和翻倍扩容法类似，需要保证新的从库和原来主库中数据的一致性。
③、时间点t3：同步完全完成后，断开主从关系，理论上此时从库和主库有着完全一样的数据集。
④、时间点t4：修改一致性Hash范围的配置，并使应用服务重新读取并生效。
⑤、时间点t5：确定所有的应用均接受到新的一致性Hash范围配置后，放开原主库的禁写操作，此时应用完全恢复服务。
⑥、启动离线的定时任务，清除冗余数据。
可以看到，该方案和翻倍扩容法的方案比较类似，但是它更加灵活，可以根据当前集群每个节点的压力情况选择性扩容，而无需整个集群同时翻倍进行扩容。
五、小结
本文主要描述了我们进行水平分库分表设计时的一些常见方案。
我们在进行分库分表设计时，可以选择例如范围分表，Hash分表，路由表，或者一致性Hash分表等各种方案。进行选择时需要充分考虑到后续的扩容可持续性，最大数据偏斜率等因素。
文中也列举了一些常见的错误示例，例如库表计算逻辑中公约数的影响，使用前若干位计算库序号常见的数据倾斜因素等等。
我们在实际进行选择时，一定要考虑自身的业务特点，充分验证分片键在各个参数因子下的数据偏斜程度，并提前规划考虑好后续扩容的方案。