雪花算法源码分析

一、概述

第一部分：1个bit位，0代表正数，1代表负数；而我们生成的id都是正数，所以正常都是0

第二部分：41个bit位，表示的是时间戳；41位的时间截，可以使用69年：

(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69           

第三部分：5个bit位：表示的是机房id，最大值：31

第四部分：5个bit位：表示的是机器id，最大值：31

第五部分：12个bit位：表示的序列号，即某个机房里，某台机器上，同一毫秒内生成的id的序号：0000 0000 0000，记录同一个毫秒内产生的不同 id，最大值：4095

二、详解

public class SnowflakeIdWorker {

    /**
     * 开始时间截：固定值，不可为new Date()，否则生成的雪花ID会重复：(2023-01-01)
     */
    private final long startTimestamp = 1672534400000L;

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

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

    /**
     * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 支持的最大数据标识id，结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

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

    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;

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

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

    /**
     * 生成序列的掩码，用位运算计算出12位能存储的最大整数，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long maxSequence = -1L ^ (-1L << sequenceBits);

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

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

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;

    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    /**
     * 获得下一个ID (该方法是线程安全的：synchronized)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        // 获取当前的时间戳
        long currentTimestamp = System.currentTimeMillis();
        // 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (currentTimestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
        }
        if (lastTimestamp == currentTimestamp) {
             /*
            关于&运算：除了 1 & 1 = 1, 其余情况都是: 0
            如果此时：sequence = 4095、且 MAX_SEQUENCE = 4095, 二者进行 & 运算，则最终结果为0
            4095:       0000 1111 1111 1111
            &
            4095 + 1:   0001 0000 0000 0000
            ===============================
            0(重置0)     0000 0000 0000 0000
             */
            // 同一毫秒内，ID自增
            sequence = (sequence + 1) & maxSequence;
            // sequence == 0：代表同一毫秒内 序列数已经达到最大4095, 则需等待下一个毫秒到来再生成
            if (sequence == 0) {
                // 阻塞到下一个毫秒, 并赋值给当前时间戳
                currentTimestamp = getNextTimestamp(lastTimestamp);
            }
        } else {
            // 不是同一毫秒，则序列号重置为0(同一毫秒内序列号回递增，最大值是：4095)
            sequence = 0L;
        }
        // 存储时间戳, 用于下次生成ID时对比是否为同一毫秒内
        lastTimestamp = currentTimestamp;
        // 移位并通过或运算拼到一起组成64位的ID
        return ((currentTimestamp - startTimestamp) << timestampLeftShift) // 时间截向左移22位(5位机房ID + 5位机器ID + 12位序列号)
                | (datacenterId << datacenterIdShift) // 机房ID向左移17位(5位机器ID + 12位序列号)
                | (workerId << workerIdShift) // 机器机器ID向左移12位(12位序列号)
                | sequence; // 最后拼接上序列号部分
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     *
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long getNextTimestamp(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        // 循环获取当前时间戳, 直到拿到下一秒的时间戳
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}           

三、时钟回拨问题

从上述源码可知，雪花ID的生成强依赖时间戳和序列号；

时钟回拨问题：指系统时间主动或被动地回到过去的某个时间，从而导致生成的ID 可能与此前已经生成的某个ID重复（前提条件：刚好在同一毫秒生成 ID 时序列号也刚好一致）。

源码中对于时钟问题的处理是直接抛异常，改进方法有多种，比如：可以等待几毫秒、调整机房ID、机器ID、序列号，为：时钟ID(4位)，机器ID(8位)、序列号(10位)

0 1 010......101 0001 10101010 1010101010

\_/ \___________/ \__/ \______/ \________/

第1位不使用 41位毫秒时间戳 4位时钟ID 8位机器ID 10位序列号

当出现时钟回拨问题时，将时钟 ID 加 1，类似序列号，周而复始。

// 如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
// maxClockId：最大时钟ID：15
// 然后调整左移数据即可
if (currentTimestamp < lastTimestamp) {
		clockId  = (clockId + 1) &maxClockId
 }