本文字数：4811字，阅读大约需要 16 分钟。
分库，分表，分库分表
首先，我们需要知道所谓的"分库分表"，根本就不是一件事，而是三件事，它们要解决的问题也都不一样。
这三件事分别是"只分库不分表"、"只分表不分库"、以及"既分库又分表"。
什么时候分库？
其实，分库主要解决的是并发量大的问题。因为并发量一旦上来了，那么数据库就可能会成为瓶颈，因为数据库的连接数是有限的，虽然可以调整，但也不是无限调整的。
所以，当你的数据库的读或者写的 QPS 过高，导致数据库连接数不足的时候，就需要考虑分库了，通过增加数据库实例的方式来提供更多的可用数据库连接，从而提升系统的并发度。
比较典型的分库场景就是在做微服务拆分的时候，会按照业务边界，把各个业务的数据从一个单一的数据库中拆分开，分别把订单、物流、商品、会员等单独放到对应的数据库中。
还有就是有的时候可能会把历史订单挪到历史库里面去。这也是分库的一种具体做法。
什么时候分表？
分库主要解决的是并发量大的问题，那分表其实主要解决的是数据量大的问题。
假如你的单表数据量非常大，因为并发不高，数据库连接可能还够，但是存储和查询的性能遇到了瓶颈，做了很多优化之后还是无法提升效率的时候，就需要考虑做分表了。
一般我们认为，单表行数超过 500 万行或者单表容量超过 2GB 时，才需要考虑做分库分表。
那我们是不是等到数据量到达 500 万后，才开始分库分表呢？
这个也不绝对，应该提前规划分库分表，如果估算 3 年后，表的数据量都不会到达 500 万，则不需要分库分表。
分库分表的时候需要考虑数据未来 2~3 年的一个增量，即使现在数据量不多，但是每天的数据增量很可观，几个月之后就可以突破 500 万上限，那么不是等到数据量到达 500 万的时候才分库分表，而是现在就应该考虑了。
什么时候既分库又分表？
那么什么时候分库又分表呢，那就是既需要解决并发量大的问题，又需要解决数据量大的问题的时候。通常情况下，高并发和大数据量的问题都是同时发生的，所以，我们会经常遇到分库分表需要同时进行的情况。
横向拆分 & 纵向拆分
谈及到分库分表，那就要涉及到该如何做拆分的问题。
通常在做拆分的时候有两种分法，分别是横向拆分(水平拆分)和纵向拆分(垂直拆分)。
假如我们有一张表，如果把这张表中某一条记录的多个字段，拆分到多张表中，这种就是纵向拆分。那如果把一张表中的不同的记录分别放到不同的表中，这种就是横向拆分。
横向拆分的结果是数据库表中的数据会分散到多张分表中，使得每一个单表中的数据的条数都有所下降。比如我们可以把不同的用户的订单，分表拆分放到不同的表中。
纵向拆分的结果是数据库表中的数据的字段数会变少，使得每一个单表中的数据的存储有所下降。比如可以把商品详情信息、价格信息、库存信息等等分别拆分到不同的表中。
纵向拆分比较适合做冷热分离，可以使得行数据变小，一个数据页就能存放更多的数据，在查询时就会减少I/O次数。
分表算法
选定了分表字段之后，如何基于这个分表字段来准确的把数据分表到某一张表中呢?
这就是分表算法要做的事情了，但是不管什么算法，我们都需要确保一个前提，那就是同一个分表字段，经过这个算法处理后，得到的结果一定是一致的，不可变的。
通常的分表算法有以下几种：
Range 范围
Range，即范围策略划分表。比如我们可以将表的主键 order_id，按照从 0~300万 的划分为一个表，300万 ~ 600万划分到另外一个表。
有时候我们也可以按时间范围来划分，如不同年月的订单放到不同的表。
- 优点：范围分表，有利于扩容。
- 缺点：最近一段时间的数据都是汇聚在一张表里面，可能会有热点问题。比如最近一个月的订单都在 0~300万之间，平时用户一般都查最近一个月的订单比较多，那么请求就都打到 order_01 了。
Hash 取模
Hash 取模策略：
指定的路由key（一般是 user_id、order_id 等作为key）对分表总数进行取模，把数据分散到各个表中。
比如原始订单表信息，我们把它分成4张分表：
比如 id=1，对 4 取模，就会得到1，就把它放到 t_order_1 ;
一般，我们会取哈希值，再做取余：
Math.abs(orderId.hashCode()) % table_number
- 优点：Hash取模的方式，不会存在明显的热点问题。
- 缺点：如果未来某个时候，表数据量又到瓶颈了，需要扩容，就比较麻烦。所以一般建议提前规划好，一次性分够（可以考虑一致性哈希）。
一致性 Hash
为了解决 Hash 扩容的问题，我们可以采用一致性哈希的方式来做分表。
一致性哈希可以按照常用的 Hash 算法来将对应的 key 哈希到一个具有 2^32 次方个节点的空间中，形成一个顺时针首尾相接的闭合环形，这个环称为哈希环。
当添加一台新的数据库服务器时，只有增加服务器的位置和逆时针方向第一台服务器之间的键会受影响。
简单来说，一致性哈希算法能够使机器节点的变动对整个集群的影响达到最小。
一致性哈希也存在一些问题，如：节点漂移、数据倾斜。这些都有对应的解决方案，这里不再赘述。
参考：一致性哈希问题及其解决方案。
斐波那契散列
前面几种分表算法，大家会接触多一点，斐波那契散列实际在分表算法中几乎不被使用。
JDK 的 ThreadLocal 源码中有一段有意思的代码，如下所示：
定义了一个魔法值 HASH_INCREMENT = 0x61c88647，这个值被称之为 “魔数”。
0x61c88647 与一个神奇的数字产生了联系，它就是 (Math.sqrt(5) - 1)/2。也就是传说中的黄金比例 0.618（0.618 只是一个粗略值），即0x61c88647 = 2^32 * 黄金分割比，同时也对应了上文提到的斐波那契散列。
它常用于在散列中增加哈希值。上面的代码注释中也解释到是为了让哈希码能均匀的分布在 2 的 N 次方的数组里。
至于为什么使用斐波那契数列后散列更均匀，就涉及到相关数学问题了，此处不做更多解释。
严格雪崩标准（SAC）
上面介绍了一些分表算法，那么一个好的分表算法有没有参考标准呢？
在密码学中，雪崩效应（avalanche effect）指加密算法的一种理想属性。雪崩效应是指当输入发生最微小的改变（例如，反转一个二进制位）时，也会导致输出的不可区分性改变（输出中每个二进制位有50%的概率发生反转）。
严格雪崩标准（SAC），建立于密码学的完全性概念上，是雪崩效应的形式化。它指出，当任何一个输入位被反转时，输出中的每一位均有 50% 的概率发生变化。
简单来说，当我们对数据库从 8库32表 扩容到 16库32表 的时候，每一个表中的数据总量都应该以 50% 的数量进行减少。这样才是合理的。
引入严格雪崩标准（SAC） 之后，斐波那契散列是不满足这个标准的，也就是说使用斐波那契散列，在分库分表扩容情况下，可能导致数据分布不均匀，这也是为什么斐波那契散列几乎不用于分表算法的原因。
订单分库分表实战
背景：订单表的读写场景复杂，⼀般有买家维度、卖家维度、订单号维度 3 个主要维度。多读写维度情况下⽆论采取哪种维度做分库分表，对另外两种维度的查询性能来说，基本都是灾难。
解决方案：双拆分列哈希（RANGE_HASH）。
选取两个拆分键，两个拆分键的后 N 位需确保一致，根据任一拆分键后 N 位计算哈希值，然后再按分库数取模，完成路由计算。
先采用 RANGE_HASH 拆分算法按买家 id 后 N 位、订单号后 N 位维度做分库分表，作为买家表逻辑表。再用 HASH 拆分函数按商家 id 冗余一份数据，作为卖家表逻辑表。
订单号生成规则需要根据买家表分表特性订单号后 N 位等于买家 id 后 N 位做设计。
比如用户id为 12345678，则用户在下单时生成的单号为：xxxxxxxxx345678，单号前几位可以根据公司自己规则设定，但是要注意不能重复。
全局 ID 的生成
涉及到分库分表，就会引申出分布式系统中唯一主键 ID 的生成问题，有以下几种方式：
UUID
UUID 是可以做到全局唯一的，而且生成方式也简单，但是我们通常不推荐使用它做唯一ID，首先 UUID 太长了，其次字符串的查询效率也比较慢，而且没有业务含义，根本看不懂。
基于某个单表做自增主键
多张单表生成的自增主键会冲突，但是如果所有表的主键都从同一张表生成是不是就可以了。
所有的表在需要主键的时候，都到这张表中获取一个自增的 ID。
这样做是可以做到唯一，也能实现自增，但是问题是这个单表就变成整个系统的瓶颈，而且也存在单点问题，一旦他挂了，那整个数据库就都无法写入了。
雪花算法
雪花算法也是比较常用的一种分布式 ID 的生成方式，它具有全局唯一、递增、高可用的特点。
雪花算法生成的主键主要由 4 部分组成，1bit 符号位、41bit 时间戳位、10bit 工作进程位以及 12bit 序列号位。
时间戳占用 41bit，精确到毫秒，总共可以容纳约 69 年的时间。
工作进程位占用 10bit，其中高位 5bit 是数据中心 ID，低位 5bit 是工作节点 ID，最多可以容纳 1024 个节点。
序列号占用 12bit，每个节点每毫秒从0开始不断累加，最多可以累加到 4095，一共可以产生 4096 个 ID。
所以，雪花算法在同一毫秒内最多可以生成 1024 X 4096 = 4194304 个唯一的 ID。
时间回拨问题
熟悉雪花算法的可能了解到雪花算法存在名为“时间回拨” 的问题。
时间回拨：由于机器的时间是动态调整的，有可能会出现时间跑到之前几毫秒，如果这个时候获取到了这种时间，则会出现数据重复。
时间回拨问题解决思路可以参考美团开源的 Leaf。
美团 Leaf 引入了 Zookeeper 来解决时钟回拨问题，其大致思路为：每个 Leaf 运行时定时向 zk 上报时间戳。每次 Leaf 服务启动时，先校验本机时间与上次发 ID 的时间，再校验与 zk 上所有节点的平均时间戳。如果任何一个阶段有异常，那么就启动失败报警。
这个解决方案还是比较好理解的，就是对比上次发 ID 的时间，还有其他机器的平均时间，通过本地存储时间戳 定时上报时间戳的方式，解决了时间回拨的问题。
分库分表迁移
有一个未分库分表的系统，现在要分库分表，如何才可以让系统从未分库分表切换到分库分表上？
停机迁移方案
先说一个最 low 的方案，就是很简单，大伙凌晨 12点 开始运维，网站或者 app 挂个公告，说 0 点到早上 6 点进行服务器维护，无法访问......
接着到 0 点，停机，系统停掉，没有流量写入了，此时老的单库单表数据库静止了。然后提前写好一个导数的一次性工具，此时直接跑起来，然后将单库单表的数据读出来，写到分库分表里面去。
导数完了之后，就 ok 了，修改系统的数据库连接配置啥的，包括可能代码和 SQL 也许有修改，那你就用最新的代码，然后直接启动连到新的分库分表上去。
但是这个方案比较 low，有个致命的问题就是业务要中断，来看看高大上一点的方案。
双写迁移方案
这个是常用的一种迁移方案，比较靠谱一些，不用停机。
大致步骤如下：
- 先改造我们的数据写入端， 使数据同时写入旧数据库和新数据库。
- 对存量数据进行不停机的迁移。
- 等到双写服务运行一段时间，再次进行旧数据和新数据的校验同步。
- 完全切换读取的数据源为新数据库，关闭旧数据库的写入和读取，下线旧数据库。
这种方式的好处是：迁移的过程可以随时回滚，将迁移的风险降到了最低。劣势是：时间周期比较长，应用有改造的成本。
分库分表带来的问题
分库分表之后，会带来很多问题。
首先，做了分库分表之后，所有的读和写操作，都需要带着分表字段，这样才能知道具体去哪个库、哪张表中去查询数据。如果不带的话，就得支持全表扫描。
还有，一旦我们要从多个数据库中查询或者写入数据，就有很多事情都不能做了，比如跨库事务就是不支持的。
所以，分库分表之后就会带来因为不支持事务而导致的数据一致性的问题。
其次，做了分库分表之后，以前单表中很方便的分页查询、排序等等操作就都失效了。因为我们不能跨多表进行分页、排序。
总之，分库分表虽然能解决一些大数据量、高并发的问题，但是同时也会带来一些新的问题。所以，在做数据库优化的时候，还是建议大家优先选择其他的优化方式，最后再考虑分库分表。
参考 & 推荐文章
https://www.cnblogs.com/xiaowangbangzhu/p/17457604.html
https://www.51cto.com/article/709614.html
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://tech.meituan.com/2016/11/18/dianping-order-db-sharding.html
https://github.com/bighong0404/bighong0404.github.io/blob/master/article/编程/算法algarithm/从ThreadLocal的实现看散列算法.md
