经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
在开源项目中看到一个改良版的雪花算法,现在它是你的了。
来源:cnblogs  作者:why技术  时间:2023/8/9 9:15:53  对本文有异议

你好呀,我是歪歪。

在 Seata 的官网上看到一篇叫做“关于新版雪花算法的答疑”的文章。

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

看明白之后,我觉得还是有点意思的,结合自己的理解和代码,加上画几张图,给你拆解一下 Seata 里面的“改良版雪花算法”。

虽然是在 Seata 里面看到的,但是本篇文章的内容和 Seata 框架没有太多关系,反而和数据库的基础知识有关。

所以,即使你不了解 Seata 框架,也不影响你阅读。

当你理解了这个类的工作原理之后,你完全可以把这个只有 100 多行的类搬运到你的项目里面,然后就变成你的了。

你懂我意思吧。

先说问题

如果你的项目中涉及到需要一个全局唯一的流水号,比如订单号、流水号之类的,又或者在分库分表的情况下,需要一个全局唯一的主键 ID 的时候,就需要一个算法能生成出这样“全局唯一”的数据。

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

此外,在当前的市场环境下,不管你是啥服务,张口就是高并发,我们也会要求这个算法必须得是“高性能”的。

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

关于雪花算法的解析,网上相关的文章比雪花还多,我这里就不展开了,这个玩意,应该是“面试八股文”中重点考察模块,分布式领域中的高频考题之一,如果是你的盲区的话,赶紧去了解一下。

比如一个经典的面试题就是:雪花算法最大的缺点是什么?

背过题的小伙伴应该能立马答出来:时钟敏感。

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

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

而“时间回拨”这个现象,是有可能出现的,不管是人为的还是非人为的。

当你回答出这个问题之后,面试官一般会问一句:那如果真的出现了这种情况,应该怎么办呢?

很简单,正常来说只要不是不是有人手贱或者出于泄愤的目的进行干扰,系统的时间漂移是一个在毫秒级别的极短的时间。

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

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

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

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

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

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

再看代码

基于前面说的问题,Seata 才提出了“改良版雪花算法”。

http://seata.io/zh-cn/blog/seata-analysis-UUID-generator.html

在介绍改良版之前,我们先把 Seata 的源码拉下来,瞅一眼。

在源码中,有一个叫做 IdWorker 的类:

io.seata.common.util.IdWorker

我带你看一下它的提交记录:

2020 年 5 月 4 日第一次提交,从提交时的信息可以看出来,这是把分布式 ID 的生成策略修改为 snowflake,即雪花算法。

同时我们也能在代码中找到前面提到的“对外抛出异常,本次 ID 获取失败”相关代码,即 nextId 方法,它的比较方式就是用当前时间戳和上次获取到的时间戳做对比:

io.seata.common.util.IdWorker#nextId

这个类的最后一次提交是 2020 年 12 月 15 日:

这一次提交对于 IdWorker 这个类进行了大刀阔斧的改进,可以看到变化的部分非常的多:

我们重点关注刚刚提到的 nextId 方法:

整个方法从代码行数上来看都可以直观的看到变化,至少没有看到抛出异常了。

这段代码到底是怎么起作用的呢?

首先,我们得理解 Seata 的改良思路,搞明白思路了,再说代码就好理解一点。

在前面提到的文章中 Seata 也说明了它的核心思路,我带着你一起过一下:

原版的雪花算法 64 位 ID 是分配这样的:

可以看到,时间戳是在最前面的,因为雪花算法利用了时间的单调递增的特性。

所以,如果前面的时间戳一旦出现“回退”的情况,即打破了“时间的单调递增”这个前提条件,也就打破了它的底层设计。

它能怎么办?

它只能给你抛出异常,开始摆烂了。

然后我主要给你解释一下里面的节点 ID 这个玩意。

节点 ID 可以理解为分布式应用中的一个服务,一个服务的节点 ID 是固定的。

可以看到节点 ID 长度为二进制的 10 位,也就是说最多可以服务于 1024 台机器,所以你看 Seata 最开始提交的版本里面,有一个在 1024 里面随机的动作。

因为算法规定了,节点 ID 最多就是 2 的 10 次方,所以这里的 1024 这个值就是这样来的:

包括后面有大佬觉得用这个随机算法一点都不优雅,就把这部分改成了基于 IP 去获取:

看起来有点复杂,但是我们仔细去分析最后一行:

return ((ipAddressByteArray[ipAddressByteArray.length - 2] & 0B11) << Byte.SIZE) + (ipAddressByteArray[ipAddressByteArray.length - 1] & 0xFF);

