Case Study: Design a Unique ID Generator in Distributed Systems

“Mỗi công dân có một số CMND/CCCD duy nhất. Mỗi sự kiện trong hệ thống phân tán cũng cần một ID duy nhất --- không trùng lặp, không xung đột, dù hàng triệu máy chủ cùng tạo ra cùng lúc. Đó chính là bài toán Unique ID Generator.”

Tags: system-design case-study unique-id snowflake distributed-systems alex-xu interview Student: Hieu Prerequisite: Tuan-01-Scale-From-Zero-To-Millions · Tuan-02-Back-of-the-envelope · Tuan-07-Database-Sharding-Replication Lien quan: Tuan-10-Consistent-Hashing · Tuan-16-Design-URL-Shortener · Tuan-20-Design-Key-Value-Store

1. Context & Why --- Tại sao cần Unique ID Generator?

1.1 Analogy: Số CMND/CCCD cho hệ thống

Hiếu, bạn hãy nghĩ thế này: mỗi công dân Việt Nam có một số CMND/CCCD duy nhất. Số này giúp nhà nước phân biệt 100 triệu người --- không ai trùng nhau. Trong hệ thống phân tán, mỗi event, mỗi record, mỗi transaction cũng cần một “số CMND” --- một globally unique identifier.

Thế giới thực	Hệ thống phân tán
Số CMND/CCCD	Unique ID
Cơ quan công an cấp	ID Generator service
Không trùng giữa các tỉnh	Không trùng giữa các datacenter
Có thể tra cứu theo thời gian	Sortable by time
Có định dạng (12 số)	Có định dạng (64-bit integer)

1.2 Tại sao không dùng `AUTO_INCREMENT` trong DB?

Khi hệ thống chỉ có một database duy nhất, AUTO_INCREMENT là đủ. Nhưng khi bạn scale ra nhiều DB server, nhiều datacenter:

Vấn đề	Giải thích
Single point of failure	Một DB đi xuống = không tạo được ID
Bottleneck	Mỗi request phải gọi DB để lấy ID --- latency cao
Không scale horizontally	10K+ IDs/sec sẽ làm DB quá tải
Không work across datacenter	2 DB ở 2 DC có thể tạo trùng ID
Không sortable by time	`AUTO_INCREMENT` chỉ tăng dần, không chứa thông tin thời gian

Aha Moment: AUTO_INCREMENT là anti-pattern trong distributed systems. Bạn cần một cơ chế tạo ID không cần coordination giữa các node.

2. Deep Dive --- Alex Xu 4-Step Framework

Overview --- Bốn bước của Alex Xu

Bước	Tên gọi	Thời gian (45 phút)
1	Understand the Problem & Establish Design Scope	~5 phút
2	Propose High-Level Design	~15 phút
3	Design Deep Dive	~20 phút
4	Wrap Up	~5 phút

Step 1 --- Understand the Problem & Establish Design Scope

2.1 Functional Requirements (Yêu cầu chức năng)

Câu hỏi cho Interviewer	Trả lời / Giả định
ID phải unique globally?	Có, không bao giờ trùng lặp
ID chỉ chứa số hay có thể chứa chữ cái?	Chỉ chứa số (numerical values only)
ID có cần sortable theo thời gian?	Có, ID tạo sau phải lớn hơn ID tạo trước (roughly)
Độ dài ID?	64-bit integer (fit vào `BIGINT` của SQL)
Hệ thống cần tạo bao nhiêu ID/giây?	10,000+ IDs/sec
Hệ thống có nhiều datacenter?	Có, nhiều datacenter, nhiều machine

Tóm tắt Functional Requirements:

Globally unique --- Không bao giờ trùng lặp, kể cả across datacenter
64-bit integer --- Fit vào BIGINT, dùng làm primary key
Sortable by time --- ID tạo sau > ID tạo trước (roughly ordered)
High throughput --- 10,000+ IDs/sec per system

2.2 Non-Functional Requirements (Yêu cầu phi chức năng)

Yêu cầu	Mục tiêu	Giải thích
High Availability	99.99% uptime	ID generation không bao giờ được down --- mọi service đều phụ thuộc
Low Latency	< 1ms per ID	ID generation nằm trên critical path của mọi write operation
Scalability	Linear scale với số machine	Thêm machine = thêm throughput, không cần coordination
Ordering	Time-sortable	IDs tạo trong cùng millisecond trên cùng machine phải có thứ tự
No coordination	Không cần central authority	Mỗi node tự tạo ID độc lập

Step 2 --- Propose High-Level Design: 4 Approaches

Hiếu, có 4 cách tiếp cận chính để tạo Unique ID trong distributed systems. Mỗi cách có trade-off riêng.

Approach 1: Multi-Master Replication (DB Auto-Increment với bước nhảy)

Ý tưởng: Dùng AUTO_INCREMENT của DB, nhưng mỗi server tăng với bước nhảy khác nhau.

Server 1: 1, 3, 5, 7, 9, ...    (start=1, increment=2)
Server 2: 2, 4, 6, 8, 10, ...   (start=2, increment=2)

Tổng quát với N servers:
Server k: k, k+N, k+2N, k+3N, ...

Ưu điểm	Nhược điểm
Đơn giản, dùng sẵn feature của DB	Khó scale: thêm/bớt server phải thay đổi `increment` của TẤT CẢ server
Không cần thêm service nào	ID không sortable by time (Server 1 có thể tạo ID 7 SAU khi Server 2 tạo ID 8)
Tương đối reliable	Không work across datacenter (latency cao)
	Throughput bị giới hạn bởi DB write speed

Khi nào dùng: Hệ thống nhỏ, ít server, không cần time-sorted IDs.

Approach 2: UUID (Universally Unique Identifier)

