分布式ID-一窥雪花算法的原生实现问题与解决方案(CosId)

本文主要是介绍分布式ID-一窥雪花算法的原生实现问题与解决方案(CosId),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

分布式ID-雪花算法的问题与方案(CosId)

基本原理

在这里插入图片描述

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=%E5%88%86%E5%B8%83%E5%BC%8FID-%E9%9B%AA%E8%8A%B1%E7%AE%97%E6%B3%95%E7%9A%84%E9%97%AE%E9%A2%98%E4%B8%8E%E6%96%B9%E6%A1%88%EF%BC%88CosId%EF%BC%89_image.&pos_id=img-SZPkqRew-1724123351152)

Snowflake算法的原理相对直观,它有不同的部分组成,每个部分单独来看可能会导致重复,但是组合在一起做到全局唯一。

它负责生成一个64位(long型)的全局唯一ID,这个ID的构成包括:1位无用的符号位, 41位的时间戳, 10位的机器ID. 以及12位的序列号,除了固定的1位符号位之外,其余的三个部分都可以根据实际需求进行调整:

  1. 41位时间戳=(1L<<41)/(1000/3600/24/365):这部分能够表示的时间跨度大约69年。即可以使用的绝对时间为EPOCH+69年,一般我们需要自定义EPOCH为产品开发时间,另外还可以通过压缩其他区域的分配位数,来增加时间戳位数来延长可用时间。
  2. 10位工作进程ID=(1L<<10)=1024:时间戳可以保证单台机器单调递增不重复,但是如果是不同机器的集群呢?那么就有可能产生相同的时间戳。这时候就可以把进程ID给拼接上来,机器ID可以唯一标识最多1024个相同的业务。
  3. 12位自增序列号=(1L<<12)*1000=4096000:如果在同一个进程中有多个线程同时生成,那么还是会产 生相同的ID,怎么办?那就再加上一个严格递增的序列位。这样就整体保证了全局的唯一性。

存在的问题

时间戳的坑:时钟回拨问题

服务器时钟回拨是由于在某些情况下,服务器的系统时钟会发生不可避免或人为的变化,在高并发场景下, 获得的高精度时间戳,有时候会往前跳,有时候又会往回拨。一旦时钟往回拨,就有可能产生重复的ID,这 就是时钟回拨问题。

