如何設計分散式唯一 ID 產生器？

題目與適用情境

請設計一個跨 4 個區域的分散式唯一 ID 產生器。每個區域最多 200 個產生節點，叢集尖峰為每秒 200 萬次發號，單一節點在任意 1 毫秒內最多產生 3,000 個 ID。ID 必須是正數 64 位元整數、全域唯一、大致依產生時間排序，至少使用 60 年；熱路徑不能為每個 ID 發出網路請求。目標延遲為 p99 不超過 5 毫秒，目標可用性為 99.99%，但發現可能重複時必須優先保證唯一性並停止發號。

本題允許 ID 有空號，也不要求跨區域嚴格單調。ID 作為內部訊息和資料庫主鍵，暫時不要求不可預測；若要暴露給不受信任的客戶端，需要另行處理資訊洩漏。上述容量與 SLO 都是面試演算限制，不代表任何公司的真實流量。

這道題適用於中高階後端、基礎架構與系統設計職缺。核心任務是把壽命、節點數和毫秒突發量轉成位元預算，再證明在時鐘、並行和 worker 身分故障下仍不會重複。只回答「使用 Snowflake」尚未完成設計。

面試官考察重點

第一，能否區分唯一性、順序性、連續性與不可預測性。Snowflake 可以提供唯一且趨勢有序的 64 位元整數，不會自動提供無空號序列、跨區域因果順序或安全權杖。不同需求會直接改變方案。

第二，能否從限制推導位元配置。好的回答會計算 41 位元毫秒時間、10 位元節點和 12 位元序號各自能涵蓋什麼，並檢查 60 年、800 個節點和每節點每毫秒 3,000 次是否同時成立，不會先照抄經典配置再找需求。

第三，能否證明「不會重複」。正確性依賴三個條件：同一碰撞時間窗內 worker 編碼只有一個有效擁有者；同一 worker 在同一毫秒內不重用序號；時鐘回撥或重啟不能讓同一 worker 重新進入已使用的時間與序號組合。

第四，能否完整設計異常路徑。序號用盡、時鐘倒退、租約遺失、舊程序復活、區域隔離和時間欄位耗盡，都可能破壞唯一性或可用性。面試官要看到明確的停止條件、警示和復原流程。

第五，能否在 Snowflake、UUIDv7、隨機 UUID 和集中號段之間依限制選擇。64 位元與無逐次協調使 Snowflake 適合本題；若允許 128 位元並希望移除 worker 註冊，UUIDv7 會成為更簡單的候選。

回答前需要釐清的問題

• 唯一性是確定性要求，還是可接受極小碰撞機率？ 確定性要求需要隔離 worker 命名空間；接受機率保證時，UUIDv4 或 UUIDv7 可以省去 worker 分配。
• 必須是 64 位元嗎？ 若資料庫、協定和索引允許 128 位元，標準 UUIDv7 提供時間前綴與隨機空間，控制平面更簡單。本題固定正數 64 位元。
• 「有序」有多強？ 大致依時間排序可以使用本地時鐘；跨區域嚴格全序需要集中 sequencer、共識日誌或依業務分割的序列，代價完全不同。
• 允許空號嗎？ 預先分配號段、程序崩潰和重試都可能產生空號。若同時要求無空號與全域嚴格遞增，發號會進入串行交易路徑。本題允許空號。
• ID 是否公開？ 時間和 worker 位元可能洩漏建立時間與部署資訊，連續或趨勢遞增值也可被列舉。內部主鍵可以接受；公開識別碼應增加獨立不透明 ID。
• 節點如何建立和替換？ 固定機器、容器編排和自動擴縮對 worker 身分重用的風險不同。動態節點需要租約、fencing 與安全重用規則。
• 發生網路分割時優先什麼？ 本題允許各區域在本地控制平面健康且租約有效時繼續發號；無法證明 worker 獨占時停止該 worker，犧牲部分可用性。

30 秒回答框架

