MrAshin
2023/02/03阅读:38主题:默认主题
分布式 ID 生成方案
为什么需要分布式 ID
对于单体系统而言,数据库主键 ID 常用基于数据库的主键自增方式生成。这种方式生成的 id 在单体系统中是可行的。但是对于分布式系统,分库分表之后就不适应了。比如某张表因为数据量太大需要分库分表,如果这时候还采用数据库主键自增的方式,就会出现不同库表主键 id 重复的情况,显然这是有问题的。
分布式 ID 的需要满足的条件
-
全局唯一性:主键 ID 作为唯一的标识,必然是不能重复的。
-
同步长递增(趋势递增):我们一般使用 MySQL 作为数据库居多,而 MySQL 数据库默认的存储引擎是 InnoDB,其使用的是聚集索引来维护数据存储,使用有序的主键 ID 有利于保证数据写入的效率。
-
不同步长递增(单调递增):保证下一个 ID 大于上一个 ID,这种情况可以保证事务版本号,排序等特殊需求实现。
-
信息安全:前面说了 ID 要自增,但是最好不要连续。如果 ID 是连续的,容易被恶意爬取数据,所以 ID 需要递增但是不规则递增会更安全。
分布式 ID 生成方案

UUID
UUID (Universally Unique Identifier),通用唯一识别码的缩写。 UUID 的标准型式包含 32 个 16 进制数字,以连字号分为五段,形式为 8-4-4-4-12 的 36 个字符,示例 863e254b-ae34-4371-87da-204b71d46a7b。 UUID 理论上的总数为 1632=2128,约等于 3.4 x 10^38。
-
优点:本地生成,不依赖与网络,性能非常高。 -
缺点:UUID 是无序的,而且长度太大,占用内存空间大。UUID 的无序性可能会引起数据位置频繁变动,影响性能。
数据库自增
在分布式的环境下也是可以使用 MySQL 的自增主键实现分布式 ID 的生成。当然,在分库分表的场景下,并不是简单的设置主键 ID 字段 auto_increment_increment 和 auto_increment_offset 就行。 在分布式系统中,我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。
比如有两台机器,设置步长 step 为 2。server1 的初始值为 1(1, 3, 5, 7, ...),server2 的初始值为 2(2, 4, 6, 8,...)。
这种方案看起来是可行的。但是如果一旦想要扩容,步长 step 等需要重新设置。假如只有一台机器,步长就是 1,比如 1,2,3,4,5,6。这时候如果要进行扩容,就要重新设置。机器 2 可以挑一个偶数的数字,这个数字在扩容时间内,数据库自增达不到这个数的,然后步长就是 2。机器 1 要重新设置 step 为 2,然后还是以一个奇数开始进行自增。这个过程看起来不是很杂,但是如果机器很多的话,那就要花很多时间去维护重新设置。
缺点:
-
ID 没有了单调递增的特性,只能趋势递增。有些业务场景就不能满足了。 -
数据库压力还是比较大,每次获取 ID 都需要读取数据库,只能通过多台机器提供稳定性和性能。
号段模式
这种模式也是现在生成分布式 ID 的一种实现方式。实现思路是,从数据库获取一个号段范围,比如 [1, 1000],生成 1 到 1000 的自增 id 加载到内存中。 建表结构如下:
CREATE TABLE id_generator (
id int(10) NOT NULL,
max_id bigint(20) NOT NULL COMMENT '当前最大id',
step int(20) NOT NULL COMMENT '号段的步长',
biz_type int(20) NOT NULL COMMENT '业务类型',
version int(20) NOT NULL COMMENT '版本号',
PRIMARY KEY (`id`)
)
-
biz_type :不同业务类型; -
max_id :当前最大的 id; -
step :代表号段的步长; -
version :版本号,就像 MVCC 一样,可以理解为乐观锁。
等 ID 都用完了,再去数据库获取,然后更改最大值:
update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX
优点:有比较成熟的方案,像百度 Uidgenerator,美团 Leaf。 缺点:依赖于数据库实现。
Redis 实现
使用 Redis 生成分布式 ID,主要是通过像 INCR
和 INCRBY
这样的自增原子命令实现。由于 Redis 单线程的特点,可以保证 ID 的唯一性和有序性。 这种实现方式,如果并发请求量上来之后,就需要集群。不过集群之后,又要和传统数据一样,设置分段和步长。
优点:Redis 性能相对较好,而且可以保证唯一性和有序性。 缺点:需要依赖 Redis 来实现,系统需要引入 Redis 中间件。
雪花算法(SnowFlake)
雪花算法(SnowFlake)是由 Twitter 开源的分布式 ID 生成算法,以划分命名空间的方式将 64-bit 位分割成多个部分,每个部分代表不同的含义。 在 Java 中 Long 类型是 64 位的,所以在 Java 程序中一般使用 Long 类型存储。
-
第一部分:第一位占用 1bit,始终是0,是一个符号位,不使用; -
第二部分:第2位开始的 41bit 是时间戳。41-bit 位可表示 241 个数,每个数代表毫秒,那么雪花算法可用的时间年限是 (241)/(1000606024365)=69
年的时间戳; -
第三部分:第3位占用10bit,表示机器数,即 2^10=1024
台机器。通常不会部署这么多台机器; -
第四部分:第4位占用12bit,表示自增序列,可表示 2^12=4096 个数。觉得一毫秒个数不够用也可以调大点。
雪花算法的优缺点:
-
优点:雪花算法生成的 ID 是趋势递增,不依赖数据库等第三方系统。生成 ID 的效率非常高,稳定性好,可以根据自身业务特性分配 bit 位,比较灵活。 -
缺点:雪花算法强依赖于机器时钟。如果机器时钟回拨,会导致发号重复或者服务处于不可用状态。如果恰巧回退之前生成过一些 ID ,而时间回退后,生成的 ID 就有可能重复。
百度 Uidgenerator
百度 Uidgenerator 是百度开源基于 Java 语言实现的唯一 ID 生成器,是在雪花算法 SnowFlake 的基础上做了一些改进。 引用官网的解释:
UidGenerator 是 Java 实现的, 基于 Snowflake 算法的唯一 ID 生成器。UidGenerator 以组件形式工作在应用项目中,支持自定义 workerId 位数和初始化策略,从而适用于 docker 等虚拟化环境下实例自动重启、漂移等场景。在实现上, UidGenerator 通过借用未来时间来解决 sequence 天然存在的并发限制;采用 RingBuffer 来缓存已生成的 UID,并行化 UID 的生产和消费,同时对 CacheLine 补齐。避免了由 RingBuffer 带来的硬件级「伪共享」问题. 最终单机 QPS 可达 600 万。
SnowFlake 算法描述:指定机器 & 同一时刻 & 某一并发序列,是唯一的。据此可以生成一个 64 bits 的唯一 ID(Long)。默认采用上图字节分配方式:
-
sign(1bit):固定 1bit 符号标识,即生成的 UID 为正数; -
delta seconds (28 bits):当前时间,相对于时间基点"2016-05-20"的增量值,单位:秒,最多可支持约8.7年; -
worker id (22 bits):机器 id,最多可支持约 420 万次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略; -
sequence (13 bits):每秒下的并发序列,13 bits 可支持每秒 8192 个并发。
具体的可以参考官方 GitHub 说明:https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
美团 Leaf
Leaf 这个名字是来自德国哲学家、数学家莱布尼茨的一句话:There are no two identical leaves in the world “世界上没有两片相同的树叶”。 Leaf 提供两种生成 ID 的方案:号段模式(Leaf-Segment)和 Snowflake模式(Leaf-snowflake)。我们可以同时开启这两种方式;也可以指定开启某一种。默认两种方式为关闭状态。
LeafSegment 数据库方案
其实就是前面介绍的号段模式的改进,可以引用美团技术博客的介绍: 主要做了如下改变:
-
原方案每次获取 ID 都得读写一次数据库,会造成数据库压力大。改为利用 proxy server 批量获取,每次获取一个 segment(step 决定大小)号段的值写入内存,用完之后再去数据库获取新的号段,可以大大减轻数据库的压力。 -
各个业务不同的发号需求用 biz_tag 字段来区分,每个 biz_tag 的 ID 获取相互隔离,互不影响。如果以后有性能需求需要对数据库扩容,不需要上述描述的复杂的扩容操作,只需要对 biz_tag 分库分表就行了。
表结构设计:
>+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field | Type | Null | Key | Default | Extra |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag | varchar(128) | NO | PRI | | |
| max_id | bigint(20) | NO | | 1 | |
| step | int(11) | NO | | NULL | |
| desc | varchar(256) | YES | | NULL | |
| update_time | timestamp | NO | | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+
LeafSnowflake 方案
LeafSnowflake 是在雪花算法上改进的,引用官网技术博客介绍:
Leaf-snowflake 方案完全沿用 Snowflake 方案的 bit 位设计,即是“1+41+10+12”的方式组装 ID 号。对于 workerID 的分配,当服务集群数量较小的情况下,完全可以手动配置。Leaf 服务规模较大,手动配置成本太高。所以使用 Zookeeper 持久顺序节点的特性自动对 Snowflake 节点配置 wokerID。
具体可以查看官网博客:https://tech.meituan.com/2017/04/21/mt-leaf.html
滴滴 Tinyid
Tinyid 是滴滴开源的,使用 Java 开发的一款分布式 ID 生成系统,基于数据库号段算法实现。Tinyid 扩展了 Leaf-segment 算法,支持多数据库和 tinyid-client。
Tinyid 也是基于号段算法实现的,系统架构实现图如下:
优点:方便集成,有成熟的方案和实现; 缺点:依赖 DB ,稳定性好,需要采用集群主从备份的方式提供 DB 可用性。
具体可以查看 GitHub 介绍:https://github.com/didi/tinyid/wiki
作者介绍