变量 & 0B11 运算之后的最大值就是 0B11 即 3。

Byte.SIZE = 8。

所以,3 << 8,对应二进制 1100000000,对应十进制 768。

变量 & 0xFF 运算之后的最大值就是 0xFF 即 255。

768+255=1023,取值范围都还是在 [0,1023] 之间。

然后你再看现在最新的算法里面,官方的老哥们认为获取 IP 的方式不够好:

所以又把这个地方从使用 IP 地址改成了获取 Mac 地址。

最后一行是这样的:

return ((mac[4] & 0B11) << 8) | (mac[5] & 0xFF);

还是我刚刚说的 0B11 << 8 和 0xFF。

那么理论上的最大值就是 768 | 255 ,算出来还是 1023。

所以不管你怎么玩出花儿来,这个地方搞出来的数的取值范围就只能是 [0,1023] 之间。

别问,问就是规定里面说了,算法里面只给节点 ID 留了 10 位长度。

最后,就是这个 12 位长度的序列号了:

这个玩意没啥说的,就是一个单纯的、递增的序列号而已。

既然 Seata 号称是改良版,那么具体体现在什么地方呢?

简单到你无法想象:

是的,仅仅是把时间戳和节点 ID 换个位置就搞定了。

然后每个节点的时间戳是在 IdWorker 初始化的时候就设置完成了,具体体现到代码上是这样的:

io.seata.common.util.IdWorker#initTimestampAndSequence

主要看第一行:

long timestamp = getNewestTimestamp();

可以看到在 getNewestTimestamp 方法里面获取了一次当前时间,然后减去了一个 twepoch 变量。

twepoch 是什么玩意?

是 2020-05-03 的时间戳。

至于为什么是这个时间,我想作者应该是在 2020 年 5 月 3 日写下的关于 IdWorker 的第一行代码,所以这个日期是 IdWorker 的生日。

作者原本完全可以按照一般程序员的习惯,写 2020 年 1 月 1 日的,但是说真的,这个日期到底是 2020-01-01 还是 2020-05-03 对于框架来说完全不重要,所以还不如给它赋予一个特殊的日期。

他真的,我哭死...

那么为什么要用当前时间戳减去 twepoch 时间戳呢?

你想,如果仅仅用 41 位来表示时间戳,那么时间戳的最大值就是 2 的 41 次方,转化为十进制是这么多 ms:

然后再转化为时间:

也就是说,在雪花算法里面,41 位时间戳最大可以表示的时间是 2039-09-07 23:47:35。

算起来也没几年了。

但是,当我们减去 2020-05-03 的时间戳之后,计算的起点不一样了,这一下,咔咔的,就能多用好多年。

twepoch 就是这么个用途。

然后,我们回到这一行代码:

前一行,我们把 41 位的时间戳算好了,按照 Seata 的设计,时间戳之后就是 12 位的序列号了呀:

所以这里就是把时间戳左移 12 位,好把序列号的位置给腾出来。

最后,算出来的值,就是当前这个节点的初始值,即 timestampAndSequence。

所以,你看这个 AtomicLong 类型的变量的名字取的,叫做 timestampAndSequence。

timestamp 和 Sequence,一个字段代表了两个含义,多贴切。

Long 类型转化为二进制一共 64 位,前 11 位不使用,中间的 41 位代表时间戳,最后的 12 位代表序列号,一个字段,两个含义。

程序里面使用的时候也是在一起使用,用 Long 来存储,在内存里面也是放在一块的:

优雅,实在优雅。

上一次看到这么优雅的代码,还是线程池里面的 ctl 变量:

现在 timestampWithSequence 已经就位了,那么获取下一 ID 的时候是怎么搞的呢?

看一下 nextId 方法:

io.seata.common.util.IdWorker#nextId

标号为 ① 的地方是基于 timestampWithSequence 进行递增,即 +1 操作。

标号为 ② 的地方是截取低 53 位,也就是 41 位的时间戳和 12 位的序列号。

标号为 ③ 的地方就是把高 11 位替换为前面说过的值在 [0,1023] 之间的 workerId。

好,现在你再仔细的想想,在前面描述的获取 ID 的过程中,是不是只有在初始化的时候获取过一次系统时间,之后和它就再也没有关系了?

所以,Seata 的分布式 ID 生成器,不再依赖于时间。

然后,你再想想另外一个问题:

由于序列号只有 12 位,它的取值范围就是 [0,4095]。

如果我们序列号就是生成到了 4096 导致溢出了,怎么办呢?

很简单,序列号重新归 0,溢出的这一位加到时间戳上,让时间戳 +1。

