雪花算法介绍

2023-12-31 13:20:13
SnowFlake算法

在这里插入图片描述

据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子组成。在雪花形成过程中,会形成不同的结构分支,所以说大自然中不存在两片完全一样的雪花,每一片雪花都拥有自己漂亮独特的形状。雪花算法表示生成的id如雪花般独一无二。
snowflake是Twitter开源的分布式ID生成算法,结果是一个long型的ID。其核心思想是:使用41bit作为毫秒数,10bit作为机器的ID(5个bit是数据中心,5个bit的机器ID),12bit作为毫秒内的流水号(意味着每个节点在每毫秒可以产生 4096 个 ID),最后还有一个符号位,永远是0。

雪花算法组成结构简介

雪花算法是 64 位 的二进制,一共包含了四部分:

最高位是符号位,默认为0
41位是时间戳,具体到毫秒,41位的二进制可以使用69年;
10位是机器标识,可以全部用作机器ID,也可以用来标识机房ID + 机器ID,10位最多可以表示1024台机器。
12位是计数序列号,12位的序列号能够区分出4096个ID。

雪花算法Id组成介绍

优点:

  1. 一秒内能够生成 4096*1000 个id,基本满足项目需求;
  2. 对比UUID的字符无序, 雪花算法的id保证唯一性的同时,自身还呈递增趋势,可以避免mysql对主键进行重排,页分裂这些负面影响

缺点

如果服务的id不是单独部署,而是直接嵌在各个服务程序里,那么会导致服务器的集群数量有上限,最多不能超过dataCenterId+workerId的最大数;

强依赖系统时钟,如果出现时钟回拨,会导致id重复,影响业务运行;
时钟回拨的场景:

  1. 闰秒回拨

    闰秒,是指为保持协调世界时接近于世界时时刻,由国际计量局统一规定在年底或年中(也可能在季末)对协调世界时增加或减少1秒的调整。由于地球自转的不均匀性和长期变慢性(主要由潮汐摩擦引起的),会使世界时(民用时)和原子时之间相差超过到±0.9秒时,就把协调世界时向前拨1秒(负闰秒,最后一分钟为59秒)或向后拨1秒(正闰秒,最后一分钟为61秒); 闰秒一般加在公历年末或公历六月末。
    全球已经进行了27次闰秒,均为正闰秒。最近一次闰秒在北京时间2017年1月1日7时59分59秒(时钟显示07:59:60)出现。这也是本世纪的第五次闰秒。 [1-2]
    2022年11月18日,科学家和政府代表在法国举行的一次会议上投票决定将在2035年取消闰秒。(百度百科)

这个取消要等到2035年。在这之前还是要注意回拨的问题;
2. NTP(网络时间同步)
3. 人手动回拨

解决措施:
  1. 生成id 检测时间是否回拨,如果回拨过,使用while循环等待,直至到当前时间;(时间回拨过大会阻塞业务)
  2. 不从系统获取当前时间,首次获取时间后,后续的时间运算由自己控制, 序列号满后,给时间加一;(服务器宕机重启,仍会有问题,可以选择将此时间存储起来,避免服务器重启带来的影响)
  3. 当检测到时间回拨时,舍弃当前雪花算法实列,重新设置dataCenterId和workerId创建新的实列;(在回拨时间内,当前的dataCenterId+workerId不可再使用,需要注意后续dataCenterId与workerId的分配)

代码实现:

package cm.redisson;

import lombok.Getter;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;

import java.time.Instant;
import java.time.LocalDate;
import java.time.ZoneOffset;
import java.util.Date;

/**
* Twitter_Snowflake<br>
* SnowFlake的结构如下(每部分用-分开):<br>
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
* 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>
* 41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
* 得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。
* 41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
* 10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>
* 12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>
* 加起来刚好64位,为一个Long型。<br>
* SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高
*/
@Getter
@Setter
@Slf4j
public class SnowflakeId {

  /**
   * 开始时间截 (2015-01-01)
   */
  private final long startTime = LocalDate.of(2023, 3, 1).atStartOfDay(ZoneOffset.systemDefault()).toInstant()
          .toEpochMilli();
  ;

  /**
   * 机器id所占的位数
   */
  private final long workerIdBits = 5L;

  /**
   * 数据标识id所占的位数
   */
  private final long dataCenterIdBits = 5L;

  /**
   * 序列在id中占的位数
   */
  private final long sequenceBits = 12L;

  /**
   * 数据标识id向左移17位(12+5)
   */
  private final long dataCenterIdShift = sequenceBits + workerIdBits;

  /**
   * 时间截向左移22位(5+5+12)
   */
  private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;

  /**
   * 生成序列的掩码
   */
  private final long maxSequence = ~(-1L << sequenceBits);

