写点什么

面试官:说说你平时都用过哪些分布式 ID 生成方案?

作者:程序员小毕
  • 2022-10-30
    湖南
  • 本文字数:4129 字

    阅读完需:约 14 分钟

面试官:说说你平时都用过哪些分布式ID生成方案?

1、为什么需要分布式 ID?

对于单体系统来说,主键 ID 可能会常用主键自动的方式进行设置,这种 ID 生成方法在单体项目是可行的,但是对于分布式系统,分库分表之后,就不适应了,比如订单表数据量太大了,分成了多个库,如果还采用数据库主键自增的方式,就会出现在不同库 id 一致的情况,虽然是不符合业务的

2、业务系统对分布式 ID 有什么要求?

  • 全局唯一性:ID 是作为唯一的标识,不能出现重复

  • 趋势递增:互联网比较喜欢 MySQL 数据库,而 MySQL 数据库默认使用 InnoDB 存储引擎,其使用的是聚集索引,使用有序的主键 ID 有利于保证写入的效率

  • 单调递增:保证下一个 ID 大于上一个 ID,这种情况可以保证事务版本号,排序等特殊需求实现

  • 信息安全:前面说了 ID 要递增,但是最好不要连续,如果 ID 是连续的,容易被恶意爬取数据,指定一系列连续的,所以 ID 递增但是不规则是最好的

3、分布式 ID 生成方案

  • UUID

  • 数据库自增

  • 号段模式

  • Redis 实现

  • 雪花算法(SnowFlake)

  • 百度 Uidgenerator

  • 美团 Leaf

  • 滴滴 TinyID

3.1 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。

  • 优点性能非常高,本地生成的,不依赖于网络

  • 缺点不易存储,16 字节 128 位,36 位长度的字符串信息不安全,基于 MAC 地址生成 UUID 的算法可能会造成 MAC 地址泄露,暴露使用者的位置 uuid 的无序性可能会引起数据位置频繁变动,影响性能

3.2、数据库自增

在分布式环境也可以使用 mysql 的自增实现分布式 ID 的生成,如果分库分表了,当然不是简单的设置好 auto_increment_increment auto_increment_offset 即可,在分布式系统中我们可以多部署几台机器,每台机器设置不同的初始值,且步长和机器数相等。比如有两台机器。设置步长 step 为 2,Server1 的初始值为 1(1,3,5,7,9,11…)、Server2 的初始值为 2(2,4,6,8,10…)。这是 Flickr 团队在 2010 年撰文介绍的一种主键生成策略(Ticket Servers: Distributed Unique Primary Keys on the Cheap )

假设有 N 台机器,step 就要设置为 N,如图进行设置:

这种方案看起来是可行的,但是如果要扩容,步长 step 等要重新设置,假如只有一台机器,步长就是 1,比如 1,2,3,4,5,6,这时候如果要进行扩容,就要重新设置,机器 2 可以挑一个偶数的数字,这个数字在扩容时间内,数据库自增要达不到这个数的,然后步长就是 2,机器 1 要重新设置 step 为 2,然后还是以一个奇数开始进行自增。这个过程看起来不是很杂,但是,如果机器很多的话,那就要花很多时间去维护重新设置

这种实现的缺陷:

  • ID 没有了单调递增的特性,只能趋势递增,有些业务场景可能不符合

  • 数据库压力还是比较大,每次获取 ID 都需要读取数据库,只能通过多台机器提高稳定性和性能

3.3、号段模式

这种模式也是现在生成分布式 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

  • 缺点:依赖于数据库实现

3.4、 Redis 实现

Redis 分布式 ID 实现主要是通过提供像 INCRINCRBY 这样的自增原子命令,由于 Redis 单线程的特点,可以保证 ID 的唯一性和有序性

这种实现方式,如果并发请求量上来后,就需要集群,不过集群后,又要和传统数据库一样,设置分段和步长

优缺点:

  • 优点:Redis 性能相对比较好,又可以保证唯一性和有序性

  • 缺点:需要依赖 Redis 来实现,系统需要引进 Redis 组件

3.4、 雪花算法(SnowFlake)

