文章

UUID 和雪花算法全面对比

发表于
作者 Optimus-Xs
58 分钟阅读
UUID 和雪花算法全面对比

分布式ID生成算法

什么是分布式ID

拿MySQL数据库举个栗子：

在我们业务数据量不大的时候，单库单表完全可以支撑现有业务，数据再大一点搞个MySQL主从同步读写分离也能对付。

但随着数据日渐增长，主从同步也扛不住了，就需要对数据库进行分库分表，但分库分表后需要有一个唯一ID来标识一条数据，数据库的自增ID显然不能满足需求；特别一点的如订单、优惠券也都需要有唯一ID做标识。此时一个能够生成全局唯一ID的系统是非常必要的。那么这个全局唯一ID就叫分布式ID。

分布式ID的需求

  • 全局唯一：必须保证ID是全局性唯一的，基本要求
  • 高性能：高可用低延时，ID生成响应要块，否则反倒会成为业务瓶颈
  • 高可用：100%的可用性是骗人的，但是也要无限接近于100%的可用性
  • 好接入：要秉着拿来即用的设计原则，在系统设计和实现上要尽可能的简单
  • 趋势递增：最好趋势递增，这个要求就得看具体业务场景了，一般不严格要求

常见的分布式ID实现

  • 数据库生成法: 基于数据库的自增ID完全可以充当分布式ID，具体实现：需要一个单独的MySQL实例用来生成ID, 当我们需要一个ID的时候，向表中插入一条记录返回主键ID
  • 数据库集群模式: 数据库生成法有一个比较致命的缺点，访问量激增时MySQL本身就是系统的瓶颈, 这时候我们可以水平扩展的数据库集群, 每台实例设置不同的初始值和步长（例如，A实例从1开始，步长为2；B实例从2开始，步长为2），这样生成的ID就不会重复
  • 号段模式: 号段模式是当下分布式ID生成器的主流实现方式之一，号段模式可以理解为从数据库批量的获取自增ID，一次性从数据库中获取一个ID区间，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存
  • Redis: 利用 Redis 的 INCR 命令实现原子性的递增, 用redis实现需要要考虑到redis持久化的问题
  • UUID: 遵循特定标准（例如RFC 4122）生成的128位唯一标识符，通常用32位的16进制数字表示, 完全去中心化，生成速度快，全球唯一
  • 雪花算法: 依赖机器时钟, 机器ID, 递增组成的一个64位的长整型的分布式ID, ID大致有序递增, 依赖机器时钟，如果时钟回拨可能会导致ID重复或冲突。需要一个机制来分配和管理Worker ID

但是, 数据库生成法、数据库集群模式、号段模式、Redis它们在运行阶段仍有单点依赖或续命依赖, 在系统初始配置完成后，如果ID生成中心节点故障则, 业务节点无法独立且持续生成合规ID

相比之下, UUID 和 雪花算法, 运行过程中不依赖中心节点生成或者发放限制来生成ID

  • UUID： 是最去中心化的方案，完全基于本地计算和随机性，不需要任何中心管理节点。
  • Snowflake 算法： 在运行阶段是去中心化的。一旦每个业务节点获取了它的 Worker ID（机器ID），它就可以独立、持续地生成ID，不受任何中心节点（如数据库、Redis）的故障影响。

UUID简介

UUID（Universally Unique Identifier），即通用唯一标识符，是一个 128 位的数字，旨在全球范围内保证唯一性。它不依赖中央机构或协调服务生成，因此是分布式系统中实现唯一 ID 的最简单、最去中心化的方法。

UUID 格式

UUID 是一个 128 位的数值，通常以 32 个十六进制字符表示，并由连字符（-）分隔成五组：

  • 格式： xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
  • 总长度： 36 个字符（32 个十六进制数字 + 4 个连字符）
  • 位数： 128 位

UUID字段详细含义：

字段长度 (十六进制字符)长度 (位)描述
Time Low832时间的低位部分。
Time Mid416时间的中位部分。
Time High & Version (M)416时间的高位部分，包含 4 位版本号 (M)。
Clock Seq & Variant (N)416时钟序列和版本变体（Variant），包含 1-3 位变体号 (N)。
Node1248节点 ID（通常是 MAC 地址或随机数）。

关键字段：

  • 版本号 (Version, M)： 位于第三组的第一个十六进制位（如 Mxxx 中的 M），用 4 位表示，定义了 UUID 的生成算法（1, 2, 3, 4, 或 5）。
  • 变体号 (Variant, N)： 位于第四组的第一个十六进制位（如 Nxxx 中的 N），定义了 UUID 所遵循的布局和编码规范，RFC 4122 定义的版本通常其高 1-3 位固定为 10x。

UUID 规范历史上主要定义了四种变体：

变体号（二进制）变体名描述
0xxNCSA/Apollo NCS遗留系统使用，现已废弃。
10xRFC 4122 (Leach-Salz)所有 Version 1 到 Version 5 遵循的标准变体。
110Microsoft COM/DEC遗留系统使用，通常指 Microsoft GUID。
111保留供未来使用未定义。

