你好呀，我是歪歪。
在 Seata 的官网上看到一篇叫做“关于新版雪花算法的答疑”的文章。
seata.io/zh-cn/blog/…
看明白之后，我觉得仍是有点意思的，结合自己的了解和代码，加上画几张图，给你拆解一下 Seata 里边的“改良版雪花算法”。
虽然是在 Seata 里边看到的，可是本篇文章的内容和 Seata 结构没有太多关系，反而和数据库的基础知识有关。
所以，即便你不了解 Seata 结构，也不影响你阅览。
当你了解了这个类的作业原理之后，你彻底能够把这个只要 100 多行的类转移到你的项目里边，然后就变成你的了。
你懂我意思吧。
先说问题
假如你的项目中涉及到需求一个大局仅有的流水号，比方订单号、流水号之类的，又或许在分库分表的状况下，需求一个大局仅有的主键 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 这个玩意。
节点 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 个子序列，每个子序列都是单调递加的。
通过前面的剖析，每个子序列总是单调递加的，所以每个子序列在有限次的割裂之后，终究都会达到稳态。
或许用一个数学上的说法：该算法是收敛的。
再或许，我给你画个图：
我画的时分极力了，至于你看懂看不懂的，就看天意了。
假如看不懂的话，自信一点，不要置疑自己，便是我画的欠好。大胆的说出来：什么玩意？这画的都是些啥，看求不懂。呸，垃圾作者。
页割裂
前面写的一切内容，你都能在官网上我前面说到的两个文章中找到对应的部分。
可是关于页割裂部分，官方并没有进行详细说明。本来也是这样的，人家仅仅给你说自己的算法，没有必要延伸的太远。
已然都说到页割裂了，那我来弥补一个我在学习的时分看到的一个有意思的当地。
也便是这个链接，这一节的内容便是来源于这个链接中：
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 的改良版雪花算法带来什么影响呢？
别问了，别问了，学不动了，学不动了。
自己看一下吧：
终究，假如本文对你有一点点协助的话，点个免费的赞，求个重视，不过分吧？