那你再进一步想想,如果让时间戳 +1 了,那么岂不是会导致一种“超前消费”的情况出现,导致时间戳和系统时间不一致了?

朋友,慌啥啊,不一致就不一致呗,反正我们现在也不依赖于系统时间了。

然后,你想想,如果出现“超前消费”,意味着什么?

意味着在当前这个毫秒下,4096 个序列号不够用了。

4096/ms,约 400w/s。

你啥场景啊,怎么牛逼?

(哦,原来是面试场景啊,那懂了~)

另外,官网还抛出了另外一个问题:这样持续不断的"超前消费"会不会使得生成器内的时间戳大大超前于系统的时间戳,从而在重启时造成 ID 重复?

你想想,理论上确实是有可能的。假设我时间戳都“超前消费”到一个月以后了。

那么在这期间,你服务发生重启时我会重新获取一次系统时间戳,导致出现“时间回溯”的情况。

理论上确实有可能。

但是实际上...

看看官方的回复:

别问,问就是不可能,就算出现了,最先崩的也不是我这个地方。

好,到这里,我终于算是铺垫完成了,前面的东西就算从你脑中穿脑而过了,你啥都记不住的话,你就抓住这个图,就完事了:

现在,你再仔细的看这个图,我问你一个问题:

改良版的算法是单调递增的吗?

在单节点里面,它肯定是单调递增的,但是如果是多个节点呢?

在多个节点的情况下,单独看某个节点的 ID 是单调递增的,但是多个节点下并不是全局单调递增。

因为节点 ID 在时间戳之前,所以节点 ID 大的,生成的 ID 一定大于节点 ID 小的,不管时间上谁先谁后。

这一点我们也可以通过代码验证一下,代码的意思是三个节点,每个节点各自生成 5 个 ID:

从输出来看,一眼望去,生成的 ID 似乎是乱序的,至少在全局的角度下,肯定不是单调递增的:

但是我们把输出按照节点 ID 进行排序,就变成了这样,单节点内严格按照单调递增,没毛病:

而在原版的雪花算法中,时间戳在高位,并且始终以系统时钟为准,每次生成的时候都会严格和系统时间进行对比,确保没有发生时间回溯,这样可以保证早生成的 ID 一定小于晚生成的 ID ,只有当 2 个节点恰好在同一时间戳生成 ID 时,2 个 ID 的大小才由节点 ID 决定。

这样看来,Seata 的改进算法是不是错的?

好,我再说一次,前面的所有的内容都是铺垫,就是为了引出这个问题,现在问题抛出来了,你得读懂并理解这个问题,然后再继续往下看。

分析一波

分析之前,先抛出官方的回答:

我先来一个八股文热身:请问为什么不建议使用 UUID 作为数据库的主键 ID ?

就是为了避免触发 MySQL 的页分裂从而影响服务性能嘛。

比如当前主键索引的情况是这样的:

如果来了一个 433,那么直接追加在当前最后一个记录 432 之后即可。

但是如果我们要插入一个 20 怎么办呢?

那么数据页 10 里面已经放满了数据,所以会触发页分裂,变成这样:

进而导致上层数据页的分裂,最终变成这样的一个东西:

上面的我们可以看出页分裂伴随着数据移动,所以我们应该尽量避免。

理想的情况下,应该是把一页数据塞满之后,再新建另外一个数据页,这样 B+ tree 的最底层的双向链表永远是尾部增长,不会出现上面画图的那种情况:在中间的某个节点发生分裂。

那么 Seata 的改良版的雪花算法在不具备“全局的单调递增性”的情况下,是怎么达到减少数据库的页分裂的目的的呢?

我们还是假设有三个节点,我用 A,B,C 代替,在数值上 A < B < C,采用的是改良版的雪花算法,在初始化的情况下是这样的。

假设此时,A 节点申请了一个流水号,那么基于前面的分析,它一定是排在 A-seq1 之后,B-seq1 之前的。

但是这个时候数据页里面的数据满了,怎么办?

分裂呗:

又来了 A-seq3 怎么办?

问题不大,还放的下:

好,这个时候数据页 7 满了,但是又来了 A-seq4,怎么办?

只有继续分裂了:

看到这个分裂的时候,你有没有嗦出一丝味道,是不是有点意思了?

因为在节点 A 上生成的任何 ID 都一定小于在节点 B 上生成的任何 ID,节点 B 和节点 C 同理。

在这个范围内,所有的 ID 都是单调递增的:

而这样的范围最多有多少个?

是不是有多少个节点,就有多少个?

那么最多有多少个节点?

