Design a unique ID generator

Design the service (or library) that gives every new order, message and photo a unique ID: a million IDs a second across three regions, no two ever the same, roughly in time order, and fitting in 64 bits so database indexes stay small. Module 20 explains the ID formats; this design is about running them: who hands out machine numbers, what happens when a clock jumps backwards, and when to avoid clocks altogether.

1. The prompt

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

What makes it hard:

• No central counter. One database sequence is unique and ordered, but every ID would wait for one machine in one region.
• Clocks lie. Time-based IDs are sortable for free, but clocks drift, get corrected backwards, and differ between machines.
• 64 bits is a tight budget. Time, machine and sequence must share 63 usable bits, and each choice limits how long the scheme lasts or how big it can grow.

2. Frame the problem

3. What it must do

1. Hand out IDs that are unique across every machine and region, forever.
2. Keep them roughly time-ordered, so new rows land at the end of indexes.
3. Keep working when a region is cut off or the coordination service is down.

Not now: short human-friendly codes (that's D01), strictly gap-free numbering (invoices need a separate, per-company sequence for legal reasons).

4. How well it must do it

5. Numbers that change the design

The lab in section 13 lets you move the bits around and see the trade-offs.

6. The nouns

• ID: 1 sign bit (always 0) · 41 bits of milliseconds since our epoch · 12 bits of generator number · 10 bits of sequence.
• Generator: a process allowed to mint IDs, holding a unique generator number under a lease.
• Lease: the right to use a generator number, renewed every few seconds in a coordination service (etcd, ZooKeeper).

id (64 bits)     0 | ms since 2026-01-01 (41) | generator (12) | sequence (10)
generator_lease  /idgen/generators/{0..4095} → holder (host:pid), expires_at, last_ms_used   (etcd)
per process      last_ms, sequence                                                          (memory)

7. The contract

Library (preferred):   id = idgen.next()          // in-process, no network, ~100 ns
Service (alternative): POST /v1/ids?count=100     → [ids]    (for clients that can't embed the library)
Decode (support tools): GET /v1/ids/{id}          → {created_at, generator, sequence}

The library form keeps ID generation off the network entirely; the service form exists for languages or devices that can't hold a lease.

8. First working version

Each application process embeds the generator library. At start-up it claims a free generator number with a lease; after that, every ID is built from the clock, its number and a counter, entirely in memory.

8.1 A process starts and claims a number

8.2 Minting IDs in one millisecond

9. Make it hold up

9.1 When the clock goes backwards data safety

Run time sync that slews (speeds up or slows down the clock gradually) rather than stepping it, which makes backward jumps rare (Module 20). And never trust wall-clock time for correctness anyway: the "last millisecond used" check is what guarantees uniqueness.

9.2 Running out of sequence speed

With 10 sequence bits a generator can mint 1,024 IDs in one millisecond. The 1,025th waits until the next millisecond: at worst a sub-millisecond pause, about a million IDs a second per generator. If that's a real limit, give the busiest services more generator numbers, or more sequence bits and fewer generator bits. Never "borrow" from the next millisecond's numbers early without recording it, or a restart can reuse them.

9.3 IDs without clocks: handing out blocks surviving failures

9.4 Three regions surviving failures

Split the generator numbers by region (0–1,365 for region 1, and so on), so each region's coordination service hands out only its own range. A region cut off from the others keeps minting with no risk of collision, because no other region can hold its numbers. IDs from different regions are ordered by their clocks, which are within milliseconds of each other: "roughly sorted", as agreed.

9.5 IDs in public security

• They reveal time. Anyone can decode when an order was placed. Usually fine; avoid for things like account creation if that's sensitive.
• They reveal volume. Two orders a day apart show how many generators and sequence numbers were used in between, roughly. Strictly sequential IDs (1, 2, 3…) reveal it exactly.
• They're guessable. Never let an ID act as permission: check that the caller may see order 7203… (Module 26). Where guessing itself is a problem (shared links), use a random token alongside the ID.

9.6 The whole design after the deep dives

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• 64-bit time-based IDs: small and roughly ordered, at the cost of generator numbers and leases.
• A library, not a service: no network call per ID.
• Refuse to mint when the clock goes back, rather than risk a duplicate.
• Generator numbers split by region, so partitions can't cause collisions.

What we'd watch: backward clock jumps · sequence exhaustion waits · free generator numbers · lease renewal errors · any duplicate-key error.

At 10×: more generator numbers (a bit from the sequence), or IDs minted by fewer, busier processes. The format must be decided once, so leave room up front.

Common mistakes:

• Hard-coding machine numbers in config, then two copies of one config start.
• Ignoring a clock that goes backwards.
• A network call to an ID service for every ID.
• Treating an unguessable ID as an access check.

13. Try it, check yourself, read more

The bit-budget lab. 63 bits to share between time, generator number and sequence. Move the sliders and see how long the scheme lasts, how many generators it allows and how fast each can mint.

Sequence bits are what's left of 63 (bit 64 is the sign, kept 0 so IDs are positive in every language). Targets from section 2: 50 years, 2,000–10,000 generators, bursts of a few hundred IDs per millisecond per generator.