背景

在复杂的分布式系统中，往往需要对大量的数据进行唯一标识，比如在对一个订单表进行了分库分表操作，这时候数据库的自增ID显然不能作为某个订单的唯一标识。除此之外还有其他分布式场景对分布式ID的一些要求：

  1. 趋势递增：由于多数RDBMS使用B-tree的数据结构来存储索引数据，在主键的选择上面我们应该尽量使用有序的主键保证写入性能。
  2. 单调递增：保证下一个ID一定大于上一个ID，例如排序需求。
  3. 信息安全：如果ID是连续的，恶意用户的扒取工作就非常容易做了；如果是订单号就更危险了，可以直接知道我们的单量。所以在一些应用场景下，会需要ID无规则、不规则。
    就不同的场景及要求，市面诞生了很多分布式ID解决方案。本文针对多个分布式ID解决方案进行介绍，包括其优缺点、使用场景及代码示例。

雪花算法是 Twitter 开源的分布式 ID 生成算法

常见解决方案

数据库

MySQL

关系型数据库。
数据库自增主键
表：

CREATE TABLE `sequence_id` (
`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
`stub` char(10) NOT NULL DEFAULT '',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

通过 replace into 来插入数据。

BEGIN;
REPLACE INTO sequence_id (stub) VALUES ('stub');
SELECT LAST_INSERT_ID();
COMMIT;

replace into 的具体步骤。。。

  • 优点：实现起来比较简单、ID 有序递增、存储消耗空间小
  • 缺点：支持的并发量不大、存在数据库单点问题（可以使用数据库集群解决，不过增加了复杂度）、ID 没有具体业务含义、安全问题（比如根据订单 ID 的递增规律就能推算出每天的订单量，商业机密啊！ ）、每次获取 ID 都要访问一次数据库（增加了对数据库的压力，获取速度也慢）

数据库号段模式
数据库自增主键的痛点。
如果我们可以批量获取，然后存在在内存里面，需要用到的时候，直接从内存里面拿就舒服了！这也就是我们说的 基于数据库的号段模式来生成分布式 ID。
表：

CREATE TABLE `sequence_id_generator` (
`id` int(10) NOT NULL,
`current_max_id` bigint(20) NOT NULL COMMENT '当前最大id',
`step` int(10) NOT NULL COMMENT '号段的长度',
`version` int(20) NOT NULL COMMENT '版本号',
`biz_type`    int(20) NOT NULL COMMENT '业务类型',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

获取的批量 id 为：current_max_id ~ current_max_id+step。
version 字段主要用于解决并发问题（乐观锁）,biz_type 主要用于表示业务类型。
相比于数据库主键自增的方式的优点。。。
数据库号段模式的优缺点:

  • 优点：ID 有序递增、存储消耗空间小
  • 缺点：存在数据库单点问题（可以使用数据库集群解决，不过增加了复杂度）、ID 没有具体业务含义、安全问题（比如根据订单 ID 的递增规律就能推算出每天的订单量，商业机密啊！ ）

Redis

非关系型数据库。
通过 Redis 的 incr 命令即可实现对 id 原子顺序递增。

127.0.0.1:6379> set sequence_id_biz_type 1
OK
127.0.0.1:6379> incr sequence_id_biz_type
(integer) 2
127.0.0.1:6379> get sequence_id_biz_type
"2"

为了提高可用性和并发，我们可以使用 Redis Cluster。
Redis 方案的优缺点：

  • 优点：性能不错并且生成的 ID 是有序递增的
  • 缺点：和数据库主键自增方案的缺点类似

算法

UUID

UUID 包含 32 个 16 进制数字（8-4-4-4-12）。

//输出示例：cb4a9ede-fa5e-4585-b9bb-d60bce986eaa
UUID.randomUUID()

  • 版本 1 : UUID 是根据时间和节点 ID（通常是 MAC 地址）生成；
  • 版本 4 : UUID 使用随机性 open in new window 或伪随机性 open in new window 生成。
    JDK 中通过 UUID 的 randomUUID() 方法生成的 UUID 的版本默认为 4。

UUID 的优缺点

  • 优点：生成速度比较快、简单易用
  • 缺点：存储消耗空间大（32 个字符串，128 位）、 不安全（基于 MAC 地址生成 UUID 的算法会造成 MAC 地址泄露)、无序（非自增，InnoDB 引擎下，数据库主键的无序性会严重影响数据库性能。）、没有具体业务含义、需要解决重复 ID 问题（当机器时间不对的情况下，可能导致会产生重复 ID）

雪花算法

Snowflake 是 Twitter 开源的分布式 ID 生成算法。Snowflake 由 64 bit 的二进制数字组成，这 64bit 的二进制被分成了几部分，每一部分存储的数据都有特定的含义。

  • **sign(1bit)**：符号位（标识正负），始终为 0，代表生成的 ID 为正数。
  • **timestamp (41 bits)**：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑 2 ^41 毫秒（约 69 年）
  • **datacenter id + worker id (10 bits)**：一般来说，前 5 位表示机房 ID，后 5 位表示机器 ID（实际项目中可以根据实际情况调整）。这样就可以区分不同集群/机房的节点。
  • **sequence (12 bits)**：一共 12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大 ID 数(2^12 = 4096),也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID。
    通过将机器ID作为雪花算法的一部分，可以确保在分布式系统中不同的机器生成的ID是唯一的。
    在实际项目中，我们一般也会对 Snowflake 算法进行改造，最常见的就是在 Snowflake 算法生成的 ID 中加入业务类型信息。

Snowflake 算法的优缺点：

  • 优点：生成速度比较快、生成的 ID 有序递增、比较灵活（可以对 Snowflake 算法进行简单的改造比如加入业务 ID）
  • 缺点：需要解决重复 ID 问题（ID 生成依赖时间，在获取时间的时候，可能会出现时间回拨的问题，也就是服务器上的时间突然倒退到之前的时间，进而导致会产生重复 ID）、依赖机器 ID 对分布式环境不友好（当需要自动启停或增减机器时，固定的机器 ID 可能不够灵活）。
    有很多基于 Snowflake 算法的开源实现比如美团 的 Leaf、百度的 UidGenerator（后面会提到），并且这些开源实现对原有的 Snowflake 算法进行了优化，性能更优秀，还解决了 Snowflake 算法的时间回拨问题和依赖机器 ID 的问题。大幅提高的 QPS。

开源框架

UidGenerator(百度)

基于 Snowflake(雪花算法)的唯一 ID 生成器。

自 18 年后，UidGenerator 就基本没有再维护了。

Leaf(美团)

这个项目的名字 Leaf（树叶） 起源于德国哲学家、数学家莱布尼茨的一句话：“There are no two identical leaves in the world”（世界上没有两片相同的树叶）。
Leaf 提供了 号段模式 和 Snowflake(雪花算法) 这两种模式来生成分布式 ID。并且，它支持双号段，还解决了雪花 ID 系统时钟回拨问题。不过，时钟问题的解决需要弱依赖于 Zookeeper（使用 Zookeeper 作为注册中心，通过在特定路径下读取和创建子节点来管理 workId） 。
Leaf 对原有的号段模式进行改进，比如它这里增加了双号段避免获取 DB 在获取号段的时候阻塞请求获取 ID 的线程。简单来说，就是我一个号段还没用完之前，我自己就主动提前去获取下一个号段。

号段模式

号段模式是对直接用数据库自增ID充当分布式ID的一种优化，减少对数据库的频率操作。相当于从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，业务服务将号段在本地生成1~1000的自增ID并加载到内存。

双 buffer 优化
数据库的 IO 问题（阻塞）：双 buffer 优化。
响应时间慢（网络抖动，慢查询，）

响应时间慢：IO 阻塞，网络抖动，慢查询。
归根结底是 DB 问题，1：取号段阻塞，2：网络和DB稳定性。

Leaf-segment 为了解决 当号段使用完之后还是会阻塞在更新数据库的I/O上，提供了双buffer优化。
简单的说就是，Leaf 取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间，并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候【网络发生抖动】，或者DB发生【慢查询】就会导致整个系统的响应时间变慢。
为了DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程，即当号段消费到某个点时就异步的把下一个号段加载到内存中，而不需要等到号段用尽的时候才去更新号段。

消费到 10% 就开始另起一个线程到数据库中取新的号段，放到另一个 segment buffer 中。
每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。

  • DB的网络和DB的性能稳定问题
    • 【网络抖动】：每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。
    • 【稳定性】：需要采用主从备份的方式提高 DB的可用性，
  • 对于这种方案依然存在一些问题：
    • 还有 Leaf-segment方案生成的ID是趋势递增的，这样ID号是可被计算的，例如订单ID生成场景，通过订单id号相减就能大致计算出公司一天的订单量，这个是不能忍受的。

雪花算法

怎么解决的时钟回拨，依赖机器 ID 的问题呢？
snowflake模式依赖于ZooKeeper，不同于原始snowflake算法也主要是在workId的生成上，Leaf中workId是基于ZooKeeper的顺序Id来生成的，每个应用在使用Leaf-snowflake时，启动时都会都在Zookeeper中生成一个顺序Id，相当于一台机器对应一个顺序节点，也就是一个workId。

Leaf-snowflake方案完全沿用 snowflake 方案的bit位设计，对于workerID的分配引入了Zookeeper持久顺序节点的特性自动对snowflake节点配置 wokerID。避免了服务规模较大时，动手配置成本太高的问题。
Leaf-snowflake是按照下面几个步骤启动的：

  • 启动Leaf-snowflake服务，连接Zookeeper，在leaf_forever父节点下检查自己是否已经注册过（是否有该顺序子节点）。

  • 如果有注册过直接取回自己的workerID（zk顺序节点生成的int类型ID号），启动服务。

  • 如果没有注册过，就在该父节点下面创建一个持久顺序节点，创建成功后取回顺序号当做自己的workerID号，启动服务。

    为了减少对 Zookeeper的依赖性，会在本机文件系统上缓存一个workerID文件。当ZooKeeper出现问题，恰好机器出现问题需要重启时，能保证服务能够正常启动。

    解决时钟回拨：
    上文阐述过在类 snowflake算法上都存在时钟回拨的问题，Leaf-snowflake在解决时钟回拨的问题上是通过校验自身系统时间与 leaf_forever/${self}节点记录时间做比较然后启动报警的措施。

    美团官方建议是由于强依赖时钟，对时间的要求比较敏感，在机器工作时NTP同步也会造成秒级别的回退，建议可以直接关闭NTP同步。要么在时钟回拨的时候直接不提供服务直接返回ERROR_CODE，等时钟追上即可。或者做一层重试，然后上报报警系统，更或者是发现有时钟回拨之后自动摘除本身节点并报警。
    在性能上官方提供的数据目前 Leaf 的性能在4C8G 的机器上QPS能压测到近5w/s，TP999 1ms。

依赖机器 ID 问题：
在雪花算法中，每个生成的唯一ID都包含一个机器ID的部分，用于标识不同的机器或节点。这个机器ID可以是一个固定的值，也可以是根据具体需求动态生成。
缺点中提到的依赖机器ID对分布式环境不友好主要有两个方面：

  1. 自动启停或增减机器时的问题：在分布式环境中，经常需要进行机器的自动启停或增减。如果使用固定的机器ID来生成唯一ID，当一个机器停止工作后，它的机器ID就会变为闲置状态。而当新增一个机器时，如果分配了与之前闲置机器的机器ID相同的ID，就会造成机器ID的冲突。这样生成的唯一ID就不再是唯一的，可能导致冲突。
  2. 灵活性问题：固定的机器ID可能会受限于特定的分布式环境，无法灵活适应变化。例如，如果需要在云环境中进行自动伸缩，动态增减机器，那么使用固定的机器ID就会变得不够灵活。此外，当需要进行硬件维护或替换时，也可能需要更改机器ID。

为了解决这些问题，可以考虑以下几种方案：

  1. 使用动态生成的机器ID：可以通过某种算法或配置来动态生成机器ID，而不是使用固定的值。这样可以在自动启停或增减机器时保证唯一ID的生成不受影响。
  2. 使用更加灵活的ID生成方案：除了雪花算法，还有其他的ID生成方案，例如基于数据库的自增ID、UUID等。这些方案不依赖于机器ID，可以在分布式环境中更加灵活地生成唯一ID。
    总的来说，依赖固定的机器ID可能会对分布式环境不友好，因为它可能限制了自动启停或增减机器的灵活性。为了解决这个问题，可以考虑使用动态生成的机器ID或其他更加灵活的ID生成方案。

Tinyid(滴滴)

滴滴开源的一款基于数据库号段模式的唯一 ID 生成器。