Design a distributed unique-ID generator

01Ask what the identifier must guarantee

An ID generator provides distinct values that other services use as record keys. Ask which namespace needs uniqueness, whether IDs must be integers, whether gaps are acceptable, and whether values must reveal creation order. Those are separate requirements. A unique value does not prove a record was committed, does not authorize access and does not make a retried business request safe.

Our order services need positive integers before batching database writes. Gaps are acceptable. IDs need not follow strict global real-time order and do not need to encode time. These choices let us build a straightforward allocator rather than begin with a custom clock-based format. Keep a unique constraint in the order database as a final detector of a violated assumption.

The complete flow is simple: the order service asks an allocator for an ID, receives a safely allocated value, and then uses it in its own order transaction. If that transaction’s reply disappears, the order API uses a separate business request key to discover its result. Asking for another ID would not establish that the original order failed.

02Functional requirements

Agree on what the service must do before choosing its components.

1. Allocate identifiers. Issue positive integer IDs within a named namespace for consuming services to use as record keys.
2. Support bounded allocation. Offer individual IDs and bounded batches, with explicit unavailable or exhaustion responses rather than wrapping into previously used values.
3. Inspect namespace state. Allow authorized inspection of allocation state and capacity. Namespace creation and migration are privileged, audited operations.

Gapless invoice numbering, secret access tokens, exact creation timestamps and business-request idempotency are outside the generator contract.

03Non-functional requirements

Use these hypothetical requirements for the worked interview. Confirm the assumptions with the interviewer; the numerical targets require testing and are not measured results. For latency, p95 and p99 mean that 95% and 99% of measured delays, respectively, are no greater than the reported value.

1. Workload. Plan for ten million IDs/s peak across 500 generator processes, or 20,000/s per process on average. Bursts and uneven distribution still require testing.
2. Latency and availability boundary. Target local p99 below 100 microseconds while the process has unused IDs already reserved for it. Local issuance may continue during an authority outage until those IDs run out; replenishment then needs the authority, and exhausted processes must wait within a deadline or fail explicitly.
3. Uniqueness and durable allocation. No successfully issued value in one namespace may be repeated under supported failures. Committed ranges and replay results must survive allocator failover; an asynchronous promotion that loses acknowledged allocation state does not meet this requirement. Unused values and non-global issue order are acceptable.
4. Safe restart and recovery. A restarted process abandons its previous range. Never restore uncertain allocation history or clone one active in-memory cursor into simultaneous issuers. Arbitrary live-memory cloning requires a stronger external allocation boundary. Backups cannot silently move the allocated boundary backward.
5. Exact representation and access. Preserve the full integer value across client types, for example with decimal strings where needed. Authenticate generators and namespace administration; a predictable ID never grants access to a business record.

04Allocate from one durable counter

Begin with one allocation service and an Allocator row:

A single-ID request follows this transaction:

1. Lock. Open a short transaction and lock the namespace row.
2. Reserve. Read its next available integer and increment nextValue.
3. Commit. Preserve the advance with the required durability.
4. Return. Send the allocated value only after that commit.

Concurrent requests take turns at this row, so they cannot receive the same value.

If nextValue is 1001, request A reserves 1001 and commits 1002 as the next value. Request B then gets 1002. If A crashes after commit but before replying, 1001 may never be used. That is an acceptable gap. It must not be recycled merely because the service did not observe the client using it.

A database sequence is another implementation option with its own documented caching and durability behavior. The essential contract is to preserve acknowledged allocation state across supported failures and never cycle into used values. A small deployment can stop here.

The allocation transaction and the order transaction remain separate. A user-visible order is created only when the order service commits it. This explains why the generator can produce gaps even during healthy operation: clients can abandon work or fail after allocation.

05Calculate the value of batching coordination

At one remote allocation per ID, ten million/s is substantial control traffic. A serial caller with a one-millisecond round trip can issue roughly 1,000 requests/s. More concurrency improves aggregate rate, but adds network and database pressure while every allocation still depends on the authority.

