How Would You Design a Distributed Unique ID Generator?

Problem Statement and When It Applies

Design a distributed unique ID generator across four regions. Each region has at most 200 generator workers. The fleet peaks at 2 million IDs per second, while any one worker may generate up to 3,000 IDs in a single millisecond. Each ID must be a positive 64-bit integer, globally unique, roughly ordered by generation time, and usable for at least 60 years. The hot path cannot make a network request for every ID. The latency target is p99 at or below 5 milliseconds and the availability target is 99.99%, but the generator must stop rather than risk a duplicate.

Gaps are allowed, and strict monotonic order across regions is not required. The IDs are internal message identifiers and database primary keys, so predictability is acceptable for now. A separate treatment is needed if an identifier will be exposed to untrusted clients. These capacities and SLOs are interview constraints, not claims about any company's production traffic.

This question fits senior backend, infrastructure, and system design interviews. The real task is to turn lifetime, worker count, and millisecond burst requirements into a bit budget, then prove that clock, concurrency, and worker-identity failures cannot create duplicates. Saying only “use Snowflake” is not a design.

What the Interviewer Is Evaluating

First, can the candidate separate uniqueness, ordering, continuity, and unpredictability? Snowflake can provide unique, roughly time-ordered 64-bit integers. It does not automatically provide a gapless sequence, causal order across regions, or a security token. A different requirement changes the design.

Second, can the candidate derive the layout from the constraints? A strong answer calculates what 41 timestamp bits, 10 worker bits, and 12 sequence bits cover, then checks the 60-year lifetime, 800 workers, and 3,000 IDs per worker per millisecond. It does not copy the classic split and look for a justification afterward.

Third, can the candidate prove that IDs do not repeat? Correctness requires one active owner for a worker code within any overlapping time range, no sequence reuse by that worker within a millisecond, and no clock rollback or restart that re-enters a previously used timestamp-and-sequence range.

Fourth, can the candidate complete the failure design? Sequence exhaustion, backward clocks, lost leases, resurrected processes, regional isolation, and timestamp exhaustion can all threaten uniqueness or availability. The answer needs explicit stop conditions, alerts, and recovery procedures.

Fifth, can the candidate choose among Snowflake, UUIDv7, random UUIDs, and centralized or segment allocation based on constraints? The 64-bit requirement and no per-ID coordination favor Snowflake here. If 128 bits were acceptable and worker registration were undesirable, UUIDv7 would be a simpler candidate.

Questions to Clarify Before Answering

• Is uniqueness deterministic, or is a tiny collision probability acceptable? Deterministic uniqueness needs isolated worker namespaces. If probabilistic uniqueness is acceptable, UUIDv4 or UUIDv7 can remove worker allocation.
• Must the identifier be 64 bits? If the database, protocol, and indexes accept 128 bits, standard UUIDv7 offers a time prefix and random space with a simpler control plane. This problem fixes the output to a positive 64-bit integer.
• How strong is “ordered”? Rough time order can use local clocks. Strict total order across regions requires a centralized sequencer, consensus log, or business-partitioned sequence and has very different costs.
• Are gaps allowed? Segment preallocation, crashes, and retries can leave gaps. Combining gaplessness with strict global increase moves allocation into a serial transaction path. Gaps are allowed here.
• Will IDs be public? Timestamp and worker bits can reveal creation time and deployment information, while increasing values can be enumerated. That may be acceptable for internal keys; public identifiers should use a separate opaque value.
• How are workers created and replaced? Fixed machines, orchestrated containers, and autoscaling have different worker-identity reuse risks. Dynamic workers need leases, fencing, and a safe reuse rule.
• What wins during a network partition? Existing workers may continue while their regional control plane is healthy and their leases remain safe. A worker must stop when exclusive ownership cannot be proved, sacrificing some availability.

The 30-Second Answer