「我先把 64 位元拆成 1 位固定符號位、41 位毫秒時間、10 位區域加 worker、12 位同毫秒序號。它涵蓋約 69.7 年、1,024 個 worker 編碼和每 worker 每毫秒 4,096 個 ID，滿足題設。每個節點在本地加鎖產生 (timestamp, worker, sequence)，熱路徑不存取網路。區域控制平面只負責分配與續租 worker；租約失效、時鐘回撥或序號溢位時禁止回繞。這個方案只保證趨勢有序，不保證跨區域嚴格全序。若允許 128 位元並想移除 worker 註冊，我會優先評估 UUIDv7。」

分步深入解析

第一步：先用限制排除不合適的預設答案

集中資料庫自動遞增可以提供清楚順序，但每次發號都進入共享寫入路徑，不符合熱路徑無網路呼叫與區域隔離要求。批次領取號段可以攤薄協調成本，卻會在節點崩潰時留下空號；本題允許空號，因此它是可行備選，但仍需要號段服務和預取策略。

UUIDv4 與 UUIDv7 都是 128 位元。UUIDv4 的隨機配置不提供時間排序；UUIDv7 依 RFC 9562 把 48 位元 Unix 毫秒時間放在高位，其餘空間包含版本、變體和隨機位元，可在不註冊 worker 的情況下產生大致有序的值。它們不符合本題的 64 位元硬限制。

因此選擇 Snowflake 風格的 64 位元配置。這裡的「無協調」只指每次發號的熱路徑；worker 身分分配仍需要控制平面。把控制平面成本藏起來不表示系統沒有協調。

第二步：從容量推導 1 + 41 + 10 + 12 位元配置

正數有符號 64 位元整數保留最高位為 0，剩餘 63 位元這樣分配：

| 欄位 | 位元數 | 可表達範圍 | 與題設的關係 | |---|---:|---:|---| | 符號位 | 1 | 固定為 0 | 保持為正數 BIGINT | | 自訂紀元後的毫秒數 | 41 | 2^41 毫秒，約 69.7 年 | 高於 60 年壽命要求 | | 區域 + worker | 10 | 1,024 個編碼 | 2 位區域 × 8 位區域內 worker，可支援 4 × 256 個節點 | | 同毫秒序號 | 12 | 0–4,095，共 4,096 個 | 高於每節點每毫秒 3,000 次的上限 |

位元數總和為 1 + 41 + 10 + 12 = 64。題設最多 4 × 200 = 800 個節點，低於 1,024；每區域 200 個節點也低於 8 位元能表達的 256。41 位元時間約為 2^41 ÷ 1000 ÷ 60 ÷ 60 ÷ 24 ÷ 365.2425 = 69.7 年。為嚴格符合「正數」，實作保留全零 ID，並把自訂紀元設在首次發號之前；即使第一個 worker 的序號為 0，也不會回傳 0。

叢集每秒 200 萬是容量總量，序號欄位必須檢查更尖銳的「單 worker 單毫秒突發」。不能用每秒平均值證明 12 位元足夠。若實際突發超過 4,096，即使全域 QPS 不高，同一節點仍會溢位。

第三步：設計本地產生演算法並證明唯一性

每個 worker 使用 64 位元整數運算，並以鎖或原子臨界區保護 lastMs 與 sequence：

nextId():
  lock
  now = wallClockMs() - customEpochMs
  if now < lastMs:
    fail("clock_moved_back")
  if now == lastMs:
    if sequence == 4095:
      now = waitUntilAfter(lastMs)
      sequence = 0
    else:
      sequence = sequence + 1
  else:
    sequence = 0
  lastMs = now
  return (now << 22) | (workerCode << 12) | sequence

不能在序號達到 4,095 後用遮罩安靜地回到 0；那會在同一毫秒產生重複值。第 4,096 個取值仍合法，因為序號從 0 開始；同一毫秒的第 4,097 次請求必須等待下一毫秒或收到過載錯誤。

唯一性可以依二元情況證明：不同 worker 的 10 位元編碼不同；同一 worker 在不同毫秒的 41 位元時間不同；同一 worker 在同一毫秒的 12 位元序號不同。只要欄位不越界、worker 不被同時重用且時鐘不回到舊狀態，完整 63 位元承載值就不會重複。

第四步：把 worker 身分放進控制平面

每個區域部署獨立 worker 租約分配器，區域的 2 位元編碼由部署設定固定。控制平面記錄：

