📣读完这篇文章里你能收获到
图文形式为你讲解原生雪花算法的特征及原理
了解时间回拨的概念以及可能引起发此现象的操作
掌握时间回拨的解决方案—基于时钟序列的雪花算法
关于雪花算法的常见问题解答
文章目录
一、原生的雪花算法
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. 简介
我这里介绍的是一种基于修改扩展位的思路，基于时钟序列的雪花算法
2. 设计思路
如上图，将原本10位的机器码拆分成3位时钟序列及7位机器码
发生时间回拨的时候，时间已经发生了变化，那么这时将时钟序列新增1位，重新定义整个雪花Id
为了避免实例重启引起时间序列丢失，因此时钟序列最好通过DB/缓存等方式存储起来
3. 算法支持
还是支持最长 69 年多的运行时间
分布式实例规模由210（1024）降至27（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年取消闰秒