Unique ID Generator

Snowflake-style distributed IDs: time-ordered, unique, and generated without a single counter.

• Advanced
• 35 min read
• 3 objectives

Before this lessonLesson 4: Queues, APIs and Reliability

Almost every product in this course needs unique IDs: posts, orders, short-URL codes, chat messages. The design problem is: generate billions of IDs per day, from many machines, with low latency, and keep them unique even when a box crashes.

Step 1 — Clarify the problem

Do not jump to a bit layout. Spend the first minutes locking constraints. Ask:

• Must IDs be unique only, or also roughly sorted by time?
• 64-bit (fits a SQL bigint) or is 128-bit acceptable?
• Numeric only, or can they be strings (UUID)?
• How many IDs per second, peak vs average? Multi-datacenter?
• Are IDs public (in URLs)? If yes, they should not leak create-time or machine id, and should not be guessable in order.

Assumptions we will design for: globally unique 64-bit integers, roughly time-ordered so new rows append in a B-tree, 10k–100k IDs/sec, generated in several datacenters, no extra network hop on the hot path. If the interviewer wants opaque public tokens, we mint an internal id and map it.

Step 2 — Options and why most of them fail

Auto-increment in one database

A single primary that does INSERT … RETURNING id is unique and ordered. It is also a single point of failure and a write bottleneck. Two primaries collide unless you use odd/even increments, which still couples you to that pair. Fine for a prototype; not a distributed answer.

UUID v4

128 random bits, no coordinator, trivial to generate anywhere. Downsides: twice the storage of a bigint, not time-ordered, random inserts scatter a clustered index and bloat pages. Fine as an internal opaque key. Poor as the only clustered primary in a large MySQL table of events.

Ticket server (range allocator)

A small service (or a SQL table) hands out blocks: “you own 1_000_000–1_001_000”. Each app process then increments locally. Unique, no collisions, one extra RPC per block instead of per ID. You lose strict time order across servers. The ticket service must be highly available — replicate it, and cache a block so a blip does not stall writes.

flowchart LR App1[App server] -->|get block of 1000| T[Ticket service] App2[App server] -->|get block of 1000| T T --> DB[(Counter table)] App1 --> Local[Hand out ids in memory]

Apps pay a network round trip only when a block is empty. The counter table is tiny and easy to replicate.

Step 3 — Snowflake-style 64-bit IDs

The usual pick when you need 64-bit, time-ordered IDs with no coordinator on the hot path. Pack the integer like this:

• 1 unused sign bit (keep IDs positive)
• 41 bits of milliseconds since a custom epoch (~69 years)
• 10 bits of worker id (for example 5 bits datacenter + 5 bits machine = 1024 workers)
• 12 bits of per-worker sequence (4096 IDs per millisecond per worker)

EPOCH = 1704067200000  # 2024-01-01 UTC in ms
WORKER_ID = 17

_last_ms = 0
_seq = 0

def next_id(now_ms: int) -> int:
    global _last_ms, _seq
    if now_ms == _last_ms:
        _seq = (_seq + 1) & 0xFFF
        if _seq == 0:
            now_ms += 1          # sequence overflow: wait next ms
    else:
        _seq = 0
    _last_ms = now_ms
    ts = now_ms - EPOCH
    return (ts << 22) | (WORKER_ID << 12) | _seq

sid = next_id(1_735_000_000_000)
print(sid)
print("time ms", sid >> 22, "worker", (sid >> 12) & 0x3FF, "seq", sid & 0xFFF)
print("capacity ids/sec", 1024 * 4096 * 1000)

129741566771269632
time ms 30932800000 worker 17 seq 0
capacity ids/sec 4194304000

Capacity: 1024 workers × 4096 seq × 1000 ms ≈ 4 billion IDs/sec on paper. In practice you are far below that; the number shows you will not run out of sequence bits.

flowchart LR API[App] --> W1[ID worker 17] API --> W2[ID worker 18] W1 --> Reg[Worker-id registry] W2 --> Reg

Each process holds a unique worker id. Minting is a few bit shifts in memory — no database round trip.

Step 4 — Deep dives

Clock skew

NTP can jump the clock backwards. If now_ms < last_ms, refuse to mint (throw) or wait until the clock catches up. Some systems persist last_ms on disk so a restart cannot rewind. Do not generate IDs from a clock you do not trust in a VM without this check.

Assigning worker ids

Ids must stay unique across restarts. Options: etcd/ZooKeeper leases, a small SQL table of (worker_id, hostname, heartbeat), or config. A box that dies and comes back must not reuse a worker id until the clock-skew window has passed, or two workers could emit the same (time, worker, seq) triple.

Sequence overflow

If one worker mints more than 4096 IDs in the same millisecond, wait for the next millisecond (or steal from the next ms as in the snippet). This is rare at human-facing QPS and common in a tight loop — mention it.

Public IDs

The layout leaks create time and datacenter. If IDs appear in URLs, either encrypt/permute the 64 bits, or keep Snowflake internal and expose a separate random public token with a unique index.

Step 5 — What to pick in the room

• Time-ordered 64-bit, high QPS → Snowflake-style, then clock skew + worker registry.
• Opaque codes (URL shortener, paste ids) → random or ticket-range + base62, uniqueness via the database.
• Low QPS internal rows → UUID v4 is honest and simple; say why you would not cluster on it.

// Write your solution here