UUID 版本

UUID 标准（RFC 4122）定义了五种生成 UUID 的方法，所有 UUID 版本都遵循 128 位的结构，并要求在特定的位上设置版本号（Version, M）和变体号（Variant, N），每种方法依赖的数据源和应用场景不同：

在现代应用中，最常见和推荐使用的UUID版本是 Version 4（随机数）和 Version 5（基于 SHA-1 哈希）。

  • Version 4 适用于绝大多数需要全局唯一随机 ID 的场景。
  • Version 5 适用于需要为特定资源（如 URL、文件）生成稳定且唯一的标识符的场景

Version 1: 基于时间戳和 MAC 地址

使用当前的 系统时间（精确到 100 纳秒）和生成 ID 的计算机的 MAC 地址（作为节点 ID）

计算过程：

  1. 获取时间戳 (60 位)：
    • 计算从 公元 1582 年 10 月 15 日 00:00:00 到当前时间的 100 纳秒间隔数。这个 60 位的值会被拆分成低位、中位和高位填入 UUID。
  2. 获取节点 ID (48 位)：
    • 通常使用生成 UUID 的计算机的 MAC 地址，作为 48 位的节点 ID (Node ID) 填入 UUID 的最后 6 个字节。
  3. 获取时钟序列 (14 位)：
    • 时钟序列（Clock Sequence）用于在时钟回拨时防止 ID 重复。它是一个 14 位的随机或半随机数，在每次时钟回拨或节点重启时递增。
  4. 设置版本号和变体号：
    • 设置版本号为 1（0001）。
    • 设置变体号为 10 (RFC 4122 变体)。

UUID Version 1 包含一个 14 位的时钟序列（Clock Sequence）字段，它的主要作用是应对时钟回拨或节点 MAC 地址发生变化时可能导致的 ID 冲突

在正常情况下（即时钟没有回拨，系统 MAC 地址稳定），时钟序列在两次 UUID 生成之间会保持不变

时钟序列在节点首次启动时会被初始化为一个随机数（通常在 0 到 $2^{14}-1$ 之间），然后每次需要递增时，就在这个初始值的基础上 +1。它不是一个持续变化的随机数，而是一个稳定的、只在特定情况下递增的计数器

特性：

  • 在同一物理硬件上具有一定的时间顺序和空间唯一性。
  • 暴露了设备的 MAC 地址，存在隐私泄露风险。

Version 2: 基于 DCE 安全

扩展了 Version 1，加入了 DCE（Distributed Computing Environment）安全机制和本地用户或组的 ID

Version 2 UUID 通过替换 Version 1 UUID 中一部分时间戳字段，来嵌入本地安全信息

  • 节点 ID (Node ID) 和 时钟序列 (Clock Sequence): 这两部分与 Version 1 保持不变
  • Version 1 中的时间戳高位和中位被替换为 本地标识符 (Local Identifier), Version 1 中的时间戳高位和中位被替换为 本地标识符 (Local Identifier)
  • UUID 中的时间低位被用来表示 DCE 域（Domain）。这个域定义了所嵌入的标识符的类型

Version 2 UUID 的主要区别就是在 ID 中硬编码了生成该 ID 的用户或组的身份信息

计算过程:

  1. Node ID 和 Clock Sequence： 与 Version 1 相同。
  2. 替换时间戳高位： Version 1 中的部分时间戳字段（Time High 和 Time Mid）被替换为本地的安全信息，例如 本地用户 ID（Local UID） 或 组 ID（Local GID）。
  3. 设置版本号和变体号：
    • 设置版本号为 2（0010）。
    • 设置变体号为 10。

特性：

  • 用于特定的分布式计算环境。
  • 应用非常罕见，通用性差。

Version 2 为什么不具备通用性？

主要原因在于其设计强耦合于特定的遗留架构和操作环境:

  • Version 2 是为 DCE 标准设计的。随着 DCE 及其 RPC (Remote Procedure Call) 机制逐渐被更现代的技术（如 Web Services, REST, gRPC）取代
  • 耦合 POSIX/本地 ID： 它强制要求在 ID 中嵌入本地操作系统的 UID 或 GID, 现代的云原生应用往往运行在无状态的容器中，或者根本不需要本地的 POSIX UID/GID 权限来生成全局 ID
  • 虽然它嵌入了本地 ID，但这只保证了 ID 在特定机器和特定用户下的唯一性，牺牲了 Version 1 在时间维度上的完整性

在今天的技术栈中，除非是与遗留的 DCE 或特定 POSIX 安全系统进行集成，否则 Version 2 UUID 几乎不会被选择

Version 3: 基于名称和 MD5 哈希

对一个 命名空间 UUID 和一个名称（如 URL、域名或文件路径）进行 MD5 哈希计算

