Interview Walkthrough: Design a Unique ID Generator

"Design a system that generates unique IDs for a distributed application."

This is a compact, well-bounded problem — which makes it a favourite. It is also one where reciting "use Snowflake" scores poorly, because the interviewer wants the reasoning that arrives there.

Step 0 — Scope it before you design

• Is there a size or format constraint? 64-bit numeric, or is a string fine?
• Do IDs need to be time-sortable, or is uniqueness enough?
• What's the generation rate — per second, and per node?
• How many nodes will generate IDs? Is that number stable?
• Are IDs externally visible? (This one has a security consequence.)
• Can we tolerate gaps in the sequence?

Then commit:

"I'll assume a 64-bit numeric ID for use as a primary key, at least a billion a day, and that we want rough time-ordering for range queries and tracing. IDs are externally visible. Gaps are acceptable. Let me start from the requirements and work through the options — I want to show why the obvious answers fail before landing on one."

Step 1 — Requirements, with the arithmetic

Uniqueness   — distinct IDs for every event
Scalability  — at least 1 billion IDs/day  (~11,600/sec)
Availability — generate for every event
Size         — 64-bit numeric

Is 64 bits enough?
  2^64 = 1.84 * 10^19
  365 * 10^9 events/year
  2^64 / (365 * 10^9) ~= 50.54 million years      -> comfortably yes

"That takes fifteen seconds and it turns the size constraint from arbitrary into justified. It also frames the real problem: 64 bits is plenty of space, so the difficulty is coordination, not exhaustion."

Step 2 — Walk the progression

Do not jump to the answer. Each step should kill the previous one.

UUID. Zero coordination, perfectly available — 128 bits and only probabilistically unique. Also random, which is the worst case for B-tree locality. Fails size and determinism.

Central database. Compact and genuinely unique — a single point of failure in front of every write. Increment-by-m fixes the SPOF and breaks the moment m changes:

"With m=3, A emits 1,4,7 and C emits 3,6,9. B dies, m becomes 2, A's next is 7+2=9 — which C already issued. It's the same trap as hash mod n: any scheme whose correctness depends on the node count breaks when membership changes."

Range handler. A central service hands out blocks; servers assign locally until exhausted.

"This satisfies all four. The key idea is amortizing coordination — the handler is consulted once per 100,000 IDs instead of once per ID, so it's not on the hot path. Gaps appear when a server dies holding an unused range, which is fine unless something downstream assumes contiguity."

Then raise the gap yourself: "But these IDs carry no time information, so if we need ordering we're not done."

Step 3 — Adding time

UNIX timestamps. Millisecond granularity caps at 86.4M/day — an order of magnitude short — and two requests in the same millisecond on the same server collide.

Snowflake. Spend the 64-bit budget deliberately:

 1 bit    41 bits         10 bits      12 bits
[sign]   [timestamp]     [worker]    [sequence]
   0      ~69 years       1,024        4,096/ms

"Each field answers a specific failure. Sequence fixes same-millisecond collisions on one worker; worker fixes cross-server collisions; timestamp gives ordering; the sign bit keeps it positive so it sorts as a signed integer.

Throughput is 4,096 per millisecond per worker across 1,024 workers — about 4.2 billion per second theoretical, against a requirement of 11,600. Enormous headroom.

One practical note: I'd set a custom epoch at our launch date. Using Twitter's 2010 default would silently spend fourteen years of the 41-bit budget before we issue anything."

Step 4 — Name the weakness before they do

"Snowflake's ordering is only as good as the clocks. Physical clock error can reach seconds per day, and if a server drifts forward and NTP corrects it backwards, it can reissue a millisecond it already used — producing duplicates or violating causality. So this is weak on causality, not solved.

If we needed provable causality, the options are vector clocks — which give it genuinely but are O(n) in cluster size and blow a fixed 64-bit budget — or TrueTime, which returns an interval instead of a point and needs GPS and atomic clocks in every data center. I'd cite TrueTime as the reference answer, not the recommendation."

Step 5 — The chosen design

"Workers generate independently with no coordination on the hot path. The only coordination is assigning worker IDs at startup — which is a control-plane operation done once per process, not per ID. I'd use a coordination service for that, or derive it from the host identity."

Deep Dives & Follow-up Questions

"A worker exceeds 4,096 IDs in one millisecond. What happens?"

The sequence field wraps, so the generator blocks until the next millisecond rather than reusing a number. A sub-millisecond stall is strictly better than a duplicate. If one worker genuinely needs more than 4 million per second sustained, the fix is more workers — we have 1,024 of them — not more sequence bits, because taking bits from the timestamp shortens the system's lifespan.

"The clock jumps backwards. Now what?"

This is the real failure mode, and it's why Snowflake is only weakly causal. The standard defence is to refuse to generate while the current time is less than the last timestamp used — the generator stalls until the clock catches up rather than risking duplicates. For small corrections that's a brief pause; for a large jump it's an outage, which is why you'd also disable NTP step adjustments on ID-generating hosts and use slew instead, correcting gradually rather than jumping.

"How do workers get their IDs without collisions?"

A coordination service like ZooKeeper assigning them at startup, or deriving from something already unique to the host. What matters is that it happens once per process, off the hot path — and that a restarting worker doesn't reuse an ID a live worker holds. If two workers ever share an ID they'll produce duplicates within the same millisecond, so this is worth getting right even though it looks like a detail.

"These IDs are in URLs. Any concern?"

Yes, a business-intelligence leak. Sequential or near-sequential IDs let anyone estimate volume — place an order Monday, another Friday, subtract the IDs, and you know the week's order count. If IDs are externally visible I'd either add random bits, use a separate opaque public identifier mapped to the internal one, or accept the leak knowingly. Note this conflicts with sortability, so it's a genuine trade rather than a free fix.

"Why not just use a global counter with consensus?"

Because the throughput is nowhere near enough. Spanner reports roughly 100 operations per second for single-row read-modify-write transactions, and we need about 11,600 per second — two orders of magnitude short. Strict global ordering requires consensus, consensus requires round trips, and that caps you far below the requirement. Relaxing strict ordering is precisely what buys Snowflake its throughput.

"Our IDs are the primary key and one shard is hot. Why?"

Time-sortable IDs are monotonically increasing, so every insert lands at the top of the key range — on whichever shard owns it. That's a hotspot created by the ID scheme itself, and it's the standard downside of sortable IDs in distributed databases. Fixes: hash the ID for the partition key while keeping it sortable for queries, or put the worker ID in the high bits so writes spread across workers rather than clustering by time.

"Can you get IDs with no coordination at all?"

UUID v4, if the size constraint goes away. That's worth stating because it reframes the whole problem: every approach here is buying compactness with some amount of coordination. Snowflake's is minimal — worker assignment at startup — which is why it's the practical sweet spot.

Now do it live

The next section drills these as standalone probes.