Java面试题（十）_java面试题 数据库分库分表设计

数据偏斜问题

一个良好的分库分表方案，它的数据应该是需要比较均匀的分散在各个库表中的。如果我们进行一个拍脑袋式的分库分表设计，很容易会遇到以下类似问题：

a、某个数据库实例中，部分表的数据很多，而其他表中的数据却寥寥无几，业务上的表现经常是延迟忽高忽低，飘忽不定。b、数据库集群中，部分集群的磁盘使用增长特别块，而部分集群的磁盘增长却很缓慢。每个库的增长步调不一致，这种情况会给后续的扩容带来步调不一致，无法统一操作的问题。

这边我们定义分库分表最大数据偏斜率为 ：（数据量最大样本 - 数据量最小样本）/ 数据量最小样本。一般来说，如果我们的最大数据偏斜率在5%以内是可以接受的。

 

分表的方案是什么呢？

Range分库分表

顾名思义，该方案根据数据范围划分数据的存放位置。

举个最简单例子，我们可以把订单表按照年份为单位，每年的数据存放在单独的库（或者表）中。如下图所示：

通过数据的范围进行分库分表，该方案是最朴实的一种分库方案，它也可以和其他分库分表方案灵活结合使用。时下非常流行的分布式数据库：TiDB数据库，针对TiKV中数据的打散，也是基于Range的方式进行，将不同范围内的[StartKey,EndKey)分配到不同的Region上。

下面我们看看该方案的缺点：

• a、最明显的就是数据热点问题，例如上面案例中的订单表，很明显当前年度所在的库表属于热点数据，需要承载大部分的IO和计算资源。

• b、新库和新表的追加问题。一般我们线上运行的应用程序是没有数据库的建库建表权限的，故我们需要提前将新的库表提前建立，防止线上故障。

这点非常容易被遗忘，尤其是稳定跑了几年没有迭代任务，或者人员又交替频繁的模块。

• c、业务上的交叉范围内数据的处理。举个例子，订单模块无法避免一些中间状态的数据补偿逻辑，即需要通过定时任务到订单表中扫描那些长时间处于待支付确认等状态的订单。

这里就需要注意了，因为是通过年份进行分库分表，那么元旦的那一天，你的定时任务很有可能会漏掉上一年的最后一天的数据扫描。

Hash分库分表

虽然分库分表的方案众多，但是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开始从其他节点搬迁数据，而是前置准备好大部分数据的方式，故一般来说没有必要引入虚拟节点来增加复杂度。