“I would split the 64 bits into one fixed sign bit, 41 bits of millisecond time, 10 bits for region plus worker, and a 12-bit per-millisecond sequence. That covers about 69.7 years, 1,024 worker codes, and 4,096 IDs per worker per millisecond, so it meets the constraints. Each worker generates (timestamp, worker, sequence) inside a local critical section, with no network call on the hot path. A regional control plane allocates and renews worker leases. The worker never wraps on sequence exhaustion and stops on lease loss or unsafe clock rollback. The result is roughly time-ordered, not strictly ordered across regions. If 128 bits were allowed and I wanted to eliminate worker registration, I would evaluate UUIDv7.”

Step-by-Step Deep Dive

Step 1: Use the constraints to reject unsuitable defaults

A centralized database sequence gives clear ordering, but every allocation enters a shared write path. That conflicts with the no-network hot path and regional-isolation requirements. Allocating ranges in batches amortizes coordination but leaves gaps when a worker crashes. Gaps are allowed, so segment allocation remains a viable alternative, though it still needs a range service and prefetch policy.

UUIDv4 and UUIDv7 are both 128-bit formats. UUIDv4 is random and does not provide time ordering. Under RFC 9562, UUIDv7 places a 48-bit Unix millisecond timestamp in the most significant portion and uses the remaining space for version, variant, and random or monotonic fields. It can produce roughly ordered values without registering workers, but it violates this problem's 64-bit requirement.

That leaves a Snowflake-style 64-bit layout. “Coordination-free” applies only to each allocation on the hot path; worker identity still needs a control plane. Hiding that cost does not make the system free of coordination.

Step 2: Derive the 1 + 41 + 10 + 12 layout from capacity

Reserve the most significant bit as zero so the value remains a positive signed 64-bit integer, then allocate the remaining 63 bits as follows:

| Field | Bits | Range | Fit to the requirement | |---|---:|---:|---| | Sign | 1 | Fixed at 0 | Keeps the BIGINT positive | | Milliseconds since a custom epoch | 41 | 2^41 milliseconds, about 69.7 years | Exceeds the 60-year lifetime | | Region + worker | 10 | 1,024 codes | 2 region bits × 8 local-worker bits supports 4 × 256 workers | | Sequence within a millisecond | 12 | 0–4,095, or 4,096 values | Exceeds 3,000 IDs per worker per millisecond |

The total is 1 + 41 + 10 + 12 = 64 bits. The fleet has at most 4 × 200 = 800 workers, below 1,024, and 200 workers per region fit within the 256 values provided by 8 bits. The 41-bit time range is approximately 2^41 ÷ 1000 ÷ 60 ÷ 60 ÷ 24 ÷ 365.2425 = 69.7 years. To satisfy “positive” strictly, reserve the all-zero ID and place the custom epoch before the first allocation. Even sequence zero on the first worker can then never return 0.

The fleet-wide rate of 2 million IDs per second is an aggregate capacity check. The sequence field must satisfy the sharper per-worker, per-millisecond burst. An average-per-second calculation cannot prove that 12 bits are sufficient: a single worker can still exhaust its sequence even when fleet-wide QPS is low.

Step 3: Implement local generation and prove uniqueness

Each worker uses 64-bit integer operations and protects lastMs and sequence with a lock or atomic critical section:

nextId():
  lock
  now = wallClockMs() - customEpochMs
  if now < lastMs:
    fail("clock_moved_back")
  if now == lastMs:
    if sequence == 4095:
      now = waitUntilAfter(lastMs)
      sequence = 0
    else:
      sequence = sequence + 1
  else:
    sequence = 0
  lastMs = now
  return (now << 22) | (workerCode << 12) | sequence

The sequence must not silently wrap to zero after 4,095 while the clock remains in the same millisecond; that immediately duplicates an earlier value. The 4,096th ID is valid because the sequence starts at zero. The 4,097th request in that same millisecond must wait for the next millisecond or receive an overload error.

The uniqueness proof has three cases. Different workers have different 10-bit worker codes. The same worker in different milliseconds has different 41-bit timestamps. The same worker in the same millisecond has different 12-bit sequence values. If the fields stay in range, worker ownership does not overlap, and the clock never re-enters used state, the full 63-bit payload cannot repeat.

