雪花算法SnowFlake

SnowFlake 算法结构如下：大致分为了无效位、时间位、机器位和序列号位。

1.第一位：占用1bit，其值始终是0，没有实际作用（因为二进制中最高位是符号位，1表示负数，0表示正数。生成的id一般都是用整数，所以最高位固定为0）。

2.时间戳：占用41bit，精确到毫秒，总共可以容纳约69年的时间。

3.工作机器id：占用10bit，其中高位5bit是数据中心ID，低位5bit是工作节点ID，最多可以容纳1024个节点。

4.序列号：占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生4096个ID。

SnowFlake算法在同一个毫秒内最多可以生成的ID数量：1024 * 4096 = 4194304（400多万）

SnowFlake优点：是全局唯一、自增、有序、纯数字组成查询效率高且不依赖于数据库。

适合在分布式的场景中应用，可根据需求调整具体实现细节。

缺点：趋势自增，依赖于系统时间，雪花算法在单机系统上ID是递增的，

但是在分布式系统多节点的情况下，所有节点的时钟改变或者其他情况，就有可能会出现不是全局递增的情况。

使用hutool生成

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.5.7</version>
</dependency>

使用

//通过雪花算法生成唯一ID
Long workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr()) >> 16 & 31;
//数据中心ID
Long dataCenterId = 1L;
//生成ID
String snowflake = IdUtil.getSnowflake(workerId, dataCenterId).nextIdStr();
long id = snowflake.nextId();

在方法nextId()，使用synchronized，保证多线程下是同步的。

方法tilNextMillis()，使得后面生成的id比上一个id大。

源码分析

public static Snowflake getSnowflake(long workerId, long datacenterId) {
   // 这个方法保证我们获取到的对象是单例的
   return Singleton.get(Snowflake.class, workerId, datacenterId);
}

public synchronized long nextId() {
   // 当前时间戳
   long timestamp = genTime();
   // 上一个时间戳，比当前时间戳还大，说明发生了时钟回拨
   if (timestamp < this.lastTimestamp) {
      if(this.lastTimestamp - timestamp < 2000){
         // 容忍2秒内的回拨，避免NTP校时造成的异常
         timestamp = lastTimestamp;
      } else{
         // 如果服务器时间有问题(时钟后退) 报错。
         throw new IllegalStateException(StrUtil.format("Clock moved backwards. Refusing to generate id for {}ms", lastTimestamp - timestamp));
      }
   }
   // 如果上次时间与当前时间相等（回拨后，也是相等的）
   if (timestamp == this.lastTimestamp) {
      final long sequence = (this.sequence + 1) & sequenceMask;
      if (sequence == 0) {
         timestamp = tilNextMillis(lastTimestamp);
      }
      this.sequence = sequence;
   } else {
      sequence = 0L;
   }

   lastTimestamp = timestamp;

   return ((timestamp - twepoch) << timestampLeftShift) | (dataCenterId << dataCenterIdShift) | (workerId << workerIdShift) | sequence;
}

private long tilNextMillis(long lastTimestamp) {
   long timestamp = genTime();
   // 循环直到操作系统时间戳变化
   while (timestamp == lastTimestamp) {
      timestamp = genTime();
   }
   if (timestamp < lastTimestamp) {
      // 如果发现新的时间戳比上次记录的时间戳数值小，说明操作系统时间发生了倒退，报错
      throw new IllegalStateException(
            StrUtil.format("Clock moved backwards. Refusing to generate id for {}ms", lastTimestamp - timestamp));
   }
   return timestamp;
}