分库分表后如何解决唯一主键问题？雪花算法、自增id详解_自增主键分表

在单库单表时，业务 ID 可以依赖数据库的自增主键实现，现在我们把存储拆分到了多处，如果还是用数据库的自增主键，势必会导致主键重复。但要是利用加锁来处理，又会严重拖垮效率。

实际开发中主要有三种方式，另附一篇博客，介绍了大厂对于以下几种思路的具体实现

UUID

虽然可以生成唯一主键，但是并不合适，因为它是36位的字符串，太长了，会让每一行数据变长，那不利于B+树节点的存储和搜索。
UUID 最大的缺陷是它产生的 ID 不是递增的。一般来说，我们倾向于在数据库中使用自增主键，因为这样可以迫使数据库的树朝着一个方向增长，而不会造成中间叶节点分裂，这样插入性能最好。而整体上 UUID 生成的 ID 可以看作是随机，那么就会导致数据往页中间插入，引起更加频繁地页分裂，在糟糕的情况下，这种分裂可能引起连锁反应，整棵树的树形结构都会受到影响。所以我们普遍倾向于采用递增的主键。自增主键还有一个好处，就是数据会有更大的概率按照主键的大小排序，两条主键相近的记录，在磁盘上位置也是相近的。那么可以预计，在范围查询的时候，我们能够更加充分地利用到磁盘的顺序读特性。

Snowflake

Snowflake 是 Twitter 开源的分布式 ID 生成算法，由 64 位的二进制数字组成，一共分为 4 部分：


那么雪花算法保证 ID 唯一性的理由也很充分了。

• 时间戳是递增的，不同时刻产生的 ID 肯定是不同的。
• 机器 ID 是不同的，同一时刻不同机器产生的 ID 肯定也是不同的。
• 同一时刻同一机器上，可以轻易控制序列号。

因为服务器的本地时钟并不是绝对准确的，在一些业务场景中，比如在电商的整点抢购中，为了防止不同用户访问的服务器时间不同，则需要保持服务器时间的同步。为了确保时间准确，会通过 NTP 的机制来进行校对，NTP（Network Time Protocol）指的是网络时间协议，用来同步网络中各个计算机的时间。
如果服务器在同步 NTP 时出现不一致，出现时钟回拨，那么 SnowFlake 在计算中可能出现重复 ID。除了 NTP 同步，闰秒也会导致服务器出现时钟回拨，不过时钟回拨是小概率事件，在并发比较低的情况下一般可以忽略。
如何解决时钟回拨问题：

• 如果时间回拨时间较短，比如配置 5ms 以内，那么可以直接等待一定的时间，让机器的时间追上来。
• 如果时间的回拨时间较长，我们不能接受这么长的阻塞等待，那么又有两个策略:
  • 直接拒绝，抛出异常。打日志，通知 RD 时钟回滚。
  • 利用扩展位。不同业务场景位数可能用不到那么多比特位，那么我们可以把扩展位数利用起来。比如：当这个时间回拨比较长的时候，我们可以不需要等待，直接在扩展位加 1。两位的扩展位允许我们有三次大的时钟回拨，一般来说就够了，如果其超过三次我们还是选择抛出异常，打日志。

面试回答亮点

调整分段

可以根据需求自定义各字段含义，比如改短时间戳字段之类的。并且机器id可以并不是物理意义上的，一个机器开两个进程就可以代表俩机器；或者这一部分就划分为机房id、机器id、进程id三字段也不是不行，百度就是这么干的。

序列号耗尽

有可能并发性很高，那么$2^{10}$不够用，可以多分配点；或者等1ms，再分配（也是限流了，但要考虑好，这可能造成业务阻塞）；或者就暴力点用128bit存储。

数据堆积

分库分表是按照 ID 除以 32 的余数来进行的，那么如果业务非常低频，以至于每一个时刻都只生成了尾号为 1 的 ID（也就是1ms就一个），那么所有的数据都分到了一张表里面。这解决方法也很简单就是每次不从0开始，而是从一个随机数开始；还有一个策略就是序列号从上一时刻的序列号开始增长，但是如果上一时刻序列号已经很大了，那么就可以退化为从 0 开始增长。这样的话要比随机数更可控一点，并且性能也要更好一点。

