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

一般来说,除了“全局唯一”这个基本属性之外,还会要求生成出来的 ID 具有“递增趋势”,这样的好处是能减少 MySQL 数据页分裂的情况,从而减少数据库的 IO 压力,提升服务的性能。

雪花算法,就是一个能生产全局唯一、递增趋势、高性能的分布式 ID 生成算法。

标准版存在的问题

时钟回拨

因为在雪花算法中,由于要生成单调递增的 ID,因此它利用了时间的单调递增性,所以是强依赖于系统时间的。

如果系统时间出现了回拨,那么生成的 ID 就可能会重复。

系统的时间漂移是一个在毫秒级别的极短的时间。

所以可以在获取 ID 的时候,记录一下当前的时间戳。然后在下一次过来获取的时候,对比一下当前时间戳和上次记录的时间戳,如果发现当前时间戳小于上次记录的时间戳,所以出现了时钟回拨现象,对外抛出异常,本次 ID 获取失败。

理论上当前时间戳会很快的追赶上上次记录的时间戳。

但是,你可能也注意到了,“对外抛出异常,本次 ID 获取失败”,意味着这段时间内你的服务对外是不可使用的。

比如,你的订单号中的某个部分是由这个 ID 组成的,此时由于 ID 生成不了,你的订单号就生成不了,从而导致下单失败。

再比如,在 Seata 里面,如果是使用数据库作为 TC 集群的存储工具,那么这段时间内该 TC 就是处于不可用状态。

简单的理解为:基础组件的错误导致服务不可用

突发性能有上限

标准版雪花算法宣称的 QPS 很大,约 400w/s,但严格来说这算耍了个文字游戏~ 因为算法的时间戳单位是毫秒,而分配给序列号的位长度为 12,即每毫秒 4096 个序列空间。 所以更准确的描述应该是 4096/ms。400w/s 与 4096/ms 的区别在于前者不要求每一毫秒的并发都必须低于 4096 (也许有些毫秒会高于 4096,有些则低于)。Seata 亦遵循此限制,若当前时间戳的序列空间已耗尽,会自旋等待下一个时间戳。

Seata 改良思路

http://seata.io/zh-cn/blog/seata-snowflake-explain.html

改进的核心思想是解除与操作系统时间戳的时刻绑定,生成器只在初始化时获取了系统当前的时间戳,作为初始时间戳, 但之后就不再与系统时间戳保持同步了。它之后的递增,只由序列号的递增来驱动。比如序列号当前值是 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 就会重复:

  • 192.168.4.10
  • 192.168.8.10

即只要 IP 的第 4 个字节和第 3 个字节的低 2 位一样就会重复。 新版的策略改为优先从本机网卡的 MAC 地址截取低 10位,若本机未配置有效的网卡,则在[0, 1023]中随机挑一个作为节点 ID。 这样调整后似乎没有新版的用户再报同样的问题了(当然,有待时间的检验,不管怎样,不会比 IP 截取策略更糟糕)。

以上就是对 Seata 的分布式 UUID 生成器的简析,如果您喜欢这个生成器,也可以直接在您的项目里使用它, 它的类声明是 public 的,完整类名为: io.seata.common.util.IdWorker文章来源地址https://www.uudwc.com/A/Oq4YG/

原文地址:https://blog.csdn.net/aoshilang2249/article/details/133171566

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年10月09日 08:46
下一篇 2023年10月09日 09:46