计算过程:

  1. 准备数据：
    • 将命名空间UUID（一个预定义的 UUID，如代表 DNS 或 URL 的 UUID）的 16 个字节与要标识的名称字字节序列（例如 www.example.com）拼接起来。
  2. 哈希计算：
    • 对拼接后的字节序列执行 MD5 哈希计算，得到一个 128 位的哈希结果。
  3. 覆盖和设置：
    • 用哈希结果覆盖 UUID 的 128 位字段。
    • 覆盖版本号位，设置其值为 3（0011）。
    • 设置变体号为 10。

特性：

  • 对于相同的命名空间和名称，生成的 UUID 是固定不变的，具有可预测性
  • MD5 算法的碰撞风险和安全性不足, Version 5 通常更推荐

Version 4: 基于随机数

绝大部分位（122 位）通过 高质量的随机数生成器 (RNG) 产生

计算过程:

  1. 生成随机数：
    • 使用一个高质量的随机数生成器（CSPRNG）产生 128 位的随机数作为初始 ID。
  2. 覆盖和设置：
    • 在生成的随机数中，覆盖版本号位，设置其值为 4（0100）。
    • 设置变体号为 10。

特性：

  • 最常用、最去中心化的版本。生成速度快，无需任何外部信息。
  • 完全无序，作为数据库主键时性能较差。

Version 5: 基于名称和 SHA-1 哈希

对一个 命名空间 UUID 和一个名称进行 SHA-1 哈希计算, Version 5 的原理与 Version 3 相同，只是将哈希算法替换为更安全的 SHA-1。

计算过程:

  1. 准备数据：
    • 与 Version 3 相同，将 命名空间 UUID 和名称字节序列拼接起来。
  2. 哈希计算：
    • 对拼接后的字节序列执行 SHA-1 哈希计算，得到一个 160 位的哈希结果。
  3. 截断和设置：
    • 取 SHA-1 结果的前 128 位作为 UUID 的值。
    • 覆盖版本号位，设置其值为 5（0101）。
    • 设置变体号为 10。

特性：

  • 与 Version 3 类似，但使用更安全的 SHA-1 哈希算法，是目前推荐的基于名称的 UUID 版本

在实际应用中，UUID Version 3 和 Version 5 使用的命名空间 UUID 主要分为两大类：RFC 4122 标准预定义命名空间和自定义命名空间。

  • 标准预定义命名空间: RFC 4122 标准定义了几个常用的、全球通用的命名空间 UUID，用于标识互联网和目录服务中的标准资源类型。如果你想确保同一个 URL 在任何系统上都对应同一个 UUID，你会使用 URL 命名空间 UUID 拼接该 URL 字符串进行哈希计算。
  • 在许多实际业务应用中，用户需要为自己的内部数据或业务对象创建 UUID，这时就会用到自定义命名空间。在许多实际业务应用中，用户需要为自己的内部数据或业务对象创建 UUID，这时就会用到自定义命名空间。
    • 随机生成: 最简单的方法是使用 Version 4 UUID 随机生成一个 ID
    • 一次性基于名称生成: 可以使用 Version 5 对一个有意义的、唯一的字符串（例如你的公司名称或业务名称）进行哈希，从而生成一个稳定的命名空间 UUID

雪花算法简介

雪花算法是由 Twitter 开源的一种生成分布式 ID 的算法。它生成的 ID 是一个 64 位的长整型（Long）数字，它保证了在分布式环境下的全局唯一性，并且 ID 是大致有序递增的（基于时间戳）

雪花算法ID结构

雪花算法将 64 位的 Long 型 ID 划分成了几个固定长度的字段，每个字段都有特定的作用。

雪花ID结构

\[\text{ID} = \underbrace{0}_{\text{符号位 (1-bit)}} + \underbrace{\text{时间戳}}_{\text{(41-bit)}} + \underbrace{\text{工作机器 ID}}_{\text{(10-bit)}} + \underbrace{\text{序列号}}_{\text{(12-bit)}}\]
  1. 符号位 (Sign Bit) - 1 位
    • 固定为 0。
    • 最高位是符号位，在 Java 中，long 型 ID 必须是正数（无符号），所以第一位固定是 0。
  2. 时间戳 (Timestamp) - 41 位
    • 记录了从某一约定的起始时间（Epoch）到当前 ID 生成时间的毫秒差值。
    • 起始时间（Epoch）： 通常是系统第一次上线的时间，例如 2020-01-01 00:00:00。
    • 容量： $2^{41}$ 毫秒，可以持续使用约 69 年（$2^{41} \text{ms} / (1000 \times 60 \times 60 \times 24 \times 365) \approx 69$ 年）。
  3. 工作机器 ID (Worker ID / DataCenter ID) - 10 位
    • 这 10 位可以由两部分组成：
      • 数据中心 ID (DataCenter ID): 5 位，支持 $2^5=32$ 个数据中心。
      • 工作机器 ID (Worker ID): 5 位，支持 $2^5=32$ 台机器。
    • 总容量： 10 位共支持 $2^{10} = 1024$ 个节点（或机器）。
    • 作用： 确保在不同的机器上生成的 ID 不会重复。这 10 位需要通过中心化机制（如 ZooKeeper 或人工配置）预先分配给每个工作节点，以保证唯一性。
  4. 序列号 (Sequence) - 12 位
    • 用于记录在同一毫秒内生成 ID 的次数。
    • 容量： $2^{12} = 4096$。
    • 作用： 如果在同一毫秒内产生了多个 ID 请求，通过递增这个序列号来区分，使得单个工作节点在每毫秒最多可以生成 4096 个 ID。

