索菲亚全屋定制官方网站,数据分析和网站开发,房产app开发公司,最新wordpress 优化版【Spring Cloud系列】 雪花算法原理及实现 文章目录 【Spring Cloud系列】 雪花算法原理及实现一、概述二、生成ID规则部分硬性要求三、ID号生成系统可用性要求四、解决分布式ID通用方案4.1 UUID4.2 数据库自增主键4.3 基于Redis生成全局id策略 五、SnowFlake#xff08;雪花算…【Spring Cloud系列】 雪花算法原理及实现 文章目录 【Spring Cloud系列】 雪花算法原理及实现一、概述二、生成ID规则部分硬性要求三、ID号生成系统可用性要求四、解决分布式ID通用方案4.1 UUID4.2 数据库自增主键4.3 基于Redis生成全局id策略 五、SnowFlake雪花算法5.1 SnowFlake特点5.2 SnowFlake结构5.3 雪花算法原理5.4 算法实现5.4 雪花算法优点5.5 雪花算法缺点 六、总结 一、概述
分布式高并发的环境下常见的就是12306节日订票在大量用户同是抢购一个方向的票毫秒级的时间下可能生成数万个订单此时为确保生成订单ID的唯一性变得至关重要。此时秒杀环境下不仅要保障ID唯一性还得确保ID生成的优先度。
二、生成ID规则部分硬性要求
全局唯一不能出现重复的ID号既然是唯一标识这是最基本的要求。趋势递增在MySQL的InnoDB引擎中适用的是聚集索引由于多数RDBMS使用BTree的数据结构来存储索引数据在主键的选择上我们尽量使用有序的主键保证写入性能。单调递增保证下一个ID一定大于上一个ID如事务版本号、排序等特殊需求。信息安全如果ID是连续的恶意用户的抓取工作就非常容易直接按照顺序下载指定URL即可如果是订单号就危险。含有时间戳生成的ID包含完整的时间戳信息。
三、ID号生成系统可用性要求
高可用发一个获取分布式ID的请求服务器就是保证99.9999%的情况下给我创建一个唯一分布式ID。低延迟发一个获取分布式ID的请求服务器要快极速。高QPS如果一次请求10万个分布式ID服务器要顶住并成功创建10万个分布式ID。
四、解决分布式ID通用方案
4.1 UUID
UUIDUniversally Unique Identifier的标准型式包含32个16进制数字以连字号分为五段形式为8-4-4-4-12的36个字符示例1E785B2B-111C-752A-997B-3346E7495CE2UUID性能非常高不依赖网络本地生成。
UUID缺点 无序无法预测它的生成顺序不能生成递增有序的数字。在MySql官方推荐主键约短越好UUID是一个32位的字符串所以不推荐使用。 索引BTree索引的分裂 分布式Id是主键主键是聚簇索引。Mysql的索引是BTree来实现的每次新的UUID数据的插入为了新的UUID数据的插入为了查询的优化都会对索引底部的BTree进行修改因为UUID数据是无序的所以每一次UUID数据的插入都会对主键的聚簇索引做很大的修改在做数据Insert时会插入主键是无序的会导致一些中间节点的产生分裂会导致大量不饱和的节点。这样大大降低了数据库插入的性能。
4.2 数据库自增主键
单机
在分布式里面数据库的自增ID机制的主要原理是数据库自增ID和MySql数据库的replace into实现的。 Replace into的含义是插入一条纪录如果表中唯一索引的值遇到冲突则替换老数据。 在单体应用的时候自增长ID使用但是在集群分布式应用中单体应用就不适合。
系统水平扩展比较困难比如定义好了增长步长和机器台数之后在大量添加服务器时需要重新设置初始值这样可操作性差所以系统水平扩展方案复杂度高难以实现。数据库压力大每次获取ID都需要读写一次数据库非常影响性能不符合分布式ID里面的延迟低和要高QPS的规则在高并发下如果都去数据库里面获取Id非常影响性能的。
4.3 基于Redis生成全局id策略
在Redis集群情况下同样和MySql一样需要设置不同的增长步长同时key一定要设置有效期。可以使用Redis集群来获取更高的吞吐量。
五、SnowFlake雪花算法
而Twitter的SnowFlake解决了这种需求最初Twitter把存储系统从MySQL迁移到Cassandra(由Facebook开发一套开源分布式NoSQL数据库系统) 因为Cassandra没有顺序ID生成机制所以开发了这样一套全局唯一ID生成服务。SnowFlake每秒能产生26万个自增可排序的ID。
5.1 SnowFlake特点
Twitter的SnowFlake生成ID能够按照时间有序生成。SnowFlake算法生成Id的结果是一个64bit大小的整数为一个Long型转换成字符串后长度最多19。分布式系统内不会产生ID碰撞由datacenter和workerid作为区分并且效率较高。
5.2 SnowFlake结构 5.3 雪花算法原理
雪花算法的原理就是生成一个的64位比特位的long类型的唯一id
最高1位固定值0因为生成的id是正整数如果是1就是负值。紧接着是41位存储毫秒级时间戳2^41/(1000 * 60 * 24 * 365) 69 大概可以使用69年。接下来10位存储机器码包括5位DataCenterId和5位WorkerId,最多可以部署2^101024台机器。最后12位存储序列号同一毫秒时间戳时通过这个递增的序列号来区分即对于同一台机器而言同一毫秒级时间戳下可以生成2^124096个不重复id。
可以将雪花算法作为一个单独的服务进行部署然后需要全局唯一id的系统请求雪花算法服务获取id即可。
对于每一个雪花算法服务需要先指定10位的机器码这个根据自身业务进行设定即可。例如机房号机器号机器号服务号或者时其他区别标识的10位比特位的整数都行。
5.4 算法实现
package com.goyeer;
import java.util.Date;/*** ClassName: SnowFlakeUtil* Author: goyeer* Date: 2023/09/09 19:34* Description:*/
public class SnowFlakeUtil {private static SnowFlakeUtil snowFlakeUtil;static {snowFlakeUtil new SnowFlakeUtil();}// 初始时间戳(纪年)可用雪花算法服务上线时间戳的值//private static final long INIT_EPOCH 1694263918335L;// 时间位取private static final long TIME_BIT 0b1111111111111111111111111111111111111111110000000000000000000000L;// 记录最后使用的毫秒时间戳主要用于判断是否同一毫秒以及用于服务器时钟回拨判断private long lastTimeMillis -1L;// dataCenterId占用的位数private static final long DATA_CENTER_ID_BITS 5L;// dataCenterId占用5个比特位最大值31// 0000000000000000000000000000000000000000000000000000000000011111private static final long MAX_DATA_CENTER_ID ~(-1L DATA_CENTER_ID_BITS);// dataCenterIdprivate long dataCenterId;// workId占用的位数private static final long WORKER_ID_BITS 5L;// workId占用5个比特位最大值31// 0000000000000000000000000000000000000000000000000000000000011111private static final long MAX_WORKER_ID ~(-1L WORKER_ID_BITS);// workIdprivate long workerId;// 最后12位代表每毫秒内可产生最大序列号即 2^12 - 1 4095private static final long SEQUENCE_BITS 12L;// 掩码最低12位为1高位都为0主要用于与自增后的序列号进行位与如果值为0则代表自增后的序列号超过了4095// 0000000000000000000000000000000000000000000000000000111111111111private static final long SEQUENCE_MASK ~(-1L SEQUENCE_BITS);// 同一毫秒内的最新序号最大值可为 2^12 - 1 4095private long sequence;// workId位需要左移的位数 12private static final long WORK_ID_SHIFT SEQUENCE_BITS;// dataCenterId位需要左移的位数 125private static final long DATA_CENTER_ID_SHIFT SEQUENCE_BITS WORKER_ID_BITS;// 时间戳需要左移的位数 1255private static final long TIMESTAMP_SHIFT SEQUENCE_BITS WORKER_ID_BITS DATA_CENTER_ID_BITS;/*** 无参构造*/public SnowFlakeUtil() {this(1, 1);}/*** 有参构造* param dataCenterId* param workerId*/public SnowFlakeUtil(long dataCenterId, long workerId) {// 检查dataCenterId的合法值if (dataCenterId 0 || dataCenterId MAX_DATA_CENTER_ID) {throw new IllegalArgumentException(String.format(dataCenterId 值必须大于 0 并且小于 %d, MAX_DATA_CENTER_ID));}// 检查workId的合法值if (workerId 0 || workerId MAX_WORKER_ID) {throw new IllegalArgumentException(String.format(workId 值必须大于 0 并且小于 %d, MAX_WORKER_ID));}this.workerId workerId;this.dataCenterId dataCenterId;}/*** 获取唯一ID* return*/public static Long getSnowFlakeId() {return snowFlakeUtil.nextId();}/*** 通过雪花算法生成下一个id注意这里使用synchronized同步* return 唯一id*/public synchronized long nextId() {long currentTimeMillis System.currentTimeMillis();System.out.println(currentTimeMillis);// 当前时间小于上一次生成id使用的时间可能出现服务器时钟回拨问题if (currentTimeMillis lastTimeMillis) {throw new RuntimeException(String.format(可能出现服务器时钟回拨问题请检查服务器时间。当前服务器时间戳%d上一次使用时间戳%d, currentTimeMillis,lastTimeMillis));}if (currentTimeMillis lastTimeMillis) {// 还是在同一毫秒内则将序列号递增1序列号最大值为4095// 序列号的最大值是4095使用掩码最低12位为1高位都为0进行位与运行后如果值为0则自增后的序列号超过了4095// 那么就使用新的时间戳sequence (sequence 1) SEQUENCE_MASK;if (sequence 0) {currentTimeMillis getNextMillis(lastTimeMillis);}} else { // 不在同一毫秒内则序列号重新从0开始序列号最大值为4095sequence 0;}// 记录最后一次使用的毫秒时间戳lastTimeMillis currentTimeMillis;// 核心算法将不同部分的数值移动到指定的位置然后进行或运行// 左移运算符, 1 2 即将二进制的 1 扩大 2^2 倍// |位或运算符, 是把某两个数中, 只要其中一个的某一位为1, 则结果的该位就为1// 优先级 |return// 时间戳部分((currentTimeMillis - INIT_EPOCH) TIMESTAMP_SHIFT)// 数据中心部分| (dataCenterId DATA_CENTER_ID_SHIFT)// 机器表示部分| (workerId WORK_ID_SHIFT)// 序列号部分| sequence;}/*** 获取指定时间戳的接下来的时间戳也可以说是下一毫秒* param lastTimeMillis 指定毫秒时间戳* return 时间戳*/private long getNextMillis(long lastTimeMillis) {long currentTimeMillis System.currentTimeMillis();while (currentTimeMillis lastTimeMillis) {currentTimeMillis System.currentTimeMillis();}return currentTimeMillis;}/*** 获取随机字符串,length13* return*/public static String getRandomStr() {return Long.toString(getSnowFlakeId());}/*** 从ID中获取时间* param id 由此类生成的ID* return*/public static Date getTimeBySnowFlakeId(long id) {return new Date(((TIME_BIT id) 22) INIT_EPOCH);}public static void main(String[] args) {SnowFlakeUtil snowFlakeUtil new SnowFlakeUtil();long id snowFlakeUtil.nextId();System.out.println(id);Date date SnowFlakeUtil.getTimeBySnowFlakeId(id);System.out.println(date);long time date.getTime();System.out.println(time);System.out.println(getRandomStr());}}5.4 雪花算法优点
高并发分布式环境下生成不重复 id每秒可生成百万个不重复 id。基于时间戳以及同一时间戳下序列号自增基本保证 id 有序递增。不依赖第三方库或者中间件。算法简单在内存中进行效率高。
5.5 雪花算法缺点
依赖服务器时间服务器时钟回拨时可能会生成重复 id。算法中可通过记录最后一个生成 id 时的时间戳来解决每次生成 id 之前比较当前服务器时钟是否被回拨避免生成重复 id。
六、总结
其实雪花算法每一部分占用的比特位数量并不是固定死的。例如你的业务可能达不到 69 年之久那么可用减少时间戳占用的位数雪花算法服务需要部署的节点超过1024 台那么可将减少的位数补充给机器码用。
注意雪花算法中 41 位比特位不是直接用来存储当前服务器毫秒时间戳的而是需要当前服务器时间戳减去某一个初始时间戳值一般可以使用服务上线时间作为初始时间戳值。
对于机器码可根据自身情况做调整例如机房号服务器号业务号机器 IP 等都是可使用的。对于部署的不同雪花算法服务中最后计算出来的机器码能区分开来即可。