Snowflake,雪花算法是由 Twitter 开源的分布式 ID 生成算法,以划分命名空间的方式将 64-bit 位分割成多个部分,每个部分代表不同的含义,64 位,在 java 中 Long 类型是 64 位的,所以 java 程序中一般使用 Long 类型存储

  • 第一部分:第一位占用 1bit,始终是 0,是一个符号位,不使用

  • 第二部分:第 2 位开始的 41 位是时间戳。41-bit 位可表示 241 个数,每个数代表毫秒,那么雪花算法可用的时间年限是(241)/(1000606024365)=69 年的时间

  • 第三部分:10-bit 位可表示机器数,即 2^10 = 1024 台机器。通常不会部署这么多台机器

  • 第四部分:12-bit 位是自增序列,可表示 2^12 = 4096 个数。觉得一毫秒个数不够用也可以调大点

  • 优点:雪花算法生成的 ID 是趋势递增,不依赖数据库等第三方系统,生成 ID 的效率非常高,稳定性好,可以根据自身业务特性分配 bit 位,比较灵活

  • 缺点:雪花算法强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些 ID,而时间回退后,生成的 ID 就有可能重复。

3.5、 百度 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,最多可支持约 420w 次机器启动。内置实现为在启动时由数据库分配,默认分配策略为用后即弃,后续可提供复用策略。sequence (13 bits):每秒下的并发序列,13 bits 可支持每秒 8192 个并发。

详细的,可以参考官网解释,链接:https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

3.6、 美团 Leaf

Leaf 这个名字是来自德国哲学家、数学家莱布尼茨的一句话: >There are no twoidentical leaves in the world > “世界上没有两片相同的树叶”

Leaf 提供两种生成的 ID 的方式:号段模式(Leaf-segment)和 snowflake 模式(Leaf-snowflake)。你可以同时开启两种方式,也可以指定开启某种方式,默认两种方式为关闭状态。

  • Leaf­segment 数据库方案


    其实就是前面介绍的号段模式的改进,可以引用美团技术博客的介绍:

第一种 Leaf-segment 方案,在使用数据库的方案上,做了如下改变: - 原方案每次获取 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 |+-------------+--------------+------+-----+-------------------+-----------------------------+
复制代码
  • Leaf­snowflake 方案


    Leafsnowflake 是在雪花算法上改进来的,引用官网技术博客介绍:

Leaf-snowflake 方案完全沿用 snowflake 方案的 bit 位设计,即是“1+41+10+12”的方式组装 ID 号。对于 workerID 的分配,当服务集群数量较小的情况下,完全可以手动配置。Leaf 服务规模较大,动手配置成本太高。所以使用 Zookeeper 持久顺序节点的特性自动对 snowflake 节点配置 wokerID。Leaf-snowflake 是按照下面几个步骤启动的:

启动 Leaf-snowflake 服务,连接 Zookeeper,在 leaf_forever 父节点下检查自己是否已经注册过(是否有该顺序子节点)。如果有注册过直接取回自己的 workerID(zk 顺序节点生成的 int 类型 ID 号),启动服务。如果没有注册过,就在该父节点下面创建一个持久顺序节点,创建成功后取回顺序号当做自己的 workerID 号,启动服务。

这种方案解决了前面提到的雪花算法的缺陷,官网没解释,不过 Leaf­snowflake 对其进行改进,官网的流程图

详细介绍请看官网:https://tech.meituan.com/2017/04/21/mt-leaf.html

3.7、 滴滴 TinyID

Tinyid 是用 Java 开发的一款分布式 id 生成系统,基于数据库号段算法实现。Tinyid 扩展了 leaf-segment 算法,支持了多数据库和 tinyid-client

Tinyid 也是基于号段算法实现,系统实现图如下:

  • 优点:方便集成,有成熟的方案和解决实现

  • 缺点:依赖 DB 的稳定性,需要采用集群主从备份的方式提高 DB 的可用性

原文:https://www.cnblogs.com/mzq123/p/16840232.html

如果感觉本文对你有帮助,点赞关注支持一下

用户头像

领取资料添加小助理vx:bjmsb2020 2020-12-19 加入

Java领域;架构知识;面试心得;互联网行业最新资讯

评论

发布
暂无评论
面试官:说说你平时都用过哪些分布式ID生成方案?_Java_程序员小毕_InfoQ写作社区