Ý tưởng: Mỗi machine tự tạo UUID 128-bit độc lập, không cần coordination.

UUID v4 Example: 550e8400-e29b-41d4-a716-446655440000
                 |--------|    |  |    |  |-----------|
                  random    version  variant   random

Ưu điểm	Nhược điểm
Đơn giản nhất, mọi ngôn ngữ đều hỗ trợ	128-bit (không fit vào yêu cầu 64-bit)
Không cần coordination giữa các node	Không sortable by time
Không có single point of failure	Hiệu suất DB kém: random UUID làm B+ tree index fragmentation
Throughput vô hạn (mỗi node tự tạo)	Dài (36 chars string) --- tốn storage

Collision probability của UUID v4:

P (collision) \approx 1 - e^{- \frac{n ^{2}}{2 \times 2 ^{122}}}

Với $n = 1 0^{18}$ UUIDs (1 quintillion):

P (collision) \approx \frac{( 1 0 ^{18} ) ^{2}}{2 \times 2 ^{122}} = \frac{1 0 ^{36}}{2 ^{123}} \approx 9.4 \times 1 0^{- 2} \approx 0.094

Thực tế collision probability cực thấp, nhưng không phải zero và không đảm bảo unique bằng Snowflake.

Khi nào dùng: Khi không cần sortable, không giới hạn 64-bit, cần triển khai nhanh (vd: session ID, correlation ID, idempotency key).

Approach 3: Ticket Server (Flickr Approach)

Ý tưởng: Dùng một (hoặc vài) server trung tâm với AUTO_INCREMENT làm “máy bán vé”. Mỗi service gọi đến Ticket Server để lấy ID tiếp theo.

          +------------------+
          |  Ticket Server   |
          |  AUTO_INCREMENT  |
          |  current_id: 1000|
          +--------+---------+
                   |
      +-----+-----+-----+
      |     |     |     |
   Svc A  Svc B  Svc C  Svc D
   id=1001 id=1002 id=1003 id=1004

Ưu điểm	Nhược điểm
Đơn giản, dễ implement	Single Point of Failure (SPOF)
ID là số, 64-bit, tăng dần	Bottleneck: mỗi request phải gọi Ticket Server
Sortable by time (roughly)	Latency tăng khi cross-datacenter
Flickr dùng thành công nhiều năm	Cần replicate Ticket Server để HA --- thêm complexity

Flickr’s solution: Dùng 2 Ticket Servers với increment = 2, giống Multi-Master nhưng chỉ dành riêng cho ID generation.

Khi nào dùng: Hệ thống vừa, chấp nhận single point of coordination, cần ID tăng dần đơn giản.

Approach 4: Snowflake (Twitter Approach) --- Recommended

Ý tưởng: Mỗi ID là một 64-bit integer được compose từ nhiều thành phần: timestamp, datacenter ID, machine ID, và sequence number. Mỗi machine tự tạo ID độc lập.

+---+-------------------------------------------+---------+---------+----------------+
| 0 |          41-bit Timestamp                  | 5-bit   | 5-bit   | 12-bit         |
|   |          (milliseconds since epoch)        |Datacenter| Machine | Sequence       |
+---+-------------------------------------------+---------+---------+----------------+
 1 bit                41 bits                     5 bits    5 bits     12 bits = 64 bits

Ưu điểm	Nhược điểm
64-bit integer --- fit yêu cầu	Phụ thuộc vào đồng hồ máy (clock)
Sortable by time (timestamp trong ID)	Clock skew giữa các machine gây ra out-of-order IDs
Không cần coordination	Cần quản lý datacenter ID và machine ID
Throughput cực cao: 4,096 IDs/ms/machine	Time-sorted chỉ trong phạm vi “roughly” --- không tuyệt đối
Dễ extract timestamp từ ID	Epoch overflow sau 69 năm

Aha Moment: Snowflake là cách tiếp cận được sử dụng nhiều nhất trong thực tế. Twitter, Discord, Instagram, Baidu đều dùng biến thể của Snowflake.

Bảng so sánh toàn bộ Approaches

Tiêu chí	Multi-Master	UUID	Ticket Server	Snowflake	ULID	KSUID	MongoDB ObjectId
Bit size	64	128	64	64	128	160	96
Globally unique	Có (với cấu hình đúng)	Có (cực cao)	Có	Có	Có	Có	Có
Sortable by time	Không	Không (v4)	Có	Có	Có	Có	Có
No coordination	Không	Có	Không	Có	Có	Có	Có
Throughput	Thấp (DB bound)	Vô hạn	Thấp (bottleneck)	4,096/ms/machine	Vô hạn	Vô hạn	16M/sec/process
Complexity	Thấp	Cực thấp	Trung bình	Trung bình	Thấp	Thấp	Thấp
DB index friendly	Có	Không (random)	Có	Có	Có	Có	Có
Dùng trong thực tế	MySQL replication	Session ID, correlation ID	Flickr	Twitter, Discord, Instagram	Shopify, CockroachDB	Segment	MongoDB
Fit 64-bit?	Có	Không	Có	Có	Không	Không	Không

Các biến thể khác (Ngoài Alex Xu)

ULID (Universally Unique Lexicographically Sortable Identifier):

128-bit: 48-bit timestamp (millisecond) + 80-bit randomness
Encoded thành 26-char Crockford Base32
Sortable by time, không cần coordination
Sử dụng: Shopify, CockroachDB

KSUID (K-Sortable Unique Identifier):

160-bit: 32-bit timestamp (second) + 128-bit random payload
Encoded thành 27-char Base62
Epoch: 2014-05-13 --- overflow sau ~136 năm
Sử dụng: Segment

MongoDB ObjectId:

