系統設計學習筆記 - Unique ID Generator in Distributed Systems
我們可以透過 Unique ID 識別唯一的資料，本文介紹在分散式系統中常見的演算法，並進一步說明 Twitter snowflake approach。
設計範圍
假設條件
唯一、可排序。
依時間遞增。
只包含數字。
長度 64 bits。
每秒可產生 10,000 個。
高階設計
常見的 Unique ID 演算法
Multi-master replication
Universally unique identifier (UUID)
Ticket server
Twitter snowflake approach
Multi-master replication
使用 database 的 auto_increment 功能，以 k 遞增，k 為 database server 的數量。以下圖為例，k 為 2。
優點：
- ID 為數字。
缺點：
不易於在多個 data center 上擴展。
ID 不會隨著時間增加。
Server 增加或減少時，不易於擴展。
Universally unique identifier (UUID)
UUID 為 128 bits 的值，以 hyphen 連接 5 組 16 進位字串來表示，如 123e4567-e89b-12d3-a456-426614174000。
優點：
每台 server 獨立產生 ID，無同步問題。
每台 server 獨立產生 ID，易於擴展。
缺點：
ID 為 128 bits，我們的需求為 64 bits。
ID 不會隨著時間增加。
ID 包含非數字。
Ticket server
Flicker 使用 ticket server 產生分散式 primary key。主要概念是在單一 database server (Ticket
Server) 上，使用中心化的 auto_increment 功能。
優點：
- ID 為數字。
缺點：
- Single point of failure。只要 ticket server 故障，所有依賴 ticket server 的系統，都會受到影響。可以設置多台 ticket server 來避免，但資料同步問題將會是一大挑戰。
Twitter snowflake approach
Twitter 的 unique ID generation system 名為 snowflake。
Sign bit: 1 bit。用來識別 signed 和 unsigned numbers，目前皆為 0 (unsigned numbers)，1 (signed numbers) 保留在未來使用。
Timestamp: 41 bits。表示從 epoch 為開始計算的 Milliseconds， Twitter
snowflake 使用 1288834974657 為預設的 epoch，即 Nov 04, 2010, 01:42:54 UTC。Datacenter ID: 5 bits。表示有 2 ^ 5 = 32 datacenters。
Machine ID: 5 bits。表示每個 datacenter 有 2 ^ 5 = 32 machines。
Sequence number: 12 bits。每個 machine/process 產生的 sequence number 以 1 遞增，每 millisecond 重設為 0。
深入設計
以 Twitter snowflake approach 為基礎設計。
Datacenter IDs 和 machine IDs 在系統啟動時決定，Timestamp 和 Sequence number 在產生 ID 決定。
Timestamp
Timestamp 隨時間增加，因此 ID 可用時間排序。下圖表示 binary 如何轉換為 UTC。
Timestamp 為 41 bits，可表示 2 ^ 41 - 1 = 2199023255551 milliseconds (ms)，約 69 years = 2199023255551 ms / 1000 seconds / 365 days / 24 hours/ 3600 seconds。
Sequence number
Sequence number 為 12 bits，共有 2 ^ 12 = 4096 種組合。只有在同一台 server，同時間 (millisecond) 產生多個 ID 時，才會有非零值。也就是說，最多可以產生 4096 個 ID。