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


title: 关于新版雪花算法的答疑
author: selfishlover
keywords: [Seata, snowflake, UUID, page split]
date: 2021/06/21

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

关于新版雪花算法的答疑

在上一篇关于新版雪花算法的解析中,我们提到新版算法所做出的2点改变:

  1. 时间戳不再时刻追随系统时钟。
  2. 节点ID和时间戳互换位置。由原版的:
    在这里插入图片描述

改成:在这里插入图片描述

有细心的同学提出了一个问题:新版算法在单节点内部确实是单调递增的,但是在多实例部署时,它就不再是全局单调递增了啊!因为显而易见,节点ID排在高位,那么节点ID大的,生成的ID一定大于节点ID小的,不管时间上谁先谁后。而原版算法,时间戳在高位,并且始终追随系统时钟,可以保证早生成的ID小于晚生成的ID,只有当2个节点恰好在同一时间戳生成ID时,2个ID的大小才由节点ID决定。这样看来,新版算法是不是错的?

这是一个很好的问题!能提出这个问题的同学,说明已经深入思考了标准版雪花算法和新版雪花算法的本质区别,这点值得鼓励!在这里,我们先说结论:新版算法的确不具备全局的单调递增性,但这不影响我们的初衷(减少数据库的页分裂)。这个结论看起来有点违反直觉,但可以被证明。

在证明之前,我们先简单回顾一下数据库关于页分裂的知识。以经典的mysql innodb为例,innodb使用B+树索引,其中,主键索引的叶子节点还保存了数据行的完整记录,叶子节点之间以双向链表的形式串联起来。叶子节点的物理存储形式为数据页,一个数据页内最多可以存储N条行记录(N与行的大小成反比)。如图所示:
在这里插入图片描述

B+树的特性要求,左边的节点应小于右边的节点。如果此时要插入一条ID为25的记录,会怎样呢(假设每个数据页只够存放4条记录)?答案是会引起页分裂,如图:
在这里插入图片描述

页分裂是IO不友好的,需要新建数据页,拷贝转移旧数据页的部分记录等,我们应尽量避免。

理想的情况下,主键ID最好是顺序递增的(例如把主键设置为auto_increment),这样就只会在当前数据页放满了的时候,才需要新建下一页,双向链表永远是顺序尾部增长的,不会有中间的节点发生分裂的情况。

最糟糕的情况下,主键ID是随机无序生成的(例如java中一个UUID字符串),这种情况下,新插入的记录会随机分配到任何一个数据页,如果该页已满,就会触发页分裂。

如果主键ID由标准版雪花算法生成,最好的情况下,是每个时间戳内只有一个节点在生成ID,这时候算法的效果等同于理想情况的顺序递增,即跟auto_increment无差。最坏的情况下,是每个时间戳内所有节点都在生成ID,这时候算法的效果接近于无序(但仍比UUID的完全无序要好得多,因为workerId只有10位决定了最多只有1024个节点)。实际生产中,算法的效果取决于业务流量,并发度越低,算法越接近理想情况。

那么,换成新版算法又会如何呢?
新版算法从全局角度来看,ID是无序的,但对于每一个workerId,它生成的ID都是严格单调递增的,又因为workerId是有限的,所以最多可划分出1024个子序列,每个子序列都是单调递增的。
对于数据库而言,也许它初期接收的ID都是无序的,来自各个子序列的ID都混在一起,就像这样:
在这里插入图片描述

如果这时候来了个worker1-seq2,显然会造成页分裂:
在这里插入图片描述

但分裂之后,有趣的事情发生了,对于worker1而言,后续的seq3,seq4不会再造成页分裂(因为还装得下),seq5也只需要像顺序增长那样新建页进行链接(区别是这个新页不是在双向链表的尾部)。注意,worker1的后续ID,不会排到worker2及之后的任意节点(因而不会造成后边节点的页分裂),因为它们总比worker2的ID小;也不会排到worker1当前节点的前边(因而不会造成前边节点的页分裂),因为worker1的子序列总是单调递增的。在这里,我们称worker1这样的子序列达到了稳态,意为这条子序列已经"稳定"了,它的后续增长只会出现在子序列的尾部,而不会造成其它节点的页分裂。

同样的事情,可以推广到各个子序列上。无论前期数据库接收到的ID有多乱,经过有限次的页分裂后,双向链表总能达到这样一个稳定的终态:
在这里插入图片描述

到达终态后,后续的ID只会在该ID所属的子序列上进行顺序增长,而不会造成页分裂。该状态下的顺序增长与auto_increment的顺序增长的区别是,前者有1024个增长位点(各个子序列的尾部),后者只有尾部一个。

