System Design · Design Question
Design a Unique ID Generator
Mint IDs at high QPS: UUID, ticket servers, Snowflake-style bits, and multi-DC concerns.
1. Requirements
- IDs unique globally (no collisions across services/DCs).
- High throughput (e.g. 10k–100k+/s).
- Low latency; preferably numeric 64-bit for DB indexes.
- Optional: roughly time-ordered for locality / sorting.
- Optional: opaque (hard to guess next ID).
Ask: 64-bit vs 128-bit? sortable? multi-region? guessable OK?
2. API
GET /v1/ids?count=1
→ { "ids": ["123456789012345678"] }
POST /v1/ids/batch { "count": 100 }
→ { "ids": [...] }
gRPC: IdService.NextId / NextIds
3. Options compared
| Approach | Pros | Cons |
|---|---|---|
| DB auto-increment | Simple, numeric | Single primary bottleneck; multi-DC hard |
| UUID v4 | No coordination | 128-bit, random → index fragmentation |
| UUID v7 / ULID | Time-ordered, decentralized | Still 128-bit |
| Ticket server (Flickr-style) | Numeric, simple | SPOF unless ticket range allocation; not time-sortable by itself |
| Snowflake | 64-bit, sortable, high QPS | Needs worker/DC IDs + clock discipline |
4. Snowflake deep dive (interview default)
64 bits:
[ 1 sign bit = 0 ][ 41 timestamp ms ][ 5 DC ][ 5 worker ][ 12 sequence ]
41-bit ms ≈ 69 years from epoch
12-bit seq ≈ 4096 IDs / ms / worker
Worker ID from config / ZooKeeper / long-lived lease
- Same millisecond → bump sequence; overflow → wait next ms.
- Clock skew backward → refuse or wait (do not mint duplicates).
- Assign worker IDs uniquely; recycle carefully after long downtime.
5. High-level design
App servers → Id Service fleet (stateless logic + worker identity)
|
+-- each instance has unique worker_id
+-- NTP / chrony for clocks
+-- optional: etcd stores worker leases
Multi-DC: embed datacenter_id in the bit layout
6. Ticket server / range allocation
Central store: UPDATE tickets SET next = next + 1000 WHERE name='order'
Returns range [n, n+1000) to an app node
Node mints locally until range exhausted → fewer round trips
Survives better than one-row-per-ID. Still need HA for the ticket table and accept gaps on crash (OK for most products).
7. Data model
Generator itself may be mostly stateful in memory. Persist only worker leases / ticket high-water marks:
workers(worker_id PK, dc, lease_until, host)
tickets(name PK, next_value)
8. Scaling and failure
- Scale QPS by adding workers (more sequence space per ms globally).
- Worker death: IDs in its space stop; no collision if IDs not reused early.
- Do not silently reuse worker_id while old process might still be alive.
9. What to recommend
“For 64-bit sortable IDs at scale: Snowflake with DC+worker bits and clock safeguards. For zero coordination: UUIDv7. For simple monoliths: DB sequence or ticket ranges.”
Quick revision
- Clarify bit width, sortability, and multi-DC needs first.
- UUID: easy, not ideal for fat B-tree indexes if random.
- Snowflake: time | DC | worker | sequence — interview classic.
- Guard against clock rollback and sequence overflow.
- Ticket ranges reduce coordination vs per-ID DB hits.
- Worker ID uniqueness is a correctness requirement.
- Gaps on crash are usually acceptable; collisions are not.