雪花算法的计算过程

雪花算法的生成过程是基于位运算的：

  1. 取时间戳： 获取当前时间与 Epoch 时间的差值（毫秒）。
  2. 移时间戳： 将 41 位时间戳左移 $(10 + 12) = 22$ 位，移动到最高有效位。
  3. 移 Worker ID： 将 10 位 Worker ID 左移 12 位，移动到中间位置。
  4. 列号位： 将 12 位序列号放在最低位。
  5. 位或（OR）： 将这三个部分进行按位或操作，得到最终的 64 位 ID。
\[\text{ID} = (\text{Timestamp} \ll 22) \mid (\text{WorkerID} \ll 12) \mid \text{Sequence}\]

雪花算法的特殊处理

时钟回拨问题

⏰ 什么是时钟回拨？

在分布式系统中，每个服务器都有自己的本地时钟。时钟回拨是指服务器的本地系统时间被调整到了过去，导致当前时间 $T_{current}$ 小于上次生成 ID 时记录的时间 $T_{last}$。

导致回拨的常见原因：

  • 人工干预： 运维人员手动将服务器时间调慢。
  • NTP（网络时间协议）同步： NTP 服务在同步时，如果发现本地时钟与标准时间偏差过大，可能会进行跳跃式校准（而非平滑调整），将时间直接调回。
  • 虚拟机快照/迁移： 虚拟机在回滚到旧快照或迁移到不同宿主机时，其系统时间可能回到过去。

🚨 时钟回拨会导致什么问题？

雪花 ID 依赖三个核心部分：时间戳、工作机器 ID 和序列号。

\[\text{ID} = \underbrace{\text{时间戳}}_{\text{(41-bit)}} + \underbrace{\text{工作机器 ID}}_{\text{(10-bit)}} + \underbrace{\text{序列号}}_{\text{(12-bit)}}\]

  1. 唯一性冲突

    ID 的唯一性依赖于 (时间戳 + 工作机器 ID) 的组合在全局是唯一的。在同一毫秒内，通过序列号来区分

    故障的生成流程:

    1. 正常生成阶段:
      • 时间 \(Tlast\)​=10:00:00.500，序列号 Seq=5
      • 生成 ID: ID1​
    2. 时钟回拨阶段:
      • 时间 \(Tcurrent\)​ 回拨到 10:00:00.300
      • 此时 \(Tcurrent​<Tlast​\)
    3. ID 生成阶段:
      • 系统认为这是一个新的毫秒，将序列号重置为 Seq=0
      • 此时生成的 ID2​ 会使用 10:00:00.300 的时间戳和 Seq=0 开始计数。如果 10:00:00.300 这个时间点之前已经有 ID 被生成过，新生成的 ID 就会和历史 ID 重复，导致唯一性冲突

  2. 破坏有序性

    雪花 ID 的一个重要优势是大致有序。时钟回拨直接导致新生成的 ID 带有较小的时间戳前缀，从而小于之前生成的 ID。这会破坏 ID 的单调递增性，影响数据库索引和基于时间排序的业务逻辑。

🛡️ 雪花算法应对时钟回拨的策略

为了解决时钟回拨问题，雪花算法的常见实现（如美团的 Leaf、百度 UIDGenerator 等）都内置了自卫机制。

策略一：拒绝服务（Fail Fast）

这是最简单、最激进的策略

  • 机制： 在每次生成 ID 时，比较当前时间 $T_{current}$ 和上次生成 ID 的时间 $T_{last}$。如果 $T_{current} < T_{last}$，则立即抛出异常，拒绝生成 ID。
  • 优点： 简单粗暴，绝对避免了 ID 冲突。
  • 缺点： 只要发生回拨，服务就中断，可用性受损。

策略二：等待追平（Wait and Spin）

这是最常用的策略，适用于短时间小幅度的回拨。

  • 机制： 如果检测到 $T_{current} < T_{last}$，服务不立即停止，而是进入自旋等待（Spin Wait），不断检查当前时间。
  • 目标： 一直等待，直到 $T_{current}$ 再次追上或超过 $T_{last}$，然后恢复正常 ID 生成。
  • 优点： 保持了服务的可用性，避免了 ID 冲突。
  • 缺点： 如果回拨幅度过大（例如回拨了几小时），服务将长时间暂停，影响系统的实时性。

