Design a distributed unique-ID generator

01Problem and scope

A distributed ID generator gives callers distinct values before they save the records that will use them. Separate uniqueness, local monotonicity, approximate time ordering and strict global order. A central sequence is a correct baseline; local generation requires assigning each generator a set of allowed field combinations that no other generator may use. This design permits gaps and uses approximately time-sorted positive 63-bit values under controlled process activation, with a unique constraint at the consuming database.

In a time/worker/sequence ID, the timestamp says which time slot is being used, the worker field distinguishes generators, and the sequence counts allocations by that worker within the same slot. Placing the timestamp in the high bits makes time dominate numeric order. The worker and sequence occupy the lower bits so many generators can issue values during one slot without sharing the same tuple.

Start with a small worked format: timestamp 12 bits, worker 3 bits, sequence 4 bits. If elapsed timestamp=160, worker=1, sequence=1, encode (160 × 2^7) + (1 × 2^4) + 1 = 20,497. The fields occupy disjoint bit positions. Uniqueness comes from never reusing the same tuple, not from the number looking complicated.

I clarify whether the identifier must be an integer, whether gaps are allowed, and whether the requirement is uniqueness or a total real-time order. The requesting service needs compact IDs generated quickly across order processes before their writes are batched. Gaps are acceptable; the order database still enforces a unique constraint. We choose approximately time-sorted 63-bit positive values under a documented namespace and controlled process lifecycle.

A generated ID is not a business request identity. If the requesting service's create-order request times out, retrying with a new generated ID could create a second order unless the order API also has an idempotency key. This chapter solves distinct allocation, not every duplicate business operation.

We use a time/worker/sequence layout to work through its correctness. If compact IDs do not justify managing clocks and worker ownership, choose a standard UUID or centrally allocated range.

02Functional requirements

1. Start a generator. Obtain a fresh incarnation—an identity for this process activation—and a timestamp grant reserving an interval that no other incarnation of the same worker may use.
2. Allocate one ID. Return a distinct value or an explicit safety/capacity error.
3. Allocate a bounded batch. Reserve and return that many unique tuples without wrapping.
4. Decode for diagnostics. Show format, approximate timestamp, worker, and sequence.
5. Restart after crash. Abandon the prior grant and acquire a fresh one before serving.
6. Migrate format. Use a new namespace so the new format cannot be confused with old IDs.

Scope and acceptance boundaries

Assume positive 64-bit-compatible integers, high throughput, uniqueness within a documented namespace, and approximate time sorting. Strict global real-time order, gapless invoice numbering, and secret access tokens are outside scope. Uniqueness means no repeated value; local monotonicity means each generator’s next value increases; global order relates all generators’ events. These are separate properties.

If the requesting service needs legal/business sequential invoice numbering, that is a separate coordinated business record. An unused generated ID can remain a gap. Predictable time-prefixed IDs may reveal activity; authorization must not depend on their obscurity.

Within one process, calls take turns updating the timestamp and sequence cursor. Across processes, the allocator gives each a non-overlapping grant. A response loss may waste an ID, which is acceptable. Remote clients that require a retry to return the same allocation can use a retained allocation-request key, but that retention has its own cost and scope.

The deployment contract forbids transparently cloning an already activated generator's memory into a second running issuer. A supported VM restore must reinitialize the generator and obtain a new incarnation before accepting traffic. If arbitrary invisible execution cloning is required, a purely local cursor cannot satisfy it; move issuance behind an external authority or a nonclonable state mechanism.

03Non-functional requirements

1. Throughput. Assume ten million IDs/s peak across 500 generator processes: 20,000/s per active process on average at that peak.
2. Local latency. Target p99 below 100 microseconds when a safe grant is available.
3. Availability. Target at least 99.9% under normal clocks and healthy replenishment. Both latency and availability need benchmarks; bit arithmetic does not guarantee them.
4. Uniqueness. Require a durable non-overlapping grant allocator, synchronized local cursors, no namespace wrap, and controlled startup/restore.
5. Failure tolerance. Handle crashes, pauses and bounded clock errors by waiting or stopping when necessary. Allocator failover must preserve committed allocation state. An allocator minority cannot issue overlapping grants.
6. Ordering. Promise approximate timestamp order, not global real-time order: workers' clocks and grant availability may differ.