96-bit (12 bytes): 32-bit timestamp (second) + 40-bit random + 24-bit counter
Sortable by time (second resolution)
Counter cho phép 16,777,216 unique IDs per second per process

Step 3 --- Design Deep Dive: Snowflake ID Generator

3.1 Bit Layout Chi Tiết

 0 | 00000000 00000000 00000000 00000000 00000000 0 | 00000 | 00000 | 000000000000
 ^ |                    41 bits                      | 5 bits| 5 bits|   12 bits
 |                       |                              |       |         |
Sign bit             Timestamp                     Datacenter Machine  Sequence
(luôn = 0)     (ms since custom epoch)               ID       ID      Number

Thành phần	Số bit	Range	Giải thích
Sign bit	1	Luôn = 0	Đảm bảo ID luôn dương (positive)
Timestamp	41	0 --- $2^{41} - 1$ ms	Millisecond kể từ custom epoch
Datacenter ID	5	0 --- 31	Tối đa 32 datacenter
Machine ID	5	0 --- 31	Tối đa 32 machine per datacenter
Sequence	12	0 --- 4095	Counter reset mỗi millisecond

3.2 Cách tạo ID (Thuật toán)

Mỗi khi một service request ID:

1. Lấy current_timestamp (ms since epoch)
2. Nếu current_timestamp == last_timestamp:
     sequence = (sequence + 1) AND 0xFFF   // 12-bit mask
     Nếu sequence == 0:  // overflow! đã tạo 4096 IDs trong 1ms
       Wait cho next millisecond
3. Nếu current_timestamp > last_timestamp:
     sequence = 0   // reset counter
4. Nếu current_timestamp < last_timestamp:
     CLOCK SKEW DETECTED! -> Handle error
5. last_timestamp = current_timestamp
6. Compose ID:
     id = (timestamp << 22) | (datacenter_id << 17) | (machine_id << 12) | sequence
7. Return id

3.3 Epoch Selection (Chọn epoch)

Snowflake KHÔNG dùng Unix epoch (1970-01-01). Tại sao?

Max timestamp = 2^{41} - 1 = 2, 199, 023, 255, 551 ms \approx 69.73 n \overset{a}{˘} m

Nếu dùng Unix epoch (1970-01-01):

Overflow date = 1970 + 69.73 \approx 2039-09-07

Đã quá gần! Nên chọn custom epoch = ngày hệ thống go-live:

Custom Epoch	Overflow Date	Còn lại (từ 2026)
2010-01-01 (Twitter)	~2079	~53 năm
2015-01-01 (Discord)	~2084	~58 năm
2020-01-01	~2089	~63 năm
2025-01-01 (recommended cho hệ thống mới)	~2094	~68 năm
Unix epoch 1970-01-01	~2039	~13 năm

Aha Moment: Chọn custom epoch gần với ngày deploy để tối ưu hóa thời gian sống của hệ thống. Discord chọn 2015-01-01 --- ngày đầu tiên của Discord.

3.4 Clock Sync và NTP (Network Time Protocol)

Vấn đề cốt lõi: Snowflake phụ thuộc vào timestamp --- nhưng đồng hồ của các machine KHÔNG BAO GIỜ đồng bộ hoàn hảo.

NTP (Network Time Protocol) đồng bộ đồng hồ giữa các máy:

Stratum 0: Atomic clock, GPS receiver (độ chính xác ~nanosecond)
Stratum 1: Server kết nối trực tiếp với Stratum 0 (~microsecond)
Stratum 2: Server sync với Stratum 1 (~millisecond)
Stratum 3+: Mỗi tầng thêm ~1-10ms drift

  GPS Satellite / Atomic Clock
         |
    [Stratum 0]
         |
    [Stratum 1]  <-- Google, Amazon NTP servers
         |
    [Stratum 2]  <-- Datacenter NTP servers
         |
    [Stratum 3]  <-- Application servers (các machine của em)

Clock drift thực tế:

Server thường: drift ~100ms/ngày nếu không có NTP
Với NTP sync mỗi 30 giây: drift < 1ms
Google TrueTime (Spanner): uncertainty < 7ms (dùng GPS + atomic clock)

3.5 Clock Skew Handling (Xử lý lệch đồng hồ)

Scenario: Machine A có đồng hồ chậm hơn Machine B 5ms.

Machine A tạo ID với timestamp = 1000
Machine B tạo ID với timestamp = 1005
Thực tế hai ID được tạo cùng lúc --- nhưng ID của B “có vẻ” tạo sau

Các cách xử lý:

Strategy	Mô tả	Trade-off
Wait	Nếu `current_time < last_time`, đợi cho đến khi `current_time >= last_time`	Đơn giản nhưng có thể block nếu clock nhảy lùi nhiều
Reject	Nếu clock skew > threshold (vd: 5ms), reject request và raise alarm	An toàn nhưng có thể mất ID trong thời gian ngắn
Logical clock	Dùng Lamport timestamp hoặc Hybrid Logical Clock (HLC) để đảm bảo causality	Phức tạp hơn nhưng đảm bảo ordering
Tolerance window	Chấp nhận ID out-of-order trong một window nhỏ (vd: 10ms)	Thực tế nhất, hầu hết các hệ thống dùng cách này

Cách Twitter Snowflake xử lý: Nếu current_timestamp < last_timestamp, throw exception và log warning. Operations team sẽ điều tra NTP issue.

Aha Moment: Clock skew là unavoidable trong distributed systems. Snowflake không đảm bảo strict global ordering --- chỉ “roughly sorted”. Nếu cần strict ordering, phải dùng single-machine approach (Ticket Server) hoặc Hybrid Logical Clock.

3.6 Sequence Overflow Scenarios

Khi một machine tạo > 4,096 IDs trong 1 millisecond:

Millisecond T=1000:
  ID #0:    ...1000...0000 00000000
  ID #1:    ...1000...0000 00000001
  ...
  ID #4095: ...1000...1111 11111111  <- MAX sequence
  ID #4096: OVERFLOW! sequence quay về 0
            -> Phải WAIT cho T=1001

Handling strategies:

Strategy	Mô tả	Khi nào dùng
Spin-wait	Busy-loop cho đến next millisecond	Default trong Snowflake, OK cho burst ngắn
Sleep	`Thread.sleep(1)`	Giảm CPU nhưng có thể mất chính xác
Pre-generate pool	Tạo trước một pool IDs, trả về từ pool	High-throughput services, giảm latency spike
Borrow from future	Tạo ID với timestamp = T+1 và sequence = 0	Nguy hiểm --- có thể gây duplicate nếu clock correction xảy ra

3.7 Ordering Guarantees

Phạm vi	Đảm bảo?	Giải thích
Cùng machine, cùng millisecond	Có, strict ordering	Sequence number tăng dần
Cùng machine, khác millisecond	Có, strict ordering	Timestamp lớn hơn = ID lớn hơn
Khác machine, cùng datacenter	Không đảm bảo	Clock skew có thể làm out-of-order
Khác datacenter	Không đảm bảo	Clock skew + network latency

ID_{A} > ID_{B} ⟺ ⎩ ⎨ ⎧ timestamp_{A} > timestamp_{B} OR timestamp_{A} = timestamp_{B} \land datacenter_{A} > datacenter_{B} OR timestamp_{A} = timestamp_{B} \land datacenter_{A} = datacenter_{B} \land machine_{A} > machine_{B} OR all equal \land sequence_{A} > sequence_{B}

Chú ý: Điều này có nghĩa là 2 ID từ 2 machine khác nhau có thể có timestamp giống nhau nhưng thứ tự so sánh phụ thuộc vào datacenter_id và machine_id, không phải thời gian thực.

3. Back-of-the-Envelope Estimation

3.1 IDs per Millisecond per Machine

IDs/ms/machine = 2^{12} = 4, 096

3.2 IDs per Second per Machine

IDs/sec/machine = 4, 096 \times 1, 000 = 4, 096, 000 \approx 4.1 M IDs/sec

3.3 Total Capacity với N Machines

Total capacity = N_{datacenter} \times N_{machine} \times 4, 096, 000 IDs/sec

Với max configuration (32 datacenter x 32 machine = 1,024 machines):

Max total = 1, 024 \times 4, 096, 000 = 4, 194, 304, 000 \approx 4.2 B IDs/sec

3.4 Yêu cầu 10K IDs/sec cần bao nhiêu machine?

N_{machine} = ⌈ \frac{10 , 000}{4 , 096 , 000} ⌉ = 1

Chỉ cần 1 machine là thừa sức cho 10K IDs/sec. Thực tế, ta deploy nhiều machine để High Availability, không phải vì throughput.

3.5 Timestamp Overflow

Max duration = \frac{2 ^{41} - 1}{1 , 000 \times 60 \times 60 \times 24 \times 365.25} \approx 69.73 n \overset{a}{˘} m

Với custom epoch = 2025-01-01:

Overflow date \approx 2025 + 69.73 = 2094

3.6 Tổng số ID có thể tạo trong 69 năm

Total IDs (1 machine) = 2^{41} \times 2^{12} = 2^{53} \approx 9.007 \times 1 0^{15} \approx 9 quadrillion

Total IDs (all machines) = 2^{41} \times 2^{5} \times 2^{5} \times 2^{12} = 2^{63} \approx 9.2 \times 1 0^{18}

3.7 Storage Estimation

Mỗi ID là 8 bytes (64-bit):

Storage (1B IDs) = 1 0^{9} \times 8 bytes = 8 GB

So sánh với UUID (16 bytes) hoặc UUID string (36 bytes):

Format	Size per ID	1 Billion IDs	DB Index Impact
Snowflake (64-bit)	8 bytes	8 GB	Sequential --- B+ tree insert O(1) amortized
UUID binary (128-bit)	16 bytes	16 GB	Random --- B+ tree split O(log n)
UUID string (36 char)	36 bytes	36 GB	Random + larger index pages

4. Security First --- Bảo mật cho ID Generator

4.1 ID Predictability Attacks (Tấn công đoán trước ID)

Threat: Nếu attacker biết ID structure, họ có thể:

Attack	Mô tả	Impact
Enumeration attack	Đoán ID của record khác bằng cách tăng/giảm ID	Truy cập dữ liệu trái phép
Timing attack	Extract timestamp từ ID để biết thời gian tạo record	Information leakage
Volume estimation	So sánh 2 IDs để ước lượng số record giữa chúng	Business intelligence leak
Infrastructure mapping	Extract datacenter_id và machine_id	Biết số lượng server, datacenter topology

Ví dụ Enumeration:

Attacker thấy order_id = 7100424390656 00001 00001 000000000001
                                        ^DC    ^Machine
Họ biết: datacenter 1, machine 1
Họ tăng sequence: 000000000002, 000000000003, ...
-> Có thể duyệt qua toàn bộ orders của machine đó

4.2 Information Leakage từ Snowflake ID

Thành phần	Thông tin bị lộ	Mức độ nghiêm trọng
Timestamp (41 bit)	Thời điểm chính xác (ms) tạo record	Trung bình --- attacker biết khi nào user đăng ký, đặt hàng
Datacenter ID (5 bit)	Topology của hệ thống	Thấp --- nhưng hữu ích cho targeted attack
Machine ID (5 bit)	Số lượng và vị trí server	Thấp --- có thể dùng cho DDoS targeting
Sequence (12 bit)	Traffic volume tại thời điểm đó	Trung bình --- business intelligence