| 欄位 | 用途 | |---|---| | regionid、workerid | 形成 10 位元全域 worker 編碼 | | owner_id | 識別目前程序或部署實例 | | fencing_token | 區分同一 worker 的新舊擁有者 | | leaseexpiresat | 限制所有權有效期 | | timestampceilingms | 限制舊擁有者最多能使用的時間值，供安全重用 |

節點啟動時領取 worker ID 與租約，發號熱路徑只檢查記憶體中的 owner、fencing 狀態、租約安全截止時間和 now <= timestampceilingms；續租非同步完成，不為每個 ID 存取控制平面。租約失效或時間到達上界後，節點立即停止發號。控制平面讓替代節點重用同一 worker ID 前，必須 fencing 舊擁有者，並讓新節點時鐘超過舊租約允許的 timestampceilingms。如此即使舊節點延遲停止，新舊擁有者也不會使用同一時間區間。

fencing token 沒有編碼進最終 ID，所以它不能在發生衝突後「修復」重複 ID；它的作用是阻止舊擁有者繼續進入發號路徑。無法可靠 fencing 的平台應為部署槽分配長期不重用的 worker ID，或改用 UUIDv7，不能假設租約天然解決程序復活。

第五步：明確時鐘、溢位與分割時的停止條件

執行中發現 now < lastMs 時，策略必須有界。範例策略是：回撥不超過 5 毫秒且請求剩餘延遲預算足夠時等待時鐘追上；等待時間計入 5 毫秒 p99 預算。更大回撥或預算不足時立即回傳可重試錯誤、移除節點並發出警示。程序啟動時還要把目前時間與該 worker 的持久化時間上界比較，落後時拒絕啟動。只在記憶體儲存 lastMs 無法涵蓋重新啟動。

序號耗盡時等待下一毫秒並記錄 sequence_exhausted；頻繁觸發表示負載傾斜或位元預算錯誤，應分散流量、增加 worker，或在下一代格式增加序號位元。嚴禁回繞。

區域與全域網路隔離時，2 位元區域欄位仍隔離命名空間。現有 worker 可以在區域內租約有效時繼續本地發號；區域租約服務不可用且安全期限耗盡後停止相關節點。唯一性優先於 99.99% 可用性目標，這個降級必須事先寫入 SLO 例外和警示。

41 位元時間最後會耗盡。系統應暴露剩餘紀元壽命並提前多年遷移；不能在溢位後把時間清零，也不能在同一 64 位元欄位中安靜改變位元配置。新增區域或擴大 worker 數也要走相同的格式遷移，不能在線重新解讀舊 ID。

第六步：限定「有序」和「安全」的真實含義

時間位元位於高位，使 ID 趨勢有序，但不同機器的時鐘誤差會讓較晚建立的記錄得到較小 ID；同一毫秒內，worker 位元也會影響排序。因此 Snowflake ID 不能證明跨區域因果關係，也不能替代支付帳本的提交序列。

如果 API 使用 id > cursor 做增量同步，時鐘偏慢節點較晚到達的小 ID 可能被永久略過。需要完整順序時，應使用資料庫提交序列、共識日誌位置，或把 sequencer 縮小到對話、帳戶等業務分割；Snowflake 只負責身分。

原始 ID 還會暴露近似建立時間，也可能洩漏區域或 worker 位元。它不是授權憑證。公開資源可以同時保存內部 64 位元主鍵和獨立的不透明外部識別碼；不要依賴「使用者猜不到 ID」保護資料。

第七步：依限制比較替代方案

| 方案 | 位元寬度與順序 | 協調方式 | 更適合的條件 | 主要代價 | |---|---|---|---|---| | Snowflake 風格 | 64 位元，趨勢有序 | 啟動/續租時協調，熱路徑本地 | 64 位元、極高吞吐量、允許近似順序 | 時鐘與 worker 管理複雜 | | UUIDv7 | 128 位元，時間前綴 | 無 worker 註冊 | 接受 128 位元，希望標準化且移除 worker 控制平面 | 更寬；唯一性依賴隨機品質與實作 | | UUIDv4 | 128 位元，隨機無序 | 無協調 | 不需要排序、重視不透明性 | 索引局部性較差，無法從 ID 推斷時間 | | 集中 sequencer / 號段 | 通常 64 位元，可嚴格或趨勢遞增 | 服務或資料庫分配；號段可批次 | 需要集中排序，或業務已依賴資料庫 | 網路/資料庫依賴；批次會產生空號 |

