分库分表方案

分库分表难题和不步骤

难题

• 新数据库集群的搭建
• 旧库数据同步到新的数据库
• 新库上线
• 数据校验，保证新库数据和旧库数据一致
• 日常中数据库表结构变更

• 数据库和表的扩容

  方案可持续性

• 前期业务数据量级不大，流量较低的时候，我们无需分库分表，也不建议分库分表

• 业务数据量级和业务流量未来进一步升高达到新的量级的时候，我们的分库分表方案可以持续使用

  数据偏斜问题

• 一个良好的分库分表方案，它的数据应该是需要比较均匀的分散在各个库表中的

• 如果我们进行一个拍脑袋式的分库分表设计，很容易会遇到以下类似问题：
  • 某个数据库实例中，部分表的数据很多，而其他表中的数据却寥寥无几，业务上的表现经常是延迟忽高忽低，飘忽不定。
  • 数据库集群中，部分集群的磁盘使用增长特别块，而部分集群的磁盘增长却很缓慢。每个库的增长步调不一致，这种情况会给后续的扩容带来步调不一致，无法操作的问题。

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

  读扩散问题

• 加入分片键选择 了自增的主键，但某个查询要根据其他字段进行查询，这时候就要到每个库没张表中进行查询然后汇总数据，随着表越来越多，查询的次数就越来越多，这就是读扩散问题

• 解决：
  • 分片表
    • 为name列建个新表(nameX)，以name为新的分片键
    • 
  • es

• tidb

  步骤

• 根据容量（当前容量和增长量）评估分库或分表个数 -> 选key（均匀）-> 分表规则（hash或range等）-> 执行（一般双写）-> 扩容问题（尽量减少数据的移动）

  分库分表方案

  Range分库分表

• 该方案根据数据范围划分数据的存放位置。

• 举个最简单例子，我们可以把订单表按照年份为单位，每年的数据存放在单独的库（或者表）

• 缺点

  • 最明显的就是数据热点问题，例如上面案例中的订单表，很明显当前年度所在的库表属于热点数据，需要承载大部分的IO和计算资源。
  • 新库和新表的追加问题。一般我们线上运行的应用程序是没有数据库的建库建表权限的，故我们需要提前将新的库表提前建立，防止线上故障

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

    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);
    }

• 以2库4表为例，0库的表中，只有0、2表中有数据；1库的表中，只有1、3表中有数据

• 以4库4表为例，0库中，只有0表有数据；1库中，只有1表有数据。。。
• 以10库100表为例，如果一个Hash值对100取余为0，那么它对10取余也必然为0。这就意味着只有0库里面的0表才可能有数据，而其他库中的0表永远为空！
• 类似的我们还能推导到，0库里面的共100张表，只有10张表中(个位数为0的表序号)才可能有数据。这就带来了非常严重的数据偏斜问题，因为某些表中永远不可能有数据，最大数据偏斜率达到了无穷大。

• 证明

• 那么是不是只要库数量和表数量互质就可用用这种分库分表方案呢？比如我用11库100表的方案，是不是就合理了呢？
• 答案是否定的，我们除了要考虑数据偏斜的问题，还需要考虑可持续性扩容的问题，一般这种Hash分库分表的方案后期的扩容方式都是通过翻倍扩容法，那11库翻倍后，和100又不再互质。
• 当然，如果分库数和分表数不仅互质，而且分表数为奇数(例如10库101表)，则理论上可以使用该方案，但是我想大部分人可能都会觉得使用奇数的分表数比较奇怪吧。

  常见错误案例二：扩容难以持续

  ```java

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);
}

- 缺点
   - 在计算表序号的时候，依赖了总库的数量，那么后续翻倍扩容法进行扩容时，会出现扩容前后数据不在同一个表中，从而无法实施
   - 数据迁移麻烦，且容易出错
<a name="z45Gf"></a>
#### 常用姿势一：标准的二次分片法
```java
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);
    }