  /**
   * 工作机器ID(0~31)
   */
  private long workerId;

  /**
   * 数据中心ID(0~31)
   */
  private long dataCenterId;

  /**
   * 毫秒内序列 0~maxSequence
   */
  private long sequence;

  /**
   * 上次生成ID的时间截
   */
  private long lastTimestamp = System.currentTimeMillis();

  // ==============================Constructors=====================================

  /**
   * 构造函数
   *
   * @param workerId     工作ID (0~31)
   * @param dataCenterId 数据中心ID (0~31)
   */
  public SnowflakeId(long workerId, long dataCenterId, long workerIdBits, long dataCenterIdBits) {
      if (workerId > ~(-1L << workerIdBits) || workerId < 0) {
          throw new IllegalArgumentException(
                  String.format("workerId can't be greater than %d or less than 0", ~(-1L << workerIdBits)));
      }
      if (dataCenterId > ~(-1L << dataCenterIdBits) || dataCenterId < 0) {
          throw new IllegalArgumentException(
                  String.format("dataCenterId can't be greater than %d or less than 0", ~(-1L << dataCenterIdBits)));
      }
      this.workerId = workerId;
      this.dataCenterId = dataCenterId;
  }



  /**
   * 测试示例
   */
  public static void main(String[] args) {

//        SnowflakeId idWorker = new SnowflakeId(1, 1, 9, 1);
//        StopWatch stopWatch = new StopWatch();
//        stopWatch.start();
//        for (int i = 0; i < 1000000; i++) {
//            idWorker.nextId();
//        }
//        stopWatch.stop();
//        System.out.println(stopWatch.prettyPrint());
//        System.out.println(stopWatch.getTotalTimeMillis());
// 11111111111111111111111111111111  10000000000000000000000000000000
      System.out.println(Integer.toBinaryString(-2147483648));
      System.out.println(Integer.toBinaryString(1));
      System.out.println(Integer.valueOf("-10000000000000000000000000000000", 2));
      System.out.println(Integer.MIN_VALUE);
      System.out.println(~(-1L << 41));
      System.out.println(Date.from(Instant.ofEpochMilli(2199023255551L)));

      byte b = Byte.parseByte("1", 2);
      System.out.println(b);


  }

  /**
   * 获得下一个ID
   *
   * @return SnowflakeId
   */
  public synchronized long nextId() {

      long timestamp = timeGen();

      if (timestamp < lastTimestamp) {
          if (lastTimestamp - timestamp < 2000) { // 短时间的回拨进行等待
              tilNextMillis(lastTimestamp);
          } else {
              throw new TimeCallBackException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp), lastTimestamp, timestamp);
          }
      }

      // 如果是同一时间生成的,则进行毫秒内序列递增
      if (lastTimestamp == timestamp) {
          sequence = (sequence + 1) & maxSequence; 
          // 毫秒内序列溢出
          if (sequence == 0) {
              // 阻塞到下一个毫秒,获得新的时间戳
              timestamp = tilNextMillis(lastTimestamp);
          }
      }
      // 时间戳改变,毫秒内序列重置
      else {
          sequence = 0L;
      }

      lastTimestamp = timestamp;
      return ((timestamp - startTime) << timestampLeftShift)
              | (dataCenterId << dataCenterIdShift)
              | (workerId << sequenceBits)
              | sequence;
  }

  /**
   * 阻塞到下一个毫秒,直到获得新的时间
   *
   * @param lastTimestamp 上次生成ID的时间截
   * @return 当前时间戳
   */
  protected long tilNextMillis(long lastTimestamp) {
      long timestamp = timeGen();
      while (timestamp <= lastTimestamp) {
          timestamp = timeGen();
      }
      return timestamp;
  }

  /**
   * 返回以毫秒为单位的当前时间
   *
   * @return 当前时间(毫秒)
   */
  protected long timeGen() {
      return System.currentTimeMillis();
  }


  @Getter
  public static class TimeCallBackException extends RuntimeException {

      public TimeCallBackException(String message) {
          super(message);
      }

      public TimeCallBackException(String message, long lastTime, long currentTime) {
          super(message);
          this.lastTime = lastTime;
          this.currentTime = currentTime;
      }

      /**
       * 最后一次生成Id的时间
       */
      long lastTime;

      /**
       * 当前时间
       */
      long currentTime;


  }

}


对dataCenterId和workerId的分配问题:

现在都是云服务支持容器自动扩容, 配置文件配置 dataCenterId 与workerId 不太现实, 可以使用redis进行竞争的方式获取dataCenterId与workerId;

文章来源:https://blog.csdn.net/weixin_44084735/article/details/135276535
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。