墨滴

MrAshin

V1

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 类型存储。 image.png

  • 第一部分：第一位占用 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 万。

image.png 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 也是基于号段算法实现的，系统架构实现图如下： image.png

优点：方便集成，有成熟的方案和实现； 缺点：依赖 DB ，稳定性好，需要采用集群主从备份的方式提供 DB 可用性。

具体可以查看 GitHub 介绍：https://github.com/didi/tinyid/wiki

分类：

后端

标签：

Java

作者介绍

MrAshin
V1