4.3 Mitigation Strategies (Chiến lược giảm thiểu)

Strategy	Mô tả	Trade-off
Không expose internal ID	Dùng public-facing ID khác (UUID hoặc encrypted ID) cho API, giữ Snowflake ID internal	Thêm một lớp mapping, tăng storage
Encrypt ID trước khi expose	Dùng Format-Preserving Encryption (FPE) để encrypt 64-bit ID thành 64-bit ciphertext	Vẫn giữ được size, nhưng mất sortability
Shuffle bits	Xáo trộn thứ tự các bit để timestamp không còn ở vị trí cố định	Mất sortability, cần lookup table
Add random bits	Thay datacenter+machine (10 bit) bằng random bits	Mất khả năng trace về source, nhưng an toàn hơn
Hash-based public ID	`public_id = HMAC-SHA256(secret_key, snowflake_id)[:8]`	Một chiều, không reverse được, nhưng cần DB lookup
Rate limit API	Giới hạn số request per user/IP để chặn enumeration	Không giải quyết root cause nhưng giảm impact

Recommended approach cho hầu hết hệ thống:

Internal: Snowflake ID (dùng cho DB, inter-service communication)
External: Encrypted Snowflake ID hoặc UUID mapping (dùng cho public API)

Database:
  +------------------+------------------+
  | snowflake_id (PK)| public_id (UNIQUE)|
  | 71004243906560001 | a8f3k2m9x1       |
  +------------------+------------------+

4.4 OWASP Considerations

OWASP Risk	Áp dụng cho ID Generator	Giải pháp
A01 Broken Access Control	Attacker dùng predicted ID để truy cập resource của người khác	Authorization check TRÊN MỌI REQUEST, không chỉ dựa vào ID
A04 Insecure Design	Expose Snowflake ID trên public API	Dùng public ID mapping hoặc FPE encryption
A09 Security Logging	Không log ai request ID nào	Log mọi ID generation request với caller identity

Aha Moment: ID Generator bản thân không có lỗi bảo mật --- lỗi là ở cách bạn expose ID ra ngoài. Luôn có một lớp abstraction giữa internal ID và public-facing ID.

5. DevOps --- Vận hành ID Generator

5.1 Monitoring Metrics

Metric	Mô tả	Alert Threshold
`id_generation_rate`	Số ID tạo per second per machine	Spike bất thường > 2x baseline
`id_generation_latency_p99`	Latency để tạo 1 ID	> 1ms (thường < 0.01ms)
`sequence_overflow_count`	Số lần sequence overflow (4096/ms)	> 0 per minute = cần thêm machine hoặc review traffic
`clock_skew_detected`	Số lần `current_time < last_time`	> 0 = NTP issue, cần điều tra ngay
`ntp_offset_ms`	Độ lệch giữa local clock và NTP server	> 10ms = critical alert
`ntp_sync_failures`	Số lần NTP sync thất bại	> 3 consecutive failures = critical
`machine_id_conflicts`	2 machine có cùng datacenter_id + machine_id	> 0 = IMMEDIATE action (duplicate IDs!)

5.2 Clock Drift Detection

# prometheus-alerts.yml
groups:
  - name: id_generator_alerts
    rules:
      # Clock skew detected
      - alert: ClockSkewDetected
        expr: increase(clock_skew_detected_total[5m]) > 0
        for: 1m
        labels:
          severity: critical
        annotations:
          summary: "Clock skew detected on {{ $labels.instance }}"
          description: "Machine {{ $labels.machine_id }} detected backward clock movement. IDs may be out of order."
 
      # NTP offset too high
      - alert: NTPOffsetHigh
        expr: abs(ntp_offset_milliseconds) > 10
        for: 5m
        labels:
          severity: warning
        annotations:
          summary: "NTP offset > 10ms on {{ $labels.instance }}: {{ $value }}ms"
 
      # NTP sync failure
      - alert: NTPSyncFailure
        expr: increase(ntp_sync_failures_total[15m]) > 3
        for: 1m
        labels:
          severity: critical
        annotations:
          summary: "NTP sync failing on {{ $labels.instance }}"
          description: "NTP has failed to sync 3+ times in 15 minutes. Clock drift will increase."
 
      # Sequence overflow
      - alert: SequenceOverflow
        expr: rate(sequence_overflow_total[1m]) > 0
        for: 1m
        labels:
          severity: warning
        annotations:
          summary: "Sequence overflow on machine {{ $labels.machine_id }}"
          description: "Machine is generating > 4096 IDs/ms. Consider adding more machines."
 
      # ID generation latency spike
      - alert: IDGenerationLatencyHigh
        expr: histogram_quantile(0.99, rate(id_generation_duration_seconds_bucket[5m])) > 0.001
        for: 5m
        labels:
          severity: warning
        annotations:
          summary: "P99 ID generation latency > 1ms on {{ $labels.instance }}"

5.3 NTP Monitoring Best Practices

Practice	Mô tả
Dùng nhiều NTP source	Cấu hình ít nhất 3 NTP server (vd: `time.google.com`, `time.aws.com`, `pool.ntp.org`)
Monitor NTP offset liên tục	Export `ntp_offset_ms` metric qua node_exporter hoặc custom exporter
Set NTP sync interval	Default 64-1024 giây, có thể giảm xuống 16-32 giây cho ID generator machine
Dùng `chrony` thay `ntpd`	`chrony` handle drift tốt hơn, khởi động nhanh hơn, chính xác hơn
Avoid NTP step (nhảy đồng hồ)	Cấu hình NTP chỉ slew (điều chỉnh từ từ) thay vì step (nhảy đột ngột)
Hardware timestamping	Dùng NIC có hỗ trợ hardware timestamping để giảm jitter

