全网最全的分布式ID生成方案解析
<svg xmlns="http://www.w3.org/2000/svg" style="display: none">
<path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0)"></path>
</svg>
<h1><a id="_0"></a>通过本文可以学到什么<button class="cnblogs-toc-button" title="显示目录导航" aria-expanded="false"></button></h1>
- 什么是全局唯一 ID
- 全局唯一 ID 特点
- 常见的全局唯一 ID 策略
什么是全局唯一 ID
全局唯一 ID 也就是分布式 ID,拿 MySQL 举个例子,在我们项目初期,数据量不大的时候,单库单表已经可以满足我们的业务需求,数据库稍微在增加些使用 MySQL 主从也读写分离也可以满足。
随着数据量的增加,在主从同步也无法抗住业务压力的时候,此时我们对数据库进行了分库分表,而分库分表就需要一个全局的唯一 ID 来满足业务的需求,很显然数据库本身的自增 ID 是无法满足我们的需求的,所以此时就出现了全局唯一 ID 这个概念,也就是对应于我们分布式系统中的分布式 ID
下面让我们看一下全局唯一 ID 的特点都是有什么?
全局唯一 ID 的特点
- 全局唯一:全局(分库分表之后的全局唯一),不能出现重复的 ID,这是最基本的要求
- 单调递增或者趋势递增:在主键的选择上面我们应该尽量使用有序的主键保证写入性能,保证下一个 ID 一定大于上一个 ID,可以满足我们业务中的大部分特殊需求,比如排序,事务版本号
- 高性能 / 高可用:ID 生成响应要快,不能有单点故障,否则会成为业务瓶颈
- 信息安全:如果 ID 是连续的,容易暴漏业务量,所以个别场景下需要 ID 无规则
- 好接入:最好是拿来即用,在系统设计和实现上尽可能的简单
- 分片支持:最后能够控制分片,比如某一个用户的所有内容都路由到同一个分片
- 长度适中
上面了解了全局唯一 ID 的特点之后,下一步就应该知道我们业务中现在常用的全局唯一 ID 策略都是有哪几种,下面跟随我的脚步带你熟悉常见的全局唯一 ID 策略
常见全局唯一 ID 策略
数据库自增长序列或字段
最常见的方式,利用数据库实现全数据库唯一
优点:
- 简单,代码实现方便,性能也能接受
- 生成的 ID 天然有序,对分页或者需要排序的业务结果很有帮助
缺点:
- 不同数据库语法或实现不同,数据库迁移的时候需要处理
- 在单个数据库或读写分离或一主多从多情况下,只有一个主库可以生成 ID,有单点故障的风险
- 在性能达不到要求的情况下比较难以扩展
- 数据迁移或者系统数据合并比较麻烦
- 分库分表时会比较麻烦
优化方案:
针对主库单点问题,如果有多个主库,可以让每个主库单起始数字不一样,步长一样,可以是主库的个数。比如主库 1 生成 1,4,7,10,主库 2 生成 2,5,8,11,主库 3 生成 3,6,9,12. 这样就可以生成集群中的唯一 ID,也可以大大降低 ID 生成数据库的负载。
- 基于数据库集群模式
单点数据库性能不够好,容易有宕机风险的话此时就可以改为集群模式,双主模式或者主从模式,也就是两个数据库实例都可以单独生成 ID
此时,还会有另一个问题,就是两个数据都生成 id,生成的 ID 重复怎么办,此时就可以使用设置自增步长和起始值
实例 1 设置起始值 1,步长为 2
实例 2 设置起始值 2,步长 2
这样两个数据库实例生成的 ID 就为
1,3,5,7,9 2,4,6,8,10
此时,如果双主集群还是无法扛住高并发,就要考虑增加数据库节点,此时的自增步长就要设置为数据库实例的数量
此时还能再优化就是基于数据库的号段模式
-
基于数据库的号段模式
号段模式是当下分布式 ID 生成器的主流实现方式之一,号段模式可以理解为从数据库批量的获取自增 ID,每次从数据库取出一个号段范围,例如(1,1000]. 代表 1000 个 ID,具体的业务将本号段,生成 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`) )
Bit_type : 代表不同的业务类型
max_id:当前最大的可用 ID
step:代表号段的长度
version:乐观锁,每次都更新 version,保证并发时数据正确性
id Bit_type Max_id Step Version 1 1001 1000 2000 0 等这批号段用完,在向数据库申请新号段,对 max_id 做一次更新操作,update max_id = max_id+step,update 成功则说明号段获取成功,新的号段范围是(max_id,max_id+step]。
update id_generator set max_id = #{max_id+step},version=version+1 where version = #{version} and biz_type="具体业务代码"
由于会有多业务端同时操作,所以采用乐观锁的方式更新,这种分布式 id 生成方式不强依赖数据库,不会频繁的访问数据库,对数据库的压力小很多
-
基于 Redis 模式
原理是使用 redis 的 incr 命令实现原子自增
使用 redis,要考虑的就是 redis 的持久化问题,redis 有两种持久化方式,AOF 和 RDB
AOF:会对每条命令进行持久化,但是由于 incr,会造成 aof 文件很大,初始化加载缓慢,不过 Redis 有 aof 文件重写优化,命令合并重写 aof 文件
RDB:redis 定时做一个快照,在 redis 宕机之后,会有 ID 重复的问题
UUID
常见的 主键生成方式,可以利用数据库生成或者程序生成
优点:
- 简单,代码方便
- 生成 ID 性能好,基本不会有性能问题
- 全局唯一,遇见数据迁移的场景,系统数据合并,或者数据库变更的情况下,可以从容应对。
缺点:
- 没有排序,无法保证递增
- UUID 一般是字符串存储,查询效率较低
- 存储占用空间大,如果是海量数据库,还需要考虑存储量的问题
- 传输数据量大
- 可读性差
UUID 的变种
- 为了解决 UUID 的不可读性,可以使用生成有序的 UUID
Zookeeper 生成 ID
- zookeeper 主要通过其 znode 版本号来生成序列号,客户端可以使用这个版本号当作分布式 id
- 也可以根据 zookeeper 的持久顺序节点的特性,多个客户端同时创建一个节点,zk 能保证有序的创建,此时创建成功之后返回的 path 就可以取出来当作分布式 id
很少会选用 zk 来生成分布式 id,主要是由于需要依赖 zookeeper,如果在竞争较大时,还需要考虑使用分布式锁,因此,在高并发环境中,并不是很理想
Mongdb ObjectId
Objectid 很小,可能是唯一的,生成速度快,有序,长度 12 个字节,包括
- 一个 4 字节的时间戳,代表创建时间,以 Unix 依赖的秒数为单位
- 没个进程生成一个 5 字节的随机数,这个随机值对于机器和过程是唯一的
- 一个 3 字节的递增计数器,初始化为随机值
雪花算法
-
描述
snowflake 是 Twitter 开源的分布式 ID 生成算法,结果是一个 long 型的 ID,核心思想是:
- 41bit 毫秒数
- 10bit 机器 id(5 个 bit 数据中心,5 个 bit 机器 id)
- 12bit 毫秒内的流水号(就是说支持每个节点每毫秒产生 4096 个序列号,1<<12=4096)
- 第一位符号位,永远是 0
-
优点
雪花算法是使用数据中心 id 和机器 id 来作为标识,不会产生重复的 id,并且也是在本地生成,效率高。
-
缺点
- 缺点就是有可能发生时钟回拨,因为雪花算法的计算依赖与实践,若是发生系统时间回拨,就会产生重复 id 情况。id 可能不是全局递增,在单机上面是递增的,但是由于涉及到分布式环境,每台机器上的时钟不可完全同步,也许有时候也会出现不是全局递增的情况
- 机器 id 分配与回收问题:机器 id 需要每台机器不一样,这样的分配方式需要有方案进行处理,同时也要考虑宕机之后的处理,如果宕机了对应的 id 分配后的回收问题
- 机器 id 的上限问题,机器 id 是固定的 bit,那么对应的机器个数是有上限的,在有些业务场景下,需要所有的机器共享同一个业务空间,那么机器的数量是有限制的
-
解决
-
时钟回拨
- 直接抛异常,很粗暴,不友好
- 采用等待跟上次时间的一段范围,这种算是简单解决,可以接受的情况,但是要是等待一段时间之后又发生了时钟回拨,则抛异常,可以接受只能说是不算完全解决
-
机器 id 分配与回收
-
采用 zookeeper 的顺序节点分配,解决分配。回收采用 zookeeper 临时节点回收,但是临时节点不可靠,存在无故消失问题,因为也不是很可靠
-
采用中数据库中插入数据作为节点值,解决了分配,但是没有解决回收
-
-
机器 id 上限
如果采用雪花算法这也是不可避免的。不过这种场景也只有在大量的业务机器在一个共享的场景才会出现,这种情况可以采用客户端双 buffer+db 的这种非雪花算法也并不是不行
-
百度 UidGenerator
uid-generator 是基于 snowflake 算法实现的,与 snowflake 算法不同的是 uid-generator 支持自定义时间戳,工作机器 id 和序列号等各部分的位数,而且 uid-generator 采用用户自定义 workid 的生成策略
uid-generator 需要与数据库配合使用,需要新增一个 worker_node 表,当应用启动时会向数据库表中插入一条数据,插入成功后返回的自增 id 就是该机器的 workid,数据有 host,port 组成
-
组成
- sign(1bit)
固定 1bit 符号标识,即生成的 UID 为正数。 - delta seconds (28 bits)
当前时间,相对于时间基点 "2016-05-20" 的增量值,单位:秒,最多可支持约 8.7 年 - worker id (22 bits)
机器 id,最多可支持约 420w 次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。 - sequence (13 bits)
每秒下的并发序列,13 bits 可支持每秒 8192 个并发
workId
,占用了 22 个 bit 位,时间占用了 28 个 bit 位,序列化占用了 13 个 bit 位,需要注意的是,和原始的snowflake
不太一样,时间的单位是秒,而不是毫秒,workId
也不一样,而且同一应用每次重启就会消费一个workId
。 - sign(1bit)
美团 Leaf
Leaf 支持两种方式,号段方式和 snowflake 模式,可以同时开启两种模式,也可以指定开启哪种模式,默认两种关闭
滴滴 Tinyid
Tinyid 是用 Java 开发的一款分布式 id 生成系统,基于数据库号段算法实现,关于这个算法可以参考美团 leaf或者tinyid 原理介绍。Tinyid 扩展了 leaf-segment 算法,支持了多 db(master),同时提供了 java-client(sdk) 使 id 生成本地化,获得了更好的性能与可用性。Tinyid 在滴滴客服部门使用,均通过 tinyid-client 方式接入,每天生成亿级别的 id。
特点
- 全局唯一的 long 型 id
- 趋势递增的 id,即不保证下一个 id 一定比上一个大
- 非连续性
- 提供 http 和 java client 方式接入
- 支持批量获取 id
- 支持生成 1,3,5,7,9…序列的 id
- 支持多个 db 的配置,无单点
适用场景: 只关心 id 是数字,趋势递增的系统,可以容忍 id 不连续,有浪费的场景
不适用场景: 类似订单 id 的业务 (因为生成的 id 大部分是连续的,容易被扫库、或者测算出订单量)
关注公众号 获取更多学习资料
回复面试获取面试宝典