雪花算法源碼分析

一、概述

第一部分：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
 }