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

server/2024/9/18 12:27:30/ 标签: java, 分布式事务, Seata, 分布式, apache, 云原生

SeataUUID%0Aauthor_selfishlover%0Akeywords_Seata_snowflake_UUID%0Adate_20210508_1">title: Seata基于改良版雪花算法的分布式UUID生成器分析
author: selfishlover
keywords: [Seata, snowflake, UUID]
date: 2021/05/08

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

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

Seata内置了一个分布式UUID生成器,用于辅助生成全局事务ID和分支事务ID。我们希望该生成器具有如下特点:

  • 高性能
  • 全局唯一
  • 趋势递增

高性能不必多言。全局唯一很重要,否则不同的全局事务/分支事务会混淆在一起。
此外,趋势递增对于使用数据库作为TC集群的存储工具的用户而言,能降低数据页分裂的频率,从而减少数据库的IO压力
(branch_table表以分支事务ID作为主键)。

在老版Seata(1.4以前),该生成器的实现基于标准版的雪花算法。标准版雪花算法网上已经有很多解读文章了,此处就不再赘述了。
尚未了解的同学可以先看看网上的相关资料,再来看此文章。
此处我们谈谈标准版雪花算法的几个缺点:

  1. 时钟敏感。因为ID生成总是和当前操作系统的时间戳绑定的(利用了时间的单调递增性),因此若操作系统的时钟出现回拨,
    生成的ID就会重复(一般而言不会人为地去回拨时钟,但服务器会有偶发的"时钟漂移"现象)。
    对于此问题,Seata的解决策略是记录上一次的时间戳,若发现当前时间戳小于记录值(意味着出现了时钟回拨),则拒绝服务,
    等待时间戳追上记录值。 但这也意味着这段时间内该TC将处于不可用状态。
  2. 突发性能有上限。标准版雪花算法宣称的QPS很大,约400w/s,但严格来说这算耍了个文字游戏~
    因为算法的时间戳单位是毫秒,而分配给序列号的位长度为12,即每毫秒4096个序列空间。
    所以更准确的描述应该是4096/ms。400w/s与4096/ms的区别在于前者不要求每一毫秒的并发都必须低于4096
    (也许有些毫秒会高于4096,有些则低于)。Seata亦遵循此限制,若当前时间戳的序列空间已耗尽,会自旋等待下一个时间戳。

在较新的版本上(1.4之后),该生成器针对原算法进行了一定的优化改良,很好地解决了上述的2个问题。
改进的核心思想是解除与操作系统时间戳的时刻绑定,生成器只在初始化时获取了系统当前的时间戳,作为初始时间戳,
但之后就不再与系统时间戳保持同步了。它之后的递增,只由序列号的递增来驱动。比如序列号当前值是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;
}

至此,我们可以发现:

  1. 生成器不再有4096/ms的突发性能限制了。倘若某个时间戳的序列号空间耗尽,它会直接推进到下一个时间戳,
    "借用"下一个时间戳的序列号空间(不必担心这种"超前消费"会造成严重后果,下面会阐述理由)。
  2. 生成器弱依赖于操作系统时钟。在运行期间,生成器不受时钟回拨的影响(无论是人为回拨还是机器的时钟漂移),
    因为生成器仅在启动时获取了一遍系统时钟,之后两者不再保持同步。
    唯一可能产生重复ID的只有在重启时的大幅度时钟回拨(人为刻意回拨或者修改操作系统时区,如北京时间改为伦敦时间~
    机器时钟漂移基本是毫秒级的,不会有这么大的幅度)。
  3. 持续不断的"超前消费"会不会使得生成器内的时间戳大大超前于系统的时间戳, 从而在重启时造成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

当然,如果您有更好的点子,也欢迎跟Seata社区讨论。


http://www.ppmy.cn/server/29352.html

相关文章

Linux快速部署大语言模型LLaMa3,Web可视化j交互(Ollama+Open Web UI)