Step 4: Put worker identity in the control plane

Run an independent worker-lease allocator in each region, while fixing the region's 2-bit code through deployment configuration. The control plane stores:

| Field | Purpose | |---|---| | regionid, workerid | Form the 10-bit global worker code | | owner_id | Identify the current process or deployment instance | | fencing_token | Distinguish newer and older owners of one worker code | | leaseexpiresat | Bound how long ownership remains valid | | timestampceilingms | Bound the timestamp range the old owner may use during safe reuse |

At startup, a node acquires a worker ID and lease. The ID hot path checks only the owner state, fencing state, an in-memory lease safety deadline, and now <= timestampceilingms; renewal happens asynchronously, so allocation does not contact the control plane for every ID. A node stops generating as soon as its lease is unsafe or it reaches the timestamp ceiling. Before reusing that worker ID for a replacement, the control plane must fence the old owner and wait until the new node's clock is beyond the old lease's timestampceilingms. Then even a delayed old node and its replacement cannot use the same timestamp range.

The fencing token is not encoded into the final ID, so it cannot repair a collision after one occurs. It keeps a stale owner out of the generation path. If a platform cannot reliably fence old processes, it should assign long-lived, non-reused worker IDs to deployment slots or use UUIDv7 instead of pretending a lease alone solves process resurrection.

Step 5: Define stop conditions for clocks, overflow, and partitions

The policy for now < lastMs must be bounded. One example is to wait for a rollback of at most 5 milliseconds only when the request has enough latency budget left; the wait counts against the 5-millisecond p99 budget. For a larger rollback or insufficient remaining budget, return a retryable error, remove the node from service, and alert. On process startup, compare the current time with the persistent high-water mark for that worker and refuse to start if the clock is behind. Keeping lastMs only in memory does not cover restarts.

When the sequence is exhausted, wait for the next millisecond and increment a sequence_exhausted metric. Frequent exhaustion means the load is skewed or the bit budget is wrong. Spread traffic, add workers, or allocate more sequence bits in a new format. Never wrap.

During isolation between regions or from the global network, the 2-bit region field still separates namespaces. Existing workers can continue locally while their regional leases remain safe. If the regional lease service is unavailable and the safety deadline expires, those workers stop. Uniqueness takes priority over the 99.99% availability target, and the exception must be documented in the SLO and alerts.

The 41-bit timestamp eventually expires. Expose the remaining epoch lifetime and begin migration years in advance. Never reset the timestamp after overflow or silently reinterpret the same 64-bit column with a new layout. Adding regions or expanding the worker count requires the same kind of format migration.

Step 6: State what “ordered” and “secure” actually mean

Putting time in the high bits makes IDs roughly ordered, but clock skew can give a later record a smaller ID. Worker bits also affect ordering inside one millisecond. A Snowflake ID does not prove causality across regions and cannot replace a payment ledger's commit sequence.

If an API performs incremental synchronization with id > cursor, a late-arriving ID from a slow clock may be smaller than the saved cursor and be skipped forever. When complete ordering matters, use a database commit sequence, a consensus-log position, or a sequencer scoped to a business partition such as a conversation or account. Snowflake remains the identity, not the ordering authority.

The raw ID also exposes an approximate creation time and may reveal region or worker bits. It is not an authorization credential. A public resource can keep the 64-bit internal key and expose an independent opaque identifier. Never rely on an ID being hard to guess to protect data.

Step 7: Compare alternatives under the same constraints

| Approach | Width and order | Coordination | Best fit | Main cost | |---|---|---|---|---| | Snowflake style | 64-bit, roughly ordered | Coordinate at startup and renewal; local hot path | 64-bit IDs, very high throughput, approximate order | Clock and worker management | | UUIDv7 | 128-bit, time-prefixed | No worker registration | 128 bits are acceptable and a standard format without a worker control plane is preferred | Wider values; uniqueness depends on randomness quality and implementation | | UUIDv4 | 128-bit, random order | None | Ordering is unnecessary and opacity matters | Worse index locality and no time inference from the ID | | Central sequencer / segments | Usually 64-bit, strictly or roughly increasing | Allocate through a service or database; segments can be batched | Central ordering is required or the system already depends on a database | Network/database dependency; batches leave gaps |