• 通过翻倍扩容后，我们的表序号一定维持不变，库序号可能还是在原来库，也可能平移到了新库中(原库序号加上原分库数)，完全符合我们需要的扩容持久性方案。
• 缺点
  • 翻倍扩容法前期操作性高，但是后续如果分库数已经是大几十的时候，每次扩容都非常耗费资源。
  • 连续的分片键Hash值大概率会散落在相同的库中，某些业务可能容易存在库热点（例如新生成的用户Hash相邻且递增，且新增用户又是高概率的活跃用户，那么一段时间内生成的新用户都会集中在相邻的几个库中）。

    常用姿势二：关系表冗余

    ```java

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);

}

- 上述实例中**selectRandomDbIdx方法**作用为生成该分片键对应的存储库序号，这边可以非常灵活的动态配置。例如可以为每个库指定一个权重，权重大的被选中的概率更高，权重配置成0则可以将关闭某些库的分配。当发现数据存在偏斜时，也可以调整权重使得各个库的使用量调整趋向接近。
- 理论上后续进行扩容的时候，仅需要挂载上新的数据库节点，将权重配置成较大值即可，无需进行任何的数据迁移即可完成
- 缺点
   - 每次读取数据需要访问路由表，虽然使用了缓存，但是还是有一定的性能损耗。
   - 路由关系表的存储方面，有些场景并不合适。例如上述案例中用户id的规模大概是在10亿以内，我们用单库百表存储该关系表即可。但如果例如要用文件MD5摘要值作为分片键，因为样本集过大，无法为每个md5值都去指定关系（当然我们也可以使用md5前N位来存储关系）
<a name="vMSsV"></a>
#### 常用姿势三：基因法
- 使用原分片键中的某些基因（例如前四位）作为库的计算因子，而使用另外一些基因作为表的计算因子
```java
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);
}

常用姿势四：剔除公因数法

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);
}

常用姿势五：一致性Hash法

• 一致性Hash算法也是一种比较流行的集群数据分区算法，比如RedisCluster即是通过一致性Hash算法，使用16384个虚拟槽节点进行每个分片数据的管理

扩容方案

翻倍扩容法

• 翻倍扩容法的主要思维是每次扩容，库的数量均翻倍处理，而翻倍的数据源通常是由原数据源通过主从复制方式得到的从库升级成主库提供服务的方式。故有些文档将其称作”从库升级法“

  流程

1. 时间点t1：为每个节点都新增从库，开启主从同步进行数据同步
2. 时间点t2：主从同步完成后，对主库进行禁写
   1. 此处禁写主要是为了保证数据的正确性。若不进行禁写操作，在以下两个时间窗口期内将出现数据不一致的问题：
      1. 断开主从后，若主库不禁写，主库若还有数据写入，这部分数据将无法同步到从库中。
      2. 应用集群识别到分库数翻倍的时间点无法严格一致，在某个时间点可能两台应用使用不同的分库数，运算到不同的库序号，导致错误写入。
3. 时间点t3：同步完全完成后，断开主从关系，理论上此时从库和主库有着完全一样的数据集。
4. 时间点t4：从库升级为集群节点，业务应用识别到新的分库数后，将应用新的路由算法
   1. 一般情况下，我们将分库数的配置放到配置中心中，当上述三个步骤完成后，我们修改分库数进行翻倍，应用生效后，应用服务将使用新的配置。这里需要注意的是，业务应用接收到新的配置的时间点不一定一致，所以必定存在一个时间窗口期，该期间部分机器使用原分库数，部分节点使用新分库数。这也正是我们的禁写操作一定要在此步完成后才能放开的原因
5. 确定所有的应用均接受到库总数的配置后，放开原主库的禁写操作，此时应用完全恢复服务。
6. 启动离线的定时任务，清除各库中的约一半冗余数据
   1. 为了节省磁盘的使用率，我们可以选择离线定时任务清除冗余的数据。也可以在业务初期表结构设计的时候，将索引键的Hash值存为一个字段。
   2. 那么以上述常用姿势四为例，我们离线的清除任务可以简单的通过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;

      一致性Hash扩容

      分库分表后需要支持的场景（查询）

• B端

• C端

  路由策略

  路由KEY选取

  路由规则

  全局ID

  雪花算法

• 

• 一共64bite，8字节
  • 第一部分：0表示正数
  • 第二部分：时间戳
  • 第三部分：5位的数据中心ID+机器ID，表示同一时刻可以允许1024台机器获取唯一ID
  • 第四部分：序列号，12位=4096
• 可以允许同意时刻，可以允许1024台机器来获取全局ID，且每台机器最多获取4096个ID
• 时钟回拨问题
  • 认为调节系统时间
  • 解决：
    • 缓存上一次的时间戳
    • 每次生成时候，比较一下当前的时间戳和上次的时间戳
    • 如果判断发生时钟回拨，则那上次的时间戳进行+1

      美团Leaf

      介绍文章

      TinyID

      Uidgenerator

      介绍