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

title: Seata基于改良版雪花算法的分布式UUID生成器分析
author: selfishlover
keywords: [Seata, snowflake, UUID]
date: 2021/05/08

本文来自 Apache Seata官方文档，欢迎访问官网，查看更多深度文章。

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

Seata内置了一个分布式UUID生成器，用于辅助生成全局事务ID和分支事务ID。我们希望该生成器具有如下特点：

高性能
全局唯一
趋势递增

高性能不必多言。全局唯一很重要，否则不同的全局事务/分支事务会混淆在一起。
此外，趋势递增对于使用数据库作为TC集群的存储工具的用户而言，能降低数据页分裂的频率，从而减少数据库的IO压力
(branch_table表以分支事务ID作为主键)。

在老版Seata(1.4以前)，该生成器的实现基于标准版的雪花算法。标准版雪花算法网上已经有很多解读文章了，此处就不再赘述了。
尚未了解的同学可以先看看网上的相关资料，再来看此文章。
此处我们谈谈标准版雪花算法的几个缺点：

时钟敏感。因为ID生成总是和当前操作系统的时间戳绑定的(利用了时间的单调递增性)，因此若操作系统的时钟出现回拨，
生成的ID就会重复(一般而言不会人为地去回拨时钟，但服务器会有偶发的"时钟漂移"现象)。
对于此问题，Seata的解决策略是记录上一次的时间戳，若发现当前时间戳小于记录值(意味着出现了时钟回拨)，则拒绝服务，
等待时间戳追上记录值。但这也意味着这段时间内该TC将处于不可用状态。
突发性能有上限。标准版雪花算法宣称的QPS很大，约400w/s，但严格来说这算耍了个文字游戏~
因为算法的时间戳单位是毫秒，而分配给序列号的位长度为12，即每毫秒4096个序列空间。
所以更准确的描述应该是4096/ms。400w/s与4096/ms的区别在于前者不要求每一毫秒的并发都必须低于4096
(也许有些毫秒会高于4096，有些则低于)。Seata亦遵循此限制，若当前时间戳的序列空间已耗尽，会自旋等待下一个时间戳。

在较新的版本上(1.4之后)，该生成器针对原算法进行了一定的优化改良，很好地解决了上述的2个问题。
改进的核心思想是解除与操作系统时间戳的时刻绑定，生成器只在初始化时获取了系统当前的时间戳，作为初始时间戳，
但之后就不再与系统时间戳保持同步了。它之后的递增，只由序列号的递增来驱动。比如序列号当前值是4095，下一个请求进来，
序列号+1溢出12位空间，序列号重新归零，而溢出的进位则加到时间戳上，从而让时间戳+1。
至此，时间戳和序列号实际可视为一个整体了。实际上我们也是这样做的，为了方便这种溢出进位，我们调整了64位ID的位分配策略，
由原版的：
在这里插入图片描述

改成(即时间戳和节点ID换个位置)：
在这里插入图片描述

这样时间戳和序列号在内存上是连在一块的，在实现上就很容易用一个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;

那么在生产ID时就很简单了：

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

至此，我们可以发现：

生成器不再有4096/ms的突发性能限制了。倘若某个时间戳的序列号空间耗尽，它会直接推进到下一个时间戳，
"借用"下一个时间戳的序列号空间(不必担心这种"超前消费"会造成严重后果，下面会阐述理由)。
生成器弱依赖于操作系统时钟。在运行期间，生成器不受时钟回拨的影响(无论是人为回拨还是机器的时钟漂移)，
因为生成器仅在启动时获取了一遍系统时钟，之后两者不再保持同步。
唯一可能产生重复ID的只有在重启时的大幅度时钟回拨(人为刻意回拨或者修改操作系统时区，如北京时间改为伦敦时间~
机器时钟漂移基本是毫秒级的，不会有这么大的幅度)。
持续不断的"超前消费"会不会使得生成器内的时间戳大大超前于系统的时间戳，从而在重启时造成ID重复？
理论上如此，但实际几乎不可能。要达到这种效果，意味该生成器接收的QPS得持续稳定在400w/s之上~
说实话，TC也扛不住这么高的流量，所以说呢，天塌下来有个子高的先扛着，瓶颈一定不在生成器这里。

此外，我们还调整了下节点ID的生成策略。原版在用户未手动指定节点ID时，会截取本地IPv4地址的低10位作为节点ID。
在实践生产中，发现有零散的节点ID重复的现象(多为采用k8s部署的用户)。例如这样的IP就会重复：