Snowflake wins this problem because of the hard 64-bit constraint and the ban on per-ID network calls. If the interviewer removes the 64-bit constraint, reconsider UUIDv7. If strict total order is required, acknowledge that Snowflake does not meet it and move to a serialized sequencer instead of patching the wrong primitive.

Step 8: Validate with failure injection

Validation must go beyond generating a large normal sample with no duplicates. Cover at least these cases:

1. Freeze time and generate 4,096 IDs from one worker in one millisecond. All must be unique; the 4,097th must wait or fail.
2. Call one generator concurrently and verify that the local critical section prevents two threads from reusing a sequence.
3. Roll the clock back by 1, 5, and 2,000 milliseconds and verify the wait, timeout, removal, and alert paths.
4. Pause an old owner, let its lease expire, activate a new owner, then resume the old owner. Verify that fencing prevents the stale process from generating.
5. Freeze all four regions and all 800 workers at the same millisecond, then generate different sequences and verify decoded field ranges and global uniqueness.
6. Isolate the regional lease service. Existing workers may continue within the safe lease interval and must fail closed afterward.
7. Advance time to 2^41 - 1 and verify that the next millisecond is rejected and triggers the migration alert.

At minimum, production monitoring should cover clockrollbackms, sequence_exhausted, lease-renewal failures, available worker-code headroom, generation latency, error rate, and remaining epoch lifetime. A database unique constraint is a useful last line of defense and alert source, but catching a collision and retrying is not a substitute for generator correctness.

High-Quality Sample Answer

“I would first confirm that the requirement is a deterministically unique, positive 64-bit ID. Gaps are allowed, and ordering only needs to be approximate. With four regions, 200 workers per region, and up to 3,000 IDs per worker per millisecond, I would choose a Snowflake-style design rather than a 128-bit UUIDv7 or a centralized sequencer call for every ID.

The most significant bit stays zero. A 41-bit custom-epoch millisecond timestamp lasts about 69.7 years. Ten worker bits split into 2 region bits and 8 local-worker bits, covering 4 × 256 nodes. A 12-bit sequence yields 4,096 values per worker per millisecond. All three dimensions exceed the stated constraints and use the 63-bit payload exactly.

Each worker keeps lastMs and sequence in a local critical section. It resets the sequence when time advances, increments within the same millisecond, and waits after sequence 4,095. It never continues through a backward clock: up to 5 milliseconds may wait within the latency budget, while a larger rollback removes the worker and alerts. Different worker codes separate workers, timestamps separate milliseconds for one worker, and sequences separate IDs within one worker-millisecond.

I would run a regional worker-lease control plane. Nodes contact it only at startup and for asynchronous renewal, while generation remains local. An old owner stops after losing its lease. Before reusing its worker ID, the allocator fences the old owner and ensures the replacement's clock is beyond the old lease's timestamp ceiling. If exclusive ownership cannot be proved, the worker stops.

Finally, I would state that this gives approximate order only. Strict order across regions needs a consensus log or business-partitioned sequencer, and public non-enumerable IDs need a separate opaque value. Validation would include the 4,097th request in one millisecond, concurrent sequence access, a two-second clock rollback, lease takeover, and epoch exhaustion—not only the happy path.”

Common Mistakes

