这是一篇由 Seata 的官网上一篇叫做“关于新版雪花算法的答疑”的文章引发的考虑。
seata.io/zh-cn/blog/…
仍是有点意思的，结合自己的了解和代码，加上画几张图来拆解一下 Seata 里边的“改善版雪花算法”。
虽然是在 Seata 里边看到的，可是本篇文章的内容和 Seata 结构没有太多关系，反而和数据库的基础知识有关。
所以，即便你不了解 Seata 结构，也不影响你阅览。
当你了解了这个类的工作原理之后，你完全能够把这个只要 100 多行的类转移到你的项目里边，然后就变成你的了。
dddd（懂的都懂）！
先说问题
雪花算法的运用场景：
假如你的项目中涉及到需求一个大局仅有的流水号，比方订单号、流水号之类的，又或许在分库分表的状况下，需求一个大局仅有的主键 ID 的时分，就需求一个算法能生成出这样“大局仅有”的数据。
一般来说，咱们除了“大局仅有”这个基本属性之外，还会要求生成出来的 ID 具有“递加趋势”，这样的优点是能减少 MySQL 数据页割裂的状况，然后减少数据库的 IO 压力，提升服务的性能。
此外，在当时的市场环境下，不论你是啥服务，张口便是高并发，咱们也会要求这个算法必须得是“高性能”的。
雪花算法，便是一个能生产大局仅有的、递加趋势的、高性能的分布式 ID 生成算法。
关于雪花算法的解析，网上相关的文章比雪花还多，这个玩意，应该是“面试八股文”中要点调查模块，分布式领域中的高频考题之一，假如是你的盲区的话，可自行去了解一下。
比方一个经典的面试题便是：
雪花算法最大的缺点是什么？
背过题的小伙伴应该能立马答出来：时钟敏感。
由于在雪花算法中，由于要生成单调递加的 ID，因而它利用了时刻的单调递加性，所以是强依赖于体系时刻的。
假如体系时刻呈现了回拨，那么生成的 ID 就或许会重复。
而“时刻回拨”这个现象，是有或许呈现的，不论是人为的仍是非人为的。
当你回答出这个问题之后，面试官一般会问一句：
那假如真的呈现了这种状况，应该怎样办呢？
很简略，正常来说只要不是不是有人手贱或许出于泄愤的意图进行干扰，体系的时刻漂移是一个在毫秒等级的极短的时刻。
所以能够在获取 ID 的时分，记载一下当时的时刻戳。然后在下一次过来获取的时分，比照一下当时时刻戳和前次记载的时刻戳，假如发现当时时刻戳小于前次记载的时刻戳，所以呈现了时钟回拨现象，对外抛出反常，本次 ID 获取失利。
理论上当时时刻戳会很快的追赶上前次记载的时刻戳。
可是，你或许也留意到了，“对外抛出反常，本次 ID 获取失利”，意味着这段时刻内你的服务对外是不行运用的。
比方，你的订单号中的某个部分是由这个 ID 组成的，此刻由于 ID 生成不了，你的订单号就生成不了，然后导致下单失利。
再比方，在 Seata 里边，假如是运用数据库作为 TC 集群的存储工具，那么这段时刻内该 TC 便是处于不行用状况。
你能够简略的了解为：基础组件的过错导致服务不行用。
再看代码
根据前面说的问题，Seata 才提出了“改善版雪花算法”。
seata.io/zh-cn/blog/…
在介绍改善版之前，咱们先把 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 长度为二进制的 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);
那么理论上的最大值便是 768 | 255 ，算出来仍是 1023。
所以不论你怎样玩出花儿来，这个地方搞出来的数的取值规模就只能是 [0,1023] 之间。
别问，问便是规则里边说了，算法里边只给节点 ID 留了 10 位长度。
终究，便是这个 12 位长度的序列号了：
这个玩意没啥说的，便是一个单纯的、递加的序列号而已。
既然 Seata 号称是改善版，那么具体体现在什么地方呢？
简略到你无法幻想：
是的，仅仅是把时刻戳和节点 ID 换个方位就搞定了。
然后每个节点的时刻戳是在 IdWorker 初始化的时分就设置完成了，具体体现到代码上是这样的：
io.seata.common.util.IdWorker#initTimestampAndSequence
在获取 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 个子序列，每个子序列都是单调递加的。
通过前面的剖析，每个子序列总是单调递加的，所以每个子序列在有限次的割裂之后，终究都会达到稳态。
或许用一个数学上的说法：该算法是收敛的。
再或许，放个图看看：
我想说作者画的时分极力了，至于你看懂看不懂的，就看天意了。
页割裂
前面写的一切内容，你都能在官网上前面说到的两个文章中找到对应的部分。
可是关于页割裂部分，官方并没有进行具体说明。原本也是这样的，人家仅仅给你说自己的算法，没有必要延伸的太远。
“刚才说到了页割裂”，以面试官的嘴脸怎样或许放过你，“打开讲讲？”
链接已放，自行打开：
mysql.taobao.org/monthly/202…
仍是先搞个图：
问，在上面的这个 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 的改善版雪花算法带来什么影响呢？
别问了，别问了，学不动了，学不动了。