解决的方法有很多,雪花算法对此并没有标准解决方案,不同框架有自己的解决方法,但是基本思路都是用上一次生成主键的时间戳,然后拿当前时间和上一次的时间进行比较,只是发现有问题后的解决方式会有不同:

  • shardingsphere解决方案:如果出现回拨(当前时间小于上一次获取的时间),当前线程就暂时sleep一小段时间,然后重新获取时间戳。
    @SneakyThrows(InterruptedException.class)private boolean waitTolerateTimeDifferenceIfNeed(final long currentMillis) {if (lastMillis.get() <= currentMillis) {return false;}long timeDifferenceMillis = lastMillis.get() - currentMillis;ShardingSpherePreconditions.checkState(timeDifferenceMillis < maxTolerateTimeDifferenceMillis,() -> new AlgorithmExecuteException(this, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds.", lastMillis.get(), currentMillis));Thread.sleep(timeDifferenceMillis);return true;}
  • CosId框架发现时钟回拨直接抛出异常。
AbstractSnowflakeIdlong currentTimestamp = getCurrentTime();
if (currentTimestamp < lastTimestamp) {throw new ClockBackwardsException(lastTimestamp, currentTimestamp);
}
  • 使用ntpd这样的时间同步服务。
  • 美团的Leaf服务:时间戳不依赖本地的服务,放在第三方服务统一管理和获取,省却了时间同步的麻烦,但是因为会依赖网络通信,从而产生IO效率和可用性问题。

工作进程ID如何分配问题

SnowflakeId中根据业务设计的位分配方案确定了基本上就不再有变更了,也很少需要维护。但是工作进程ID总是需要配置的,而且集群中是不能重复的,还要考虑服务重启后分配ID保持稳定性,否则分区原则就会被破坏而导致ID唯一性原则破坏,当集群规模较大时工作进程ID的维护工作是非常繁琐,低效的。

COSID提供的方案如下:

MachineIdDistributorSnowflakeId 的机器号分配器,它负责分配机器号,同时还会存储MachineId的上一次时间戳,用于启动时时钟回拨的检查。

目前 CosId 提供了以下六种 MachineId 分配器。

  • ManualMachineIdDistributor: 手动配置machineId,一般只有在集群规模非常小的时候才有可能使用,不推荐。
  • StatefulSetMachineIdDistributor: 使用KubernetesStatefulSet提供的稳定的标识ID(HOSTNAME=service-01)作为机器号。
  • RedisMachineIdDistributor: 使用Redis作为机器号的分发存储,同时还会存储MachineId的上一次时间戳,用于启动时时钟回拨的检查。
  • JdbcMachineIdDistributor: 使用关系型数据库作为机器号的分发存储,同时还会存储MachineId的上一次时间戳,用于启动时时钟回拨的检查。
  • ZookeeperMachineIdDistributor: 使用ZooKeeper作为机器号的分发存储,同时还会存储MachineId的上一次时间戳,用于启动时时钟回拨的检查。
  • MongoMachineIdDistributor: 使用MongoDB作为机器号的分发存储,同时还会存储MachineId的上一次时间戳,用于启动时时钟回拨的检查。
    在这里插入图片描述

对于实例应用分成两类,一类是stable应用,就是稳定的应用,一类是不稳定的应用。以JdbcMachineIdDistributor分发器为例:

  • 不稳定的应用会回收机器号。每个新应用启动时在cosid_machine表就会有一条记录,并把分配的机器号写到machine_id字段,那么应用实例怎么跟这个机器号关联呢?这条记录还有一个instance_id字段(默认为ip:pid), 当这个应用设置成不稳定的应用时,instance_id字段在写入后暂时与分配的机器号形成了关联关系,然而到应用停止时,Spring的SmartLifecycle回调会回收这个关系(清空这条记录的instance_id字段),这条记录也不是不再用了,它会等待其它应用启动时重新回收利用(重新写入instance_id字段以建立关联关系)。
  • 稳定的应用相比不稳定的应用就是应用停止时不会有回收的动作,并且在本地的.cosid-machine-state目录会保存当前应用的机器号和时间戳,下次启动时还是会找到同一条记录。

下图展示了CosId分配工作进程id的过程:
在这里插入图片描述

序列号部分的不连续性

在雪花算法中,排在最后的12位自增序列号部分,默认的生成逻辑是当时间戳部分相等时,自增序列号部分才会+1,否则,将从0重新开始。我们想想这样的话会有什么问题,因为时间戳相同的情况很少,所以我们生成出来的id末尾大部分会导致取模的时候分布并不均匀,比如分库分表时,数据大部分就会落到一个地方,不适用于需要做取模运算的场景。

我们先复现一下问题,使用hutool的雪花算法工具类生成唯一id,然后做一个简单的取模运算:

    @Testpublic void hutoolSnowflakeMod() throws InterruptedException {for (int i = 0; i < 100; i++) {long id = IdUtil.getSnowflake(1).nextId();Thread.sleep(1);log.info("id: {}, after mod 4: {}", id, id % 4);}}

截取的结果可以看到,基本上就是0,几乎没有其它数字,取模的结果很不均匀。

[2024-08-19 15:46:45.486] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244152344576, after mod 4: 0
[2024-08-19 15:46:45.487] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244160733184, after mod 4: 0
[2024-08-19 15:46:45.490] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244164927488, after mod 4: 0
[2024-08-19 15:46:45.492] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244177510400, after mod 4: 0
[2024-08-19 15:46:45.493] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244185899008, after mod 4: 0
[2024-08-19 15:46:45.496] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244190093312, after mod 4: 0
[2024-08-19 15:46:45.498] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244202676224, after mod 4: 0
[2024-08-19 15:46:45.501] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244211064832, after mod 4: 0
[2024-08-19 15:46:45.503] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244223647744, after mod 4: 0
[2024-08-19 15:46:45.505] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244232036352, after mod 4: 0
[2024-08-19 15:46:45.507] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.hutoolSnowflakeMod(41)] - id: 1825439244240424960, after mod 4: 0

在CosId框架中,解决方案也很简单 – 轻易不要重置这个自增序列位即可,通过引入 sequenceResetThreshold 属性,巧妙地解决了取模分片不均匀的问题,这一设计在无需牺牲性能的同时,为用户提供了更加出色的使用体验。

sequenceResetThreshold 在不同的情况下可能会取不同的值,但是作用都是一样的,通过限制自增序列不要轻易重置来达到目的。

AbstractSnowflakeId//region Reset sequence based on sequence reset threshold,Optimize the problem of uneven sharding.if (currentTimestamp > lastTimestamp&& sequence >= sequenceResetThreshold) {sequence = 0L;
}

我们跑一遍CosId的取模情况:

    @Testpublic void cosIdSnowflakeMod() throws InterruptedException {for (int i = 0; i < 100; i++) {long id = snowflakeId.generate();Thread.sleep(1);log.info("id: {}, after mod 4: {}", id, id % 4);}}

可以看出已经不存在取模分配不均匀的问题

[2024-08-19 15:50:35.949] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209755045889, after mod 4: 1
[2024-08-19 15:50:35.951] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209763434498, after mod 4: 2
[2024-08-19 15:50:35.953] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209771823107, after mod 4: 3
[2024-08-19 15:50:35.955] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209780211716, after mod 4: 0
[2024-08-19 15:50:35.957] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209788600325, after mod 4: 1
[2024-08-19 15:50:35.959] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209796988934, after mod 4: 2
[2024-08-19 15:50:35.961] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209805377543, after mod 4: 3
[2024-08-19 15:50:35.963] [Test worker] [ INFO] [o.OakHybridCacheWithDBCosIdTest.cosIdSnowflakeMod(50)] - id: 615936209813766152, after mod 4: 0

JavaScript数值溢出

JavaScriptNumber.MAX_SAFE_INTEGER只有53-bit,如果直接将63位的SnowflakeId返回给前端,那么会产生值溢出的情况(所以这里我们应该知道后端传给前端的long值溢出问题,迟早会出现,只不过SnowflakeId出现得更快而已)。 很显然溢出是不能被接受的,一般可以使用以下俩种处理方案:

  • 将生成的63-bitSnowflakeId转换为String类型。
    • 直接将long转换成String
    • (CosId方案)使用SnowflakeFriendlyIdSnowflakeId转换成比较友好的字符串表示:{timestamp}-{machineId}-{sequence} -> 20210623131730192-1-0
  • 自定义SnowflakeId位分配来缩短SnowflakeId的位数(53-bit)使 ID 提供给前端时不溢出
    • (CosId方案)使用SafeJavaScriptSnowflakeId(JavaScript 安全的 SnowflakeId)

这篇关于分布式ID-一窥雪花算法的原生实现问题与解决方案(CosId)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092696

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time