Skip to content

雪花算法介绍

雪花算法（Snowflake Algorithm）是Twitter开源的分布式ID生成算法，其目的是在分布式系统中生成全局唯一、趋势递增的64位整数ID。它解决了传统数据库自增ID在分布式环境下难以扩展和管理的问题，也避免了UUID过长、无序、占用空间大等缺点。

背景

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

雪花算法旨在提供一种去中心化、高性能、高可用的解决方案，生成具有以下特性的ID： * 全局唯一：在整个分布式系统中都不会重复。 * 趋势递增：虽然不是严格的单调递增，但总体上是递增的，有利于数据库索引和存储。 * 高性能：ID在本地生成，不依赖网络通信，生成速度极快。 * 不依赖数据库：避免了数据库的性能瓶颈。

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依然唯一。

工作原理

当一个服务需要生成一个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

优缺点

优点

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

缺点

  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位序列号的划分是固定的，如果未来业务需求（如需要更多工作节点或更长时间的服务）超出这些限制，则需要修改算法或调整位数分配。

优化

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