Safety during allocator outages

A process may continue within a committed grant while the allocator is unavailable. After the grant expires, it stops rather than guesses a worker number or reuses time. Safety takes priority at that boundary.

Identity is not authority

An ID does not prove authorization, secrecy or creation time. Public URLs that must conceal activity may use a separate random reference. Business invoice numbering is separately coordinated under its regulatory and accounting requirements.

04Capacity estimates

The timestamp field stores elapsed time from a chosen starting instant, called the custom epoch. It does not store an unlimited calendar timestamp. Allocating bits therefore sets both the lifetime of this format and the capacity reserved for workers and same-millisecond calls.

Consider an illustrative 63-bit positive layout: 41 timestamp bits in milliseconds, 10 worker bits, 12 sequence bits.

Changing one field’s width takes capacity from another. Persist the custom epoch and namespace version as part of the contract. A benchmark, not the bit arithmetic alone, establishes actual generation throughput.

At 500 processes and 20,000 IDs/s each, the nominal demand is 20 IDs per millisecond per process, far below 4,096, but bursts and synchronization still need measurement. The namespace has only 1,024 worker values; running more processes requires sharing an allocator service, changing the layout, or choosing another format. Before reusing a worker value, prove that the new generator cannot repeat an old generator’s IDs.

For this design, the authority grants nonoverlapping timestamp intervals per worker, with an illustrative 1,000 ms interval. Five hundred active processes replenishing once per second create about 500 allocation transactions/s rather than ten million per-ID transactions/s. Shorter intervals reduce unused future time after a crash but increase authority traffic; longer intervals reduce control traffic but can delay a replacement until its fresh time range starts.

Prefetching grants for the next ten seconds lets a process continue briefly during an allocator outage, but a replacement using the same worker must wait past those already reserved intervals, even if the old process never used them. Assigning a different available worker can avoid that wait while spare identities remain. More prefetched time helps during outages but can lengthen replacement waits or require spare workers.

The 41-bit epoch lifetime is finite. A new deployment cannot use an epoch from nearly 70 years ago and assume it has another 70 years left. Track remaining range and plan an explicit format migration before overflow.

05APIs and contracts

A grant names an allowed timestamp interval. We use a half-open interval: the start is included and the end is excluded. Thus [160,200) permits timestamps 160 through 199, leaving 200 available as the start of the next non-overlapping grant.

The grant response is {worker:1,incarnation:8,grantId:"g8",startMs:160,endMsExclusive:200,format:"example-v1"} in the tiny example. A production interval might span 1,000 ms. The local generator can issue only timestamp values in that half-open interval and cannot infer ownership from a machine hostname.

nextId() returns {id:"20497",format:"example-v1"}. Sequence exhaustion may wait for a safe tick within a bounded deadline or return capacity_exhausted. A clock before the grant start yields not_yet_valid; an expired grant yields grant_exhausted; uncertain authority yields unavailable. These are safer than returning a value assembled from unchecked fields.

Remote batch allocation caps count and deadline. A repeated request key returns the previously allocated batch only if that remote API explicitly retains the result; ordinary local nextId calls have no such retry identity. Strings let JavaScript and JSON clients preserve every digit of the ID.

Decoding is a diagnostic operation: it reports the encoded timestamp, not a proof of database commit time or the real-world order of two events. The custom epoch and format version must accompany persisted schema and migration documentation.

06Data model and access patterns

The allocator’s high-water mark is the end of the timestamp space already reserved for a worker, including values that may never have been emitted. Keeping that boundary durable is what lets each process advance its small local cursor without persisting every generated ID. A restart sacrifices unused space rather than guessing which values were safe to reuse.