Reserve a numeric range of 10,000 IDs per control transaction. At 20,000 IDs/s, each process needs roughly two ranges/s. Across 500 processes, the authority handles about 1,000 range transactions/s instead of ten million per-ID calls. Local increments handle the remaining work.

Size range requests with expected rate and acceptable outage duration. Benchmark local synchronization under bursts, not just arithmetic. Integer capacity is finite even when it is very large: define the maximum and reject a reservation whose end exceeds it. Do not silently wrap a counter or reuse another namespace’s space.

06Make range ownership and API identity explicit

Separate namespace allocation state from individual reservations:

An incarnation identifies one start of a process. A replacement uses a new incarnation so it cannot claim the old process’s range.

Range request from a trusted generator

POST /ranges

{
  "namespace": "orders",
  "incarnation": "A9",
  "requestId": "r17",
  "count": 10000
}

Example reserved range

Interval:       [1001, 11001)
First value:    1001
Last value:     11000
Exclusive end:  11001

A half-open interval includes the start and excludes the end. The following range can therefore start at 11001 without sharing an endpoint.

Authenticate the generator and bound requested count. Within the same live incarnation, repeating r17 returns the saved range; different count or namespace under r17 conflicts. The range record and boundary advance commit together. Install a returned reservation only once within the live incarnation. A duplicate response for r17 refers to the already installed range and its current cursor; it must never reset that cursor to the range start. A new incarnation must use new request identity and receive a fresh range, rather than recovering an old cursor after a crash.

Local nextId() returns one value from the current range or a clear unavailable/exhausted response. A remote batch API can additionally retain its returned batch under a request key, but that is a separate replay contract with storage and retention costs.

07Move only the fast counter into each process

Scale the authority operation from “reserve one” to “reserve count.” Perform these steps in one database transaction:

1. Lock the namespace row. Read its current nextValue.
2. Calculate the reservation. Set start = nextValue and end = start + count.
3. Check capacity. Validate the bound before changing allocation state.
4. Record both changes. Advance nextValue to end and insert the request/result record.
5. Commit, then return. Return the range only after commit.

Each process keeps a cursor and the exclusive end of its committed range. An atomic increment or short local lock reserves the next unused value. No network call is required while usable values remain. Near exhaustion, a background replenisher asks for another range and installs it under the same local synchronization rules.

The ranges are disjoint because the database serialized their boundary advances. Adding generator processes therefore increases aggregate local capacity without changing the central uniqueness argument. The authority still controls a small stream of range reservations.

Partition allocation by independent namespaces if the product already has them. Splitting one integer space among several uncontrolled allocators would require another disjointness rule and is unnecessary at the assumed control rate. First measure whether a replicated database can meet roughly 1,000 short range transactions/s with recovery headroom. Avoid adding a distributed custom protocol before that measurement shows a need.

08Trace local calls and the last value in a range

Generator A holds [1001,11001) with cursor 1001. Under a local lock, request 1 reads 1001, advances cursor to 1002 and returns 1001. Request 2 observes 1002 and returns it. Without synchronization, both threads could read 1001 before either advanced the cursor, duplicating a value despite perfectly disjoint cross-process ranges.

At cursor 11000, the process can return the last allowed value and advance to 11001. It cannot issue 11001 from this range. If a prefetched range is ready, atomically switch to its start; otherwise wait within the caller’s deadline or return unavailable. Never increment beyond the end and continue after an error.

A local batch reserves its whole requested span under the same guard. Decide whether a batch may cross into another already committed range or must return fewer values; document the response instead of assuming contiguity across separate reservations.

The order service then creates the order using the ID and its own stable business request key. If its response is lost, a retry finds that order’s saved result. A generation call lost before the caller receives it can waste an ID, but it must never cause the allocator to return that possibly delivered value again.

09Prove uniqueness through crashes and failover

