📣读完这篇文章里你能收获到

• 图文形式为你讲解原生雪花算法的特征及原理
• 了解时间回拨的概念以及可能引起发此现象的操作
• 掌握时间回拨的解决方案—基于时钟序列的雪花算法
• 关于雪花算法的常见问题解答

文章目录

• 一、原生的雪花算法
• • 1. 简介
  • 2. 特征
  • 3. 原理
  • • 3.1 格式（64bit）
    • 3.2 字节分配
• 二、雪花算法的时间回拨问题
• • 1. 问题描述
  • 2. 现象引发
  • 3. 常见的处理方式
  • • 3.1 直接抛出异常
    • 3.2 延迟等待
• 三、基于时钟序列解决时间回拨的方案
• • 1. 简介
  • 2. 设计思路
  • 3. 算法支持
  • 4. 关键实现代码
• 四、关于雪花算法的常见问题解答
• • 1. 雪花算法支持的并发数最大多少？
  • 2. 雪花算法支持最多支持系统运行多少年？
  • 3. 用了雪花Id，出现负闰秒为什么会导致系统大量抛异常？

一、原生的雪花算法

1. 简介

• 分布式 ID 生成算法用于在分布式系统中生成全局唯一的 ID 标识
• Twitter 提出的雪花算法便是其中一种知名的算法，也是一种发号器方案
• 百度（uid-generator）、美团（Leaf）及滴滴（Tinyid）等开源分布式ID都是基于雪花算法实现的，如果有人问你有关唯一 ID 生成的问题，你应该立即想到雪花！
• 雪花是二进制的 64位（只有 63 位用于填充有符号整数），最终数字一般以十进制序列化

2. 特征

• 全局唯一性：雪花算法可以保证集群系统的ID全局唯一
• 趋势递增：由于强依赖时间戳，所以整体趋势会随着时间递增
• 单调递增（×）：不满足单调递增，在不考虑时间回拨的情况下，虽然在单机中可以保持单调递增，但在分布式集群中无法做到单调递增，只能保证总体趋势递增
• 信息安全指的是ID生成不规则，无法猜测下一个

3. 原理

3.1 格式（64bit）

二进制64位长整型数字：1bit保留 + 41bit时间戳 + 10bit机器 + 12bit序列号

3.2 字节分配

• 1bit不用：因为二进制中最高位是符号位，1表示负数，0表示正数，生成的id一般都是用整数，所以最高位固定为0
• 41bit时间戳：这里采用的就是当前系统的具体时间，单位为毫秒
• 10bit工作机器ID（workerId）：每台机器分配一个id，这样可以标示不同的机器，但是上限为1024，标示一个集群某个业务最多部署的机器个数上限
• 12bit序列号（自增域）：表示在某一毫秒下，这个自增域最大可以分配的bit个数，在当前这种配置下，每一毫秒可以分配2^12 = 4096个数据

二、雪花算法的时间回拨问题

1. 问题描述

简单说就是时间被调整回到了之前的时间，由于雪花算法重度依赖机器的当前时间，所以一旦发生时间回拨，将有可能导致生成的 ID 可能与此前已经生成的某个 ID 重复（前提是刚好在同一毫秒生成 ID 时序列号也刚好一致），这就是雪花算法最经常讨论的问题——时间回拨

2. 现象引发

• 网络时间校准
• 人工设置
• 出现负闰秒（关于闰秒的介绍会在后面讲到）

3. 常见的处理方式

3.1 直接抛出异常

在雪花算法原本的实现中，针对这种问题，算法本身只是返回错误，由应用另行决定处理逻辑，如果是在一个并发不高或者请求量不大的业务系统中，错误等待或者重试的策略问题不大，但是如果是在一个高并发的系统中，这种策略显得过于粗暴

3.2 延迟等待

将当前线程阻塞3ms，之后再获取时间，看时间是否比上一次请求的时间大，如果大了，说明恢复正常了，则不用管如果还小,说明真出问题了，则抛出异常，缺点仍然如3.1所描述

当使用雪花算法出现时间回拨时，不想抛异常，又希望能继续保持全局唯一性、趋势递增、信息安全，可以了解第四点，基于时间序列的方案

