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

devtools/2024/10/16 0:24:40/

CosId_0">分布式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一小段时间，然后重新获取时间戳。
java">    @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框架发现时钟回拨直接抛出异常。
java">AbstractSnowflakeIdlong currentTimestamp = getCurrentTime();
if (currentTimestamp < lastTimestamp) {throw new ClockBackwardsException(lastTimestamp, currentTimestamp);
}
  • 使用ntpd这样的时间同步服务。
  • 美团的Leaf服务：时间戳不依赖本地的服务，放在第三方服务统一管理和获取，省却了时间同步的麻烦，但是因为会依赖网络通信，从而产生IO效率和可用性问题。

工作进程ID如何分配问题

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

COSID提供的方案如下：

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

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

  • ManualMachineIdDistributor: 手动配置machineId，一般只有在集群规模非常小的时候才有可能使用，不推荐。
  • StatefulSetMachineIdDistributor: 使用Kubernetes的StatefulSet提供的稳定的标识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，然后做一个简单的取模运算：

java">    @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，几乎没有其它数字，取模的结果很不均匀。

java">[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 在不同的情况下可能会取不同的值，但是作用都是一样的，通过限制自增序列不要轻易重置来达到目的。

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

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

java">    @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);}}

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

java">[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数值溢出

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

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

http://www.ppmy.cn/devtools/97906.html

相关文章

使用css如何获取最后一行的元素？使用css解决双边框问题

使用css如何获取最后一行的元素？使用css解决双边框问题

一、项目场景&#xff1a; 在小程序上需要实现一个如下图的ui效果图 需要满足以下条件 一行放不下 自动换行最后一行或者只有一行时&#xff0c;文字底部不能有线 二、初版实现 按照上面的要求&#xff0c;最开是的实现代码如下 我是给每一个元素都添加了一个下边框&#x…
阅读更多...
软件测试费用怎么算?湖南软件测评公司简析

软件测试费用怎么算?湖南软件测评公司简析

随着信息技术的迅猛发展&#xff0c;软件在各行各业中的应用日益广泛&#xff0c;软件测试的重要性愈加凸显。特别是对于各种规模的企业&#xff0c;确保软件质量和安全性不仅是提升竞争力的关键因素&#xff0c;更是维护用户信赖的基础。 软件测试作为软件开发过程中的关键环…
阅读更多...
python进阶语法---异常处理

python进阶语法---异常处理

在 Python 中&#xff0c;异常处理是一种机制&#xff0c;用于处理程序运行时可能发生的错误&#xff0c;以确保程序能够优雅地处理错误情况&#xff0c;而不是直接崩溃。异常处理机制的核心是使用 try、except、else 和 finally 语句。 一、基础语法 异常处理的基本语法如下…
阅读更多...
简易版PHP软文发稿开源系统

简易版PHP软文发稿开源系统

软文发稿系统源码&#xff08;软文发布系统&#xff09;基于旧版本的媒介软文项目基础上整理出一套简易版&#xff0c;以满足不同客户群体。虽然是简易版 但麻雀虽小五脏俱全&#xff0c;基本能满足小众群体需求 具体功能如下&#xff1a; 大模块功能&#xff1a; 1、媒体发布 …
阅读更多...
【C++初阶】一篇手撕vector类

【C++初阶】一篇手撕vector类

vector类 一&#xff0c;vector的介绍二&#xff0c;vector的使用2.1 vector的定义2.2 vector iterator2.3 vector空间增长问题2.4 vector增删查改2.5 vector<char> 可以替代 string 嘛&#xff1f; 一&#xff0c;vector的介绍 vector 是表示可变大小数组序列容器。就像…
阅读更多...
记录一次搭建uniapp-vue3的基础项目

记录一次搭建uniapp-vue3的基础项目

1.使用 HBuilder X 创建uniapp vue3的基础项目 2.安装 自动导包插件 unplugin-auto-import npm install unplugin-auto-import或者 pnpm install unplugin-auto-import2.1 根目录下创建 vite.config.js 复制粘贴以下内容 import { defineConfig } from vite import uni fro…
阅读更多...
网络编程第三天

网络编程第三天

服务器&#xff1a; #include<sys/types.h> // 支持套接字地址结构 #include <sys/socket.h> // 提供套接字API #include <netinet/in.h> // 定义IP地址结构体 #include <string.h> // 提供字符串操作函数 #include <stdio.h> // 提供标准I/O操…
阅读更多...
数字化转型对金融服务业的影响

数字化转型对金融服务业的影响

数字化转型正在塑造每个行业&#xff0c;从快速消费品到金融&#xff0c;每个行业都受到新兴技术的影响。 那么&#xff0c;数字化转型在金融服务中扮演什么角色&#xff1f;这对招聘前景有何影响&#xff1f; 我们探讨了数字化转型对该行业的影响、其对招聘策略的影响、数据…
阅读更多...
最新文章

Copyright @ 2022~2023