The allocator transaction locks worker 1's high-water row, chooses start=max(highWater,eligibleTime), reserves [start,end), advances highWater to end, and records the grant before returning it. Grant request identity is (incarnation, requestId), authenticated against that activated process. A retry by that same live incarnation returns its recorded grant; a fresh incarnation must use a new identity and receive a fresh interval rather than recover an old process’s grant. Committed highWater never moves backward, including after backup restore.

A process crash does not require recovering its last local sequence because the supported restart abandons the entire prior grant. Even unused values remain unavailable. Accepting those gaps and possible waits makes restart safe without reconstructing every local call. A restored process may not resume its old in-memory cursor under the same grant.

The allocator is a small strongly consistent authority, replicated across failure domains. Its backup policy must preserve committed grant boundaries or choose a fresh namespace after uncertain recovery. If a restored allocator reissues an old range, two otherwise correct generators could produce the same IDs.

Keep the worker field fixed for an incarnation and reserve only increasing timestamp intervals for it. Initialize a fresh local cursor before the first usable timestamp; do not restore an old cursor. If positive values exclude zero, permanently reserve tuple (timestamp=0, worker=0, sequence=0), and validate all field widths before issuance. The namespace authority rejects a grant whose end would exceed the timestamp field.

07Basic working design

The simplest correct allocator uses one database sequence or one transactional counter row. The requesting service requests an ID, the database advances allocation state, and the service returns the number only after the required durable transaction commit. Concurrent callers serialize through that authority, so they cannot receive the same allocation. A process crash after receiving a number can leave a gap without causing duplication.

The baseline is often sufficient. At a modest rate, its operational simplicity outweighs the attraction of a custom bit layout. It also avoids assigning worker identities and reasoning about wall-clock rollback. PostgreSQL documents that a nextval result intended for persistent use outside its database must be committed before that external use: a crash before commit can leave sequence state uncertain. Do not return an externally usable allocation before the required commit, use a logged non-cycling sequence, and preserve acknowledged state across the supported failover. Sequence gaps and cached allocations remain normal; not every allocated value represents a committed order.

Reserve a non-overlapping numeric range in one transaction to share one network round trip across a large batch. A generator then issues from its range locally. Restart can burn the remainder and request another range. This is the first scaling step if approximate timestamp ordering is unimportant.

The time/worker/sequence design is justified only after the requirements prefer compact roughly time-prefixed values and the allocation rate makes per-ID coordination expensive. Keep the baseline as a benchmark and a practical alternative.

08Find the baseline flaws

Ten million per-ID requests/s would make a single remote allocation path expensive even before its database update. At an assumed 1 ms round trip, a serial caller can request only about 1,000 IDs/s; concurrency increases aggregate throughput but adds sockets, coordination, and an availability dependency on every allocation. Batching reduces how often callers need that remote operation.

A naive local time layout removes the round trip but introduces a correctness failure. Processes A and B both believe they own worker 1. At timestamp 160 and sequence 1, both emit 20,497. Different machines do not imply different worker fields.

Clock rollback creates a second collision. A emits timestamp 160/sequence 1, restarts with a clock at 158, later reaches 160, and resets its sequence to 1. Unless restart ownership or persisted boundaries prevent reuse, it emits 20,497 again. Merely using a high-resolution clock does not establish uniqueness.

A lease alone has another gap. A pauses before its lease expires, B is assigned worker 1, and A resumes without noticing. If their permitted tuple spaces overlap, both can issue duplicates even though the allocator's current lease row looks correct. The protection must prevent overlapping outputs, not merely declare one process the current owner.

09Improve the design, step by step

First, allocate disjoint batches or ranges. The trigger is a remote call per ID. The authority advances a durable high-water mark once for many values, and a synchronized local cursor serves them. This reduces control traffic by the batch size, but wastes unused values after a crash and no longer provides strict global issue order. Per-ID sequencing remains appropriate for a low-rate product that truly needs one central order.

