Cruxly › System design › Design Exercises

Distributed ID Generator

unique, roughly sortable IDs from machines that can't coordinate

Prompt: design a service that generates unique 64-bit IDs for rows across a fleet of database shards — no two generators, anywhere, ever produce the same ID, and a generator can issue thousands of IDs per second with no coordination call to any other generator or a central authority.

40 minutes first. This is a short exercise with one real idea in it — resist the urge to pad it with unrelated scope.

Applying the four moves: Scope — unique 64-bit IDs, thousands per second per generator, no coordination calls; global strict ordering out (and say why it's out). Estimate — the bit budget is the estimate: how many bits for timestamp, how many for generator ID, how many for a per-millisecond sequence, and how long the timestamp range lasts before it wraps. Sketch — a Snowflake-style layout where uniqueness comes from the structure of the ID itself, not from asking anyone. Deep dive — clock skew and clocks moving backwards: the generator has to detect it and refuse to issue IDs rather than silently produce duplicates.

Why auto-increment and random UUIDs both fail here

Auto-increment breaks the moment there's more than one writer. Two shards, each with their own auto-increment counter, will both produce id=4001 independently — coordinating a single global counter across shards means every insert on every shard now waits on one shared piece of state, which defeats the entire point of sharding for write throughput.

A random UUID (v4) solves uniqueness perfectly and throws away everything else. 128 bits of randomness collide with negligible probability, no coordination needed — but the IDs are completely unordered. An index built on a random UUID primary key gets random-order inserts forever, which is measurably worse for B-tree page locality (see this track's indexing exercise) than an ID that at least roughly increases over time. Many real systems specifically want "insert into the index is mostly append-only," which random UUIDs actively defeat.

The actual requirement is uniqueness with no coordination, plus rough time-ordering. Twitter's Snowflake design (and its many descendants: Sonyflake, Instagram's scheme, Discord's) answers exactly this by putting structure into the bits instead of relying on either pure sequence or pure randomness.

The bit layout, and why each field is sized the way it is

Every field's width is a deliberate trade against a concrete limit: how long the ID scheme lasts, how many generators can run at once, and how many IDs one generator can mint in a single millisecond.

41 bits of timestamp, milliseconds since a custom epoch (not the Unix epoch — starting the count at the service's own launch date roughly doubles the useful range before the field overflows) gives about 69 years of range, which is "solved for the career lifetime of this service."

10 bits of machine/worker ID allows 1,024 concurrent generators, each assigned a unique ID at startup — typically from a small coordination service (ZooKeeper, etcd, or even a row claimed in a database table) at process startup only, not per-request, which is the key detail: the one coordination point in the whole design happens once per generator's lifetime, not once per ID minted.

12 bits of per-millisecond sequence lets a single generator mint 4,096 IDs within the same millisecond before it has to either wait for the clock to tick forward or (in stricter implementations) reject requests briefly. 4,096/ms per machine, times 1,024 machines, is over 4 billion IDs/second of theoretical ceiling — nowhere near a real bottleneck at any plausible scale.

The one coordination point, and the one real failure mode

Startup-time machine-ID assignment is the only place this design touches shared state, and it only has to happen once per process lifetime, which is why it doesn't undermine the "no coordination per ID" claim. A simple approach: each generator process, on boot, atomically claims the next free integer from a small table (UPDATE machine_ids SET claimed=1 WHERE id = (SELECT id FROM machine_ids WHERE claimed=0 LIMIT 1) RETURNING id) — the same find-and-claim atomic UPDATE pattern used for the parking lot and job scheduler exercises elsewhere in this track, just claiming an integer instead of a resource.

Clock skew and, worse, clock rollback are the real failure mode. If a generator's system clock is corrected backward (NTP adjustment, VM migration, manual fix) and the generator's next timestamp would be earlier than its last emitted timestamp, IDs would stop being even roughly ordered, and in the worst case a sequence-number collision at the same timestamp with different real order becomes possible. The fix is to never emit an ID with a timestamp older than the last one this process emitted — if the clock appears to have gone backward, either wait until real time catches up to the last-used timestamp, or (for a small, bounded rollback) fall back to an error and let the caller retry, rather than silently emitting a timestamp that lies about ordering.

A generator process restarting loses its in-memory 'last timestamp' state, which is fine for correctness (starting fresh with the current real time is safe) but means a restart cannot itself detect a clock rollback that happened while it was down — persisting the last-used timestamp to local disk on every ID mint (or at least periodically) closes that gap, at a small write-throughput cost that is worth it for a service whose entire purpose is not lying about ordering.

How to say it in the interview

"A database auto-increment column doesn't survive sharding, and a random UUID doesn't survive anyone wanting the IDs to sort roughly by time — the interesting part is a bit-layout that gets uniqueness, rough time-ordering, and zero coordination all from the same 64 bits."

Checklist

Rejected auto-increment because it re-introduces a single point of write coordination across shards
Rejected pure random UUIDs because they destroy index insert locality
Put the timestamp in the highest bits so the ID sorts roughly by creation time with no lookup
Sized the machine-ID field around a concrete ceiling — 1,024 concurrent generators
Restricted the one coordination point to startup-time machine-ID assignment, not per-ID minting
Identified clock rollback, not clock skew alone, as the real failure mode
Refused to emit a timestamp older than the process's own last-emitted timestamp
Persisted the last-used timestamp so a process restart can still detect a rollback that happened while it was down

Practice this interactively