雪花算法(Snowflake)介绍和Java实现

2024-01-01 07:44

本文主要是介绍雪花算法(Snowflake)介绍和Java实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、雪花算法介绍

(1) 雪花算法(SnowFlake)是分布式微服务下生成全局唯一ID,并且可以做到去中心化的常用算法,最早是Twitter公司在其内部的分布式环境下生成ID的方式。 雪花算法的名字可以这么理解,世界上没有两片完全相同的雪花,而雪花算法希望自己生成的ID是独一无二的。

去中心化可以理解成不需要依赖某一个中间件,比如可以用Redis来生成全局唯一的ID,但Redis此时就属于中心,同时还会需要依赖网络。 而雪花算法通过10位bit的本地标识实现去中心化。

(2) 雪花算法生成的ID特点

  • 64bit位的正整数,即java中的long类型;
  • 整体结构是有序的。

(3) 64个bit位

  • 最高位:0, 代表是 一个正整数;
  • 41位:存储毫秒级的时间戳,在java中可以使用 System.currentMillons()获取,并且保证了自增特性;
  • 10位:存储机房/机器/操作系统/容器/服务的ID;
  • 12位:存储一个自增的序列。

说明:雪花算法内部的bit位数可以进行微调,比如5位机器id和5位服务id组合成10位。

2、Java方式实现雪花算法

(1)整体实现逻辑

64个bit位的long类型的值

第一位:占 1 个bit位,就是0

第二位:占 41 个bit位, 代表时间戳

第三位:占 5 个bit位, 代表机器id (这里将 10 bit 位 做了调整)

第四位:占 5 个bit位,服务id

第五位:占 12 个bit位, 自增序列

(2) 具备知识

  • java实现bit位移运算以及异或运算,用于计算固定bit位代表的最大数值,以及将bit位移动到固定位置。

例如:java中41个bit位的最大数值

long max41Bit = (1L << 41) - 1; // 41 bit 位 可以表示的最大数值 2的42次方减1, 即 1往左移41位减1

(3) 核心逻辑

  1. 先是定义5个位数对应的变量, 以及对应的偏移量,因为需要通过偏移后变量的bit位才能到达固定的位置;
  2. 再是计算自定义的机器id和服务id的最大值,用于严谨校验;
  3. 分别拿到对应的值,然后做位移运算;
  4. 做位移运算时的时间戳不从1900-01-01开始算起,因为41bit位的时间戳大概可用70年。

逻辑难点:在同一毫秒生成多个ID时,当前时间戳 与 自增序列的关系

  1. 拿到当前系统的毫秒值,记录生成上一个ID的毫秒值;
  2. 如果是同一毫秒生成ID,则自增序列递增(递增时要注意不能超出递增序列允许的最大值,超出需要等待下一毫秒);不同毫秒自增序列还原为初始值;
  3. 对于时针回拨问题,需要注意将当前的时间戳与生成的上一个ID的时间戳进行比较。

(4) Java代码具体实现