到这里,我们可以回答开头所提出的问题了:新算法从全局来看的确不是全局递增的,但该算法是收敛的,达到稳态后,新算法同样能达成像全局顺序递增一样的效果。


扩展思考

以上只提到了序列不停增长的情况,而实践生产中,不光有新数据的插入,也有旧数据的删除。而数据的删除有可能会导致页合并(innodb若发现相邻2个数据页的空间利用率都不到50%,就会把它俩合并),这对新算法的影响如何呢?

经过上面的流程,我们可以发现,新算法的本质是利用前期的页分裂,把不同的子序列逐渐分离开来,让算法不断收敛到稳态。而页合并则恰好相反,它有可能会把不同的子序列又合并回同一个数据页里,妨碍算法的收敛。尤其是在收敛的前期,频繁的页合并甚至可以让算法永远无法收敛(你刚分离出来我就又把它们合并回去,一夜回到解放前~)!但在收敛之后,只有在各个子序列的尾节点进行的页合并,才有可能破坏稳态(一个子序列的尾节点和下一个子序列的头节点进行合并)。而在子序列其余节点上的页合并,不影响稳态,因为子序列仍然是有序的,只不过长度变短了而已。

以seata的服务端为例,服务端那3张表的数据的生命周期都是比较短的,一个全局事务结束之后,它们就会被清除了,这对于新算法是不友好的,没有给时间它进行收敛。不过已经有延迟删除的PR在review中,搭配这个PR,效果会好很多。比如定期每周清理一次,前期就有足够的时间给算法进行收敛,其余的大部分时间,数据库就能从中受益了。到期清理时,最坏的结果也不过是表被清空,算法从头再来。

如果您希望把新算法应用到业务系统当中,请务必确保算法有时间进行收敛。比如用户表之类的,数据本就打算长期保存的,算法可以自然收敛。或者也做了延迟删除的机制,给算法足够的时间进行收敛。

如果您有更好的意见和建议,也欢迎跟seata社区联系!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/583567.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

web前端学习笔记4

4. 盒子模型 4.0 代码地址 https://gitee.com/qiangge95243611/java118/tree/master/web/day044.1 什么是盒子模型(Box Model) 所有HTML元素可以看作盒子,在CSS中,"box model"这一术语是用来设计和布局时使用。 CSS盒模型本质上是一个盒子,封装周围的HTML元素,…

在Docker中部署Java应用:Java版本隔离的实践案例

在Docker中部署Java应用:Java版本隔离的实践案例 人生就是一场又一场的相遇,一个明媚,一个忧伤,一个华丽,一个冒险,一个倔强,一个柔软,最后那个正在成长。 背景需求 在软件开发和部…

Debian 12 -bash: netstat: command not found 解决办法

问题表现: debian 12系统中,不能使用 netstat命令 处理办法: netstat 命令就的net-tools中,把net-tools工具安装上就好了。 apt-get install netstat 安装之后就可以使用netstat 命令了,如查询端口情况: …

基于SpringBoot+Vue高校宣讲会管理系统设计与实现

项目介绍: 传统办法管理信息首先需要花费的时间比较多,其次数据出错率比较高,而且对错误的数据进行更改也比较困难,最后,检索数据费事费力。因此,在计算机上安装高校宣讲会管理系统软件来发挥其高效地信息…

C# Web控件与数据感应之 Control 类

目录 关于数据感应 Control 类 范例运行环境 simpleDataListEx方法 设计 实现 调用示例 数据源 调用 小结 关于数据感应 数据感应也即数据捆绑,是一种动态的,Web控件与数据源之间的交互,诸如 ListControl 类类型控件,在…

pytest教程-35-钩子函数-pytest_unconfigure

领取资料,咨询答疑,请➕wei: June__Go 上一小节我们学习了pytest_configure钩子函数的使用方法,本小节我们讲解一下pytest_unconfigure钩子函数的使用方法。 pytest_unconfigure(config) 是一个 pytest 钩子函数,它在 pytest 退…

【linux运维】vim基础应用

系列综述: 💞目的:本系列是个人整理为了学习基本的shell编程和linux命令,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于b站大学——linux运维课程进行的,…

【MHA】MySQL高可用MHA源码1-主库故障监控

1 阅读之前的准备工作 1 一个IDE工具 ,博主自己尝试了vscode安装perl的插件,但是函数 、变量 、模块等都不能跳转,阅读起来不是很方便。后来尝试使用了pycharm安装perl插件,阅读支持跳转,自己也能写一些简单的测试样例…

[iOS]组件化开发