2 的 10 次方,1024 个节点。

所以官方的文章中有这样的一句话:

新版算法从全局角度来看,ID 是无序的,但对于每一个 workerId,它生成的 ID 都是严格单调递增的,又因为 workerId 是有限的,所以最多可划分出 1024 个子序列,每个子序列都是单调递增的。

经过前面的分析,每个子序列总是单调递增的,所以每个子序列在有限次的分裂之后,最终都会达到稳态。

或者用一个数学上的说法:该算法是收敛的。

再或者,我给你画个图:

我画的时候尽力了,至于你看懂看不懂的,就看天意了。

如果看不懂的话,自信一点,不要怀疑自己,就是我画的不好。大胆的说出来:什么玩意?这画的都是些啥,看求不懂。呸,垃圾作者。

页分裂

前面写的所有内容,你都能在官网上我前面提到的两个文章中找到对应的部分。

但是关于页分裂部分,官方并没有进行详细说明。本来也是这样的,人家只是给你说自己的算法,没有必要延伸的太远。

既然都说到页分裂了,那我来补充一个我在学习的时候看到的一个有意思的地方。

也就是这个链接,这一节的内容就是来源于这个链接中:

http://mysql.taobao.org/monthly/2021/06/05/

还是先搞个图:

问,在上面的这个 B+ tree 中,如果我要插入 9,应该怎么办?

因为数据页中已经没有位置了,所以肯定要触发页分裂。

会变成这样:

这种页分裂方式叫做插入点(insert point)分裂。

其实在 InnoDB 中最常用的是另外一种分裂方式,中间点(mid point)分裂。

如果采用中间点(mid point)分裂,上面的图就会变成这样:

即把将原数据页面中的 50% 数据移动到新页面,这种才是普遍的分裂方法。

这种分裂方法使两个数据页的空闲率都是 50%,如果之后的数据在这两个数据页上的插入是随机的话,那么就可以很好地利用空闲空间。

但是,如果后续数据插入不是随机,而是递增的呢?

比如我插入 10 和 11。

插入 10 之后是这样的:

插入 11 的时候又要分页了,采用中间点(mid point)分裂就变成了这样:

你看,如果是在递增的情况下,采用中间点(mid point)分裂,数据页 8 和 20 的空间利用率只有 50%。

因为数据的填充和分裂的永远是右侧页面,左侧页面的利用率只有 50%。

所以,插入点(insert point)分裂是为了优化中间点(mid point)分裂的问题而产生的。

InnoDB 在每个数据页上专门有一个叫做 PAGE_LAST_INSERT 的字段,记录了上次插入位置,用来判断当前插入是是否是递增或者是递减的。

如果是递减的,数据页则会向左分裂,然后移动上一页的部分数据过去。

如果判定为递增插入,就在当前点进行插入点分裂。

比如还是这个图:

上次插入的是记录 8,本次插入 9,判断为递增插入,所以采用插入点分裂,所以才有了上面这个图片。

好,那么问题就来了,请听题:

假设出现了这种情况,阁下又该如何应对?

在上面这个图的情况下,我要插入 10 和 9:

当插入 10 的时候,按 InnoDB 遍历 B+ tree 的方法会定位到记录 8,此时这个页面的 PAGE_LAST_INSERT 还是 8。所以会被判断为递增插入,在插入点分裂:

同理插入 9 也是这样的:

最终导致 9、10、11 都独自占据一个 page,空间利用率极低。

问题的根本原因在于每次都定位到记录 8(end of page),并且都判定为递增模式。

哦豁,你说这怎么办?

答案就藏在这一节开始的时候我提到的链接中:

前面我画的所有的图都是在没有并发的情况下展开的。

但是在这个部分里面,牵扯到了更为复杂的并发操作,同时也侧面解释了为什么 InnoDB 在同一时刻只能有有一个结构调整(SMO)进行。

这里面学问就大了去了,有兴趣的可以去了解一下 InnoDB 在 B+ tree 并发控制上的限制,然后再看看 Polar index 的破局之道。

反正我是学不动了。

哦,对了。前面说了这么多,还只是聊了页分裂的情况。

有分裂,就肯定有合并。

那么什么时候会触发页合并呢?

页合并会对我们前面探讨的 Seata 的改良版雪花算法带来什么影响呢?

别问了,别问了,学不动了,学不动了。

自己看一下吧:

最后,如果本文对你有一点点帮助的话,点个免费的赞,求个关注,不过分吧?

原文链接:https://www.cnblogs.com/thisiswhy/p/17611163.html

 友情链接:直通硅谷  直通硅谷 怎么样 mac软件下载