Within a live process, synchronized cursor updates assign different values. Between processes, committed numeric ranges do not overlap. Those two facts establish the ordinary uniqueness proof without any wall-clock assumption.

If a generator crashes halfway through its range, restart abandons all remaining values and requests a fresh range. It does not need to recover the exact last local increment, because none of its old range is reused. This deliberately trades gaps for simpler crash safety. A paused process can resume using its existing range while a replacement has a different range; their values still differ.

If the allocator commits a range but loses its reply, the same running process retries with the same request identity and receives the saved range. Duplicate responses reuse an already installed reservation’s current cursor; they never reinstall it from the beginning. A new process must not take that old permission if the former process might still be alive. Restart therefore uses a new incarnation and a new range.

Allocator failover must retain committed boundaries and result records. A stale promoted replica or restored backup can otherwise allocate an overlapping historical range. Refuse service when that evidence cannot be established, or move to an explicitly different namespace. A downstream unique constraint can detect failure but is not permission to tolerate an unsafe allocator.

10Keep identifiers exact and order claims modest

Return large integer IDs as decimal strings when clients cannot represent the full integer range exactly. JavaScript Number is exact only through 2^53 − 1; rounding a valid larger ID can collapse distinct values at the client. Parse directly into an appropriate integer type and keep namespace information wherever values from different spaces can meet.

Numeric ranges do not provide global issue order. Process A may still issue 1002 after process B has issued 11001. That does not violate uniqueness. Store an explicit business createdAt when the application needs creation time, and use an actual sequencing protocol if global real-time order is required.

IDs can reveal rough activity or be predictable. Authorization checks must verify the actor and record owner. If public URLs need to conceal internal ordering, store a separate random reference rather than treating the integer as a secret.

Do not reset the counter when deploying a new version or restoring a test dataset into production. Namespace creation and migration are privileged audited actions. Mixing two independently allocated spaces as bare integers loses the uniqueness scope that made each one correct. API documentation must state that scope as clearly as the wire format.

11Explain when the simpler design stops fitting

If clients need decentralized allocation without a control service, an established UUID implementation may be preferable. UUIDv4 provides probabilistic uniqueness from correctly generated randomness. UUIDv7 is a standard timestamp-leading format that improves time locality without promising strict global real-time order. Neither should be casually truncated into a smaller integer.

A Snowflake-style format combines timestamp, worker and per-timestamp sequence fields. It can provide compact approximate time ordering, but now worker reuse, sequence overflow and clock rollback affect uniqueness. Introduce it only when that ordering/storage requirement justifies the extra protocol. Resetting a sequence when a clock moves backward can repeat a tuple; safe waiting or an explicitly proved alternative is required.

The main design remains numeric ranges because the agreed product does not require encoded time. Strict global ordering instead favors a shared sequencer with its latency and availability cost. Gapless invoice numbers must be tied to business commit and cancellation rules, not inferred from an ordinary allocator.

Measure range reservation latency, remaining local capacity, abandoned IDs, cursor contention, boundary exhaustion and failed safety checks. Drill lost replies, process restarts, pauses, stale backups and allocator quorum loss before optimizing steady-state throughput further.

12Check the design against its requirements

Before closing, check the final design against the agreed requirements. FR means functional requirement and NFR means non-functional requirement; the numbers refer to the lists above. These are proposed validation checks, not test results.

13Rapid revision

Rehearse the numbered functional requirements and non-functional targets first. Use this table to recall the mechanisms, then close with the requirements check above.

Remember: Separate ranges between processes; synchronize within each.

Close with: “I start with a durable counter and scale by reserving ranges. The authority proves ranges are disjoint, while each process synchronizes its cursor. Restart burns unused values instead of reconstructing uncertain local history. At the assumed load, 10,000-value ranges reduce authority traffic to about 1,000 reservations/s. The costs are gaps and no strict global issue order, both accepted in our contract.”

Recall the key ideas

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