Design a distributed unique ID generator

Billions of unique, roughly ordered IDs a day from many machines with no coordination on the hot path.

Problem 064 of 100Infrastructure and platformL41 Nov 2026

Concepts this design leans on

Unique ID generation — IDs that are unique, roughly ordered and made without a central counter.
Clocks and ordering — Why machines disagree about time, and how to order events anyway.
Replication — Keeping copies so reads scale and a dead machine loses nothing.
Failure detection and health checks — Telling a slow machine from a dead one, quickly and without false alarms.

01The design, in the six-step framework

1. Requirements

Functional

Generate identifiers for events, orders, messages: unique across the whole system, forever.
IDs sort roughly by creation time, so recent items cluster and range scans by time are possible.
Fit in 64 bits, so they are cheap to store and index and usable as database keys.
Available from thousands of machines with no coordination on the request path.
Out of scope: human-readable or guessable-resistant ids (a separate concern), URL short codes.

Non-functional

Scale: 10 billion IDs a day, bursts of 1 million a second, from 5,000 machines across regions.
Latency: under 1 millisecond, ideally in-process.
Correctness: no duplicates even across machine failures, restarts and clock problems.
Ordering: within a few milliseconds of true time order; strict order is not required.

Back of the envelope

10¹⁰ IDs/day ≈ 116,000/s average, 10⁶/s at peak

64 bits: 41 bits of milliseconds = 2⁴¹ ms ≈ 69 years; 10 bits of machine id = 1,024 generators; 12 bits of sequence = 4,096 per ms per generator

Capacity: 1,024 × 4,096 × 1,000 = 4.2 × 10⁹ IDs/s, 4,000× the peak

A time-based layout fits with room to spare; the design work is in assigning machine ids and surviving clock trouble.

2. Core entities

ID: 1 sign bit (unused), 41 bits timestamp since a custom epoch, 10 bits generator id, 12 bits sequence.
Generator: the in-process component with its id, last timestamp, sequence counter.
GeneratorLease: generator id, holder (machine, process), lease expiry; stored in the coordination service.
Epoch: the fixed start time baked into the format (so 41 bits last 69 years from it).

3. API

In-process: next_id() returns an int64; next_ids(n) for batches. This is the hot path, a library call.
POST /generators/lease on startup: returns a generator id and a lease duration; POST /generators/{id}/renew periodically.
Optional service form for languages without the library: GET /ids?n=100 returning a batch, backed by the same generator.
GET /ids/{id}/decode for debugging: timestamp, generator, sequence.

4. High-level design

On start, the process asks the lease service for a free generator id in its region's range and holds it with a renewable lease.
Each call reads the current millisecond, compares with the last timestamp used: same millisecond increments the sequence; a new millisecond resets it to zero; a sequence overflow spins until the next millisecond.
The ID is composed by shifting and ORing the three fields. No network, under a microsecond.
Processes that cannot embed the library call the ID service for batches, which runs the same generator with its own leased ids.

5. Deep dives

Why not UUIDs, a database sequence, or a central ticket server?

UUIDv4 is 128 bits, random, and sorts badly: inserting random keys into a B-tree index touches random pages and halves write throughput, and a 128-bit key doubles index size. A database auto-increment is a single point of coordination; a round trip per id and one writer's throughput. A central ticket server handing out ranges is workable (each machine takes 1,000 ids at a time) and is the right choice if strict monotonic order matters, but it adds a dependency and a hot spot. Time-based 64-bit ids give locality, no hot path dependency and 69 years of room; the price is the machine-id assignment and the clock discussion below. UUIDv7 is the same idea in 128 bits for systems that want a standard (unique ID generation).

How are generator ids assigned without duplicates after crashes?

Two processes with the same generator id in the same millisecond collide. Assign ids through a lease in a consensus-backed store: a process acquires an unused id with a 60-second lease and renews every 20 seconds; if it cannot renew, it stops generating before the lease expires, so a partitioned process can never overlap with the process that takes its id afterwards. Reserve ranges per region and per environment so a misconfigured staging box cannot collide with production. The lease service is only on the startup path; a lease outage means new processes cannot start generating, not that running ones stop, which is the availability property to state.

What happens when the clock goes backwards or drifts?

If the wall clock jumps back (NTP correction, VM migration), reusing earlier milliseconds with a reset sequence can duplicate ids. Keep the last timestamp used and never go below it: if the clock reads earlier, either keep issuing in the last millisecond until the sequence runs out, then wait, or refuse for the few milliseconds of difference. Large jumps (seconds) should alarm and pause the generator. Use the monotonic clock for the comparison and the wall clock only to seed it. Drift between machines is fine because uniqueness never depends on cross-machine time; it only loosens ordering by the drift, typically under 10 ms with NTP, which satisfies "roughly ordered" (clocks and ordering).

What does a hot generator do when it exhausts 4,096 per millisecond?

It waits for the next millisecond, which caps one generator at about 4 million ids a second, far above any single process's need; a process that needs more runs several generators with separate ids. Batches (next_ids(1000)) are cheaper than loops and are what bulk importers use. For the service form, each instance pre-generates a small buffer so a request is a memory copy. Across the fleet, 1,024 generator ids per region range supports a million processes only if ids are leased on demand rather than assigned statically, which is one more reason for the lease design; widen the layout to 12 bits of generator and 10 of sequence if the fleet is larger than the per-process rate.

How are ids used downstream, and what do they leak?

Because the top bits are time, a range scan over ids is a time-range scan, which is the point: a messages table keyed by id returns recent messages with one index read. The same property means a database sharded by the id's leading bits puts all new writes on one shard; shard on a hash of the id or on a separate key such as user id instead. Externally visible ids reveal creation time and, through the sequence, a rough rate of creation; if that matters for a product (order numbers that competitors could count), expose an encrypted or hashed form and keep the sortable id internal.

6. What a strong answer sounds like

Write the bit layout on the board with its arithmetic: years of range, generators, ids per millisecond, and compare to the peak.
Explain why random UUIDs hurt databases and why a central sequence is a bottleneck.
Make generator-id assignment a lease with a stop-before-expiry rule; that is what makes uniqueness survive crashes and partitions.
Handle clock regression explicitly with a last-timestamp guard and the monotonic clock.
Follow-ups to expect: strictly increasing ids across machines (not possible without coordination; offer the ticket-range server), ids that must not reveal volume or time (encrypt or add a random component and lose sortability), and sharding by id (the timestamp prefix makes recent writes hit one shard; append or hash a shard key instead).

02Where this question was reported

IGotAnOffer · EM list
PracHub · 'fault-tolerant ID generation service', PM