三、基于时钟序列解决时间回拨的方案

1. 简介

我这里介绍的是一种基于修改扩展位的思路，基于时钟序列的雪花算法
二进制64位长整型数字：1bit保留 + 41bit时间戳 + 3位时钟序列 + 7bit机器 + 12bit序列号

2. 设计思路

• 如上图，将原本10位的机器码拆分成3位时钟序列及7位机器码
• 发生时间回拨的时候，时间已经发生了变化，那么这时将时钟序列新增1位，重新定义整个雪花Id
• 为了避免实例重启引起时间序列丢失，因此时钟序列最好通过DB/缓存等方式存储起来

3. 算法支持

• 还是支持最长 69 年多的运行时间
• 分布式实例规模由2^{10（1024）降至2}7（128）
• 单实例每毫秒仍然支持 4096次请求
• 每个分布式实例支持最多 2^3（8） 次时间回拨

4. 关键实现代码

.Net Demo 其他语言参考流程自行改造

/// 

/// 获取下一个ID
/// 
/// 
public long NextId()
{lock (_lock){//当前系统时间戳var currentTimestamp = TimeGen();//出现时间回拨 当前系统时间小于最后更新时间if (currentTimestamp < _lastTimestamp){// _clockSequence自增，和CLOCK_SEQUENCE_MASK相与一下，去掉高位_clockSequence = (_clockSequence + 1) & CLOCK_SEQUENCE_MASK;}// 如果上次生成时间和当前时间相同，在同一毫秒内if (_lastTimestamp == currentTimestamp){// sequence自增，和SEQUENCE_MASK相与一下，去掉高位_sequence = (_sequence + 1) & SEQUENCE_MASK;//判断是否溢出,也就是每毫秒内超过1024，当为1024时，与sequenceMask相与，sequence就等于0if (_sequence == 0){//等待到下一毫秒currentTimestamp = TilNextMillis(_lastTimestamp);}}else{//如果和上次生成时间不同,重置sequence，就是下一毫秒开始，sequence计数重新从0开始累加,_sequence = 0;}_lastTimestamp = currentTimestamp;return ((currentTimestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | _clockSequence << CLOCK_SEQUENCE_SHIFT | (WorkerId << WORKER_ID_SHIFT) | _sequence;}
}

‘

四、关于雪花算法的常见问题解答

1. 雪花算法支持的并发数最大多少？

• 这个是由序列号的位数决定的，原生雪花算法序列号12位，也就是1毫秒最大可生成2^12（4096），相当于1秒可生成 4096 * 1000 个ID，也就是QPS可以到 409.6 w/s

2. 雪花算法支持最多支持系统运行多少年？

• 这个是由时间戳位数决定的，原生雪花算法时间戳占41位，也就是支持最大的时间戳为2^41（2199023255552），而1年的总毫秒数为3600 * 1000 * 24 * 365 = 31,536,000,000，因此2^41 / 1年的总毫秒数≈69.7年

• 其实衍生出另一个问题，41位能表示的最大的时间戳为2^41（2199023255552）对应的时间应该是2039-09-07 23:47:35，距离现在只有不到20年的时间，为什么算出来的是69年呢？

• 其实时间戳的算法是1970年1月1日到指点时间所经过的毫秒或秒数，那咱们把开始时间从2021年开始，就可以延长41位时间戳能表达的最大时间，所以这里实际指的是相对自定义开始时间的时间戳

3. 用了雪花Id，出现负闰秒为什么会导致系统大量抛异常？

• 闰秒是偶尔运用于协调世界时（UTC）的调整，经由增加或减少一秒，以消弥精确的时间（使用原子钟测量）和不精确的观测太阳时（称为UT1)，之间的差异
• 这种做法已被证明具有破坏性，特别是在二十一世纪，尤其是在依赖精确时间戳或时间关键程序控制的服务中
• 而雪花算法严重依赖时间戳，当出现负闰秒也就是时间减少一秒时（时间往前回拨1秒），雪花Id就可能出现重复，而原生的雪花算法出现时间回拨的处理方式是直接抛异常
• 2022年11月，在第27届国际计量大会上，科学家和政府代表投票决定到2035年取消闰秒