5.4 Machine ID Management

Strategy	Mô tả	Khi nào dùng
Static config	Cấu hình `datacenter_id` và `machine_id` trong config file hoặc env var	Hệ thống nhỏ, ít thay đổi
ZooKeeper/etcd	Mỗi machine đăng ký với ZooKeeper để nhận machine_id unique	Hệ thống lớn, cần auto-assignment
Cloud metadata	Dùng cloud instance metadata (AWS instance ID, GCP zone) để tính machine_id	Cloud-native systems
MAC address hash	Hash MAC address thành 10-bit (datacenter + machine)	Đơn giản nhưng có thể conflict

Pitfall: Khi một machine restart hoặc bị thay thế, machine_id PHẢI được bảo toàn hoặc de-register trước khi assign cho machine mới. Nếu 2 machine có cùng ID chạy đồng thời --- duplicate IDs sẽ xảy ra.

5.5 Grafana Dashboard Panels

Panel	Query	Visualization
ID Generation Rate	`sum(rate(ids_generated_total[1m])) by (machine_id)`	Time series, stacked
Latency P50/P95/P99	`histogram_quantile(0.99, rate(id_gen_duration_bucket[5m]))`	Time series, multi-line
Sequence Overflow Events	`increase(sequence_overflow_total[1h])`	Stat panel (should be 0)
NTP Offset per Machine	`ntp_offset_milliseconds`	Time series, threshold line at 10ms
Active Machines	`count(up{job="id-generator"} == 1)`	Gauge
Clock Skew Events (24h)	`increase(clock_skew_detected_total[24h])`	Stat panel (should be 0)

6. System Design Diagrams

6.1 Snowflake Bit Layout

block-beta
    columns 4
    block:header:4
        A["Snowflake ID: 64-bit Layout"]
    end
    block:bits:4
        B["0"]
        C["Timestamp (41 bits)"]
        D["DC(5) + Machine(5)"]
        E["Sequence (12 bits)"]
    end
    block:detail:4
        F["Sign<br/>(always 0)"]
        G["Milliseconds since<br/>custom epoch<br/>(~69.7 years)"]
        H["Datacenter: 0-31<br/>Machine: 0-31<br/>(1,024 nodes max)"]
        I["0-4095 per ms<br/>(4.096M IDs/sec<br/>per machine)"]
    end

    style B fill:#6c757d,color:#fff
    style C fill:#0d6efd,color:#fff
    style D fill:#198754,color:#fff
    style E fill:#dc3545,color:#fff
    style F fill:#6c757d,color:#fff
    style G fill:#0d6efd,color:#fff
    style H fill:#198754,color:#fff
    style I fill:#dc3545,color:#fff

6.2 Multi-Datacenter ID Generation Architecture

graph TB
    subgraph "Client Services"
        SvcA["Order Service"]
        SvcB["User Service"]
        SvcC["Payment Service"]
        SvcD["Inventory Service"]
    end

    subgraph "Load Balancer Layer"
        LB["Load Balancer<br/>(Route to nearest DC)"]
    end

    subgraph "Datacenter 1 (US-East) — dc_id=00001"
        direction TB
        subgraph "ID Generator Cluster DC1"
            M1_1["Machine 1<br/>machine_id=00001<br/>Snowflake Generator"]
            M1_2["Machine 2<br/>machine_id=00010<br/>Snowflake Generator"]
            M1_3["Machine 3<br/>machine_id=00011<br/>Snowflake Generator"]
        end
        NTP1["NTP Server DC1<br/>(Stratum 2)<br/>Sync: time.google.com"]
        ZK1["ZooKeeper Node 1<br/>(Machine ID Registry)"]
    end

    subgraph "Datacenter 2 (EU-West) — dc_id=00010"
        direction TB
        subgraph "ID Generator Cluster DC2"
            M2_1["Machine 1<br/>machine_id=00001<br/>Snowflake Generator"]
            M2_2["Machine 2<br/>machine_id=00010<br/>Snowflake Generator"]
        end
        NTP2["NTP Server DC2<br/>(Stratum 2)<br/>Sync: time.aws.com"]
        ZK2["ZooKeeper Node 2<br/>(Machine ID Registry)"]
    end

    subgraph "Datacenter 3 (AP-Southeast) — dc_id=00011"
        direction TB
        subgraph "ID Generator Cluster DC3"
            M3_1["Machine 1<br/>machine_id=00001<br/>Snowflake Generator"]
            M3_2["Machine 2<br/>machine_id=00010<br/>Snowflake Generator"]
        end
        NTP3["NTP Server DC3<br/>(Stratum 2)<br/>Sync: pool.ntp.org"]
        ZK3["ZooKeeper Node 3<br/>(Machine ID Registry)"]
    end

    subgraph "Monitoring"
        Prometheus["Prometheus<br/>(Metrics Collection)"]
        Grafana["Grafana<br/>(Dashboard)"]
        AlertManager["AlertManager<br/>→ Slack / PagerDuty"]
    end

    SvcA & SvcB & SvcC & SvcD --> LB
    LB --> M1_1 & M1_2 & M1_3
    LB --> M2_1 & M2_2
    LB --> M3_1 & M3_2

    NTP1 -.->|sync| M1_1 & M1_2 & M1_3
    NTP2 -.->|sync| M2_1 & M2_2
    NTP3 -.->|sync| M3_1 & M3_2

    ZK1 -.->|assign machine_id| M1_1 & M1_2 & M1_3
    ZK2 -.->|assign machine_id| M2_1 & M2_2
    ZK3 -.->|assign machine_id| M3_1 & M3_2

    ZK1 <-->|replicate| ZK2 <-->|replicate| ZK3

    M1_1 & M1_2 & M1_3 & M2_1 & M2_2 & M3_1 & M3_2 --> Prometheus
    Prometheus --> Grafana
    Prometheus --> AlertManager

    style M1_1 fill:#0d6efd,color:#fff
    style M1_2 fill:#0d6efd,color:#fff
    style M1_3 fill:#0d6efd,color:#fff
    style M2_1 fill:#198754,color:#fff
    style M2_2 fill:#198754,color:#fff
    style M3_1 fill:#dc3545,color:#fff
    style M3_2 fill:#dc3545,color:#fff
    style NTP1 fill:#f9a825,stroke:#333
    style NTP2 fill:#f9a825,stroke:#333
    style NTP3 fill:#f9a825,stroke:#333
    style ZK1 fill:#6f42c1,color:#fff
    style ZK2 fill:#6f42c1,color:#fff
    style ZK3 fill:#6f42c1,color:#fff
    style Prometheus fill:#e65100,color:#fff
    style Grafana fill:#388e3c,color:#fff

