1. 背景

在关系数据库中，当单个库的负载、连接数、并发数等达到数据库的最大上限时，就得考虑做数据库和表的拆分。如一个简单的电商数据库，在业务初期，为了快速验证业务模式，把用户、商品、订单都放到一个数据库中，随着业务的发展及用户量的增长，单数据库逐渐不能支撑业务（MySQL中单记录容量超过1K时，单表数据量建议不超过一千万条），这时就得考虑把数据库和表做出拆分。

2. 垂直拆分

所谓垂直拆分，就是将数据库及表由一个拆分为多个，即垂直拆分为用户数据库、商品数据库和订单数据库（垂直拆库），订单表可以垂直拆分为订单基本信息表，订单收货地址表、订单商品表（垂直拆表）等，每一个表里保存了一个订单的一部分数据

image.png

3. 水平拆分

所谓垂直拆分，就是说在垂直拆库/表后，单库/表容量还是太大，那就将一个库、一个表水平扩展为多个库，多个表，每一个拆分后的表中保存的依然是一个订单的完整信息。如电商数据库，我们按水平拆分数据库和表后，每一个拆分后的数据库表与现有未拆分前的都保持一致。

image.png

4. 拆分键

随着业务的发展及用户量的增长，分库分表是必然的选择，但是分库分表后，容易遇到的问题，就是拆分键的设计。

一般情况下，拆分键的选取遵循以什么维度进行查询就选取该维度为拆分键。如：订单表就以订单号作为拆分键，商品表就以商品编号作为拆分键。拆分键选取后，对于一些非拆分键的单条件查询，我们需要怎么支持呢？

4.1 等值法

对于非拆分键的单条件查询，对这一个单条件的赋值，可以将其值与拆分键保持一致。比如在电商场景中，用户下订单后，需要通过物流给用户把商品送到用户手上。对于用户来说仅能看到订单信息，订单上展示的物流信息用户也是通过订单号查询而来；但对于物流系统来说，其系统里的业务主键（拆分键）是运单号，此时，运单号如果和订单号相同，即可完美解决这一问题。订单表和运单表的基本数据模型如下：

订单表

image.png

运单表

image.png

在订单表中，拆分键order_id与运单表中的拆分键waybill_code值相同，当按订单号查询运单表里的运单信息时，可以直接查询拆分键waybill_code获取订单对应的运单信息。

小公司可以直接这样设计，因为订单和运单都是同一个部门处理，但是稍微大点的公司就不太可能用这种方案，因为需要跨部门协作，不同部门不同业务，很难使用同一个单号来当订单号和运单号，通常是会有个流水号作为全链路唯一。

4.2 索引法

对于常用的非拆分键，我们可以将其与拆分键之间建立一个索引关系，当按该条件进行查询时，先查询对应的拆分键，再通过拆分键查询对应的数据信息。

image.png

当查询用户（user001）的下单记录时，通过用户编码先查询索引表，查询出user001的所有下单的订单号（10001），再通过订单号查询订单表获取用户的订单信息；同理，根据运单号（Y00232）查询订单信息时，在索引表里先查询到对应的订单号，再根据订单号查询对应的订单信息。

缺点：

1. 需要先从索引表反查一次；
2. 这张索引表会很大，有时候索引表也需要分表，

4.3 基因法

基因法是对上面等值法的优化，等值法要求不同表的拆分键值保持一致，但是实际上不同业务表的拆分键值是有其业务意义的。

但是我们可以让不同拆分键存在相同规则的部分，且这部分用来做拆分键，从而定位库表。

4.1 理论基础

如果我们对一个10进制的数字按10取模，取模的结果与这串数的前面所有位都没有任何关系，最后1位决定取模结果：

image.png

同理，按100(10^{2)取模，最后2位决定取模结果，按1000(10}3)取模，最后3位决定取模结果：

image.png

同理：一个二进制的值，按2^n取模，也是最后n位决定取模结果：

image.png

那么我们在生成订单号的时候，只要把order_no二进制的最后（n+1）位的二进制数设置为user_id的最后（n）位，那么我们对user_id/order_no取余都能得到相同的结果了。（原理：比n位高的值，都是b数的倍数，取余时直接归零，所以取余就是取二进制最后n位）

4.2 应用

假如我们现在现有16个库，128个表，定位的流程是hash(user_id）% 16 定位库的位置， hash(user_id）% 128 定位表的位置；

所以在我们生成订单号时，先对user_id提取一个基因， 也就是二进制最后 7位，然后这个最后7位二进制也作为order_no的二进制最后7位，这样就能保证order_no的路由结果与user_id完全一致；

通过基因法，我们可以通过非拆分键也能快速定位到具体的表。

4.3 代码实现

备注：这个demo有点问题

    public static void main(String[] args) {
        SnowFlakeIdGenerator snowFlakeIdGenerator = new SnowFlakeIdGenerator();
 
        for (int i = 1; i < 1000; i++) {
            //生成userId和提取基因
            long userId = snowFlakeIdGenerator.generateId();
            String userIdGene = fetchGene(userId, 128);
            
            //利用基因生成orderId
            long rawOrderId = snowFlakeIdGenerator.generateId();
            Long orderId = generateWithGene(rawOrderId, userIdGene);
 
            System.out.println("userId: " + userId + ",余数：" + userId % 128);
            System.out.println("orderId: " + rawOrderId + ",余数：" + orderId % 128);
        }
    }
 
    /**
     * 抽取基因
     *
     * @param id    id
     * @param index 16/128 需要取余的数
     * @return {@link String}
     */
    public static String fetchGene(Long id, Integer index) {
        return String.format("%07d", Integer.valueOf(Long.toBinaryString(id % index)));
    }
 
    /**
     * 根据基因，生成id
     *
     * @param rawId        原始id
     * @param binarySuffix 二进制后缀
     * @return {@link Long}
     */
    public static Long generateWithGene(Long rawId, String binarySuffix) {
        String s = Long.toBinaryString(rawId);
        String substring = s.substring(0, s.length() - binarySuffix.length() + 1);
        String newBinaryString = substring + binarySuffix;
        return Long.parseLong(newBinaryString, 2);
    }

分库分表后，我们通常会采用雪花算法来生成分片键，比如订单号，商品编号，
我们在雪花算法的图下加入了订单id生成的示意图， 比如我们有16个库，128张表，则需要截取二进制订单id的最后LOG(128,2)=7位，作为分库/分表基因。

image.png

然后对订单id用hash生成60位，加上从用户id那边获取的4位基因，形成最终的订单id。其他业务id也使用相同的办法处理。

分库/分表策略时，直接设定使用该id进行水平切分。由于所有业务都有相同的最后4位，这样sharding时都会进入相同的库/表