策略三：使用备用序列号（牺牲位数）

  • 机制： 牺牲一部分 Worker ID 或时间戳的位数，将其用于回拨补偿计数器。
    • 当发生回拨时，不是等待时间追平，而是递增这个补偿计数器。这个补偿计数器会作为 ID 的一部分，保证即使时间回拨，也能生成新的、唯一的 ID。
  • 优点： 实现了不阻塞的 ID 生成，可用性最高。
  • 缺点： 牺牲了 Worker ID 或时间戳的长度，降低了系统的容量（能支持的机器数或寿命）。

策略四：多时钟源（Multi-Source Clock）

  • 机制： 不仅依赖本地时钟，还依赖一个外部的、可靠的时间源（如 GPS 时钟、NTP 服务器或 Etcd/ZK 集群时间）。
  • 作用： 当本地时钟发生回拨时，与外部时间源进行比对，若外部时间源正常，则根据外部时间源进行校准或选择等待。

在实际生产环境中，“策略二：等待追平”通常是最平衡和广泛应用的解决方案，因为它在可用性和唯一性之间找到了最佳的平衡点。

Worker ID 分配问题

1024 个 Worker ID 必须在所有工作节点中保持唯一，且分配过程必须保证强一致性。

解决方案：

  • 中心化分配： 使用 ZooKeeper 或 Etcd，让每个工作节点在启动时向中心服务注册并获取一个唯一的 Worker ID。
  • 数据库或 Redis： 使用数据库或 Redis 维护 Worker ID 的分配表。

并发量限制

雪花算法通过序列号来应对并发，但这也正是其并发能力的天花板所在。

在雪花算法的 64 位结构中，序列号占据了最低的 12 位：

\[\text{ID} = \text{Timestamp} \text{ (41-bit)} + \text{Worker ID} \text{ (10-bit)} + \underbrace{\text{序列号}}_{\text{(12-bit)}}\]

序列号的作用是解决同一毫秒内，单个工作节点（Worker ID）产生的 ID 冲突问题, 当工作节点在同一毫秒内收到多个 ID 生成请求时，它会不断地递增这个序列号。

当工作节点在同一毫秒内收到多个 ID 生成请求时，它会不断地递增这个序列号。

  1. 单节点并发上限 \(4096 \text{ ID/ms} \times 1000 \text{ ms/s} = 4,096,000 \text{ ID/s}\)

    即 409.6 万个 ID/秒

  2. 全局并发上限

    如果系统部署了所有的 1024 个节点，则全局的理论并发上限为：

    \[4,096 \text{ ID/ms/node} \times 1024 \text{ nodes} = 4,194,304 \text{ ID/ms}\]

    即4.19亿个 ID/秒

📉 序列号超限后的处理机制

实际应用中，单节点每秒几百万的请求量已经非常高了。但如果真的在某个毫秒内，单个节点收到的请求超过了 4096 次，序列号就会溢出

此时，标准的雪花算法实现会采取以下阻塞机制来保证唯一性：

  • 序列号溢出： 当序列号达到 4095 后，如果还有新的 ID 请求到达。
  • 自旋等待： 节点会暂停（阻塞）当前的 ID 生成线程。
  • 等待下一毫秒： 节点进入一个循环，不断地检查当前系统时间，直到时间进入下一毫秒（即时间戳发生变化）。
  • 重置序列号： 当时间进入下一毫秒后，序列号会被重置为 0，ID 生成服务恢复。

带来的影响:

  • 瞬时延迟： 在并发高峰期，如果序列号溢出，部分 ID 请求会经历 毫秒级或更长 的阻塞延迟，这会影响系统的响应时间（Latency）。
  • 无法应对瞬时脉冲式流量： 如果流量是以脉冲形式（例如瞬间 10 毫秒内来了极高的请求）到达，系统可能会在这几毫秒内反复触发序列号溢出，导致服务吞吐量下降。

提高并发能力的变种方案

为了解决 12 位序列号的限制，一些基于雪花算法的定制化实现会进行调整：

  • 牺牲位数： 如果业务对 Worker ID 的数量要求不高，可以牺牲 Worker ID 的位数来增加序列号的位数。
  • 秒级时间戳： 将时间戳精度从毫秒降低到秒，这样可以为序列号腾出更多空间（但会牺牲 ID 的时间有序粒度）
  • 批量生成： 节点一次性生成一个序列号范围（例如 1000 个）并在本地内存中快速发放，避免频繁的位运算

雪花算法的变体实现

百度Uidgenerator

百度 UidGenerator 也是基于雪花算法的优化变体，项目地址: github.com/baidu/uid-generator，其核心改进在于解决了时钟回拨问题和自定义位结构。

时间戳与 Worker ID 的自定义

百度 UidGenerator 允许用户根据业务需求自定义 64 位的结构，但其最大特点是：

  • 时间戳： 默认使用 秒级时间戳（而不是毫秒级）。秒级时间戳意味着有更多的位可以分配给序列号，大大提高了单节点的容量。
  • Worker ID 分配： 依赖数据库或 Redis。启动时，节点会向数据库注册，获取分配的 Worker ID，并定期向数据库发送心跳，确保 Worker ID 的有效性和防止冲突。