Second, choose an explicit compact time layout. The trigger is approximate time sorting and fixed-width integer storage. Reserve fields for elapsed milliseconds, worker identity, and a per-timestamp sequence. Compared with random IDs, nearby times tend to occupy nearby index positions. Local generation is cheap, but timestamp range and same-timestamp bursts are limited. A standard UUIDv7 is preferable when 128-bit storage is acceptable and avoiding a custom lifecycle protocol matters more than integer compactness.

Third, grant nonoverlapping timestamp intervals per worker. The trigger is safe reuse after pauses or restarts. Instead of relying only on a revocable lease, the authority durably reserves disjoint time ranges. A replacement gets a new range; the old process can never issue its timestamps. This tolerates an old paused process resuming within its original range without colliding with the replacement. After a crash, unused time ranges stay unavailable. Replacements may wait, and the allocator must retain its high-water marks. Permanently assigned workers are simpler for a small stable fleet, but still need restart and snapshot rules.

Fourth, replicate the allocator and prefetch bounded grants. The trigger is control-plane failure stopping all generators. A quorum-backed allocator preserves committed boundaries, while processes prefetch a limited horizon. Local issuance continues inside committed ranges during a short outage. This adds consensus latency to replenishment and a tradeoff between outage tolerance and replacement delay. Guessing a new worker or issuing beyond the granted interval is rejected; a random standard identifier can be a different product format, not an invisible emergency substitution.

These changes preserve a checkable proof: distinct worker fields differ, and reused workers receive disjoint timestamps. Local synchronization ensures uniqueness within each granted timestamp. The restore procedure must prevent two active generators from sharing a copied cursor.

10Detailed architecture

Activation and grant authority

The final system contains a replicated namespace/grant authority, controlled generator processes, and downstream record stores. A deployment controller activates a fresh process incarnation. The generator requests an available worker and committed time interval through an authenticated allocator endpoint. Allocator replicas agree durably on configuration, high-water marks, process incarnations and saved request results.

Local issuance and clock checks

Each process holds a small bounded grant cache and a synchronized timestamp/sequence cursor. Ordinary nextId calls read local state and the clock, validate the tuple against a committed grant, advance the cursor, and assemble bits. They do not contact the allocator per ID. A background replenisher obtains a future nonoverlapping interval before the current one runs out.

The clock monitor reports offset and rollback, but it is not the uniqueness authority. The generator rejects timestamps outside its grant or earlier than its last issued timestamp under the chosen policy. Monitoring alone cannot prevent a bad ID after an unchecked clock jump.

Consumers and recovery limits

Order services use the returned ID when creating records and separately enforce business request idempotency. Database unique constraints detect any violated assumption. A decoder and operational audit service can inspect format and grant history without issuing IDs. The allocator commits a grant before returning success. Each ID is then generated locally; telemetry and audit export run separately.

Every live replica of the allocator has its own durable state copy. An isolated minority cannot allocate a new range. The chosen failure model explicitly excludes an invisible memory clone that bypasses fresh activation; supporting such clones requires an external service or nonclonable state to coordinate each allocation, so copying process memory cannot copy permission to issue the same next value.

Implementation option and limits

A small deployment can implement the authority with PostgreSQL transactions over namespace and worker high-water rows, an idempotent grant-result table, and explicit locking. Require durable commits and a failover policy that retains acknowledged grants; ordinary asynchronous replication does not by itself provide that condition. An established consensus store is another option for this small control-plane state. Neither database replication nor a lease removes the process-activation and non-overlapping-range rules of this custom generator.

11Write path and acknowledgement

Before serving local calls, reserve an unused interval durably and protect the cursor from concurrent updates. A generator cannot issue from an exhausted or expired grant, or resume an old grant merely because its memory was restored.