本題的 64 位元硬限制與無逐次網路呼叫使 Snowflake 勝出。若面試官取消 64 位元要求，UUIDv7 應重新參與決策；若要求嚴格全序，應承認 Snowflake 不符合需求並改用序列化 sequencer，不能繼續加補丁。

第八步：用故障注入驗證設計

驗證不能停在「產生一批沒有重複」。至少涵蓋：

1. 凍結時鐘，在同一 worker 同一毫秒產生 4,096 個 ID，確認全部唯一；第 4,097 次必須等待或失敗。
2. 並行呼叫同一產生器，驗證本地臨界區不會讓兩個執行緒重用序號。
3. 讓時鐘分別回撥 1、5 和 2,000 毫秒，核對等待、逾時、移除與警示分支。
4. 模擬舊 owner 暫停、租約過期、新 owner 接管、舊 owner 恢復，確認 fencing 後舊程序不能發號。
5. 在 4 個區域、800 個 worker 上凍結相同毫秒並產生不同序號，檢查解碼後的欄位範圍與全域唯一性。
6. 隔離區域租約服務，確認有效租約內繼續、超過安全截止時間後失敗關閉。
7. 把時間推進到 2^41 - 1，確認下一刻拒絕產生並觸發遷移警示。

線上至少監控 clockrollbackms、sequence_exhausted、租約續期失敗、有效 worker 餘量、發號延遲、錯誤率和紀元剩餘壽命。資料庫唯一限制可以作為最後防線與警示來源，但不能用捕捉衝突後重試取代產生器正確性。

高品質示範回答

「我先確認這道題要確定性唯一的正數 64 位元 ID，允許空號，只要求趨勢有序。容量是 4 個區域、每區域 200 個 worker，單 worker 每毫秒最多 3,000 個，所以我選擇 Snowflake 風格，不使用 128 位元 UUIDv7 或每次存取集中 sequencer。

64 位元中最高位固定為 0。41 位元保存自訂紀元後的毫秒數，可使用約 69.7 年；10 位元 worker 拆成 2 位元區域和 8 位元區域內編號，涵蓋 4 × 256 個節點；12 位元序號提供每 worker 每毫秒 4,096 個值。三項都高於題設，同時正好使用 63 位元承載值。

每個 worker 在本地臨界區維護 lastMs 和 sequence。時間前進時序號歸零，同毫秒時遞增，達到 4,095 後等待下一毫秒。時間回撥不允許繼續：小於 5 毫秒可以在延遲預算內等待，更大回撥就移除並發出警示。如此不同 worker 由 worker 位元區分，同 worker 不同毫秒由時間位元區分，同 worker 同毫秒由序號區分。

我會在每個區域設置 worker 租約控制平面。節點只在啟動和非同步續租時存取它，熱路徑本地產生。舊 owner 遺失租約後停止；worker ID 被重用前先 fencing 舊 owner，並讓新 owner 的時間越過舊租約上界。無法證明獨占時寧可停止發號。

最後我會強調這只是趨勢有序。跨區域嚴格順序要使用共識日誌或業務分割 sequencer；公開不可列舉 ID 要另加不透明識別碼。驗證會涵蓋 4,097 次同毫秒請求、並行序號、2 秒回撥、租約接管和紀元耗盡，不只測試正常路徑。」

常見錯誤