一、组件化开发基础 1.组件定义 在软件开发中,一个组件是指一个独立的、可替换的软件单元,它封装了一组相关的功能。组件通过定义的接口与外界交互,并且这些接口隔离了组件内部的实现细节。在Swift语言中,组件可以是一个模块、一…

CCF-CSP真题题解:201312-2 ISBN号码

201312-2 ISBN号码 #include <iostream> #include <cstring> #include <algorithm> using namespace std;string s;int main() {cin >> s;int num 0;for (int i 0, p 1; i < s.size() - 1; i)if (s[i] ! -) {num (s[i] - 0) * p;p;}num % 11;ch…

win11 自带分区磁盘管理,右键U盘 删除卷,显示不支持该请求

win11 自带分区磁盘管理&#xff0c;右键U盘 删除卷&#xff0c;显示不支持该请求&#xff0c;打开cmd 输入下面命令 1.diskpart 2.list disk 3.sel disk (U盘盘符编号) 4.clean

Linux vi\vim编辑器

vi/vim编辑器 一、vi\vim 编辑器的三种工作模式1.命令模式&#xff08;Command mode&#xff09;2.输入模式&#xff08;Insert mode&#xff09;3.底线命令模式&#xff08;Last line mode&#xff09; 二、参考 vi\vim 是 visual interface 的简称&#xff0c;是 Linux 中最经…

Tcp 协议的接口测试

首先明确 Tcp 的概念&#xff0c;针对 Tcp 协议进行接口测试&#xff0c;是指基于 Tcp 协议的上层协议比如 Http &#xff0c;串口&#xff0c;网口&#xff0c; Socket 等。这些协议与 Http 测试方法类似&#xff08;具体查看接口自动化测试章节&#xff09;&#xff0c;但在测…

大数据计算引擎中的Calcite

1.Calcite介绍 Calcite是一个动态数据库管理框架&#xff0c;具备数据库管理系统的功能 Calcite具备SQL解析、校验、优化、生成、连接查询等功能 Calcite能够为不同平台和数据源提供统一的查询引擎 2.Calcite能力 比如&#xff0c;对于HBase而言&#xff0c;没有SQL查询的能力…

Qt 6 开源版(免费) -- 安装图解

Qt6起&#xff0c;两项重大改变&#xff08;并非指技术&#xff09;&#xff1a; 必须在线安装&#xff0c;不再提供单独的安装包主推收费的商业版 当然的&#xff0c;为了引流、培养市场&#xff0c;提供了一个免费的开源版本。 开源版相对于收费的商业版&#xff0c;主体是…

PostgreSQL 14 向量相似度搜索插件 (pgvector) 安装指南

本文是关于在 PostgreSQL 14 中安装并使用向量相似度搜索插件(pgvector)的详细指南。此插件允许用户在数据库中执行高效的向量运算,特别适用于机器学习模型的向量数据存储与检索场景。 环境需求 已安装PostgreSQL 14或更高版本。安装了Visual Studio 2022,用于编译插件。安装…

微信小程序+esp8266温湿度读取

本文主要使用微信小程序显示ESP8266读取的温湿度并通过微信小程序控制LED灯。小程序界面如下图所示 原理讲解 esp8266 通过mqtt发布消息,微信小程序通过mqtt 订阅消息,小程序订阅后,就可以实时收到esp8266 传输来的消息。 个人可免费注册五个微信小程序账号,在微信小程序官…

渗透之sql注入---实战1

本期的sql注入实战在&#xff1a;BUUCTF在线评测 (buuoj.cn) 该网站上进行。 启动靶机&#xff1a; 1.进来后搜索web1 2.点击【SWPU2019】Web1启动靶机。 3.进来之后在此界面进行注入。 开始注入&#xff1a; 1.找注入点&#xff1a; 我们输入1 后查看广告详情发现报错&a…

利用kimi等大模型进行运维参数解析和调优

在运维时&#xff0c;经常遇到很多参数&#xff0c;有些参数不知道意义&#xff0c;知道意义的也有些不知道合理参考值是多少。利用kimi等大模型来当老司机&#xff0c;轻松解决运维难题。 例如在运维hive参数时&#xff0c;有些不知道作用&#xff0c;提示次如下 你的角色是…

vue根据输入n动态生成n个表单

我的构想&#xff1a;在输入框中输入一个数字n&#xff0c;然后点击一个按钮&#xff0c;弹出一个弹窗&#xff0c;里面有n个表单。 这是按钮的vue代码&#xff1a;数值保存在form.number里面&#xff0c;每次数字改变会触发numberChange //...略 <el-form-item prop"…