对于uid-generator ID组成结构：

workId，占用了22个bit位，时间占用了28个bit位，序列化占用了13个bit位，需要注意的是，和原始的snowflake不太一样，时间的单位是秒，而不是毫秒，workId也不一样，而且同一应用每次重启就会消费一个workId。

\[\text{ID} = \underbrace{0}_{\text{符号位 (1-bit)}} + \underbrace{\text{时间戳}}_{\text{(28-bit)}} + \underbrace{\text{工作机器 ID}}_{\text{(22-bit)}} + \underbrace{\text{序列号}}_{\text{(13-bit)}}\]

UidGenerator 的设计哲学：通过牺牲时间戳的精度和寿命，来换取更大的 Worker 节点容量和更稳定的单节点并发处理能力。

解决时钟回拨

百度 UidGenerator 使用 RingBuffer（环形缓冲区）来缓存 ID，以解决雪花算法的两个问题：

  • 解决时钟回拨： ID 是预先生成的并缓存在 RingBuffer 中的。当应用请求 ID 时，它从 RingBuffer 中获取，而不是实时计算。如果系统时钟发生回拨，由于 RingBuffer 中的 ID 已经被生成并确定，它会继续发放，不会立刻抛异常。当 RingBuffer 消耗完需要重新生成批次时，才会进行时间校验。
  • 提高发放速度： 预生成和缓存的方式使 ID 的发放速度极快，避免了并发时的锁竞争。

美团Leaf

美团点评技术团队开源的 Leaf 是一个非常全面的分布式 ID 解决方案, 项目地址: github.com/Meituan-Dianping/Leaf。它在一个服务中集成了基于数据库的号段模式和雪花算法模式，可以灵活切换。

这里我们专注于分析雪花算法模式:

Leaf 实现了标准的雪花算法, 保持了标准的雪花ID结构，但解决了其核心痛点：Worker ID 的分配。

  • Worker ID 分配:
    • 依赖 ZooKeeper 或 Etcd。 每个 Leaf 节点启动时，会向 ZK 注册一个临时顺序节点，ZK 返回的顺序号即作为该节点的 Worker ID, 实现了 Worker ID 的自动、全局唯一分配，大大简化了运维难度
  • 时钟回拨处理:
    • 记录上次时间，如果检测到回拨，会自旋等待（Spin Wait），直到时钟追平，确保不生成重复 ID。

UUID和雪花算法的特性分析

碰撞概率

UUID (Version 4) 的碰撞概率分析

UUID Version 4 依赖于 122 位的高质量随机数。其碰撞概率计算主要基于生日攻击（Birthday Attack）模型

  • 总空间 (N)： $2^{122}$ 个可能的 ID (去除 6 位版本和变体位)。
  • 生日问题： 在一个集合中随机选取 $k$ 个元素，它们中至少有两个元素相同的概率。
  • 近似公式： 当生成的 ID 数量 $k$ 远小于总空间 $N$ 时，碰撞概率 $P(\text{Collision})$ 可以近似为： \(P(\text{Collision}) \approx \frac{k^2}{2N}\)

UUID v4 的碰撞概率在工程上可以被认为是 0。在实际应用中，你更可能遇到磁盘故障、网络瘫痪或彗星撞地球，而不是 UUID v4 的随机碰撞。

雪花 ID (Snowflake) 的重复概率分析

雪花 ID 的碰撞风险不是来自随机数，而是来自系统性故障，主要是时钟回拨

雪花 ID 在理想运行状态下（时钟准确、Worker ID 唯一），其设计保证了 ID 的强唯一性：

  • 不同毫秒： 时间戳不同，ID 必不相同。
  • 相同毫秒、不同机器： Worker ID 不同，ID 必不相同。
  • 相同毫秒、相同机器： 序列号不同，ID 必不相同。

雪花 ID 的碰撞风险几乎 100% 来自于 时钟回拨（Clock Backwards），并且没有有效的数学概率来量化，因为它依赖于外部运维行为或系统配置错误。

有序性

这是两者最核心的区别，也是决定选型的关键因素：

  • UUID (V4)： 由于是随机生成的，将 UUID 作为数据库的主键（尤其是在使用聚簇索引如 MySQL InnoDB 引擎时），会导致新的数据被插入到随机的位置，造成大量的页分裂和磁盘随机 I/O，严重影响数据库的写入性能。
  • 雪花 ID： ID 的高位是时间戳，这意味着 ID 是随时间增长而递增的。新数据总是在索引的末尾追加，保持了索引的顺序性，极大地优化了插入性能和范围查询。

有序ID为什么会提升数据的写入性能

我们知道 MySQL InnoDB 存储引擎使用 B+ 树存储索引数据，而主键也是一种索引。索引数据在 B+ 树中是有序排列的，就像下面这张图一样，图中 2，10，26 都是记录的 ID，也是索引数据。

索引结构示例

