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 |
| 時鐘同步問題 | 需要額外處理時鐘回撥 |
雪花算法 是一種高效、低成本的全局唯一 ID 方案，適用於 高併發的分佈式系統，但使用時需要考慮機器 ID 分配、時鐘同步等問題。如果業務場景對 ID 長度較為敏感，則可以考慮基於雪花算法的變種方案來縮短 ID 位數。