6.3 Clock Sync Flow

sequenceDiagram
    participant AC as Atomic Clock<br/>(Stratum 0)
    participant S1 as NTP Stratum 1<br/>(time.google.com)
    participant S2 as NTP Stratum 2<br/>(DC NTP Server)
    participant IDGen as ID Generator<br/>(Machine)
    participant Mon as Monitoring<br/>(Prometheus)

    Note over AC,S1: Stratum 0 → 1: ~microsecond accuracy
    AC->>S1: Time reference signal

    Note over S1,S2: Stratum 1 → 2: ~millisecond accuracy
    S2->>S1: NTP Request (T1)
    S1-->>S2: NTP Response (T2, T3)
    S2->>S2: Calculate offset<br/>offset = ((T2-T1) + (T3-T4)) / 2

    Note over S2,IDGen: Stratum 2 → 3: ~1-10ms accuracy
    loop Every 16-32 seconds
        IDGen->>S2: NTP Request
        S2-->>IDGen: NTP Response
        IDGen->>IDGen: Adjust clock (slew, not step)
    end

    IDGen->>Mon: Export ntp_offset_ms metric

    alt NTP offset > 10ms
        Mon->>Mon: Fire NTPOffsetHigh alert
        Mon-->>IDGen: Alert → Ops team investigates
    end

    alt Clock goes backward
        IDGen->>IDGen: DETECT: current_time < last_time
        IDGen->>Mon: Increment clock_skew_detected counter
        IDGen->>IDGen: WAIT until current_time >= last_time
        Mon->>Mon: Fire ClockSkewDetected alert
    end

6.4 ID Generation Request Flow