这时，当插入的下一条记录的 ID 是递增的时候，比如插入 30 时，数据库只需要把它追加到后面就好了。但是如果插入的数据是无序的，比如 ID 是 13，那么数据库就要查找 13 应该插入的位置，再挪动 13 后面的数据，这就造成了多余的数据移动的开销。

索引插入示例

空间占用

  • UUID： 长度为 128 位，随机数空间巨大，保证了全球唯一性。
  • 雪花 ID： 长度为 64 位，牺牲了部分唯一性空间，换取了更短的长度。其唯一性依赖于 Worker ID 的正确分配和时钟的准确性。

独立性

  • UUID： 完全去中心化。任何机器在任何时候都可以独立生成 ID，无需任何外部依赖。因此，它的高可用性是最高的。
  • 雪花 ID： 虽然运行时是去中心化的，但在启动时仍然需要一个机制来分配 Worker ID，以确保唯一性。这引入了对外部协调服务（如 ZooKeeper 或数据库）的弱依赖。如果 Worker ID 分配服务故障，新的节点将无法加入集群并生成 ID。

业务含义

其实现实世界中使用的 ID 中都包含有一些有意义的数据，这些数据会出现在 ID 的固定的位置上。

比如说我们使用的身份证的前六位是地区编号；7～14 位是身份证持有人的生日；不同城市电话号码的区号是不同的；你从手机号码的的前三位就可以看出这个手机号隶属于哪一个运营商。

而如果生成的 ID 可以被反解，那么从反解出来的信息中我们可以对 ID 来做验证，我们可以从中知道这个 ID 的生成时间，从哪个机房的发号器中生成的(例如雪花ID的数据中心ID和WorkerID)，为哪个业务服务的，对于问题的排查有一定的帮助。

UUID 不具备业务含义，是因为它的生成机制与业务逻辑或状态是解耦且独立的

一个随机生成的 UUID，例如 f81d4fae-7dec-11d0-a765-00a0c91e6bf6，对于业务系统而言，它只是一个没有规律的、随机的数字。你无法从这个数字中推断出它是哪个用户的 ID、它是什么时候创建的订单，或者它属于哪个数据中心。

ID包含业务含义的一个典型案例是: 自寻址 ID（Self-Addressing ID）

它是分布式系统设计中的一个高级且非常实用的模式, 将 ID 的部分位用来编码业务信息或路由信息，从而使得系统可以不依赖额外的查询或配置表，仅通过解析 ID 本身就能知道如何处理或存储它。

例如：为了实现自寻址，订单 ID 的 64 位结构可以被调整为包含用户信息的片段

\[\text{Order ID} = \underbrace{\text{时间戳}}_{\text{(41-bit)}} + \underbrace{\text{集群 ID}}_{\text{(3-bit)}} + \underbrace{\text{用户 ID 片段}}_{\text{(10-bit)}} + \underbrace{\text{序列号}}_{\text{(10-bit)}}\]

集群/机房 ID 自动寻址：

  • 步骤一：路由信息嵌入
    • 当在机房 A 生成订单 ID 时，这 3 位会被固定设置为机房 A 的 ID。
    • 在 ID 中预留 3 位作为 集群 ID (Cluster ID)，支持 $2^3 = 8$ 个不同的物理集群或机房。
  • 步骤二：生成和存储
    • 用户发起订单请求，请求进入机房 A 的订单服务。
    • 订单服务生成 Order ID，该 ID 中天然嵌入了 机房 A 的 ID。
    • 订单数据根据用户 ID 片段（或订单 ID 中的片段）被路由到机房 A 内的特定分库进行存储。

  • 步骤二：生成和存储

    假设现在系统需要查询这个订单。

    • 客户端/路由层获取到 Order ID：[Time] [Cluster ID = A] [User ID Segment] [Sequence]。
    • 解析 ID： 路由中间件立即解析 ID，发现 Cluster ID 部分是 A。
    • 寻址： 路由中间件将查询请求直接转发到机房 A 的订单集群。
    • 分库定位： 请求到达机房 A 后，再根据 用户 ID 片段 定位到具体的数据库分片。

通过这种设计，系统实现了“用户 ID 切分到哪个分片，订单 ID 也切分到哪个分片”的目标。

当查询用户的所有订单时，所有数据都集中在少数几个分片上，避免了全局扫描。

应用场景选择

在实际工程选型中，选择 UUID（V4、V5）还是雪花 ID（及其变体）取决于对 ID 有序性、性能、去中心化程度和 ID 长度的要求。

随机 UUID V4：绝对去中心化和随机性

UUID V4 是最纯粹的随机 ID

核心特性:

  • 绝对去中心化： 完全不依赖任何外部服务或协调机制。
  • 高随机性： 128 位随机数，碰撞概率极低，具有高度不可预测性。