• 直接說「用 UUID」→ 沒有確認 64 位元、順序和碰撞語意 → 先區分 UUIDv4、UUIDv7 與確定性 worker 命名空間。
• 照抄 41-10-12 → 不知道節點、壽命或突發是否放得下 → 分別計算 2^41 毫秒、2^10 worker 和 2^12 序號。
• 只用叢集每秒平均 QPS → 單節點單毫秒突發仍可能耗盡序號 → 容量驗證使用最小時間粒度和最熱 worker。
• 序號溢位後按位元回繞 → 同一 worker、同一毫秒會立即重複 → 等待下一毫秒、背壓或回報錯誤。
• 把 worker ID 寫進設定就結束 → 擴縮容、舊程序復活和設定複製會產生雙 owner → 設計租約、fencing、重用隔離和停止條件。
• 回撥時繼續使用目前系統時鐘 → 同一時間與序號組合可能再次使用 → 有界等待或失敗關閉，並涵蓋重啟時的高水位檢查。
• 把趨勢有序稱為全域單調 → 時鐘誤差和多 worker 並行會改變順序 → 需要嚴格順序時引入序列化日誌或分割 sequencer。
• 把 ID 當成權限控制 → 可解碼或可列舉 ID 不提供授權 → 公開面使用獨立不透明識別碼，伺服器端仍執行權限檢查。
• 只測百萬次隨機產生 → 正常隨機負載很難觸發邊界 → 凍結時鐘並注入回撥、租約接管和欄位耗盡。

追問與應對

追問一：如果要求跨區域嚴格遞增且沒有空號呢？

Snowflake 不再適用。嚴格全序需要所有發號經過一個線性化點，例如共識日誌中的單一序列狀態；無空號還表示編號只能與成功交易一起提交，不能靠預取號段提升吞吐量。網路分割時少數側必須停止，延遲、吞吐量和可用性都會下降。先追問業務是否真的需要「無空號」，許多稽核情境只需要不可竄改的業務流水號，不需要把資料庫主鍵也變成連續序列。

追問二：擴展到第 5 個區域或每區域 300 個 worker 怎麼辦？

目前 2 位元區域和 8 位元區域內 worker 已無法表達。可以在上線前重新分配 10 位元，例如增加區域位元並減少每區域 worker 位元；但既有 ID 不能在線依新配置重新解讀。已投入使用時，應引入明確的新格式或遷移到 128 位元 ID，並讓讀寫鏈路同時識別舊、新版本。偷偷改變位元邊界會讓解碼、排序和唯一性全部失效。

追問三：某節點時鐘突然回撥 2 秒，可以借用序號位元繼續發號嗎？

不能無狀態地「借位」後繼續，因為重新啟動後可能忘記借用了哪個邏輯時間。目前策略會立即停止該節點、發出警示並轉移流量；復原前讓系統時鐘追上 lastMs，或從持久高水位恢復經過證明的邏輯時間。若業務要求回撥期間仍可用，應選擇帶持久邏輯時鐘的專門設計，並重新證明溢位、重啟和排序語意，不能用一句「使用邏輯時鐘」略過狀態復原。

追問四：ID 將出現在公開訂單 URL 中，如何防止列舉和單量洩漏？

保留 Snowflake 作為內部關聯鍵，同時產生獨立的隨機外部識別碼；外部識別碼可以使用符合熵要求的 UUIDv4，或在接受時間前綴洩漏時使用 UUIDv7。映射由訂單表保存。無論使用什麼 ID，讀取訂單仍必須驗證目前使用者權限；不可猜測性只降低列舉風險，不取代授權。

追問五：區域與全域控制平面中斷後還能繼續嗎？

區域位元已隔離不同區域的命名空間，所以不需要聯絡全域控制平面。區域內既有 worker 在本地租約仍處於安全期時可以繼續；若區域租約分配器也不可用，續租失敗的 worker 到安全截止時間後停止。為提高可用性，可以讓區域租約儲存本身採用區域內共識叢集，但不能讓兩個分割同時續租同一個 worker。

追問六：單節點突然需要每毫秒 5,000 個 ID 呢？

12 位元序號最多提供 4,096 個取值。即時措施是背壓並把請求分散到更多 worker，不能回繞。長期可以增加序號位元，但必須從時間壽命或 worker 數借位，並形成新格式；也可以取消 64 位元限制改用 UUIDv7。選擇前要重新量化真實的一毫秒突發分布，不能按每秒平均值擴位。

追問七：只要求同一對話內嚴格有序，是否需要全域 sequencer？

不需要。把對話映射到固定分割，在每個分割內維護提交序列即可；Snowflake 繼續作為全域身分，分割序列負責對話順序。如此故障和協調範圍隨分割縮小，也避免為了局部順序把所有區域寫入串行化。讀取時明確使用 (conversation_id, sequence) 排序，不能假設 Snowflake ID 等於對話提交順序。