System design deep dive · HLD
Design a Distributed Unique ID Generator (Snowflake-style): full high-level design.
Requirements, back-of-envelope capacity estimation from a real 64-bit layout, a high-level design diagram, a deeper deployment architecture diagram with worker-ID coordination via etcd, sequence diagrams for worker startup and ID generation (including a clock-rollback scenario), and an entity-relationship diagram for the audit side of the system - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
A strong system design answer starts by pinning down scope out loud. For a distributed ID generator, that means separating "generate a unique number" (trivial with one database) from "generate a unique number without any single centralized component on the hot path, across thousands of instances, in multiple datacenters, without ever going backwards" - which is the actual hard problem.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
Everything downstream - how many bits go to the worker ID, how many workers the system can ever support, and whether 2 million IDs/sec is even reachable - falls out of one design choice: the 64-bit layout. This is the classic Twitter Snowflake split: 1 unused sign bit, 41 bits of millisecond timestamp, 10 bits of worker ID, 12 bits of per-millisecond sequence.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Bit layout | 1 sign (unused) + 41 timestamp + 10 worker + 12 sequence | 64 bits total, fits a signed long with room to spare |
| Timestamp range | 41 bits, milliseconds since a custom epoch | 2^41 ms ≈ 69.7 years of range before rollover |
| Worker ID space | 10 bits (5 datacenter + 5 machine) | 2^10 = 1,024 unique workers system-wide |
| Sequence space | 12 bits, resets to 0 every millisecond | 2^12 = 4,096 IDs per worker per millisecond |
| Per-worker max throughput | 4,096 IDs/ms × 1,000 ms/sec | 4,096,000 IDs/sec per worker - a ceiling, never actually approached |
| Theoretical system ceiling | 1,024 workers × 4.096M IDs/sec | ≈4.19 billion IDs/sec - purely theoretical, not the design target |
| Real target peak | Order creation, chat messages, payment events combined | ≈2 million IDs/sec system-wide at peak |
| Active worker pool | Sized for the real target, not the theoretical ceiling | ~200-400 active workers day-to-day, leaving headroom under the 1,024 cap |
3. High-level design (HLD)
The HLD names the major components and draws a hard line between the ID-generation hot path (in-process, per request) and the coordination/control-plane path (touched only at worker startup and on a heartbeat) - that separation is the single most important idea in this design.
What each box owns
Calling services + embedded ID client library
Each service instance (order, chat, payment, ...) links the ID-generation client as a library, not a network call. generateId() executes entirely in-process, which is what makes sub-millisecond p99 latency possible - there's no RPC, no serialization, and no shared network service that could become a bottleneck.
Local clock + in-memory sequence state
Every generated ID reads the local system clock against an in-process last_timestamp and sequence counter. Both are volatile, worker-local state - never shared across processes - which is exactly why two workers can never produce the same ID as long as their worker ID bits differ.
Worker Coordination Service (etcd/ZooKeeper)
Touched exactly once at startup (to acquire a worker ID via a lease or sequential znode) and periodically thereafter only to renew that lease with a heartbeat. It is never on the per-ID hot path, so an etcd outage does not stop already-running workers from generating IDs - it only blocks brand-new workers from starting up.
Worker Registry (control-plane audit DB)
A relational table populated by the coordination layer whenever a lease is granted, renewed, or expires. It exists purely so humans and dashboards can answer "which host holds worker ID 217 right now, and since when?" - the generator itself never reads or writes it during ID generation.
4. Detailed architecture diagram
The architecture diagram answers "how is worker-ID coordination actually deployed, and what happens when a clock drifts?" - the two questions that separate a candidate who has memorized "Snowflake" as a buzzword from one who has actually thought through the failure modes.
| Decision | Choice | Reasoning |
|---|---|---|
| Worker-bit split | 5 bits datacenter + 5 bits machine (10 bits total) | Caps workers at 1,024 systemwide but lets each datacenter assign its own machine IDs independently, with no cross-DC coordination needed on every startup. |
| Coordination store | etcd (Raft) deployed per region, not one global cluster | A regional outage only stalls new worker registrations in that region; already-running workers keep generating IDs locally with zero runtime dependency on etcd. |
| Lease TTL & heartbeat | 15s TTL, heartbeat every 5s | Short enough that a crashed worker's ID is reclaimed within seconds; long enough that a brief network blip doesn't cause false reclamation while the worker is still alive. |
| Clock-rollback response | Block briefly for small drift; reject and page for large drift | Blocking a few milliseconds is invisible at p99, but silently continuing past a large rollback risks a duplicate or out-of-order ID - which is worse than a visible error. |
5. Sequence diagrams for the two critical flows
A sequence diagram is where an interviewer checks whether you actually understand what happens once, at startup, versus what happens on every single request - and whether you've thought through the clock-rollback branch instead of hand-waving past it.
5.1 Worker startup and worker-ID registration
Step 4 is drawn as a dashed, fire-and-forget arrow because writing the audit record must never block the worker from becoming ready - the Worker Registry is for observability, not correctness. Step 5's heartbeat loop is the only ongoing dependency on etcd after startup, and it runs on a background thread, never in the same call path as generateId(). Step 7 is why a worker ID is never assigned to two hosts at once: if a worker dies without renewing, etcd expires its lease and only then is worker_id 217 eligible to be handed to a new host.
5.2 ID generation request, including a clock-rollback scenario
Steps 4a/5a are the overwhelming majority case: the local clock has moved forward (or stayed within the same millisecond), so the client either resets the sequence to zero on a new millisecond or increments it, composes the three fields with two bit-shifts, and returns - no I/O, no branch to any external system. Step 4b is the branch that matters: if now is ever behind last_timestamp, the client refuses to generate an ID rather than risk emitting one that collides with or precedes an ID it already handed out. A small drift (a few milliseconds, typical of an NTP slew correction) is handled by blocking briefly until the clock catches back up; a large drift (the clock stepped back by seconds or hours, typical of a misconfigured NTP daemon or a hypervisor snapshot restore) is handled by rejecting the request outright and paging on-call, because blocking for an unbounded amount of time would itself violate the sub-millisecond latency requirement.
6. Entity-relationship (ER) diagram and schema
These two tables sit entirely on the audit/control-plane side of the system. The Snowflake generator itself never queries them at ID-generation time - they exist so a human (or an alerting rule) can answer "which host holds this worker ID, and is it still healthy?", and so teams that prefer a pre-allocated-range strategy over pure per-request Snowflake generation have somewhere durable to record each range.
Key modeling decisions
| Coordination need | Choice | Reasoning |
|---|---|---|
| Live worker-ID assignment | etcd/ZooKeeper (lease, ephemeral znode) | Needs sub-second consistency and automatic reclamation on crash - a relational table alone can't do that without an external heartbeat sweeper. |
| Historical/audit record | Relational audit DB (Postgres) | Humans and dashboards want durable, queryable history ("which host held worker 217 last Tuesday?") - etcd is not a system of record and often TTLs old data away. |
| Pre-allocated range strategy | id_allocation_ranges table only, no etcd involved | Some teams skip live coordination entirely and hand each worker a pre-committed epoch+range row up front; simpler operationally, but ranges must be sized conservatively or a worker can exhaust its block early. |
7. Deep dives interviewers actually probe
How are the 64 bits actually assembled, and how is a clock rollback checked?
Every ID is built from three fields packed into a single signed long: a 41-bit millisecond timestamp (relative to a custom epoch, not Unix epoch, to maximize the usable range), a 10-bit worker ID, and a 12-bit sequence. The rollback check happens in the same critical section, before any bits are shifted:
// 41 timestamp bits | 10 worker bits | 12 sequence bits
long timestamp = System.currentTimeMillis() - CUSTOM_EPOCH;
synchronized (this) {
if (timestamp < lastTimestamp) {
long driftMs = lastTimestamp - timestamp;
if (driftMs <= MAX_TOLERABLE_DRIFT_MS) {
sleepUninterruptibly(driftMs); // small NTP slew - wait it out
timestamp = System.currentTimeMillis() - CUSTOM_EPOCH;
} else {
throw new ClockRolledBackException(driftMs); // large step-back - refuse
}
}
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & MAX_SEQUENCE; // 12 bits, wraps at 4096
if (sequence == 0) timestamp = waitNextMillis(lastTimestamp);
} else {
sequence = 0L;
}
lastTimestamp = timestamp;
}
return (timestamp << 22) | (workerId << 12) | sequence;Why not just use UUIDv4?
A random UUIDv4 solves uniqueness but nothing else this design needs. It has no ordering, so you lose the ability to sort by creation time without a separate timestamp column. Used as a database primary key, its randomness causes poor B-tree index locality: inserts land at random points across the index rather than appending to the right edge, which triggers constant page splits and index fragmentation under write load. And a UUID carries no embedded metadata - a Snowflake ID lets you extract the creation timestamp and even the originating worker/datacenter directly from the number itself, which is invaluable for debugging without a lookup.
What happens if you outgrow 1,024 workers?
The 10-bit worker field is a hard ceiling baked into the bit layout, and it can't be silently expanded without breaking every existing ID's decoding. Two realistic paths: reshape the 64 bits - trade sequence bits for worker bits (e.g. 8 sequence + 14 worker gives 16,384 workers at 256 IDs/ms/worker, still far above the ~7k/sec average per worker this design targets); or move to a scheme with a wider ID, like UUIDv7 (128 bits, time-ordered, effectively unlimited node space) or a hierarchical worker namespace (region → datacenter → cluster → machine, each level borrowing bits) if 64 bits must stay fixed. Both require a coordinated migration, which is exactly why the initial bit split should be sized with real headroom (this design keeps 200-400 active workers under a 1,024 cap) rather than cutting it close.
Clock rollback in depth: small slew vs a large step-back
These are genuinely different failure modes and get different handling. A small rollback - a few milliseconds, the common case when NTP slews the clock to correct minor drift - is handled by blocking the calling thread briefly until the local clock catches back up to last_timestamp, then proceeding normally; callers see a slightly elevated but bounded latency, never a wrong answer. A large rollback - the clock stepped back by seconds, minutes, or hours, typically from a misconfigured NTP daemon, a VM snapshot restore, or a manual clock change - is handled by rejecting the request immediately and alerting on-call, because blocking for an unbounded duration would itself violate the latency requirement, and continuing to generate IDs under a false timestamp risks producing one that collides with an ID already issued under the real (later) time. It's also worth noting that a monotonic clock (like Java's System.nanoTime()) does not fully solve this on its own: monotonic clocks only guarantee non-decreasing values within a single process's lifetime, so a worker restart resets the monotonic reference entirely - the wall-clock rollback check against a persisted last_timestamp is still required across restarts.
Snowflake vs database auto-increment vs a centralized ticket server
| Approach | Throughput | Ordering | Operational complexity |
|---|---|---|---|
| DB auto-increment (single counter) | Limited by one primary's write throughput; a hard bottleneck | Perfectly ordered | Simplest to reason about, but a single point of failure and a scaling ceiling |
| Centralized ticket server (Flickr-style MySQL bulk range allocation) | High - each app server checks out a block of, say, 1,000 IDs at a time, amortizing the network hop | Ordered within a block, coarser across servers | Moderate - still a shared service, needs its own HA setup, but far less chatty than per-ID calls |
| Snowflake-style (this design) | Highest - fully local, no shared component in the request path | Roughly time-ordered (millisecond granularity), not globally sequential | Highest upfront cost - requires worker-ID coordination and clock-rollback handling - but zero shared runtime dependency |
What happens on worker restart?
A restarted worker must never resume generating IDs under a worker ID that another live instance currently holds - that would produce colliding or out-of-order IDs from two processes using the same worker bits simultaneously. The design handles this because worker IDs are leased, not statically configured: on restart, the worker re-registers with etcd like any fresh boot. If its previous lease already expired (because it was down longer than the 15s TTL), the coordination service will happily hand it a fresh free worker ID - possibly the same one, possibly a different one - but only after confirming no other live lease holds it. If the worker restarts fast enough that its old lease technically hasn't expired yet, it should reconnect using its previous lease ID rather than requesting a new one, so it resumes as the same worker rather than triggering an unnecessary reassignment.
Post a Comment
Add