如何设计分布式ID发号器

系统背景

一般在分库分表场景，就会有分布式 ID（全局唯一 ID）的需求，因为需要有一个唯一标识来标记一个订单或者其他类似的数据等。

具体需求：

全局唯一（所有系统要求）：生成的 ID 不能重复，否则在分库分表的场景下会造成冲突。
单调递增（部分系统要求[1]）：保证写入数据库的时候是顺序写入，提高写入性能。

[1]：并不是所有系统都需要，例如分布式追踪的请求 ID 就可以不需要单调递增。而那些需要存到数据库里作为 ID 主键的场景，可能就需要保证全局唯一 ID 是单调递增的。
另外，还需要考虑安全方面的问题。如果全局唯一 ID 是顺序递增的，那么可能会造成业务信息的泄露。例如竞争对手可以通过订单 ID 计算我们每天的订单数。

全局唯一 ID 有很多解决方案，常见的为以下4种：

UUID
雪花算法
基于数据库自增主键
Redis原子自增

解决方案

UUID

UUID（Universally Unique Identifier），即全局唯一标识符，它是 Java 中自带的 API。一个标准的 UUID 包含 32 个 16 进制的数字，以中横线作为分隔符分为 5 段，每段的长度分别为 8 字符、4 字符、4 字符、4 字符、12 字符，大小为 36 个字符。一个简单的 UUID 示例：630e4100-e29b-33d4-a635-246652140000

UUID 优点

本地生成，无外部依赖，性能高且实现简单。

UUID 缺点

字段太长，占用存储空间。
非自增，无序插入会导致数据页频繁分裂，降低数据库写入性能。

因此，UUID 比较适用于非数据库 ID 存储的情况，例如生成一个本地的分布式追踪请求 ID。

雪花算法

雪花算法（SnowFlake）是 Twitter 开源的分布式 ID 生成算法，其思路是用 64 位来表示一个 ID，并将 64 位分割成 4 个部分。

实际上就用到了63bit，第一个bit没用，固定为 0，表示为正整数。二进制中最高位是符号位，1 表示负数，0表示正数。由于 ID 都是正整数，所以固定为0。

雪花算法ID结构

第二部分 41bit 是时间戳，精确到毫秒，可以使用 69 年。时间戳带有自增属性。
第三部分 10bit 是机器 ID，可以表示 1024 个节点。如果有机房的划分，可拆分成 5 位 datacenterId 和 5 位 workerId，datacenterId 代表机房，workerId 表示机器 ID。
第四部分 12bit 是自增序列号，12bit 可以表示 2 的 12 次方个 ID，即可以支持同一节点同一毫秒生成最多 4095 个 ID。

雪花算法的优点

有序，提高写入性能。ID 从整体来看有序的、单调递增的，将其作为数据库主键 ID 时可以实现顺序写入，提高写入性能。
不依赖第三方。生成方式简单、配置灵活，不依赖外部三方组件或中间件，因此其稳定性较高。
保证业务安全问题。雪花算法生成的 ID 是单调递增的，但其递增步长又不是确定的，因此无法从 ID 的差值推断出生成的数量，从而可以保护业务隐私。
可自定义。许多国内大厂的开源发号器的实现，都是在雪花算法的基础上做改进（例如：百度开源的 UidGenerator、美团开源的 Leaf 等等）。这些类雪花算法的核心都是将 64 位进行更合理的划分，从而使得其更适合自身场景。

雪花算法的缺点

依赖时钟，如果机器的系统时间发生时钟回拨，即时间较正常的时间慢，可能会导致发号重复。

时钟回拨解决方案：
（1）理论上可以存储上一次发号的时间，如果当前发号的时间小于之前的发号时间，则说明时钟回拨，此时拒绝发号，可以报警或者重试（重试几次时间可能就回来了）。
（2）可以在本地维护一个文件，写入上次的时间戳，随后与当前时间戳比较。如果当前时间戳小于上次时间戳，说明系统时间出了问题，应该及时处理。