import org.springframework.beans.factory.annotation.Value;
import javax.annotation.PostConstruct;/*** 雪花算法生成全局唯一的ID* 64个bit位的long类型的值* 第一位:占 1 个bit位,就是0* 第二位:占 41 个bit位, 代表时间戳* 第三位:占 5 个bit位, 代表机器id (这里将 10 bit 位 做了调整)* 第四位:占 5 个bit位,服务id* 第五位:占 12 个bit位, 自增序列*/
public class SnowFlakeUtil {/*** 41 个bit位存储时间戳, 从0开始计算, 最多可以存储 69.7年。* 如果从默认使用, 从1970年到现在,最多可以用到2040年。* 按照从 2023-12-28号开始计算,存储41个bit位, 最多可以使用到2093年*/private long timeStart = 1703692800000L;/*** 机器id, 通过yml配置的方式声明*/@Value("${snowflake.machineId:0}")private long machineId = 0;/*** 服务id, 通过yml配置的方式声明*/@Value("${snowflake.serviceId:0}")private long serviceId = 0;/*** 自增序列*/private long sequence;// 需要做机器id和服务id的兼容性校验, 不能超过了5位的最大值/*** 机器id占用的bit位数*/private long machineIdBits = 5L;/*** 服务id占用的bit位数*/private long serviceIdBits = 5L;/*** 序列占用的bit位数*/private long sequenceBits = 12L;/*** 计算出机器id的最大值 -1 往左移 machineIdBits 位, 再做亦或运算*/private long maxMachineId = -1 ^ (-1 << machineIdBits); // -1 往左移 machineIdBits 位, 再做亦或运算// 11111111 11111111 11111111 11111111 11111111// 11111111 11111111 11111111 11111111 11100000// 00000000 00000000 00000000 00000000 00011111/*** 计算出服务id的最大值*/private long maxServiceId = -1 ^ (-1 << serviceIdBits);/*** 校验 机器id 和 服务id 是否超过最大范围值*/@PostConstructpublic void init() {if (machineId > maxMachineId || serviceId > maxServiceId) {System.out.println("机器id或服务id超过最大范围值");}}/*** 服务id需要位移的位数, 即从右侧开始, 将数字左移 sequenceBits 到固定的位置*/private long serviceIdShift = sequenceBits;/*** 机器id需要位移的位数, 即从右侧开始, 将数字左移 sequenceBits + serviceIdBits  到固定的位置*/private long machineIdShift = sequenceBits + serviceIdBits;/*** 时间戳需要位移的位数, 即从右侧开始, 将数字左移 sequenceBits + serviceIdBits + machineIdBits 到固定的位置*/private long timestampShift = sequenceBits + serviceIdBits + machineIdBits;/*** 序列的最大值 -1 往左移 sequenceBits 位, 再做亦或运算*/private long maxSequenceId = -1 ^ (-1 << sequenceBits);/*** 记录最近一次获取id的时间*/private long lastTimestamp = -1;/*** 拿到当前系统时间的毫秒值** @return*/private long timeGen() {return System.currentTimeMillis();}/*** 生成全局唯一id* 因为有很多服务调用这个方法, 所以需要加sychronized锁*/public synchronized long nextId() {//1. 拿到当前系统时间的毫秒值long timestamp = timeGen();// 避免时间回拨造成出现重复的idif (timestamp < lastTimestamp) {// 说明出现了时间回拨System.out.println("当前服务出现时间回拨");}//2. 41个bit的时间知道了存什么了, 但是序列也需要计算一下。 如果是同一毫秒,序列就需要 还原 或者 ++// 判读当前生成的id的时间 和 上一次生成的时间if (timestamp == lastTimestamp) {// 同一毫秒值生成idsequence = (sequence + 1) & maxSequenceId; // 加1最大值进行与运算, 结果是如果超过了maxSequenceId则为0, 小于则不变if (sequence == 0) {// 进到这个if,说明已经超出了sequence序列的最大取值范围// 需要等到下一个毫秒值再回来生成具体的值timestamp = timeGen();// 写 <= 而不 写 == 是为了避免出现时间回拨的问题while (timestamp <= lastTimestamp) {// 时间还没动timestamp = timeGen();}}} else {// 另一个时间点生成idsequence = 0;}//3. 重新给 lastTimestamp 赋值lastTimestamp = timestamp;//4. 计算id,将几位值拼接起来, 41bit位的时间, 5位的机器, 5位的服务, 12位的序列return ((timestamp - timeStart) << timestampShift) | // 相减的差值 往左移  timestampShift(machineId << machineIdShift) |  // machineId 往左移  machineIdShift(serviceId << serviceIdShift) |  // serviceId 往左移  serviceIdShiftsequence &Long.MAX_VALUE;}
}

这篇关于雪花算法(Snowflake)介绍和Java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。(1)简单定义-什么是

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容:获取整页文本与指定区域内容获取页面上的所有文本内容获取

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

Java使用HttpClient实现图片下载与本地保存功能

《Java使用HttpClient实现图片下载与本地保存功能》在当今数字化时代,网络资源的获取与处理已成为软件开发中的常见需求,其中,图片作为网络上最常见的资源之一,其下载与保存功能在许多应用场景中都... 目录引言一、Apache HttpClient简介二、技术栈与环境准备三、实现图片下载与保存功能1.

canal实现mysql数据同步的详细过程

《canal实现mysql数据同步的详细过程》:本文主要介绍canal实现mysql数据同步的详细过程,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的... 目录1、canal下载2、mysql同步用户创建和授权3、canal admin安装和启动4、canal