20250213 隨筆雪花算法

雪花算法（Snowflake Algorithm）

雪花算法（Snowflake） 是 Twitter 在 2010 年開發的一種 分布式唯一 ID 生成算法，它可以在 高併發場景下快速生成全局唯一的 64-bit 長整型 ID，且不依賴資料庫，具備 有序性、低延遲、高可用性 等特性。

1. 雪花算法 ID 結構

雪花算法生成的 ID 是一個 64-bit（8 字節）長整型數字，其組成結構如下：

  0 | 41bit 时间戳 | 10bit 机器ID | 12bit 序列号

每一個 ID 的 64-bit 被劃分成以下幾個部分：

位數	名稱	說明
1 bit	符號位	固定為 `0`，因為 Snowflake ID 是正數
41 bits	時間戳（毫秒級）	表示當前 ID 生成的時間
10 bits	機器 ID（Worker ID）	用於區分不同的機器或節點
12 bits	序列號（Sequence）	用於同一毫秒內的流水號（防止並發衝突）

2. 雪花算法 ID 生成邏輯

雪花算法的生成規則如下：

獲取當前時間戳（毫秒級），並去掉符號位，只保留 41-bit（大約可用 69 年）。
拼接機器 ID（Worker ID），確保在分布式環境中每台機器的 ID 唯一（10-bit，最多支持 1024 台機器）。
在同一毫秒內累加序列號（Sequence Number），如果超過 12-bit（最大 4096），則等待下一毫秒。
將上述部分組合成 64-bit 整數，並返回。

3. 為什麼使用雪花算法？

✅ 優勢

全球唯一性：ID 由時間戳 + 機器 ID + 序列號組成，確保唯一性。
趨勢有序性：由於前 41-bit 是時間戳，因此 ID 大致是遞增的（但不是嚴格連續）。
高效能：ID 生成完全本地化，不依賴數據庫，每台機器每毫秒可生成 4096 個 ID，並發性能高。
適合分布式系統：機器 ID 區分不同節點，不會因多節點並行生成導致衝突。

⚠️ 缺點

依賴系統時鐘
- 若 機器時鐘回撥（時間倒退），可能導致 ID 重複，需要額外處理（如阻塞、報錯、時鐘同步）。
ID 不連續
- ID 是趨勢遞增的，但 由於多機器、多併發生成 ID，ID 可能不連續，不適合用來作為數據庫的主鍵索引（可搭配 分段索引）。
機器 ID 配置需要規劃
- 10-bit 只能支持 1024 台機器，如果機器超過 1024 需要進一步優化（如 機房 ID + 機器 ID）。

4. 雪花算法的 Java 實現

public class SnowflakeIdGenerator {
    private final static long START_TIMESTAMP = 1609459200000L; // 起始時間戳（2021-01-01）
    private final static long WORKER_ID_BITS = 10L; // 機器 ID 佔用 10-bit
    private final static long SEQUENCE_BITS = 12L; // 序列號佔用 12-bit

    private final static long MAX_WORKER_ID = (1L << WORKER_ID_BITS) - 1; // 1023
    private final static long MAX_SEQUENCE = (1L << SEQUENCE_BITS) - 1; // 4095

    private final static long WORKER_ID_SHIFT = SEQUENCE_BITS; // 機器 ID 左移位數
    private final static long TIMESTAMP_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS; // 時間戳左移位數

    private long workerId; // 當前機器 ID
    private long sequence = 0L; // 當前毫秒內的序列號
    private long lastTimestamp = -1L; // 記錄上一次的時間戳

    public SnowflakeIdGenerator(long workerId) {
        if (workerId > MAX_WORKER_ID || workerId < 0) {
            throw new IllegalArgumentException("Worker ID 超過範圍");
        }
        this.workerId = workerId;
    }

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();

        // 時鐘回撥處理
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("時鐘倒退，請求被拒絕");
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) {
                while (timestamp <= lastTimestamp) {
                    timestamp = System.currentTimeMillis(); // 等待下一毫秒
                }
            }
        } else {
            sequence = 0;
        }

        lastTimestamp = timestamp;

        return ((timestamp - START_TIMESTAMP) << TIMESTAMP_SHIFT) | (workerId << WORKER_ID_SHIFT) | sequence;
    }
}

這段程式碼：

保證了多執行緒安全性（使用 synchronized 保證 ID 唯一）。
防止時鐘回撥導致的重複 ID 問題（如果發生時間回撥，則拋異常）。
ID 趨勢遞增（由於高位是時間戳）。

5. 雪花算法的應用場景

場景	使用雪花算法的優勢
分佈式數據庫主鍵 ID	避免數據庫 ID 自增帶來的競爭
訂單號生成	高併發下快速生成唯一訂單號
日誌 ID、追蹤 ID	方便分佈式系統中日誌的追蹤
消息隊列（Kafka、RocketMQ）	保證消息的唯一性與排序
分佈式鎖的標識符	避免鎖 ID 重複

6. 變種與優化

1. 進一步縮短 ID 長度

如果 64-bit ID 太長，可以考慮：

減少時間戳位數（如用秒級而非毫秒級）。
減少機器 ID 或序列號位數。

2. 多機房支持

如果 機器 ID 不夠（超過 1024 台機器），可以：
- 拆分機器 ID → 5-bit 機房 ID + 5-bit 機器 ID（最多支持 32 個機房，每個機房 32 台機器）。

7. 總結

特性	描述
高性能	毫秒級生成唯一 ID，不依賴 DB
全球唯一性	基於時間 + 機器 ID + 序列號組成
趨勢遞增	保持 ID 有序性（但不連續）
高併發	每台機器每毫秒可產生 4096 個 ID
時鐘同步問題	需要額外處理時鐘回撥