Design a distributed unique ID generator
You have 64 bits and a fleet of machines that don't trust each other's clocks. Every requirement — ordering, sharding, scale, privacy, recovery — is a fight over how you spend those bits. The design is a contract hidden inside a number.
1. The bit budget — the load-bearing arithmetic
Start here, because every later decision is just a consequence of this division. Twitter's Snowflake spends 64 bits like this:
Add them up out loud: 1 + 41 + 10 + 12 = 64 bits. The sign bit is held at 0 so the value is always a positive int64 — that matters because it slots into a standard signed BIGINT column without games. Now turn each field into a capacity number, because those numbers are the design constraints:
- Timestamp — 41 bits of milliseconds = lifespan. 2^{41} = 2{,}199{,}023{,}255{,}552 ms. Divide by ms/year: 2^{41} / (1000 \cdot 60 \cdot 60 \cdot 24 \cdot 365) \approx 69.7 years. So a 41-bit timestamp buys you ~69.7 years of IDs counted from your custom epoch, not from 1970 — picking a recent epoch (say 2020-01-01) is what claws those years back from Unix time.
- Sequence — 12 bits = burst per worker per ms. 2^{12} = 4096 IDs per worker per millisecond. That is the per-worker ceiling inside one tick of the clock.
- Worker — 10 bits = fleet size. 2^{10} = 1024 distinct workers can coexist without ever colliding.
Multiply the last two for the theoretical ceiling: 4096 \text{ IDs/ms/worker} \times 1024 \text{ workers} = 4{,}194{,}304 IDs per millisecond, i.e. ~4.2 billion IDs/ms, or ~4.2 trillion IDs/second fleet-wide. That number is comically large on purpose — it tells you the design is never globally bottlenecked. The bottleneck is always local, and that is the next paragraph.
(timestamp, worker, sequence) triple — that is a silent duplicate. Choosing (a) vs (b) is a back-of-envelope decision driven entirely by your real peak throughput per worker.2. Clarify the contract
Treat the prompt as a product contract before a box diagram. What it must do:
- Uniqueness across machines and regions — the one non-negotiable.
- No central per-ID round trip — generation must be local and survive partial outages.
- Fit a 64-bit integer field — so it indexes and stores like any BIGINT key.
- Roughly time-sortable — k-sorted, not strictly monotonic, is the usual ask.
And — just as important in an interview — what it need not do:
- Not strict global total order. Two IDs minted in the same millisecond on two workers have no defined order between them. If you genuinely need a single linear sequence, that is a consensus/sequencer problem (lesson 10), not an ID generator — say so explicitly.
- Not unguessable. A decodable Snowflake ID is the opposite of a secret (see deep dive 2). If you need opacity, that's a different requirement and a different design.
- Not gapless. Blocking on sequence overflow and discarding sequence numbers on a clock tick both leave gaps. Gaps are fine; duplicates are fatal.
3. Define the surface area
Keep the API tiny. It should express the operation, not leak the bit layout.
| API / operation | Why it exists |
|---|---|
next_id() -> int64 | The hot path. Local, lock-light, no network. Returns a packed 64-bit ID. |
reserve_worker_id(host) -> worker_id | Called once at boot. Leases a unique worker ID from the registry — the single point where coordination happens (lesson 10). |
decode(id) -> (timestamp, worker, sequence) | Unpacks the fields. Useful for debugging and sharding — and the source of the privacy leak in deep dive 2. |
4. Model the data
The state is deliberately minimal. Per-worker, in memory, the generator holds only: the worker ID (leased at boot), the last timestamp it emitted (to detect rollback and ms-rollover), the sequence counter for the current ms, and the custom epoch constant. The only shared, durable state is the worker-ID registry — and that is exactly where the consistency requirement concentrates.
5. Linearized design — follow one next_id()
Walk the design in the order a single call actually executes. The bottleneck exposes itself at step 4.
- At boot: the worker calls
reserve_worker_id()and leases a 10-bit ID from a strongly consistent registry (ZooKeeper/etcd). The lease is fenced (lesson 10) so a hung-then-resumed worker can't keep using a reassigned ID. - Read the clock:
now = current_millis(). - Rollback guard: if
now < last_timestamp, the clock went backward — do not emit. Wait, or fail. (Deep dive 1; this is the whole point of the case.) - Sequence step: if
now == last_timestamp, incrementsequence. If that overflows 4096, busy-wait to the next millisecond and reset the sequence — the local bottleneck from §1. Ifnow > last_timestamp, resetsequence = 0. - Pack:
id = ((now - epoch) << 22) | (worker_id << 12) | sequence. Updatelast_timestamp. Return.
6. The allocator — trading bits across requirements
There is no universal split. The "right" layout is whichever survives your worst-case peak throughput and your fleet size and your required lifespan. Read this table as: pick the row whose three capacity numbers all clear your requirements; the flagged rows are where a target throughput overflows the sequence budget and forces blocking.
| Bit split (ts / worker / seq) | Lifespan | Max workers | IDs / ms / worker | Verdict |
|---|---|---|---|---|
| 41 / 10 / 12 (classic Snowflake) | ≈ 69.7 yr | 1024 | 4096 | The default. Balanced; fine until one worker peaks > 4096/ms. |
| 41 / 13 / 9 | ≈ 69.7 yr | 8192 | 512 | Huge fleet, but 512/ms/worker overflows easily — blocks under any real burst. |
| 41 / 8 / 14 | ≈ 69.7 yr | 256 | 16384 | Few, very hot workers. Absorbs the 5000/ms case with headroom. |
| 39 / 10 / 13 | ≈ 17.4 yr | 1024 | 8192 | Buy burst capacity by spending lifespan. Clears 5000/ms; re-epoch in ~17 yr. |
| 42 / 12 / 9 | ≈ 139 yr | 4096 | 512 | Long life + big fleet, starved sequence — overflows at > 512/ms. |
Concretely: the 5000-IDs/ms hot worker from §1 fails on rows 1, 2 and 5 (it exceeds 4096, 512, 512) and must block. It passes on rows 3 and 4. Row 4 is the instructive trade: spending 2 timestamp bits drops lifespan from 69.7 to ~17.4 years but doubles per-worker burst to 8192/ms — a deliberate exchange of future capacity for present throughput. There is no free lunch; 64 bits is a zero-sum budget.
7. Deep dives
7.1 The clock is part of correctness — what happens on NTP step-back
A time-ordered ID generator is a distributed system, because clocks lie. This is DDIA Ch. 8's core warning: the time-of-day clock (the wall clock NTP disciplines) can jump backward when NTP corrects drift, and a VM resumed from a pause/migration can see time leap or — worse for us — appear to stall and then jump. If now ever goes backward and we naively keep packing IDs, we can re-mint a (timestamp, worker, sequence) triple that already exists → a duplicate primary key, the one failure the whole design exists to prevent.
The disciplines, in order of preference:
- Read a monotonic clock for the rollback guard. DDIA Ch. 8 distinguishes time-of-day from monotonic clocks, which only ever move forward. Compare against a monotonic source so a wall-clock correction can't fool the guard. (You still encode wall-clock ms in the ID for human-readable timestamps, but you gate on monotonic time.)
- On a small backward step: wait it out. If
now < last_timestampby a few ms, busy-wait until the clock catches back up tolast_timestamp, then resume. Costs a little latency, risks zero duplicates. - On a large step or sustained skew: refuse and alert. If the gap is large (seconds), don't burn CPU waiting — fail
next_id()loudly and let the worker be pulled from rotation. A brief generation outage is recoverable; a duplicate ID is forever. - Advanced: a reserved drift bucket. Some designs steal a high sequence bit or a dedicated field as a "this ID was minted during a known clock anomaly" namespace, preserving uniqueness without waiting. More machinery; only worth it if even brief stalls are unacceptable.
7.2 Decodable IDs leak time and region
The very property that makes Snowflake nice — decode(id) hands you creation time and worker/region — is an information leak when the ID is public. Two concrete leaks: (1) the timestamp bits expose exactly when a record was created — scraping the IDs of new signups reveals your growth rate and signup timing to a competitor (the classic "enumerate user IDs to estimate company size" attack); (2) the worker bits can encode which datacenter/region served the request. For internal IDs this is a debugging gift. For IDs exposed in URLs it is a business-intelligence and privacy gift to outsiders. The honest options: keep Snowflake IDs internal and hand out a separate opaque public handle, or accept the leak when it doesn't matter (most internal records).
7.3 UUIDv4 vs UUIDv7 — the index-locality argument
The reflexive alternative is "just use UUIDs, no coordination at all." That works for uniqueness but collides head-on with how databases store primary keys. UUIDv4 is 122 random bits: consecutive inserts land at random positions in a clustered B-tree index, so the working set of dirty index pages is huge, page splits are frequent, and write throughput craters. (DDIA Ch. 3: B-tree writes love locality; random keys are the pathological anti-pattern.) Snowflake's high-bit timestamp gives the opposite — near-sequential inserts that append to the right edge of the tree, hot in cache. UUIDv7 is the modern compromise: a 48-bit Unix-ms timestamp prefix + random tail, so it is time-sortable like Snowflake (good B-tree locality, k-sorted) yet needs no worker-ID coordination at all — the random bits handle uniqueness probabilistically. The price is 128 bits instead of 64 (bigger keys, bigger indexes) and no clean decode of worker/region. If you can afford 128-bit keys and want zero coordination, reach for UUIDv7; if you need 64-bit keys or want decodable region bits, Snowflake earns its complexity.
8. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Central allocator vs local generator | simple, strict global ordering | availability bottleneck + per-ID round trip | small systems with a true total-order need |
| Random UUIDv4 vs time-sortable (Snowflake / UUIDv7) | zero coordination, no clock dependency | index-locality loss, no ordering, 128-bit keys | fully decentralized external identifiers where DB locality is irrelevant |
| More worker bits vs more sequence bits | larger fleet | lower per-worker burst (overflow → blocking) | many small, low-burst generators |
| Opaque ID vs decodable ID | privacy (no time/region leak) | loses debugging + sharding-by-time value | public URLs and enumerable resources |
The sharpest of these is the first. A central allocator (a single counter, or a DB sequence) is seductively simple and gives strict monotonic order — but it puts a network round trip and a SPOF on the hot path of every single insert in your system. The Snowflake bet is to trade strict ordering for availability: accept that two IDs in the same ms across workers are unordered, in exchange for a generator that never makes a network call on the hot path and survives the registry being down (you only need it at boot). That is the same availability-vs-coordination tension as lesson 09's CAP discussion, applied to a 64-bit integer.
9. Failure modes
| Failure | Mitigation |
|---|---|
| Duplicate worker IDs (two boxes lease the same ID) | Lease worker identity from a strongly consistent registry (etcd/ZK) and fence expired leases (lesson 10) so a resumed-after-pause worker can't reuse a reassigned ID. |
| Clock rollback (NTP step-back, VM resume) | Gate on a monotonic clock; on small step wait it out, on large step refuse + alert. Never emit while now < last_timestamp. |
| Sequence overflow (> 4096/ms on one worker) | Busy-wait to the next millisecond and reset sequence; or re-allocate bits (§6) for permanently hot workers. |
| Hot DB inserts (right-edge contention) | Time-ordered IDs are intentionally right-heavy — good for locality, bad for write-hotspotting one shard. Add a shard-suffix or hash-prefix when write throughput on the newest partition saturates. |
10. Interview prompts you should be ready for
- NTP steps the clock backward 50 ms — what does your generator do? (senior answer) It must never emit while
now < last_timestamp, because that risks re-minting a(ts, worker, seq)triple — a duplicate. For a 50 ms step I busy-wait until the monotonic clock catches back up tolast_timestamp, then resume; a brief generation stall is fine. For a large jump I refuse and alert rather than spin. The guard should compare against a monotonic clock (DDIA Ch. 8), not the wall clock NTP just corrected, so the correction can't fool it. Optionally a reserved drift-bucket bit preserves uniqueness without waiting. - Walk me through the bit budget. (senior answer) 1 sign + 41 timestamp + 10 worker + 12 sequence = 64. 2⁴¹ ms ≈ 69.7 years from a custom epoch; 2¹² = 4096 IDs/ms/worker; 2¹⁰ = 1024 workers; product ≈ 4.2 billion IDs/ms fleet-wide. The fleet number is irrelevant — the real ceiling is 4096/ms on a single hot worker.
- One worker needs 5000 IDs in a millisecond. Now what? (senior answer) 5000 > 4096, so the sequence field overflows. Either block — spin to the next ms and reset sequence, smearing the burst across 2 ms — or re-allocate bits (e.g. 39/10/13 gives 8192/ms at the cost of dropping lifespan to ~17 yr). I'd never wrap and reuse a sequence value; that's a silent duplicate.
- Why not just use UUIDv4 everywhere? (senior answer) Uniqueness is free, coordination is zero — but 122 random bits scatter clustered-B-tree inserts (DDIA Ch. 3), causing page splits and tanking write throughput, and they're not sortable. UUIDv7 fixes both with a time prefix and still needs no coordination, at the cost of 128-bit keys. Snowflake wins when you need 64-bit keys or decodable region bits.
- How are worker IDs assigned without collisions? (senior answer) Lease them from a strongly consistent registry (etcd/ZooKeeper) at boot, with a fencing token (DDIA Ch. 9 / lesson 10). The fence is the subtle part: a worker that pauses past its lease, then resumes, must be prevented from using the ID that's since been reassigned — otherwise two boxes share a worker ID and collide.
- What does a public Snowflake ID leak? (senior answer) Creation time (timestamp bits) and often region/datacenter (worker bits). Enumerating signup IDs reveals growth rate and timing to competitors. If IDs are public and that matters, mint internal Snowflakes but expose a separate opaque handle.
- Is this strictly monotonic / a total order? (senior answer) No — it's k-sorted. Two IDs minted in the same ms on different workers have no defined order. If you need a true global total order, that's a sequencer/consensus problem (lesson 10), not an ID generator; conflating the two is a common mistake.
Related foundation lessons
This case leans on three foundations. The worker-ID assignment is the textbook use of lesson 10 (consensus & coordination) — a strongly consistent registry plus fencing tokens (DDIA Ch. 9) to stop a paused-then-resumed worker reusing a reassigned ID. The reason we want time-sortable IDs at all is lesson 04's (data modeling & storage) B-tree write-locality argument (DDIA Ch. 3): sequential keys append to the index's hot right edge, random keys (UUIDv4) thrash it. And the flip side — time-ordered keys concentrating writes on the newest partition — is exactly lesson 07's (partitioning) hot-shard problem, which a shard-suffix mitigates. The decode/clock discipline draws on DDIA Ch. 8 (unreliable clocks; monotonic vs time-of-day).