如何使用

常见的 hutool 就有提供了雪花算法工具类。

雪花算法的机器 ID 如何动态配置？因为现在机器都是动态扩容部署，机器数都是不固定的，如果机器 ID 没配置好，容易导致冲突。
可以借助 Redis 或者 zookeeper 来实现机器 ID 的分配。
redis 的执行是单线程的，机器启动时候调用 redis incr 即可得到自增 id ，可将这个 id 作为机器 ID。
zookeeper 的使用也很简单，机器启动时候可以利用 zookeeper 持久顺序节点特性，将注册成功的顺序号作为机器 ID。

基于数据库

对 MySQL 来说，直接利用自增 id 即可实现。

1 2	`REPLACE INTO table(bizTag) VALUES("order"); SELECT last_insert_id();`

将bizTag设为唯一索引，可以填写业务值（也可以不同业务多张表），REPLACE INTO执行后自增 ID 会 +1，通过 last_insert id 即可获得自增的 ID 。

数据库自增优点

简单、利用数据库就能实现，且ID 有序,

数据库自增缺点

性能不足。当请求增多时，我们只能堆机器提高性能。

水平扩展困难。当我们需要增加一台机器时，其处理过程非常麻烦。首先，需要先把新增的服务器部署好，设置新的步长，起始值要设置一个不可能达到的值。当把新增的服务器部署好之后，再一台台处理旧的服务器。

水平扩展优化

可以利用auto_increment_increment和auto_increment offset实现横向扩展。

比如现在有两台数据库，auto_increment_increment都设置为2，即步长是2。第一台数据库表auto increment offset设置为 1，第二台数据库表auto_increment offset设置为2。

即TicketServer1从1开始发号，TicketServer2从2开始发号，两台机器每次发号之后都递增2

这样一来，第一台的 ID 增长值就是 1、3、5、7、9…，第二台的ID 增加值就是 2、4、6、8、10…

这样也能保证全局唯一性，多加几台机器弥补性能问题，只要指定好每个表的步长和初始值即可。要部署 N 台机器，步长需设置为 N，每台的初始值依次为 0,1,2…N-1。

不过单调递增特性没了，且加机器的成本不低，动态扩容很不方便。

批量思想优化

每次操作数据库就拿一个 ID，如果一次性拿 1000 个，那不就大大减少操作数据库的次数，性能不就上去了吗?

重新设计下表，主要字段如下：

bizTag：业务标识 maxld：目前已经分配的最大 ID step：步长，可以设置为 1000 那么每次就是拿 1000 ，设置成 1w 就是拿 1w 个

每次来获取 ID 的 SQL如下:

1 2	`UPDATE table SET maxId = max_id + step WHERE bizTag = xxx SELECT maxId, step FROM table WHERE biz_tag = xxx`

这其实就是批量思想，大大提升了ID 获取的性能。

假设业务并发量很高，此时业务方一批 ID 刚好用完后，来获取下一批 ID ，因为当前数据库压力大，很可能就会产生性能抖动，即卡了一下才拿到ID，从监控上看就是产生毛刺。
这样怎么处理？
其实这就是预处理思想，很多开源组件预处理的场景很多，例如 RocketMQcommitlog 文件的分配就是预处理，即当前 commitlog 文件用完之前，就会有后台线程预先创建后面要用的文件，就是为了防止创建的那一刻的性能抖动。

同理，这个场景我们也可以使用预处理思想。

发号器服务可以本地缓存两个 buffer，业务方请求 ID 每次从其中一个 buffer 里取，如果这个 buffer 发现 ID 已经用了 20%（或者另外的数量），则可以起一个后台线程，调用上面的 SQL 语句，先把下一批的 ID 放置到另一个 buffer 中。

当前面那个 buffer ID 都用完了，则使用另一个 buffer 取号，如此循环使用即可，这样就能避免毛刺问题。

将 ID 放在本地缓存性能好，即使服务重启了也没事，无非就是中间空了一点点 ID 罢了，整体还是有序的。