一般来说，这个问题只在利用 ID 进行哈希的分库分表里面有解决的意义。在利用 ID 进行范围分库分表的情况下，很显然某一段时间内产生的 ID 都会落到同一张表里面。不过这也是我们的使用范围分库分表预期的行为，不需要解决。

主键内嵌分库分表键

加分项，可以不拘泥于雪花算法原始字段的含义，可以把例如分库分表用的用户id键嵌入到生成主键订单id的雪花算法里。比如在时间戳的后几位嵌入主键后四位。虽然通常情况下都是用户用自己id查自己的订单，但假设我们只有订单id也可以取出用户id后四位来判断数据存在了哪个库哪个表里。反正就是可以把实际业务用到的东西嵌入到里面，只要我们最终能够保证 ID 生成是全局递增（整体递增，因为有时间戳）的，并且是独一无二的（需要同一时刻同一用户下了两个订单并且随机到的序列号一致才会冲突）就可以。

自增id

淘宝的TDDL等数据库中间件使用的主键生成策略。首先在数据库中创建 sequence 表，其中的每一行，用于记录某个业务主键当前已经被占用的 ID 区间的最大值。sequence 表的主要字段是 name 和 value，其中 name 是当前业务序列的名称，value 存储已经分配出去的 ID 最大值。接下来插入一条行记录，当需要获取主键时，每台服务器主机从数据表中取对应的 ID 区间缓存在本地，同时更新 sequence 表中的 value 最大值记录。比如我们这里设置步长为 200，原先的 value 值为 1000，更新后的 value 就变为了 1200。取到对应的 ID 区间后，在服务器内部进行分配，涉及的并发问题可以依赖乐观锁等机制解决。有了对应的 ID 增长区间，在本地就可以使用 AtomicInteger 等方式进行 ID 分配。

经过分库分表之后我有十个表，那么我可以让每一个表按照步长来生成自增 ID。比如说第一个表就是生成 1、11、21、31 这种 ID，第二个表就是生成 2、12、22、32 这种 ID。

不同的机器在相同时间内分配出去的 ID 可能不同，这种方式生成的唯一 ID，不保证严格的时间序递增，，但是在一个表内部，它肯定是递增的。可以保证整体的趋势递增，在实际生产中有比较多的应用。

面试回答亮点

其实总体来说就是三个思路，一个是不等用完提前取防止阻塞，一个是取得时候一次多取点，最后一个是一个线程取完拿回来存着所有线程一起分

批量取

批量取是指业务方每次跟发号器打交道，不是只拿走一个 ID，而是拿走一批，比如说 100 个。拿到之后业务方自己内部慢慢消耗。消耗完了再去取下一批。

这种优化思路的优点就是极大地减轻发号器的并发压力。比如说一批是 100 个，那么并发数就降低为原本的 1%了。缺点就是可能破坏递增的趋势。比如说一个业务方 A 先取走了 100 个 ID，然后业务方 B 又取走 100 个，结果业务方 B 先用完了自己取的 ID，插到了数据库里面；然后业务方 A 才用完自己的 100 个。

提前取

提前取是指业务方提前取到 ID，这样就不需要真的等到需要 ID 的时候再临时取。提前取可以和批量取结合在一起，即提前取一批，然后内部慢慢使用。在快要用完的时候，再取一批。同时也要设计一个兜底措施，如果要是用完了，新的一批还没取过来，要让业务方停下来等待。

这个思路的优点是能够提高业务方的性能，缺点和前面一样是会破坏 ID 的递增性。

singleflight取

这个就类似于在缓存中应用 singleflight 模式。假如说业务方 A 有几十个线程或者协程需要 ID，那么没有必要让这些线程都去取 ID，而是派一个代表去取。这个代表取到之后再分发给需要的线程。这也能够降低发号器的并发负载。

这个思路还可以进一步优化，就是每次取的时候多取一点，那么后续还有别的线程需要，也不用自己去取了。

局部分发

假如说现在整个实例上有 1000 个 ID，这些 ID 是批量获取的。那么一个线程需要 ID 的时候，它就不再是只拿一个，而是拿 20 个，然后存在自己的 TLB（thread-local-buffer) 里面，以后这个线程需要 ID 的时候，就先从自己的 TLB 里面拿，避开了全局竞争，减轻了并发压力。