Skip to content

雪花算法介绍

1. 背景

在分布式系统中，生成唯一 ID 是一个常见的挑战。

  • 数据库自增 ID：简单易用，但难以在多个数据库实例之间保持唯一性，扩展性差。
  • UUID (GUID)：全局唯一，但长度过长（128 位），无序（导致数据库索引效率低下），不易读。
  • 中心化 ID 服务：可以保证唯一性，但可能成为单点故障和性能瓶颈。

雪花算法旨在提供一种去中心化、高性能、高可用的解决方案，生成具有以下特性的 ID：

  • 全局唯一：在整个分布式系统中都不会重复。
  • 趋势递增：虽然不是严格的单调递增，但总体上是递增的，有利于数据库索引和存储。
  • 高性能：ID 在本地生成，不依赖网络通信，生成速度极快。
  • 不依赖数据库：避免了数据库的性能瓶颈。

2. ID 结构

雪花算法生成的 ID 是一个 64 位的 Long 型整数，其结构被巧妙地划分为几个部分：

1 bit        41 bits           10 bits           12 bits
+-----+---------------------+-----------------+--------------+
| 0   |   时间戳 (毫秒)      |   工作节点ID     |    序列号     |
+-----+---------------------+-----------------+--------------+

  • 1 位：符号位 (Sign Bit)

    • 始终为 0。由于 ID 是正数，最高位不需要表示正负，所以这一位是预留的，或者说不使用。

  • 41 位：时间戳 (Timestamp)

    • 表示 ID 生成时的时间戳，精确到毫秒。
    • 这个时间戳并非当前精确时间，而是 当前时间减去一个预设的“起始时间”（Epoch）。这个起始时间可以自己定义，例如 2020-01-01 00:00:00。
    • 41 位的时间戳可以表示 2^41 - 1 毫秒，大约是 69 年。这意味着从定义的起始时间开始，ID 生成器可以不间断地工作 69 年而不会出现时间戳溢出。
    • 这一部分是 ID 能够趋势递增的核心。

  • 10 位：工作节点 ID (Worker ID)

    • 用于标识生成 ID 的机器或进程。
    • 10 位可以表示 2^10 - 1 = 1023 个工作节点。这意味着你可以部署最多 1024 台独立的机器（或进程）来生成 ID，每台机器都有一个唯一的 ID。
    • 这个 ID 通常需要预先配置给每个机器，或者通过某种方式（如 Zookeeper）动态分配。
    • 这一部分是 ID 在分布式环境下能保持唯一性的关键。

  • 12 位：序列号 (Sequence Number)

    • 用于表示在同一个毫秒内，同一个工作节点上生成的 ID 的序列号。
    • 12 位可以表示 2^12 - 1 = 4095 个序列号。这意味着在同一个毫秒内，一个工作节点最多可以生成 4096 个不同的 ID。
    • 如果在一个毫秒内生成的 ID 数量超过 4096，则会等待下一个毫秒再生成。
    • 这一部分保证了在极高并发下，同一毫秒内同一机器上的 ID 依然唯一。

3. 工作原理

当一个服务需要生成一个 ID 时，它会执行以下步骤：

  1. 获取当前时间戳：获取当前的毫秒级时间戳 current_timestamp。
  2. 处理时钟回拨：
    • 如果 current_timestamp 小于上次生成 ID 的时间戳 last_timestamp，说明系统时钟回拨了，这会导致 ID 重复。通常会抛出一个异常，或者等待时钟追上。
    • 如果 current_timestamp 等于 last_timestamp：
      • 序列号 sequence 加 1。
      • 如果 sequence 超过了 12 位最大值（4095），说明当前毫秒内 ID 已用尽，需要等待直到下一个毫秒。
    • 如果 current_timestamp 大于 last_timestamp：
      • 重置序列号 sequence 为 0。
      • 更新 last_timestamp 为 current_timestamp。
  3. 组合 ID：
    • 将 (current_timestamp - epoch) 左移 (worker_id_bits + sequence_bits) 位。
    • 将 worker_id 左移 sequence_bits 位。
    • 将 sequence 直接组合。
    • 最终通过位或 (OR) 操作将三部分合并成一个 64 位的 Long 型 ID。

位移计算示例： 如果 worker_id_bits 是 10，sequence_bits 是 12：

  • 时间戳部分需要左移 10 + 12 = 22 位。
  • 工作节点 ID 部分需要左移 12 位。

ID = (timestamp_diff << 22) | (worker_id << 12) | sequence

4. 优缺点

4.1 优点

  1. 全局唯一性：通过时间戳、工作节点 ID 和序列号的组合，保证了在分布式环境下的 ID 唯一性。
  2. 高性能高可用：ID 在本地生成，无需进行网络 IO 和数据库操作，生成速度极快，且不依赖外部服务，减少了单点故障的风险。
  3. 趋势递增：由于高 41 位是时间戳，生成的 ID 是趋势递增的。这对于数据库索引（如 MySQL 的 InnoDB）非常友好，可以减少页分裂和碎片，提高写入性能。
  4. 不暴露业务信息：ID 不包含任何业务含义，具有一定的安全性。
  5. 占用空间小：64 位 Long 型，比 UUID（128 位）小一半，存储效率更高。

4.2 缺点

  1. 依赖系统时钟：
    • 时钟回拨问题：如果服务器的时钟发生回拨（例如，NTP 同步导致时钟调整到过去），可能会生成重复的 ID。这是雪花算法最主要的挑战。
    • 解决方案：
      • 检测到时钟回拨时，抛出异常，或者暂停服务，等待时钟追上。
      • 设置一个“等待”策略：如果时钟回拨在一个可接受的范围内（如几百毫秒），可以等待到时钟达到上次生成 ID 的时间，或者等待到下一毫秒。
      • 严格 NTP 同步，并监控系统时钟。
      • 有些改进算法（如百度 UidGenerator）会使用与系统时间无关的“自定义时间”来缓解此问题。
  2. 工作节点 ID（Worker ID）管理：
    • 需要为每个 ID 生成器实例分配一个唯一的 Worker ID。
    • 在弹性伸缩、容器化部署的环境中，动态分配和管理 Worker ID 是一个挑战。
    • 解决方案：
      • 手动配置：简单但维护成本高。
      • 利用 Zookeeper/Eureka 等注册中心：在服务启动时向注册中心注册并获取 Worker ID。
      • 通过机器 IP 地址/端口号等信息生成。
  3. 固定位数的限制：41 位时间戳、10 位工作节点 ID、12 位序列号的划分是固定的，如果未来业务需求（如需要更多工作节点或更长时间的服务）超出这些限制，则需要修改算法或调整位数分配。

5. 优化

  • Epoch 的选取：选择一个合适的起始时间（Epoch），可以最大化 41 位时间戳的使用寿命。通常选一个距离当前时间较近的日期。
  • Worker ID 的分配：
    • 对于小规模部署，可以手动配置或从配置文件读取。
    • 对于大规模部署或容器化环境，可以集成 ZooKeeper、Etcd、Consul 等服务注册与发现工具，在应用启动时自动注册并获取唯一的 Worker ID。
  • NTP 服务：确保所有机器的时钟都通过 NTP 服务进行同步，以减少时钟回拨的可能性。
  • 高可用性：即使单个 Worker 宕机，其他 Worker 仍能继续生成 ID，具有良好的分布式容错性。