在本章中，你的任務是設計一個分散式系統的唯一 ID 產生器（unique ID generator）。
你的第一個想法可能是使用傳統資料庫中具有 auto_increment 屬性的主鍵。然而，auto_increment 在分散式環境中無法運作，因為單一資料庫伺服器不夠大，而要在多個資料庫之間以最小延遲產生唯一 ID 是有挑戰性的。
以下是一些唯一 ID 的範例：
Step 1 - Understand the problem and establish design scope#
提出釐清問題是處理任何系統設計面試問題的第一步。以下是應徵者與面試官互動的範例：
應徵者：唯一 ID 有什麼特性？
面試官：ID 必須是唯一且可排序的。
應徵者：對於每筆新紀錄，ID 是否每次加 1？
面試官：ID 隨時間遞增，但不一定每次只加 1。同一天傍晚建立的 ID 會比早上建立的更大。
應徵者：ID 是否只包含數值？
面試官：是的，沒錯。
應徵者：ID 長度的需求是什麼？
面試官：ID 應符合 64-bit。
應徵者：系統規模如何？
面試官：系統應能每秒產生 10,000 個 ID。
以上是一些你可以問面試官的範例問題。理解需求並釐清模糊之處很重要。對於這個面試問題，需求列出如下：
- ID 必須是唯一的。
- ID 只包含數值。
- ID 符合 64-bit。
- ID 按日期排序。
- 能夠每秒產生超過 10,000 個唯一 ID。
Step 2 - Propose high-level design and get buy-in#
可以使用多種方法在分散式系統中產生唯一 ID。我們考慮的選項是：
- 多主複製（Multi-master replication）
- 通用唯一識別符（Universally unique identifier，UUID）
- Ticket server
- Twitter snowflake 方法
讓我們看看每個方法、它們如何運作，以及每個選項的優缺點。
多主複製#
如圖 2 所示，第一種方法是多主複製。
這種方法使用資料庫的 auto_increment 功能。我們不將下一個 ID 加 1，而是加 k，其中 k 是使用中的資料庫伺服器數量。如圖 2 所示，要產生的下一個 ID 等於同一台伺服器中前一個 ID 加 2。這解決了一些可擴展性問題，因為 ID 可以隨資料庫伺服器數量擴展。
然而，這個策略有一些主要缺點：
- 難以跨多個資料中心擴展
- 跨多台伺服器時，ID 不會隨時間遞增。
- 當伺服器被新增或移除時擴展性不佳。
UUID#
UUID 是另一種獲得唯一 ID 的簡單方式。UUID 是一個 128-bit 的數字，用於識別電腦系統中的資訊。
UUID 發生衝突的機率非常低。引述自 Wikipedia：「以每秒產生 10 億個 UUID 約 100 年後，產生單一重複的機率才會達到 50%」[1]。
以下是 UUID 的範例：09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID 可以獨立產生，不需要伺服器之間的協調。圖 3 呈現 UUID 設計。
在這個設計中，每台 web 伺服器包含一個 ID 產生器，每台 web 伺服器負責獨立產生 ID。
優點：
- 產生 UUID 很簡單。伺服器之間不需要協調，因此不會有任何同步問題。
- 系統易於擴展，因為每台 web 伺服器負責產生其所消耗的 ID。ID 產生器可以輕易地隨 web 伺服器擴展。
缺點：
- ID 長度為 128 bit，但我們的需求是 64 bit。
- ID 不隨時間遞增。
- ID 可能不是數值。
Ticket Server#
Ticket server 是另一種有趣的產生唯一 ID 的方式。Flicker 開發了 ticket server 來產生分散式主鍵 [2]。值得一提的是這個系統如何運作。
這個想法是在單一資料庫伺服器（Ticket Server）中使用集中式 auto_increment 功能。要進一步了解，請參考 flicker 的工程部落格文章 [2]。
優點：
- 數值 ID。
- 易於實作，適用於中小規模應用。
缺點：
- 單點故障（Single point of failure）。單一 ticket server 意味著如果 ticket server 停機，所有依賴它的系統都會出問題。為了避免單點故障，我們可以設定多個 ticket server。然而，這會引入新的挑戰，例如資料同步。
單點故障是 ticket server 方案最大的風險。雖然可以透過設置多台 ticket server 來緩解，但會引入資料同步的新挑戰。
Twitter snowflake 方法#
上述方法給了我們一些關於不同 ID 產生系統如何運作的想法。然而，它們都不符合我們的特定需求；因此，我們需要另一種方法。Twitter 名為「snowflake」的唯一 ID 產生系統 [3] 啟發人心，並能滿足我們的需求。
分而治之是我們的好朋友。我們不直接產生 ID，而是將 ID 分為不同區段。
圖 5 顯示 64-bit ID 的版面配置。
每個區段的解釋如下。
- Sign bit：1 bit。它將永遠為 0。這是保留供未來使用。它可能用於區分有號數與無號數。
- Timestamp：41 bits。從 epoch 或自訂 epoch 起的毫秒數。我們使用 Twitter snowflake 預設的 epoch 1288834974657，等同於 2010 年 11 月 4 日 01:42:54 UTC。
- Datacenter ID：5 bits，給我們 2 ^ 5 = 32 個資料中心。
- Machine ID：5 bits，給我們每個資料中心 2 ^ 5 = 32 台機器。
- Sequence number：12 bits。對於該機器/行程上產生的每個 ID，序號加 1。每毫秒重設為 0。
Step 3 - Design deep dive#
在高階設計中，我們討論了在分散式系統中設計唯一 ID 產生器的多種選項。我們決定採用基於 Twitter snowflake ID 產生器的方法。讓我們深入設計。為了喚起記憶，設計圖再次列出如下。
Datacenter ID 與 machine ID 在啟動時被選定，一旦系統運作通常就固定不變。對 datacenter ID 與 machine ID 的任何變更都需要仔細審查，因為這些值的意外變更可能導致 ID 衝突。
Timestamp 與序號在 ID 產生器運作時產生。
Timestamp#
最重要的 41 bits 構成 timestamp 區段。由於 timestamp 隨時間遞增，ID 可按時間排序。圖 7 顯示二進位表示如何轉換為 UTC 的範例。你也可以使用類似的方法將 UTC 轉換回二進位表示。
41 bits 可以表示的最大 timestamp 是
2 ^ 41 - 1 = 2199023255551 毫秒（ms），這給我們：~ 69 年 = 2199023255551 ms / 1000 / 365 days / 24 hours/ 3600 seconds。
這意味著 ID 產生器將運作 69 年，而採用接近今天日期的自訂 epoch 時間可以延後溢位時間。69 年後，我們將需要新的 epoch 時間或採用其他技術來遷移 ID。
Sequence number#
序號為 12 bits，給我們 2 ^ 12 = 4096 種組合。除非在同一伺服器上於同一毫秒內產生多個 ID，否則此欄位為 0。理論上，一台機器每毫秒可支援最多 4096 個新 ID。
Step 4 - Wrap up#
在本章中，我們討論了設計唯一 ID 產生器的不同方法：多主複製、UUID、ticket server 與類 Twitter snowflake 唯一 ID 產生器。我們決定採用 snowflake，因為它支援我們所有的使用情境，並在分散式環境中具有可擴展性。
如果在面試結束時還有額外時間，以下是一些額外的討論點：
- 時鐘同步。在我們的設計中，我們假設 ID 產生伺服器擁有相同的時鐘。當伺服器在多核心上運作時，這個假設可能不成立。在多機器場景中也存在相同的挑戰。時鐘同步的解決方案超出本課程範圍；然而，理解這個問題的存在很重要。Network Time Protocol 是這個問題最熱門的解決方案。對此有興趣的讀者，請參考參考資料 [4]。
- 區段長度調整。例如，較少的序號但更多的 timestamp 位元對於低並行性與長期應用程式有效。
- 高可用性。由於 ID 產生器是任務關鍵系統，它必須具備高可用性。
恭喜你看到這裡！現在給自己拍拍背，做得好！