SnowFlake

Twitter 的 雪花算法 算法的 Java 实现版本。

算法思路

8字节（64位）占位的模式

主要分为以下四个部分：时间序列|数据中心序列|机器序列|自增序列

在当前代码中的大小设置如下：

• 时间序列：42 位，每 139 年开始重复
• 数据中心序列：5 位，共能承载 32 个数据中心
• 机器序列：5 位，共能承载 32 台机器（ID 生成机器）
• 自增序列：12 位，值的范围为：0 ～ 4095

算法调整说明

  在实际开发中可以根据自己的需要去调整每个序列的占位比，如 DC 可能不会有那么多，而机器会偏多，此时可扩宽机器序列位，减少 DC 序列位。同样的，可以为了简便，采用 int 型（4 字节，32 位）来处理，或者采用 String 灵活调节字节数。

测试运行

• 编译：javac SnowFlake.java
• 运行：java SnowFlake

注意事项

注意不同机器、不同 DC 需要配置不同的值序列号，如果配置了相同的值，就会造成长生相同 ID。

PS: 很多人在灰度发布、或者实例扩容的时候容易忘记更改机器的序列号。

实现

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.atomic.LongAdder;

/**
 * twitter的snowflake算法 雪花算法，用于生成long型ID ID为64位Long。 从高位算起，第一部分为 毫米时间戳， 占 64 - 22
 * = 42 位。其次数据中心5位，机器标识5位，最后同一毫秒内的序列号12位。
 */
public class SnowFlake {

  /**
   * 起始的时间戳 2018-08-20
   */
  private static final long START_TIMESTAMP = 1534694400000L;

  /**
   * 每一部分占用的位数
   */
  private static final long SEQUENCE_BIT = 12; // 序列号占用的位数
  private static final long MACHINE_BIT = 5; // 机器标识占用的位数
  private static final long DATA_CENTER_BIT = 5;// 数据中心占用的位数

  /**
   * 每一部分的最大值
   */
  private static final long MAX_DATA_CENTER_NUM = (1L << DATA_CENTER_BIT) - 1;
  private static final long MAX_MACHINE_NUM = (1L << MACHINE_BIT) - 1;
  private static final long MAX_SEQUENCE = (1L << SEQUENCE_BIT) - 1;

  /**
   * 每一部分向左的位移
   */
  private static final long MACHINE_LEFT = SEQUENCE_BIT;
  private static final long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
  private static final long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

  private final long dataCenterId; // 数据中心
  private final long machineId; // 机器标识
  private long sequence = 0l; // 序列号
  private long lastTimestamp = -1L;// 上一次时间戳

  /**
   * constructor
   *
   * @param dataCenterId
   * @param machineId
   */
  public SnowFlake(long dataCenterId, long machineId) {
    if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
      throw new IllegalArgumentException("dataCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0");
    }
    if (machineId > MAX_MACHINE_NUM || machineId < 0) {
      throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
    }
    this.dataCenterId = dataCenterId;
    this.machineId = machineId;
  }

  /**
   * 产生下一个ID
   *
   * @return
   */
  public synchronized long nextId() {
    long curStamp = getNewTimestamp();
    if (curStamp < lastTimestamp) {
      throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
    }

    if (curStamp == lastTimestamp) {
      // 相同毫秒内，序列号自增
      sequence++;
      // 同一毫秒的序列数已经达到最大，则等待下一毫秒，且重制sequence
      if (sequence > MAX_SEQUENCE) {
        curStamp = getNextMill();
        sequence = 0L;
      }
    } else {
      // 不同毫秒内，序列号置为0
      sequence = 0L;
    }

    lastTimestamp = curStamp;
    return (curStamp - START_TIMESTAMP) << TIMESTAMP_LEFT // 时间戳部分
        | dataCenterId << DATA_CENTER_LEFT // 数据中心部分
        | machineId << MACHINE_LEFT // 机器标识部分
        | sequence; // 序列号部分
  }

  private long getNextMill() {
    long mill = getNewTimestamp();
    while (mill <= lastTimestamp) {
      mill = getNewTimestamp();
    }
    return mill;
  }

  private long getNewTimestamp() {
    return System.currentTimeMillis();
  }

  public static void main(String[] args) {
    SnowFlake snowFlake = new SnowFlake(1, 1);
    Set<String> ids = new HashSet<>();
    for (int i = 0; i < 1000000; i++) {
      long id = snowFlake.nextId();
      ids.add(String.valueOf(id));
      System.out.println(id);
    }
    System.out.println(ids.size());
  }

}

可参见： source code