System Design · Design Question

Design a Unique ID Generator

Mint IDs at high QPS: UUID, ticket servers, Snowflake-style bits, and multi-DC concerns.

In simple words: Create different IDs without one database bottleneck. Snowflake combines time, machine identity, and a small counter into one sortable number.

Concrete example: Twitter's Snowflake ID might encode timestamp + datacenter + machine + sequence into one 64-bit number — sortable by time, unique across thousands of machines, no central DB sequence.

1. Requirements

Functional

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).

Non-functional

Generate IDs in microseconds without one central database hop.
Continue in multiple regions without collisions.

Back-of-envelope

100k IDs/s ≈ 8.64B IDs/day. A 12-bit sequence allows 4,096 IDs/ms/worker, so 25 busy workers already provide roughly 100M IDs/s of theoretical sequence space.

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.”

10. Edge cases

Clock moves backward → pause, use a logical clock, or fail safely; never reuse a timestamp/sequence pair.
Sequence fills within one millisecond → wait for the next millisecond.
Two live workers receive the same worker ID → fencing token or lease prevents split-brain generation.

Interview talking points

Lead with: Ask about bit width, ordering, opacity, and regions before choosing Snowflake.
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.