sequenceDiagram
    participant Svc as Client Service
    participant LB as Load Balancer
    participant IDGen as ID Generator<br/>(Machine #5, DC #2)
    participant Clock as System Clock

    Svc->>LB: Request new ID
    LB->>IDGen: Forward to nearest generator

    IDGen->>Clock: Get current_timestamp_ms
    Clock-->>IDGen: timestamp = 1742300000123

    alt timestamp == last_timestamp
        IDGen->>IDGen: sequence++
        alt sequence > 4095 (overflow)
            IDGen->>IDGen: WAIT for next millisecond
            IDGen->>Clock: Get current_timestamp_ms
            Clock-->>IDGen: timestamp = 1742300000124
            IDGen->>IDGen: sequence = 0
        end
    else timestamp > last_timestamp
        IDGen->>IDGen: sequence = 0
    else timestamp < last_timestamp (CLOCK SKEW!)
        IDGen->>IDGen: Log warning + wait
    end

    IDGen->>IDGen: Compose ID:<br/>= (timestamp << 22)<br/>| (dc_id << 17)<br/>| (machine_id << 12)<br/>| sequence

    IDGen-->>LB: Return ID = 7300811265438109697
    LB-->>Svc: ID = 7300811265438109697

    Note over Svc: Extract info from ID:<br/>timestamp: 2025-03-18T12:00:00.123Z<br/>datacenter: 2<br/>machine: 5<br/>sequence: 1

7. Aha Moments & Common Pitfalls

Aha Moments --- Đúc kết

#1 --- Clock skew là điều không thể tránh khỏi trong distributed systems: Không có cách nào đồng bộ hoàn hảo đồng hồ giữa các machine. Snowflake chấp nhận “roughly sorted” thay vì “strictly sorted”. Nếu cần strict global ordering --- dùng Lamport Clock, Hybrid Logical Clock, hoặc Google TrueTime.

#2 --- UUID vs Snowflake không phải chọn 1 bỏ 1: UUID phù hợp cho idempotency key, session ID, correlation ID (không cần sort, không cần compact). Snowflake phù hợp cho primary key, event ID, message ID (cần sort, cần fit 64-bit). Nhiều hệ thống dùng cả hai cho các mục đích khác nhau.

#3 --- DB index performance với random vs sequential IDs: Đây là lý do lớn nhất để không dùng UUID làm primary key trong relational DB. B+ tree index yêu sequential insert --- mỗi record mới append vào cuối leaf node. Random UUID gây page split liên tục, làm giảm write throughput 2-5x và tăng disk I/O.

#4 --- 1 machine Snowflake tạo đủ 4.1M IDs/sec: Throughput không phải lý do deploy nhiều machine. Lý do chính là High Availability --- nếu 1 machine chết, các machine khác vẫn tạo ID bình thường.

#5 --- Custom epoch là quyết định một lần, không thể thay đổi: Chọn epoch sai (quá xa trong quá khứ) = lãng phí bit timestamp. Chọn epoch trong tương lai = ID âm. Chọn epoch = ngày go-live là tốt nhất.

#6 --- Snowflake ID có thể bị reverse-engineer: Bất kỳ ai có ID cũng có thể extract timestamp, datacenter, machine, và sequence. Đừng bao giờ expose Snowflake ID trực tiếp trên public API nếu bạn quan tâm security.

Common Pitfalls --- Sai lầm thường gặp

Pitfall 1: Không xử lý clock skew

Sai: “Đồng hồ máy luôn chính xác, không cần lo.” Đúng: Clock skew LUÔN xảy ra. NTP step, leap second, VM migration, hardware issue --- tất cả đều có thể làm đồng hồ nhảy lùi. Phải có logic detect và handle.

Pitfall 2: Dùng UUID làm primary key rồi thắc mắc sao DB chậm

Sai: “UUID unique, dùng làm PK luôn cho tiện.” Đúng: Random UUID gây B+ tree fragmentation. Nếu phải dùng UUID, dùng UUID v7 (time-ordered) hoặc ULID. Hoặc dùng Snowflake ID làm PK và UUID làm public-facing ID.

Pitfall 3: Hard-code machine_id

Sai: machine_id = 1 trong config file, deploy lên 5 server. Đúng: 5 server cùng machine_id = 1 = duplicate IDs. Phải có cơ chế assign unique machine_id --- ZooKeeper, etcd, hoặc cloud metadata.

Pitfall 4: Không monitor sequence overflow

Sai: “4096 IDs/ms là đủ rồi, không cần lo.” Đúng: Traffic spike, retry storm, hoặc bug có thể gây burst > 4096/ms. Sequence overflow = ID generator phải wait = latency spike. Phải monitor và alert.

Pitfall 5: Quên tính epoch overflow date

Sai: Dùng Unix epoch 1970 cho hệ thống deploy 2025. Đúng: $1970 + 69.73 = 2039$ . Chỉ còn 13 năm! Chọn custom epoch = 2025 để có 69 năm runway.

Pitfall 6: Nghĩ Snowflake đảm bảo global ordering

Sai: “ID lớn hơn = tạo sau, luôn luôn.” Đúng: Chỉ đúng trên cùng 1 machine. Giữa 2 machine khác nhau, clock skew có thể làm ID nhỏ hơn được tạo sau ID lớn hơn. Snowflake chỉ đảm bảo roughly time-sorted, không phải strictly time-sorted.

Pitfall 7: Không có kế hoạch cho sau khi epoch overflow

Sai: “69 năm nữa mới hết, không phải việc của mình.” Đúng: Document rõ overflow date. Đặt calendar reminder. Lên kế hoạch migration: tăng timestamp lên 42+ bit (giảm machine/sequence bits), hoặc chọn epoch mới và migrate.

8. Wrap Up --- Tóm tắt cho Interviewer

Bước	Nội dung chính
Step 1: Scope	64-bit, globally unique, time-sortable, 10K+ IDs/sec, multi-datacenter
Step 2: High-Level	4 approaches: Multi-Master, UUID, Ticket Server, Snowflake (chọn)
Step 3: Deep Dive	Bit layout (1+41+5+5+12), clock sync (NTP), clock skew handling, sequence overflow
Step 4: Wrap Up	Monitoring (clock drift, overflow), Security (ID enumeration), Alternatives (ULID, KSUID)

Interview tip: Khi interviewer hỏi “Design a Unique ID Generator”, họ muốn nghe:

Bạn hỏi câu hỏi để làm rõ requirements (không nhảy vào Snowflake ngay)
Bạn trình bày nhiều options rồi chọn có lý do
Bạn hiểu trade-offs (clock skew, ordering guarantees, security)
Bạn biết vận hành hệ thống (monitoring, alerting, NTP)

9. Internal Links --- Liên kết nội bộ

Topic	Link	Liên quan
Scaling	Tuan-01-Scale-From-Zero-To-Millions	Tại sao cần distributed ID khi scale
Capacity Estimation	Tuan-02-Back-of-the-envelope	Công thức IDs/sec, overflow calculation
Database Sharding	Tuan-07-Database-Sharding-Replication	ID làm shard key, sequential vs random impact
Consistent Hashing	Tuan-10-Consistent-Hashing	Phân phối ID generation across nodes
Monitoring	Tuan-13-Monitoring-Observability	Clock drift monitoring, alerting
Security	Tuan-14-AuthN-AuthZ-Security · Tuan-15-Data-Security-Encryption	ID enumeration, information leakage
URL Shortener	Tuan-16-Design-URL-Shortener	Snowflake ID dùng làm base cho short code
Key-Value Store	Tuan-20-Design-Key-Value-Store	ID làm key trong distributed KV store

Tham khảo

Alex Xu, System Design Interview --- Chapter 7: Design a Unique ID Generator in Distributed Systems
sdi.anhvy.dev --- Vietnamese System Design Reference
Twitter Snowflake (GitHub) --- Original Snowflake implementation
Announcing Snowflake (Twitter Engineering Blog, 2010)
Discord Snowflake IDs --- Discord’s Snowflake variant
Instagram Sharding & IDs --- Instagram’s ID generation
ULID Spec --- Universally Unique Lexicographically Sortable Identifier
KSUID (Segment) --- K-Sortable Unique Identifier
Baidu uid-generator --- Baidu’s Snowflake variant
Sony Sonyflake --- Sony’s Snowflake variant (focus on machine ID from IP)
NTP RFC 5905 --- Network Time Protocol v4
Google TrueTime (Spanner Paper) --- Globally-consistent distributed database

Case Study liên quan: Tuan-16-Design-URL-Shortener (Snowflake ID dùng để tạo short code) · Tuan-20-Design-Key-Value-Store (ID làm key trong distributed store)

lthieu's notes

Explorer

Case-Design-Unique-ID-Generator