雪花算法

雪花算法（Snowflake Algorithm）是一种用于生成唯一标识符（Unique Identifier）的算法

它最初由 Twitter 开发并开源，用于在分布式系统中生成全局唯一 ID

雪花算法的原理就是生成一个的 64 位比特位的 long 类型的 ID

符号位（1 位）：固定固定为 1，因为 ID 都为正数
时间戳（41 位）：毫秒级别的时间戳，大约可以使用 69 年（事实上很多实现会减去一个 offset）
机器码（10 位）：分布式服务 ID，2 ^ 10 = 1024 台机器
序列号（12 位）：同一时间戳、同一机器下，通过序列号自增进行 ID 生成，即同一毫秒下可以生成 2 ^ 12 = 4096 个不同的 ID

64 位如下所示：

0 - 00000000000000000000000000000000000000000 - 0000000000 - 000000000000

符号位（1 位）
时间戳（41 位）
机器码（10 位）
序列号（12 位）

Seata 改良

在老版 Seata（1.4 以前），内置的 UUID 生成器的实现基于标准版的雪花算法

在后续的更新中 Seata 对标准雪花算法进行了改良

问题

Seata 认为标准的雪花算法有以下几个缺点

时钟敏感：因为 ID 生成总是和当前操作系统的时间戳绑定的（利用了时间的单调递增性），如果服务发生了时钟回拨，生成的 ID 就会重复；当然一些实现会避免该问题，方案一般是记录上次生成 ID 时的时间戳，如果发现当前时间小于记录时间，则说明发生了时钟回拨，则拒绝服务意味着出现时钟回拨，会导致服务在一定时间内不可用
突发性能有限：序列号的位长度为 12，也就是同一 ms 并发都必须低于 4096；一些实现会自旋等待，当差距较大时则抛出限流异常等拒绝服务

改进

改进的核心思想是解除与操作系统时间戳的时刻绑定

生成器只在初始化时获取了系统当前的时间戳，作为初始时间戳，但之后就不再与系统时间戳保持同步了；随后 ID 的递增，只递增序列号；当序列号溢出时，进位到时间戳位（低 12 位满），序列号重新归零

为了方便这种溢出进位，Seata 调整了 64 位 ID 的位分配策略

0 - 0000000000 - 00000000000000000000000000000000000000000 - 000000000000

符号位（1 位）
机器码（10 位）
时间戳（41 位）
序列号（12 位）

这样时间戳和序列号在内存上是连在一块的，在实现上就很容易用一个 AtomicLong 来同时记录块数据

/**
 * timestamp and sequence mix in one Long
 * highest 11 bit: not used
 * middle  41 bit: timestamp
 * lowest  12 bit: sequence
 */
private AtomicLong timestampAndSequence;

高 11 位（符号位 + 机器码）在服务启动时就已经确定，服务运行过程中也不会变化

/**
 * business meaning: machine ID (0 ~ 1023)
 * actual layout in memory:
 * highest 1 bit: 0
 * middle 10 bit: workerId
 * lowest 53 bit: all 0
 */
private long workerId;

这样生成 UUID 的代码如下

public long nextId() {
   // 获得递增后的时间戳和序列号
   long next = timestampAndSequence.incrementAndGet();
   // 截取低53位
   long timestampWithSequence = next & timestampAndSequenceMask;
   // 跟先前保存好的高11位进行一个或的位运算
   return workerId | timestampWithSequence;
}

收益

由上可以发现，问题得到了改善：

生成器不再有 4096/ms 的突发性能限制了；如果某个时间戳的序列号空间耗尽，它会直接推进到下一个时间戳
生成器弱依赖于操作系统时钟；在运行期间，生成器不受时钟回拨的影响无论是人为回拨还是机器的时钟漂移，因为生成器仅在启动时获取了一遍系统时钟，之后两者不再保持同步；可能产生重复 ID 的只有在重启时的大幅度时钟回拨
对于推进到下一个时间戳的 “超前消费” 问题，如果生成器内的时间戳大大超前于系统的时间戳，从而在重启时造成 ID 重复？实际上不可能，达到这种情况需要特别大的 QPS

补充

Work ID 优化

Work ID 是分布式下的机器码，基本要求是每个实例拥有唯一的标识

常见的确定 Work ID 的方式：

手动配置
基于网络信息：因为网络信息一般带有唯一性，例如使用 IP 地址、MAC 地址、主机名等作为 Work ID 的一部分
自动化生成：使用一些工具进行生成，比如依赖 ZK 节点来进行唯一的保证

无论选择哪种方法，都需要确保每个机器或节点的 Work ID 是唯一的，并且在分布式系统中保持稳定；这样可以避免生成重复的 ID，确保整个系统的正确运行

Seata 基于网络信息进行 Work ID 的确定，截取本地 IPv4 地址的低 10 位作为 Work ID，很明显这样会造成 Work ID 重复，例如如下 IP

192.168.4.10
192.168.8.10

优化后将优先使用网卡 MAC 地址截取，若本机未配置有效的网卡，则在 [0, 1023] 中随机挑一个作为 ID（其实应该依然存在重复问题，只是减少了概率；感觉还是美团的 leaf 等使用 ZK 方式比较好，但是会引入新中间件，增加系统复杂度）

单调递增和页分裂

Seata 改良后的雪花算法是否是单调递增的？

在标准雪花算法中，时间戳排在机器码之前，即多节点服务，依然可以保证一定程度上有序（同一 ms 内生成的 ID 可能无序，不同 ms 之间单调递增）

在 Seata 改良后的雪花算法中，机器码在时间戳之前，进一步加大了这种无序性

那么这种无序性是否会造成页分裂？

按照 Seata 的解释是短时期内会造成，但在有限次分裂后，不会进行新的页分裂，因为 Work ID 是有限的，最终一定会出现能容纳固定 Work ID 的页

到达终态后，后续的ID只会在该ID所属的子序列上进行顺序增长，而不会造成页分裂

该状态下的顺序增长与 auto_increment 的顺序增长的区别是，前者有 1024 个增长位点（各个子序列的尾部），后者只有尾部一个

到这里我们可以回答开头所提出的问题了：新算法从全局来看的确不是全局递增的，但该算法是收敛的，达到稳态后，新算法同样能达成像全局顺序递增一样的效果

理论上依然存在的问题

虽然 Seata 一致在论证改进后 ID 生成方式的优势，但我觉得从理论上来看依然存在一些问题（虽然很多问题从应用层面考虑认为无法出现，但并不是从理论层面解决）

时钟回拨后重启服务：虽然 ID 生成过程中不依赖时间戳，但如果回拨时间太长、部署时间短依然会导致 ID 重复的问题
- 应用层面：不会有太长时间回拨，服务部署需要一定时间
超前消费：虽然 QPS = 400w/s，但理论上仍然存在超前消费，重新部署后 ID 重复问题
- 应用层面：对 QPS 的要求基本不可能达到
Work ID 重复：上述 Work ID 生成操作依然会存在重复问题，只不过概率较小
页合并导致的页分裂无法收敛：详情见关于新版雪花算法的答疑 | Seata

参考

Seata基于改良版雪花算法的分布式UUID生成器分析 | Seata

关于新版雪花算法的答疑 | Seata

贫瘠之地

Seata 改良版雪花算法

雪花算法

Seata 改良

问题

改进

收益

补充

Work ID 优化

单调递增和页分裂

理论上依然存在的问题

参考