适用场景:

  • 会话/令牌 ID： 用于生成 Session ID、API Key、CSRF 令牌或 JWT 的 JTI（JWT ID）。此时要求 ID 具有随机性和不可预测性。
  • 临时标识符： 用于缓存 Key、临时文件名、请求跟踪 ID 等，这些 ID 只需要保证在短时间内是唯一的。
  • 不作为主键： 在 NoSQL 数据库（如 Cassandra、MongoDB）或关系型数据库中不作为主键使用的场景。
  • 日志系统： 作为日志链路追踪 ID，其随机性在分布式系统中非常实用。

原则：当 ID 越短和越有序带来的性能收益，不如完全去中心化和随机性带来的架构简化和安全收益时，选择 UUID V4

哈希 UUID V5：命名空间下的稳定标识符

UUID V5 基于 SHA-1 哈希，其目的是对特定名称生成一个稳定的、可预测的 UUID

核心特性:

  • 可预测性： 对于相同的（命名空间 + 名称）输入，输出的 UUID 永远相同。
  • 逻辑绑定： 将一个 UUID 与一个特定的外部名称（如 URL、域名、用户名）永久绑定。

适用场景:

  • 外部资源标识： 为外部资源（如 URL、API 路径、文件路径）生成 UUID，以保证在不同系统间引用该资源时 ID 是统一的。
  • 内容寻址（Content-Addressing）： 类似 Git 的哈希值，当内容不变时，ID 也不变，用于识别不随时间变化的静态实体。
  • 数据迁移/同步： 在需要将某个业务名称（如用户登录名）作为唯一标识符在多个系统间同步时，使用 V5 可以确保 ID 不冲突。

当需要根据一个已知的、唯一的字符串（名称）来生成一个稳定且唯一的 ID 时，选择 UUID V5

雪花 ID (及其变体)：高性能的分布式主键

雪花 ID（Snowflake）是为了解决 UUID V4 在关系型数据库中作为主键的性能问题而设计的

核心特性:

  • 高性能写入： ID 有序递增，极大地提高了数据库聚簇索引的写入效率。
  • 短小精悍： 64 位 Long 型，存储和索引效率远高于 128 位字符串。
  • 可追溯性： ID 中包含时间戳，可以大致逆推出 ID 的生成时间。

适用场景:

  • 关系型数据库主键： 最核心的适用场景。适用于订单 ID、交易 ID、用户 ID 等需要作为数据库主键且数据量巨大的核心业务表。
  • 高并发要求： 适用于对 ID 吞吐量有极高要求的场景（如电商订单、秒杀系统）。
  • 数据切分键： 适用于将 Worker ID 或 ID 的部分位用作分库分表键或集群寻址的自寻址 ID 场景。

当 ID 被用作关系型数据库的主键，且对数据库的写入性能和存储效率有高要求时，必须选择雪花 ID 或其变体（如 UUID v7 或 ULID）

相比UUID和雪花算法, 另一种可选的无中心依赖的分布式ID生成算法是 ULID (可排序的通用唯一标识符 / Universally Unique Lexicographically Sortable Identifier)

ULID: 旨在结合 UUID 的唯一性和去中心化生成能力，以及 Snowflake 的时间排序特性

ULID 是一个 128 位的标识符，由两部分组成，完全由本地节点生成

  • 前48位： 时间戳（毫秒精度）。
  • 后80位： 随机或伪随机数。
\[\text{ULID} = \underbrace{\text{48-bit Time}}_{\text{排序}} + \underbrace{\text{80-bit Random}}_{\text{唯一性}}\]

UUID Version 7（UUID v7）是一种相对较新的 UUID 标准，它旨在结合 UUID 的全球唯一性和雪花算法的时间有序性， 虽然它叫UUID， 但是结构上来看更类似于雪花ID和ULID

UUID v7 仍然是一个 128 位的标识符，但其结构被划分为三个主要部分，类似于雪花算法和 ULID:

\[\text{UUID v7} = \underbrace{\text{Unix Time (ms)}}_{\text{(48-bit)}} + \underbrace{\text{Version \& Variant}}_{\text{(4-bit + 4-bit)}} + \underbrace{\text{Randomness}}_{\text{(74-bit)}}\]
  1. Unix 毫秒时间戳 (48 位)
  2. 版本号和变体号 (8 位)
  3. 随机/序列号(74 位)

UUID v7 的主要优势:

  • 高效率的数据库索引： 由于前缀是时间戳，UUID v7 是时间有序的，作为数据库主键时，可以大幅减少索引碎片和随机 I/O，解决了 UUID v4 的核心性能问题。
  • 绝对的去中心化： 与雪花 ID 不同，UUID v7 不需要 Worker ID 的分配机制，完全在本地计算，简化了部署和运维。
  • ID 寿命长： 48 位毫秒时间戳提供了长达数千年的寿命，比雪花 ID 的 69 年长得多。
  • 极强的唯一性： 128 位 ID 长度和 74 位随机/序列号空间，提供了超越所有 64 位 ID 方案的碰撞抵抗能力。

参考

Software Development
Architecture Design 分布式 微服务
本文由作者按照 CC BY 4.0 进行授权