• Saying “use UUID” immediately → The answer never clarifies width, order, or collision semantics → Separate UUIDv4, UUIDv7, and a deterministic worker namespace first.
• Copying 41-10-12 → There is no proof that lifetime, workers, or burst capacity fit → Calculate 2^41 milliseconds, 2^10 worker codes, and 2^12 sequence values separately.
• Using only average fleet QPS → A per-worker, per-millisecond burst can still exhaust the sequence → Validate capacity at the smallest time unit and hottest worker.
• Wrapping the sequence with a mask → The same worker repeats an ID in the same millisecond → Wait for the next millisecond, apply backpressure, or fail.
• Putting a worker ID in configuration and stopping there → Autoscaling, copied configuration, and process resurrection create two owners → Design leases, fencing, safe reuse, and stop conditions.
• Continuing with the current wall clock after rollback → The worker can repeat a timestamp-and-sequence pair → Wait within a bound or fail closed, and check a persistent high-water mark after restart.
• Calling rough order globally monotonic → Clock skew and concurrent workers change the order → Use a serialized log or partitioned sequencer when strict order is required.
• Treating the ID as access control → A decodable or enumerable ID does not authorize a request → Expose a separate opaque identifier and still enforce server-side authorization.
• Testing only millions of normal IDs → Ordinary random load rarely reaches the dangerous boundaries → Freeze time and inject rollback, lease takeover, and field exhaustion.

Follow-Up Questions and Responses

Follow-up 1: What changes if IDs must increase strictly across regions with no gaps?

Snowflake no longer qualifies. Strict total order requires every allocation to pass through a linearization point, such as a single sequence state in a consensus log. Gaplessness also means the number must commit with the successful business transaction, so unused prefetched segments are unacceptable. The minority side of a network partition must stop, reducing throughput, availability, and increasing latency. Ask whether the business truly needs gaplessness; many audit systems need an immutable business reference, not a gapless database primary key.

Follow-up 2: How would you add a fifth region or support 300 workers per region?

The current 2 region bits and 8 local-worker bits cannot represent either case. Before launch, the 10 bits could be repartitioned by adding a region bit and reducing local-worker capacity. Once IDs exist, old values cannot be reinterpreted online under the new boundary. Introduce an explicit new format or migrate to 128-bit identifiers, with readers and writers recognizing both versions. Silently moving the bit boundary breaks decoding, ordering, and uniqueness assumptions.

Follow-up 3: A node's clock moves backward by two seconds. Can sequence bits keep it available?

Not safely with an unstored workaround. After a restart, the process may forget which logical timestamp it borrowed. Under the stated policy, remove the node immediately, alert, and shift traffic elsewhere. Restore it only after wall time catches up to lastMs or after recovering a proven logical time from a persistent high-water mark. If availability through rollback is mandatory, use a deliberately persistent logical-clock design and re-prove overflow, restart, and ordering behavior; saying only “use a logical clock” skips the hard state-recovery problem.

Follow-up 4: The ID will appear in a public order URL. How do you prevent enumeration and sales-volume leakage?

Keep Snowflake as the internal join key and generate a separate random external identifier. UUIDv4 is suitable when sufficient entropy and opacity are desired; UUIDv7 is an option if leaking a time prefix is acceptable. Store the mapping on the order row. Every order read must still authorize the current user, regardless of identifier format. Unpredictability reduces enumeration risk but does not replace authorization.

Follow-up 5: Can generation continue when a region loses contact with the global control plane?

Yes, because region bits isolate namespaces and allocation does not need the global control plane. Existing workers continue while their regional leases remain within the safe interval. If the regional lease allocator is also unavailable, workers whose renewal deadline expires stop. The regional lease store can itself use an in-region consensus cluster for availability, but two partitions must never renew the same worker code concurrently.

Follow-up 6: What if one worker suddenly needs 5,000 IDs per millisecond?

A 12-bit sequence supplies only 4,096 values. The immediate response is backpressure and load distribution to more workers; wrapping is forbidden. Long term, allocate more sequence bits in a new format by taking them from timestamp lifetime or worker capacity, or remove the 64-bit constraint and use UUIDv7. Measure the actual one-millisecond burst distribution before changing the layout; per-second averages do not answer this question.

Follow-up 7: If strict order is required only within one conversation, is a global sequencer necessary?

No. Map each conversation to a stable partition and maintain a commit sequence inside that partition. Snowflake remains the global identity, while the partition sequence carries conversation order. This reduces the coordination and failure domain compared with serializing all regions. Readers sort by (conversation_id, sequence) and never assume the Snowflake ID equals conversation commit order.