雪花算法SnowFlake 细致易懂 Java/Springboot实现

文章目录

一、雪花算法是什么？

分布式中生成唯一性ID的一种算法。

为啥不用数据库的自增主键呢？

唯一性: 如果数据库数据特别多，你会同一张表建立不同节点上，数据也在不同节点上存，那么如果俩ID都是 001 违背主键定义吗？
顺序性: 雪花算法计算出来ID 有顺序如果你了解数据库 B+树，对于索引来说字段是 数字类型，有顺序，唯一 在查找以及插入效率很高而UUID是字符串没顺序不适合做数据库主键了

二、雪花算法的构成

雪花算法由64位构成ID，对应java数据类型的话 long类型

这里位是二进制位

最左一位（图中没有标出）都是 0 因为二进制中 最左符号位 1代表负数 0是正数 而我们生成ID肯定是正数所以是0
timestamp : 时间戳我们一般情况给初始时间用系统当前时间减去初始时间这个差值的时间戳作为ID的时间戳也就是timestamp占用41位。至于为啥差值作为时间戳 1.减小时间戳长度 2.时钟回拨处理
instance ：这个表示机器个数分布式系统中多个节点可以左边5位是机器的ID 右边5位数据中心ID（机房ID）加起来是10位
sequence：序列号这个主要用途并发执行代码有时候获取时间一样的那么区分ID 用序列号自增进行区分

在这里插入图片描述

时钟回拨： 一种情况管理员手动把时间调整当前系统之前时间，这样的话生成ID和之前ID可能冲突了。虽然上边时间戳插值减轻该问题但是插值仍有可能为正值，

三、雪花算法实现思路

3.1 如何把时间戳，机器ID，序列号等合在一起变成一个long类型数字？

3.2 如果并发访问同一时间对于要生成ID多于2的12次方个也就是多余4096个ID如何处理？

3.3 发生时钟回拨如何处理？

3.1的思路是

首先移动好说的。数据中心ID datacenterID (属于instance) 假设 1L 号用long表示可以（二进制） 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 将它左移动12位（序列号最长位）代码 datacenterID << 12 结果 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 0000 0000
机器ID 左移动 12位（序列号） + 5位（数据中心ID）= 17 workID << 17 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000
我们随便用时间戳差值 1110 0101 1010 0001 0001 10111 11 那么他图中右移12 + 5 + 5 = 22位 0000 0000 0000 0000 1110 0101 1010 0001 0001 10111 1100 0000 0000 0000 0000 0000
序列号最右边所以不用移动 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

接下来如何合并时间戳，机器ID，数据中心ID，序列号呢？
可以将两个long类型按位或进行合并（按位或只要有1 结果1 否则是0）

拿数据中心ID和机器ID举例子

数据ID 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 0000 0000
机器ID 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000

(或 | ）结果 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00

0 000

0000 0000 0000
这样进行合并了 3.1问题解决了。

3.2 问题思路

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

1111 1111 1111 1111

该时间再生成ID就是
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 000

1 0000 0000 0000 0000

对于这个我们构建一个类似于掩码数字二进制表示
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

1111 1111 1111 1111

进行按位与（&）两个都为1结果是1 否则为0
上边两个& 结果刚好

这个结果可以判断是否溢出
对于构建掩码那个数字可以 -1 ^ （-1 << 12)

^ 是异或符号 两个二进制位 不同为1 相同为0

-1 的二进制如下
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111

3.3 问题思路

可以记录上一次时间字段，如果当前时间 < 上一次记录时间发送时钟回拨抛异常提示
可以进行等待，时间过了上一次记录时间进行ID生成
也可以采用更高时间精度来生成时间戳

Clock clock =Clock.systemUTC();long currentTimestamp = clock.millis();

三、Java代码实现

代码如下（示例）：