本文在个人博客同步发布,前往阅读 1 介绍 本文将介绍使用开源工具Ollama(60.6k⭐)部署LLaMa大模型,以及使用Open WebUI搭建前端Web交互界面的方法。 我们先来过一遍几个相关的概念,对这块比较熟悉的朋友可跳过。 1.1 大规模语言模型 大规…

装饰器模式、代理模式、适配器模式对比

装饰器模式、代理模式和适配器模式都是结构型设计模式,它们的主要目标都是将将类或对象按某种布局组成更大的结构,使得程序结构更加清晰。这里将装饰器模式、代理模式和适配器模式进行比较,主要是因为三个设计模式的类图结构相似度较高、且功…

Redis基本數據結構 ― String

Redis基本數據結構 ― String 介紹常用命令範例1. 為字串鍵設值/取得字串鍵的值2. 查看字串鍵的過期時間3. 如何為key設置時間?4. 如何刪除指定key?5. 如何增加value的值?6. 獲取value值的長度 介紹 字串鍵是Redis中最基本的鍵值對類型,這種類型的鍵值對會在數據…

数据结构复习指导之数组和特殊矩阵

文章目录 数组和特殊矩阵 考纲内容 复习提示 前言 1.数组的定义 2.数组的存储结构 3.特殊矩阵的压缩存储 3.1对称矩阵 3.2三角矩阵 3.3三对角矩阵 4.稀疏矩阵 5.知识回顾 数组和特殊矩阵 考纲内容 (一)栈和队列的基本概念 (二&a…

Chrome 插件如何开发?

开发 Chrome 插件涉及几个关键步骤,包括了解 Chrome 插件的架构、编写必要的代码、测试和发布。以下是开发 Chrome 插件的基本流程: 1. 了解 Chrome 插件的基础知识: - Chrome 插件通常由 HTML、CSS 和 JavaScript 文件组成。 - 它们可…

Web前端开发之CSS_2

关系选择器CSS盒子模型弹性盒子模型文档流浮动清除浮动定位 1. 关系选择器 1.1 后代选择器 E F{} 选择所有被 E 元素包含的 F 元素&#xff0c;中间用空格隔开 <ul> <li>后代列表1</li> <div> <ol> <li>后代列表2</li> </ol>…

行为型设计模式

一、责任链设计模式 &#xff08;一&#xff09;概念 使多个对象都有机会处理同一个请求&#xff0c;从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链&#xff0c;并沿着这条链传递该请求&#xff0c;直到有一个对象处理它为止。 &#xff08;二&#xf…

变革 Perplexica:AI驱动的问答搜索引擎

Perplexica是一个开源的人工智能搜索工具&#xff0c;也可以说是一款人工智能搜索引擎&#xff0c;它深入互联网以找到答案。受Perplexity AI启发&#xff0c;它是一个开源选择&#xff0c;不仅可以搜索网络&#xff0c;还能理解您的问题。它使用先进的机器学习算法&#xff0c…

【并行计算】【《并行程序设计导论》笔记】第三章:用MPI进行分布式内存编程

文章目录 3.1|预备知识编译与执行打印来自进程问候语句的MPI程序编译执行 通信子SPMD程序MPI_Send()方法status_p参数MPI_Send()和MPI_Recv()的语义潜在的陷阱 个人主页&#xff1a;丷从心 系列专栏&#xff1a;并行计算 3.1|预备知识 编译与执行 打印来自进程问候语句的MPI…

Kafka(十二)Streams

目录 Streams1 什么式是流式处理2 流式处理的相关概念2.1 拓扑2.2 时间2.2.1 输入时间2.2.2 输出时间 2.3 状态2.4 流和表2.5 时间窗口2.5.1 测试时间窗口 2.6 处理保证 3 流式处理设计模式3.1 单事件处理3.2 使用本地状态3.3 多阶段处理和重分区3.4 使用外部查找&#xff1a;流…

Redis发布-订阅模式之Channel的发布订阅

文章目录 一、简介二、通过频道&#xff08;Channel&#xff09;实现三、代码示例&#xff08;1&#xff09;发布者发送消息&#xff08;2&#xff09;订阅者订阅频道 一、简介 Redis 发布订阅&#xff08;Pus/Sub&#xff09;是一种消息通信模式&#xff1a;发送者通过 publi…

Find My无人机|苹果Find My技术与无人机结合,智能防丢,全球定位

无人机是利用无线电遥控设备和自备的程序控制装置操纵的不载人飞机&#xff0c;或者由车载计算机完全地或间歇地自主地操作。无人机按应用领域&#xff0c;可分为军用与民用。军用方面&#xff0c;无人机分为侦察机和靶机。民用方面&#xff0c;无人机行业应用&#xff0c;是无…

小程序API wx.startLocationUpdateBackground 的使用

若使用该接口&#xff0c;需要在 app.json 中进行声明 requiredPrivateInfos: [getLocation,onLocationChange,startLocationUpdate,startLocationUpdateBackground],requiredBackgroundModes: [audio,location],代码&#xff1a; 1、使用wx.startLocationUpdateBackground需要…

SpringMVC(SSM框架)

目录 一、MVC模式 二、获取请求参数 1. 通过HttpServletRequest获取 2. 通过方法参数获取 3. 通过PathVariable获取 4. 通过ModelAttributes获取 5. 使用RequestBody获取请求体 三、处理响应 四、异常处理 1. 使用ExceptionHandler注解 2. 使用ControllerAdvice和Re…

全景剖析阿里云容器网络数据链路(七):Terway DataPath V2(Terway≥1.8.0)

作者&#xff1a;余凯 前言 近几年&#xff0c;企业基础设施云原生化的趋势越来越强烈&#xff0c;从最开始的IaaS化到现在的微服务化&#xff0c;客户的颗粒度精细化和可观测性的需求更加强烈。容器网络为了满足客户更高性能和更高的密度&#xff0c;也一直在高速的发展和演…

vue使用pdfjs-dist在电脑上展示PDF文件

安装 安装的时候一定要带上版本号,这里采用的是2.0.943(因为这个版本对于我目前的项目比较合适可以正常使用,其他版本大概率会报错),当前项目使用的是vue2,vue的版本是2.5.10 npm install pdfjs-dist@2.0.943 查看版本发现这玩意版本非常之多 使用 在使用pdfjs-dist库…

三丰云搭建QQ-bot的服务器---注册账号

网址&#xff1a;https://www.sanfengyun.com >> 三丰云免费云服务器 本人使用的是qq官方提供的bot&#xff0c;因为要用于群聊&#xff0c;所以使用的是企业bot开发 群聊场景&#xff1a;仅支持企业主体【个人主体暂不支持】频道场景&#xff1a;企业主体与个人主体均可…

Vue 使用Canvas画布手写电子版签名 保存 上传服务端

电子版签名效果 定义画布 <canvas width"500"height"250"ref"cn"mousedown"cnMouseDown"mousemove"cnMouseMove"mouseup"cnMouseUp"style"width:500px;height: 250px;background-color:snow;padding: 10p…

【C++】vector类的增删改查模拟实现(图例超详细解析!!!)

目录 一、前言 二、源码引入 三、vector的模拟实现 ✨实现框架 ✨前情提要 ✨Member functions —— 成员函数 ⚡构造函数 ⭐无参构造 ⭐迭代器区间构造 ⭐n个值构造 ⚡拷贝构造 ⚡运算符赋值重载 ⚡析构函数 ✨Element access —— 元素访问 ⚡operator[ ] …

鸿蒙开发接口Ability框架:【@ohos.ability.dataUriUtils (DataUriUtils模块)】

DataUriUtils模块 DataUriUtils模块提供用于处理使用DataAbilityHelper方案的对象的实用程序类的能力&#xff0c;包括获取&#xff0c;添加&#xff0c;更新给定uri的路径组件末尾的ID。 说明&#xff1a; 本模块首批接口从API version 7开始支持。后续版本的新增接口&#x…