多时钟解决雪花算法的时间回拨问题

分布式 ID 生成算法用于在分布式系统中生成全局唯一的 ID 标识，而 twitter 提出的雪花算法便是其中一种知名的算法，其每次会生成一个 64 位的全局唯一整数，算法的基本思想非常巧妙：

    0        1010......101     1010101010     101010101010
   \_/       \___________/     \________/     \__________/
第1位不使用    41位毫秒时间戳      10位机器ID       12位序列号

除了开头的第 1 位不使用，接下来的 41 位时间戳是从指定的起始时间到当前时间所经历的毫秒数，比如设定系统起始时间为 2022 年 3 月 15 日 0 点整，则在 2022 年 4 月 1 日中午 12:00:00.123 时，此时间戳的值应该为 1,512,000,123，整个时间戳片段，支持最多 69.7 年，这显然也超出了绝大多数 IT 系统的存活年限。

而 10 位机器 ID，对应最多容纳一个 1024 个 ID 生成器实例的分布式集群，12 位序列号从 0 到 4095 周而复始连续递增，可以支持单个实例每毫秒 4096 次 ID 生成请求，意味着整个 ID 生成器实例的集群，理论上每毫秒便可以支持最多 4194304 个 ID 生成，效率非常高。

雪花算法生成的 ID 的全局唯一的理论基础是全局唯一性与单实例唯一性的结合，全局唯一性由唯一的机器 ID 保证，不同的机器ID保证不同实例生成的 ID 必然不会一致，而单实例唯一由同一毫秒结合不同的序列号来保证，这里的序列号只能做到理论上限，即理论上一毫秒内不会有超过 4096 次的请求。

雪花算法的时间回拨问题

时间回拨问题是指系统在运行过程中，可能由于网络时间校准或者人工设置，导致系统时间主动或被动地跳回到过去的某个时间：

由于雪花算法重度依赖机器的当前时间，所以一旦发生时间回拨，将有可能导致生成的 ID 可能与此前已经生成的某个 ID 重复（前提是刚好在同一毫秒生成 ID 时序列号也刚好一致），这就是雪花算法最经常讨论的问题——时间回拨。在雪花算法原本的实现中，针对这种问题，算法本身只是返回错误，由应用另行决定处理逻辑，如果是在一个并发不高或者请求量不大的业务系统中，错误等待或者重试的策略问题不大，但是如果是在一个高并发的系统中，这种策略显得过于粗暴。

解决雪花算法的时间回拨问题的一种思路——多时钟

网上有很多对于解决雪花算法的时间回拨问题的思路和讨论，我这里介绍的是一种基于扩展位的思路，但是为了便于理解，我自己取名为多时钟的雪花算法。

算法的思路也比较简单，既然时间回拨问题的本质上是时间回到了“过去”，那么哪怕回到了过去，只要实现“此时间非彼时间”不就实现时间唯一了？顺着这个思路想的话，一种直观的思路是：既然我已经发现了时间回拨，那我就认为原先的“时钟”已经不可用，使用一个新的“时钟”即可，并将新的当前时间仍为是新时钟的时间。

算法描述

类似经典的雪花算法，基于多时钟改进的雪花算法需要占用少量的位用于存储时钟 ID，所需的位数只能从原有的时间戳、机器ID或者序列号中分割，具体业务实现中需要结合业务的并发量、集群规模等综合考虑，这里为了讨论方便，假设从机器 ID 以及序列号中各取 2 位，用于 1 个 4 位的时钟 ID：

    0       1010......101    0001     10101010   1010101010
   \_/      \___________/    \__/     \______/   \________/
第1位不使用   41位毫秒时间戳   4位时钟ID   8位机器ID   10位序列号

于是，新的算法理论上：

还是支持最长 69 年多的运行时间；
分布式实例规模缩小到 256；
单实例每毫秒支持最多 1024 次请求；
单实例支持最多 16 次回拨同一时间范围（如果时间回拨发生在互不交叠的时间段，则理论上可以完美解决时间回拨问题）；