packagecom;publicclassSnowFlakeUtil{//起始时间戳privatestaticlong startTimeStamp;//机器IDprivatestaticlong workID;//数据中心IDprivatestaticlong  dataCenterID;//序列号privatestaticlong sequence;//数据中心ID移动位数privatestaticlong dataCenterIndex;//机器ID移动位数privatestaticlong workIDIndex;//时间戳移动位数privatestaticlong timeStampIndex;//记录上一次时间戳privatestaticlong lastTimeStamp;//序列号掩码privatestaticlong sequenceMask;//序列号长度12位privatestaticlong sequenceLength;//初始化数据static{
        startTimeStamp =1577808000000L;//设置机器编号 1
        workID =1L;//设置数据中心ID 1
        dataCenterID =1L;//起始序列号 0开始
        sequence =0L;//数据中心位移位数
        dataCenterIndex =12L;//机器ID位移位数
        workIDIndex =17L;//时间戳位移位数
        timeStampIndex =22L;//记录上次时间戳
        lastTimeStamp =-1L;//序列号长度
        sequenceLength =12L;//序列号掩码
        sequenceMask =-1L^(-1L<< sequenceLength);}publicsynchronizedstaticlonggetID(){//获得当前时间long now =System.currentTimeMillis();//当前系统时间小于上一次记录时间if(now < lastTimeStamp){thrownewRuntimeException("时钟回拨异常");}//相同时间 要序列号进制增量if(now == lastTimeStamp){//防止溢出
            sequence =(sequence +1)& sequenceMask;if(sequence ==0L){//溢出处理try{Thread.sleep(1L);}catch(InterruptedException e){thrownewRuntimeException(e);}//获取下一毫秒时间 （有锁）
                now =System.currentTimeMillis();}}else{//置0 之前序列号同一时间并发后自增 到这里说明时间不同了 版本号所以置0
            sequence =0L;}//记录当前时间
        lastTimeStamp = now;//当前时间和起始时间插值 右移 22位long handleTimeStamp =(now - startTimeStamp)<< timeStampIndex;// 数据中心数值 右移动 17位 并且 按位或long handleWorkID =(dataCenterID << dataCenterIndex)| handleTimeStamp;// 机器ID数值 右移动 12位 并且 按位或long handleDataCenterID =(workID << workIDIndex)| handleWorkID;// 序列号 按位或longID= handleDataCenterID | sequence;returnID;}}

//用法调用工具类方法即可long id =SnowFlakeUtil.getID();

四、Springboot代码实现

4.1 Maven引入依赖

<!--  开始属性绑定 配置文件有提示  --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-configuration-processor</artifactId><optional>true</optional></dependency>

4.2 创建 SnowFlakeProperties java文件

注意包名和你项目包路径要一致 该文件放在启动类同级目录或者子目录

packagecom;importorg.springframework.boot.context.properties.ConfigurationProperties;@ConfigurationProperties(prefix ="sf")publicclassSnowFlakeProperties{//起始时间戳privatelong startTimeStamp;//机器IDprivatelong workID;//数据中心IDprivatelong dataCenterID;//序列号privatelong sequence;//数据中心ID移动位数privatelong dataCenterIndex;//机器ID移动位数privatelong workIDIndex;//时间戳移动位数privatelong timeStampIndex;//记录上一次时间戳privatelong lastTimeStamp;//序列号掩码privatelong sequenceMask;//序列号长度12位privatelong sequenceLength;publicSnowFlakeProperties(){//默认时间 2020-1-1 00:00:00this.startTimeStamp =1577808000L;//设置机器编号 1this.workID =1L;//设置数据中心ID 1this.dataCenterID =1;//起始序列号 0开始this.sequence =0L;//数据中心位移位数this.dataCenterIndex =12L;//机器ID位移位数this.workIDIndex =17L;//时间戳位移位数this.timeStampIndex =22L;//记录上次时间戳this.lastTimeStamp =-1L;//序列号长度this.sequenceLength =12L;//序列号掩码 等同于 -1L ^ (-1L << 12)this.sequenceMask =~(-1L<< sequenceLength);}publicSnowFlakeProperties(long startTimeStamp,long workID,long dataCenterID,long sequence,long dataCenterIndex,long workIDIndex,long timeStampIndex,long lastTimeStamp,long sequenceMask,long sequenceLength){this.startTimeStamp = startTimeStamp;this.workID = workID;this.dataCenterID = dataCenterID;this.sequence = sequence;this.dataCenterIndex = dataCenterIndex;this.workIDIndex = workIDIndex;this.timeStampIndex = timeStampIndex;this.lastTimeStamp = lastTimeStamp;this.sequenceMask = sequenceMask;this.sequenceLength = sequenceLength;}publiclonggetStartTimeStamp(){return startTimeStamp;}publicvoidsetStartTimeStamp(long startTimeStamp){this.startTimeStamp = startTimeStamp;}publiclonggetWorkID(){return workID;}publicvoidsetWorkID(long workID){this.workID = workID;}publiclonggetDataCenterID(){return dataCenterID;}publicvoidsetDataCenterID(long dataCenterID){this.dataCenterID = dataCenterID;}publiclonggetSequence(){return sequence;}publicvoidsetSequence(long sequence){this.sequence = sequence;}publiclonggetDataCenterIndex(){return dataCenterIndex;}publicvoidsetDataCenterIndex(long dataCenterIndex){this.dataCenterIndex = dataCenterIndex;}publiclonggetWorkIDIndex(){return workIDIndex;}publicvoidsetWorkIDIndex(long workIDIndex){this.workIDIndex = workIDIndex;}publiclonggetTimeStampIndex(){return timeStampIndex;}publicvoidsetTimeStampIndex(long timeStampIndex){this.timeStampIndex = timeStampIndex;}publiclonggetLastTimeStamp(){return lastTimeStamp;}publicvoidsetLastTimeStamp(long lastTimeStamp){this.lastTimeStamp = lastTimeStamp;}publiclonggetSequenceMask(){return sequenceMask;}publicvoidsetSequenceMask(long sequenceMask){this.sequenceMask = sequenceMask;}publiclonggetSequenceLength(){return sequenceLength;}publicvoidsetSequenceLength(long sequenceLength){this.sequenceLength = sequenceLength;}}

4.3 创建 SnowFlake java文件

packagecom;publicclassSnowFlake{privateSnowFlakeProperties properties;publicSnowFlake(){}publicSnowFlake(SnowFlakeProperties properties){this.properties = properties;}publicsynchronizedlonggetID(){//获得当前时间long now =System.currentTimeMillis();long lastTimeStamp = properties.getLastTimeStamp();//当前系统时间小于上一次记录时间if(now < lastTimeStamp){thrownewRuntimeException("时钟回拨异常");}//相同时间 要序列号进制增量if(now == lastTimeStamp){//防止溢出long sequence = properties.getSequence();
      sequence =(sequence +1)& properties.getSequenceMask();//更新sequence 的值
      properties.setSequence(sequence);if(sequence ==0L){//溢出处理try{Thread.sleep(1L);}catch(InterruptedException e){thrownewRuntimeException(e);}//获取下一毫秒时间 （有锁）
        now =System.currentTimeMillis();}}else{//置0
      properties.setSequence(0L);}//记录当前时间
    properties.setLastTimeStamp(now);return((now - properties.getStartTimeStamp())<< properties.getTimeStampIndex())|(properties.getDataCenterID()<< properties.getDataCenterIndex())|(properties.getWorkID()<< properties.getWorkIDIndex())| properties.getSequence();}}