1. Generator A obtains worker 1 under an exclusive allocation policy before serving requests.
2. The generator reads safe timestamp 160 and sees lastTime 160/sequence 0.
3. Under local synchronization, it increments sequence to 1 and assembles 20497.
4. A concurrent call cannot read the old sequence; it receives sequence 2, yielding 20498.
5. At timestamp 161, reset sequence to 0 only after proving that timestamp/worker combination is unused: the value becomes 20624.
6. Use only a timestamp interval already durably reserved for this incarnation. A restart abandons the entire old grant rather than restoring its local cursor.

Local synchronization prevents races inside one process. It does not prevent another process from accidentally using worker 1, nor does it survive restoring an old VM snapshot.

7. The order process writes its business record with the returned ID. A timeout on that database write is resolved using the order's business request key; requesting another ID is not evidence that the original order failed.
8. Before timestamp 200, the example generator replenishes or stops. If worker 1's next grant is [200,240), the old [160,200) grant cannot issue timestamp 200. Half-open boundaries avoid an overlapping endpoint.
9. If the process crashes after allocating 20,497 but before returning it, that value may remain unused. The next incarnation obtains a fresh interval and never tries to recover and recycle “probably unused” values from the old one.

The local clock can skip from 160 to 170 without causing duplication; it burns unused timestamp/sequence combinations. A backward jump invokes the waiting or explicit failure policy. The implementation checks field widths before shifting so a sequence overflow cannot spill into the worker bits and masquerade as a valid new tuple.

12Read and delivery path

Consumers parse the complete namespace and integer without floating-point rounding. An ID grants neither record access nor business-operation idempotency.

1. A receiving API validates the format namespace and parses the decimal string with an integer type capable of representing the full value. It does not round through a JavaScript Number first.
2. The order store uses the complete namespace/ID as its key and verifies the customer's authorization separately. Knowing or predicting 20,497 is not permission to read that order.
3. A diagnostic decoder masks the sequence bits, extracts the worker field, and shifts the timestamp field. For 20,497 in the example layout, the result is timestamp 160, worker 1, sequence 1.
4. The timestamp is interpreted relative to the documented custom epoch. It describes the encoded generator time, not an exact transaction commit time. A queue or delayed database write can make record creation much later.
5. Scanning time-prefixed IDs can group roughly contemporaneous records. For an exact business-time report, use the authoritative createdAt field. Clock differences and gaps mean numeric ID order does not prove which event happened first.
6. During format migration, consumers retain the version or namespace and decode accordingly. A new epoch using the same untagged 63-bit space can alias old IDs, so it is not a safe transparent reset.

A public-facing random alias may be stored alongside the internal compact ID when activity inference matters. That alias solves a privacy property; it should not be confused with the internal allocation proof.

13Correctness deep dive

At lastTime 160/sequence 15 in the tiny format, all sixteen sequence values for that timestamp are consumed. Wrapping to 0 would repeat an earlier ID. Wait for a safe next tick, use separately allocated capacity, or reject.

If the wall clock moves from 160 back to 158, simply resetting the counter is unsafe. A bounded logical-time policy can continue only with sufficient sequence capacity and durable restart protection. A lease record alone does not stop a paused old process from issuing after worker 1 is reassigned. Require an explicit self-fencing/timing model and safe reuse interval, reserve disjoint time/ranges, or encode a new allocation generation. When safety is uncertain, stop issuance.

nextId():
  lock local generator cursor
  t = physical elapsed milliseconds
  require grant.start <= t < grant.end
  require t >= lastTime; otherwise wait or return clock_error
  candidateSequence = 0 if t > lastTime else lastSequence + 1
  if t == 0 and worker == 0 and candidateSequence == 0:
      candidateSequence = 1  # reserve ID zero for this positive-ID format
  require candidateSequence < 2^sequenceBits; otherwise wait or reject
  id = (t << (workerBits+sequenceBits)) |
       (worker << sequenceBits) | candidateSequence
  lastTime = t; lastSequence = candidateSequence
  return id

Check the limit before changing the cursor. A rejected allocation must leave it safe, and a retry must run the same checks again. Batches reserve their entire sequence span under the lock and split only across valid safe ticks or return fewer values under an explicit contract.

