手撕雪花 Snow Flake

分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra，因为Cassandra没有顺序ID生成机制，所以开发了这样一套全局唯一ID生成服务。

理论说明

• 能满足高并发分布式系统环境下ID不重复
• 基于时间戳，可以保证基本有序递增（有些业务场景对这个又要求）
• 不依赖第三方的库或者中间件
• 生成效率极高

• 1位，不用。二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0
• 41位，用来记录时间戳（毫秒）。41位可以表示2^41−1个数字，因为要保证自增，不允许回调时间！
• 10位，用来记录工作机器ID。 可以部署在2^10=1024个节点
• 12位，序列号，用来记录同毫秒内产生的不同id。 12位可以表示的最大正整数是2^12−1=4095，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号

额外的，可以在这41+10+12位中，取出一些连续的位，设置为特别需求的标志位，如业务ID啥的

 1L == 0000 0000 0000 0001
-1L == 1111 1111 1111 1111，-1 的补码 为 1 的 反码 +1
-1L << MACHINE_SHIFT：-1 左移 10 位：高位舍弃，低位用 0 补齐，为 1111 1100 0000 0000
则：
  1111 1111 1111 1111
^ 1111 1100 0000 0000
---------------------
= 0000 0011 1111 1111

补充说明

• 当进入下一毫秒时，序列号不应直接置0，因为如果一个业务量恰好1ms生成一次，那出现的结果均为偶数，不利于分库分表，可以根据时间奇偶性，来设定 0 或 1 来改善奇偶性
• 项目的 START_STAMP 是不允许会退的，因为要保证 ID 自增且唯一，如果回退了，有可能会出现重复 ID，当发现时间回退时，应抛出异常
• 当同一毫秒生成数达到最大值时，不能继续生成，否则序列号必然重复，需要自旋等待下一毫秒

Java 代码

package vip.housir;

/**
 * @author housirvip
 */
public class SnowFlake {

    /**
     * 起始的时间戳, 2020-09-14 17:08:33
     * 为保证id递增，不允许回退！！！
     */
    private final static long START_STAMP = 1600074513000L;

    /**
     * 序列号占用的长度
     */
    private final static int SERIAL_LEN = 12;

    /**
     * 机器标识占用的长度
     */
    private final static int MACHINE_LEN = 10;

    /**
     * 最大支持的机器数量
     * -1L ^ (-1L << MACHINE_LEN)
     * 或者
     * ~(-1L << MACHINE_LEN)
     */
    private final static long MAX_MACHINE = -1L ^ (-1L << MACHINE_LEN);

    /**
     * 用位运算计算出12位能存储的最大正整数：4095
     */
    private final static long MAX_SERIAL = -1L ^ (-1L << SERIAL_LEN);

    /**
     * 机器标志的偏移量
     */
    private final static int MACHINE_SHIFT = SERIAL_LEN;

    /**
     * 时间戳的偏移量
     */
    private final static int TIMESTAMP_SHIFT = MACHINE_LEN + SERIAL_LEN;

    private long serialNum = 0L;

    private long lastTimeStamp = -1L;

    private final int machineId;

    public SnowFlake(int machineId) {
      	// MachineID 越界
        if (machineId > MAX_MACHINE) {
            throw new RuntimeException("Machine ID out of the range, MAX_MACHINE: " + MAX_MACHINE);
        }
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return 新的雪花ID
     */
    public synchronized long generateId() {
        // 获取当前时间戳
        long curStamp = getNewStamp();

        // 如果当前时间戳小于上次时间戳则抛出异常
        if (curStamp < lastTimeStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        // 相同毫秒内
        if (curStamp == lastTimeStamp) {
            // 相同毫秒内，序列号自增
            serialNum = (serialNum + 1) & MAX_SERIAL;
            // 同一毫秒的序列数已经达到最大
            if (serialNum == 0L) {
                //自旋，等待下一毫秒
                curStamp = waitNextMill();
            }
        } else {
            // 不同毫秒内，序列号置为初始值，0L或者1L，防止出现全为偶数的情况
            serialNum = curStamp & 1;
        }

        //当前时间戳存档记录，用于下次产生id时对比是否为相同时间戳
        lastTimeStamp = curStamp;

        return ((curStamp - START_STAMP) << TIMESTAMP_SHIFT)
                | (machineId << MACHINE_SHIFT)
                | serialNum;
    }

    private long waitNextMill() {
        long mill = getNewStamp();
        //自旋，等待下一毫秒
        while (mill <= lastTimeStamp) {
            mill = getNewStamp();
        }
        return mill;
    }

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