4.4 在任意@Configuration 或者启动各类加上注解

@EnableConfigurationProperties(SnowFlakeProperties.class)

配置类里这样写即可

@BeanpublicSnowFlakesnowFlake(SnowFlakeProperties properties){returnnewSnowFlake(properties);}

我是这样写的

packagecom;importorg.springframework.boot.context.properties.EnableConfigurationProperties;importorg.springframework.context.annotation.Bean;importorg.springframework.context.annotation.Configuration;@Configuration@EnableConfigurationProperties(SnowFlakeProperties.class)publicclassConfig{@BeanpublicSnowFlakesnowFlake(SnowFlakeProperties properties){returnnewSnowFlake(properties);}}

packagecom;importjava.util.HashMap;importjava.util.Map;importorg.springframework.beans.factory.annotation.Autowired;importorg.springframework.web.bind.annotation.RequestMapping;importorg.springframework.web.bind.annotation.RestController;@RestControllerpublicclassController{//注入即可@AutowiredpublicSnowFlake snowFlake;@RequestMapping("/hello")publicMapgetID(){//这里直接调用该方法 获取雪花算法生成IDlong id = snowFlake.getID();HashMap<Object,Object> map =newHashMap<>();
    map.put("ID",id);
    map.put("Binary",Long.toBinaryString(id));
    map.put("BinaryLength",Long.toBinaryString(id).length());return map;}}

如何设置机器ID，数据中心ID呢？

当然你不设置也可以 默认1号机器 1号数据中心

配置文件
在这里插入图片描述
如果没有提示重新构建项目

由于前端（Web）最大支持53位（二进制）数字所以后端传给前端转换字符串来存否则精度会损失

可以通过配置文件来设置
雪花算法 41位时间戳不要动剩下（53-41=12）剩下12位可以分6位的序列号，数据中心分2位机器ID分4位配置文件如

sf:
  work-i-d:3
  #序列号长度  
  sequence-length:6
  #数据中心位移移 位数  
  data-center-index:6
  #机器ID位移移 位数  
  work-i-d-index:8
  #时间戳位移移 位数  
  time-stamp-index:12

结果如图
在这里插入图片描述

测试

这里机器ID1 数据中心1 序列号0
用JMeter 100个请求并发查询时间相同请求