14Failure and recovery

15Operations, security, and cost

Generator A’s VM snapshot contains timestamp 160, sequence 0, worker 1. Restoring it while the original machine still runs would duplicate tuples. Startup must acquire a fresh committed grant, validate saved boundaries, and reject copied or expired grants. Treat clock rollback, long process pauses, sequence exhaustion, and namespace rollover as test cases, not rare afterthoughts.

Authenticate allocators, protect namespace changes, bound remote batch requests, and monitor clock offsets, generation pauses, sequence utilization, ownership failures, and downstream duplicate constraints. Keep a unique constraint in record storage to detect duplicates, while designing the generator to prevent them. Document ID-format migration and public-reference privacy separately from generation speed.

The restore gate is concrete: the service does not expose nextId until its activation record names a fresh incarnation and its grant response is committed. Restored VM images clear serialized generator state before that gate. A snapshot taken after activation cannot simply be resumed as a second issuer; infrastructure policy and startup hooks enforce this restriction. If that restriction is unacceptable, select the external-allocation design instead.

Test two concurrent threads at a tick boundary, sequence exhaustion, backward and forward clock jumps, process pause past grant end, response loss on grant allocation, and allocator failover after commitment. Include a stale-backup restore drill: it must preserve grant high-water state or refuse the namespace. A throughput benchmark that never restarts a process does not validate uniqueness.

At 500 grants/s with an illustrative 200-byte grant record, raw authority history grows 100 KB/s, about 8.64 GB/day before indexes and replicas. Retention can compact old grant detail only if the durable high-water marks and namespace safety evidence remain intact. This is far smaller than a ten-million/s per-ID ledger, but it is still an operational dataset.

Monitor how long generators wait for future grants, not only how many IDs they produce. Repeated restarts can burn future intervals and cause an outage even while average issuance is far below the sequence capacity.

16Decision ledger and limitations

UUIDv7 allocates 48 leading bits to Unix milliseconds and defines the remaining version/variant/random-or-monotonic fields. Use an established implementation rather than truncating or improvising a compatible-looking layout. RFC 9562. If global order is essential, introduce a sequencer/consensus-backed allocation path and explain its availability/latency cost.

Our compact layout saves space and keeps the fast path local, but it requires a controlled generator lifecycle, an allocator, and explicit behavior under clock anomalies. Non-overlapping grants let an old paused process resume without colliding with its replacement. They do not protect two copies of the same active process state.

A range allocator avoids wall-clock assumptions if approximate time sorting is unnecessary. UUIDv4 removes worker coordination with probabilistic collision resistance when generated correctly. UUIDv7 offers a standardized timestamp-leading format but still does not establish global real-time order or hide generation time. Neither should be truncated to fit 63 bits without a new collision analysis.

17Interview closing

“I start with a database sequence or disjoint range allocation because they are simple and correct. For the chosen time-prefixed format, I allocate 41 timestamp bits, 10 worker bits, and 12 sequence bits, giving a finite 69.7-year epoch and 4,096 values per worker per millisecond.

“The hard part is lifecycle safety, not bit shifting. The allocator durably reserves nonoverlapping timestamp intervals for each worker. Local calls synchronize their cursor and stop on rollback, overflow, or grant exhaustion. A paused old worker and its replacement have disjoint timestamp space, so they cannot collide. A supported restart abandons its old interval. Invisible cloning of activated memory is outside this local design and requires an external issuance boundary.

“The fast path is local; with 500 processes and one-second grants, control traffic is roughly 500 transactions/s rather than ten million. The cost is gaps, future-range waiting, clock policy, and finite worker capacity. I would test pauses, snapshot restore, allocator recovery, and sequence exhaustion before trusting a throughput chart.”

If the interviewer relaxes the compact-integer requirement, I would strongly consider a standard UUID implementation. If they demand global order or gapless invoices, I would introduce explicit coordination and explain the latency and availability cost rather than claiming the same local generator already provides it.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.