雪花算法介绍

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。

优点：

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;