在具体的实现逻辑上，主要是在每次发现时间回拨（即之前最后一次生成 ID 的时间戳小于等于当前时间戳）的时候，便将时钟 ID 加 1，类似序列号，周而复始。

timeNow := 当前系统时间
if last_time >= timeNow:  // 时钟回拨
	clock_id = (clock_id + 1) & (1<<4-1)
last_time = timeNow
seq := 下一个序列号
return encode(timeNow, machineID, seq, clock_id)

场景分析

还是上面图片中的例子，假如在某一时刻，系统生成 ID，此时时间为 10:15:00，之后系统经历 5 秒后，在另一时刻 10:15:05，系统再次生成 ID，在这段时间里，系统一直使用的时钟为 1。在下一次生成 ID 时，系统发现 lastTime 为 10:15:05，而系统查询机器当前时间为 10:15:00，判定时间回拨，于是切换时钟为 2，此时生成的 ID 即会对应于 2 号时钟的 10:15:00，与此前时钟 1 的 10:15:00 在逻辑上已经是两个不同的时间，于是生成的 ID 自然不同。

极端场景：进程重启+时间回拨

上面的算法，能够很好应对运行过程中的时间回拨问题，但是如果非常不巧，在进程刚好遇到崩溃重启的过程中，系统又正好完成了时间回拨，这个时候，如何保证不会因为使用了相同的时钟而可能产生一样的 ID 呢？一种继续改进的思路是在 ID 生成器初始化的时候，尝试从本地磁盘文件中获取重启前的时钟 ID，并且加 1，意味着每次重启一定不会使用进程退出前的时钟，而在运行过程中，每次切换了时钟之后，都应该把新的时钟 ID 写入磁盘，考虑到性能友好，这个操作尽可能异步完成。

高并发优化思路：时钟 ID 复用

这个基于多时钟的优化算法，由于需要额外的比特位来存储时钟 ID，而占用了用于控制并发的序列号的比特位，假如系统确实有较高的并发，这里可以考虑的优化是复用时钟 ID：每次在当前时钟下，一旦当前序列号达到上限重置时，都切换到下一个时钟，这样的话，理论上同一毫秒里，并发规模可以达到 2^14，也即是 16384。大多数情况下，时钟回拨应该是个极少发生的现象，这种复用时钟 ID 的方法，能够更充分地利用好时钟 ID 的 4 个比特位。

多时钟雪花算法的一些问题

当然，这个算法并不完美的，它基于一些假设，同时使用前需要认真考虑一些它仍无法避免的问题：

时间回拨不会频繁发生在同一个时间段（在上面举例中，时间回拨不会在同一时间段上重复发生超过 16 次）；
递增问题：当时间回拨时，ID 递增性会被破坏，对于需要严格递增的场景，需要考虑其他解决方案，比如基于“历史时间”的改进算法；
机器ID和序列号空间的评估：如何保证获得全局唯一的机器 ID，也是一个复杂的问题，另外时钟 ID 的引入，会占用额外的比特位，需要综合考虑从哪些比特片段中腾出这些需要留给时钟 ID 的比特位；
多时钟雪花算法只是缓解了时钟回拨问题，但是不能完全解决时间回拨问题，所以仍然需要考虑一种极端情况下的容错方案，不过既然是极端场景，采用类似错误重试之类的简单方案足矣。

解决雪花算法时间回拨问题的其他思路

采用历史时间：详见彻底解决雪花算法时间回拨问题新方案
等待时钟校正
时间追赶
错误重试

总结

通过引入多时钟来实现时间回拨场景下的时间唯一性，理想场景下可无限次应对时间回拨
多时钟雪花算法可以通过复用时钟ID来优化比特位的利用效率
多时钟雪花算法也需要结合其他容错处理来应对极端场景下的时间回拨问题