雪花算法介绍和实现

type

status

date

slug

summary

1、雪花算法简介

1.1 雪花算法是什么

雪花算法是 Twitter 开发的一种分布式 ID 生成算法，用于在分布式系统中生成全局唯一且有序的ID。雪花算法的特点：

全局唯一：在分布式系统中生成的 ID 不会重复

时间有序：ID 按时间顺序递增

高性能：本地生成，无需依赖数据库或其他服务

可扩展：可根据需要调整各部分的位数

雪花算法 ID 是一个二进制 64 位长整型数字，由以下几部分组成：

1位符号位：因为二进制中最高位是符号位，1 表示负数，0 表示正数，生成的 id 一般都是用整数，所以最高位固定为 0。

41位时间戳：记录生成 ID 的时间戳（毫秒级），可用约 69 年

10位工作机器ID：每个机器分配一个 ID，通常分成两部分：

5位数据中心ID
5位机器ID

12位序列号：同一毫秒内的自增计数器，支持每毫秒生成 4096 个 ID

1.2 雪花算法的实现原理

获取当前时间戳（毫秒）

比较当前时间戳与上次生成ID的时间戳：

如果相同，则序列号+1

如果不同，则序列号归零

如果当前时间戳小于上次时间戳，说明时钟回拨，抛出异常或等待

组合各部分（符号位 + 时间戳 + 机器ID + 序列号）生成最终ID

2、雪花算法常见问题

2.1 时钟回拨问题

由于雪花算法严重依赖服务器时间，当服务器时间由于 NTP 同步或人为调整，导致当前时间比上次生成 ID 的时间还要早。这会导致可能生成重复 ID，破坏 ID 的唯一性，这就是时钟回拨问题。

时钟回拨问题常见的解决方案：

直接抛出异常：雪花算法原本的实现中，针对这种问题，算法直接返回错误，有点过于简单粗暴。

休眠等待：当检测到时钟回拨时，让线程休眠等待，直到时间追回，可以容忍较小范围的时间回拨。这也是业界常用的解决方案。

备用时间源：当检测到系统时钟回拨时，使用备用时间源获取时间戳继续生成ID，直到系统时间追上备用时间源的时间。备用时间源可以部署专门的时间服务，也可以调用第三方时间 API（如阿里云、腾讯云提供的时间服务）。

2.2 机器ID分配问题

雪花算法的机器 ID 如果发生重复，可能会导致 ID 重复的问题。目前常用的机器 ID 分配方案有：

静态配置：最简单的是在每台机器上静态配置机器ID，这种方式实现简单，但是需要人工维护，可能会出错。

数据库分配：创建机器注册表，新机器启动时插入记录获取自增ID。这种方式可以实现集中自动分配，但是需要引入数据库依赖，而且 ID 一直自增，有可能会超出机器 ID 位数上限。

Zookeeper分配：利用 Zookeeper 临时顺序节点的特性（自增有序、客户端断开自动删除节点），在新机器启动时创建临时顺序节点，该节点编号就是机器ID；当机器停止时自动删除临时顺序节点。这种方式可以实现集中自动分配，且可以保证机器 ID 不会超过位数上限。缺点是需要引入 Zookeeper 依赖。

实际可以结合多种方式，例如
首先尝试从配置文件读取
如果没有配置，尝试从 Zookeeper 获取

2.3 数据倾斜问题

如果 12 位序列号在每个毫秒都从 0 开始自增，在生成 ID 频率较低的情况下，生成的分布式 ID 始终都是偶数，会产生严重的数据倾斜问题，例如

原因是 64 位二进制最后 12 位一直都是 000000000000，而决定奇偶的关键在于最后一个 0。为 0 就是偶数，为 1 就是奇数。

解决方案是在一个毫秒里面，起始值取 0 或者 1 的随机数。

3、雪花算法实践

下面是雪花算法的一个简单实现，实现要点：

通过主机名生成数据中心ID。

通过网络生成机器ID。

使用休眠等待的方式处理时钟回拨问题。

Snowflake 类

SnowflakeUtils 工具+测试类

测试结果如下：

4、业界常用雪花算法工具

4.1 美团Leaf

美团Leaf 包含 Leaf-segment 模式和 Leaf-snowflake 两种模式

Leaf-segment模式：对数据库生成方案的优化。主要体现在

segment 分段取 id，减少 mysql 的 IO 次数
双 buffer 机制，号码消耗到一定程度（10%）就开启异步线程去取新的id

Leaf-snowflake：对 snowflake 方案的优化，需要依赖 zookeeper 生成 workerID。

该仓库已经很久没人维护，第三方组件依赖较重，技术选型的时候需要认真考虑。

代码仓库 https://github.com/Meituan-Dianping/Leaf

4.2 Hutool的IdUtil

国产工具类开源框架 Hutool 实现了雪花算法，没有第三方组件依赖，使用起来比较简单。如果你的团队没有排斥 Hutool 框架，技术选型的时候可以考虑一下。

代码仓库https://github.com/looly/hutool

4.3 MyBatis-Plus的IdWorker

MyBatis-Plus 的主键的生成策略实现了雪花算法，默认生成策略就是使用雪花算法。有两种使用方式：

第一种方式，局部配置，在主键字段上使用 @TableId 注释。

第二种方式，全局配置

之后在插入数据库的时候主键字段就会自动填充雪花算法生成的 id。

MyBatis-Plus 支持的主键生成类型：
IdType.AUTO：使用数据库自增 ID 作为主键。
IdType.NONE：无特定生成策略，如果全局配置中有 IdType 相关的配置，则会跟随全局配置。
IdType.INPUT：在插入数据前，由用户自行设置主键值。
IdType.ASSIGN_ID：自动分配 ID，适用于 Long、Integer、String 类型的主键。默认使用雪花算法通过 IdentifierGenerator 的 nextId 实现。@since 3.3.0
IdType.ASSIGN_UUID：自动分配 UUID，适用于 String 类型的主键。默认实现为 IdentifierGenerator 的 nextUUID 方法。@since 3.3.0