Infrastructure
Design Unique ID Generator
01
What the generator must guarantee
What the generator must guarantee
- Return a 64-bit integer that is unique across every service, region and restart, for the lifetime of the platform.
- IDs minted later should usually compare greater, so B-tree inserts land at the right edge of the index.
- Callers can request one ID or a batch of up to 1,000 in a single call.
- Any ID can be decoded back into its creation time and the worker that minted it, for debugging and data retention jobs.
- Offer a short string form for URLs and logs.
- Minting an ID needs no network round trip on the hot path; target p99 under 2 microseconds in process.
- Sustain 1.4 million IDs per second across the fleet at peak, with headroom for ten times that.
- A duplicate ID is a correctness bug, not a degraded mode. The generator must refuse to issue rather than risk one.
- Keep working for at least 60 years from the chosen epoch without a format change.
- IDs must not reveal business volume to outsiders in an obvious way when exposed in public URLs.
Ask whether IDs must be strictly increasing or only roughly ordered, whether they must fit in 64 bits, how many processes mint at once, and whether IDs appear in public URLs. Strict global ordering needs a single sequencer and kills throughput; roughly ordered within a few milliseconds is almost always enough. The 64-bit limit rules out UUIDs immediately if the interviewer insists on it.
02
Sizing the bit budget
Sizing the bit budget
Assume a platform of about 3,000 application pods across three regions. Peak demand is 1.4 million new IDs a second, mostly chat messages and event rows, with an average of around 350,000. The busiest single pod mints about 20,000 a second during bulk imports.
| Quantity | Working | Result |
|---|---|---|
| Peak IDs per second, fleet | assumption | 1.4M |
| Busiest pod | bulk import job | about 20,000 / s |
| Concurrent minting processes | 3,000 pods, plus 30% headroom for rolling deploys | about 3,900, so 12 worker bits (4,096) |
| Per-worker ceiling | 2^10 sequence values per millisecond | 1,024 / ms, about 1M / s |
| Fleet ceiling | 4,096 workers x 1M / s | about 4.2B / s |
| Timestamp range | 2^41 ms / (1,000 x 86,400 x 365) | about 69.7 years from the epoch |
| Custom epoch | 2026-01-01T00:00:00Z | runs out around 2095 |
| IDs created per year | 350K / s x 31.5M s | about 11 trillion |
| Key storage, 64-bit vs UUID | 11T rows x (16 B - 8 B), primary key only | about 88 TB a year saved before secondary indexes |
| String length | 2^63 in base62 | 11 characters |
Throughput is not the challenge: one pod can mint a million IDs a second with a counter and a clock read. The scarce resource is bits. Every bit given to workers is taken from time or sequence, and the split you choose decides how many processes you can run, how long the format lasts and how bursty a single worker can be.
An 8-byte key fits in a CPU register, a database BIGINT and a JSON number up to 253 if you send it as a string. A 16-byte UUID doubles the size of every primary key and every foreign key that points at it.
03
API design
API design
The generator ships as a library linked into every service. A small standalone service exists for languages and jobs that cannot run the library, and it exposes the same operations over HTTP.
A network call per ID would add a millisecond of latency and a dependency to every insert in the company. The only network traffic in this design is the lease renewal, one small call every 10 seconds per pod.
04
Architecture overview
Architecture overview
flowchart LR
subgraph POD["Application pod"]
APP["Service code"] --> LIB["ID library: clock, sequence, worker slot"]
end
LIB -. "lease and renew every 10 s" .-> LS["Lease service"]
LS --> ETCD[("etcd: worker slots")]
NTP["Time sync: chrony"] --> LIB
LIB --> MET["Metrics: clock drift, waits, refusals"]
JOB["Batch job or other language"] --> SVC["ID HTTP service"]
SVC --> LIB2["Same ID library"]
LIB2 -. "lease" .-> LSThere is almost nothing in the architecture, and that is the point. Each process holds three pieces of state: a worker number it leased at start-up, the last timestamp it used, and a sequence counter for the current millisecond. Minting an ID reads the clock, compares it with the last timestamp, bumps or resets the counter, and packs the three values into 64 bits. No lock is shared with any other process.
Uniqueness rests on one invariant: no two live processes ever hold the same worker number at the same time. The lease service enforces that using etcd, which gives linearisable compare-and-set and key expiry. A pod that cannot renew its lease stops minting before the lease can expire and be handed to someone else.
Time comes from the host clock disciplined by chrony or NTP. The library reads a monotonic clock for elapsed time and anchors it to wall time at start-up, which protects it from most sudden adjustments. Metrics on drift and refusals go to the normal monitoring stack, because clock trouble is the one thing that can make this system misbehave.
About 200 lines in each supported language. Thread-safe with a single atomic compare-and-swap on a packed 64-bit state word, so there is no mutex on the hot path.
A thin wrapper over etcd that hands out worker numbers 0 to 4,095, records the last timestamp each slot reported, and expires slots whose holder has gone quiet for 30 seconds.
Three or five nodes per region. It sees about 300 small writes a second from renewals, which is far below its limits. If it is down, pods keep minting on their current leases.
A handful of stateless pods for callers that cannot link the library. Batched requests keep its cost tiny.
05
Deep dive: bit layout, clocks and slot handover
Deep dive: bit layout, clocks and slot handover
How do thousands of processes produce numbers that never collide and still sort by time, when they share no memory and their clocks disagree by a few milliseconds? The answer is to carve the 64 bits so that each process owns a disjoint slice of the number space, and then to be paranoid about time.
The bit layout
| Field | Size | Why |
|---|---|---|
| Sign | 1 bit, always 0 | Keeps IDs positive in languages and databases with signed 64-bit integers. |
| Timestamp | 41 bits, milliseconds since 2026-01-01 | About 69.7 years of range. The custom epoch buys back the 56 years since 1970 that a Unix-epoch timestamp would waste. |
| Worker | 12 bits, 0 to 4,095 | Leased per process. Enough for 3,000 pods plus deploy overlap. |
| Sequence | 10 bits, 0 to 1,023 | Resets every millisecond. Caps one worker at 1,024 IDs per millisecond. |
Putting the timestamp in the high bits is what makes IDs sort by time: comparing two IDs compares their milliseconds first. Within one millisecond, IDs from different workers interleave by worker number, so ordering across machines is only approximate. That is fine for index locality and for "newest first" queries, but you must not use these IDs as a strict happened-before clock.
Why 12 and 10 instead of the classic 10 and 12? Because this platform has many processes that each mint modestly, not a few dedicated servers that mint heavily. The busiest pod needs 20 per millisecond; 1,024 is fifty times that. The extra worker bits are what let every pod embed the library directly.
Clocks that go backwards
NTP corrections, VM migrations and a misconfigured host can all move wall time backwards. If the library simply trusted the clock, it would re-enter milliseconds it already used and could repeat a sequence value. The library therefore never issues a timestamp lower than the last one it used, and handles a backward step by size:
- Under 5 ms: spin until the clock catches up. Callers see a few milliseconds of latency once.
- 5 ms to 2 seconds: keep using the last timestamp and keep incrementing the sequence, rolling into the next millisecond value when it fills. The process is "living in the future" until real time catches up, and a gauge reports how far ahead it is.
- Over 2 seconds: stop minting, release the lease, and restart. Something is badly wrong with this host and a duplicate is worse than an outage of one pod.
Handing over a worker slot safely
Leases close the gap between processes, but there is a subtle case. Pod A holds worker 1187, freezes in a long garbage collection pause, and its lease expires. Pod B gets 1187. Pod A wakes up and mints one more ID before noticing. Two defences close this:
First, the library checks its lease deadline before every mint, using the monotonic clock, and stops at TTL minus a 5-second safety margin. A paused process wakes up, sees the deadline has passed, and refuses. Second, each renewal stores the highest timestamp the holder has used. A new holder receives that value as not_before_ms and will not mint until its own clock is past it, so even a slot reused within milliseconds cannot produce an ID the previous owner might have produced.
flowchart TD
S["Pod starts"] --> L["Lease a free slot from etcd"]
L --> W{"Clock past not_before?"}
W -->|no| WAIT["Wait"] --> W
W -->|yes| M["Mint IDs locally"]
M --> R{"Renewed before deadline?"}
R -->|yes| M
R -->|no| STOP["Stop minting and release"]The alternatives, briefly
UUID v4 is 122 random bits: no coordination at all, but 16 bytes and no ordering, so B-tree inserts scatter across the index. UUID v7, standardised in RFC 9562, puts a millisecond timestamp in the top 48 bits followed by random bits, which fixes ordering and still needs no coordinator; it is the right default when 128 bits are acceptable. ULID is a similar idea with a Crockford base32 text form.
Range allocation from a database, as in Flickr's ticket servers or Meituan's Leaf segment mode, hands each process a block of numbers from a central counter. IDs are dense and short, but ordering is only by block and the counter is a dependency at block boundaries. Database-embedded generation, where each shard combines time, shard number and a per-shard sequence in a stored procedure, works well when IDs are only ever created inside the database.
06
Designs to avoid
Designs to avoid
Every write in the company now depends on one service and pays a round trip for it. When the service hiccups, everything that creates data stops.
Two pods deployed from the same config, or a cloned VM, share a worker number and quietly produce duplicates that surface weeks later as primary key violations.
A one-second NTP step backwards replays a thousand milliseconds of IDs for that worker.
By the birthday bound, generating 11 trillion random 64-bit values a year means millions of expected collisions in the first year alone.
07
Decisions and their costs
Decisions and their costs
Small keys, ordered by time, no per-ID coordination and decodable for debugging. You take on clock discipline and a lease system for worker numbers.
Best fit for 64-bit keysNo leases and no worker numbers at all, and still sortable by time. The cost is twice the key size everywhere, which adds up across trillions of rows and their foreign keys.
Choose when 128 bits is fineNo latency, no shared service on the write path, and throughput scales with the fleet automatically. Each supported language needs a careful implementation and shared test vectors.
Fastest and most availableOne place to reason about uniqueness, and good for small systems. It adds a network hop to every insert and becomes the most critical dependency in the company.
Single point of painFits thousands of short-lived pods, each well under its per-millisecond limit. A pod that needs more can lease two slots.
Matches this fleetThe classic split suits a few dozen dedicated generator nodes that each mint millions a second. With 3,000 pods it simply runs out of worker numbers.
Right for few heavy nodesRecovers about 56 years of range, so 41 bits last until the 2090s. Every decoder must know the epoch, which belongs in one shared constant.
Free rangeFamiliar and easy to read, but a 41-bit millisecond counter from 1970 runs out in 2039, which is too close for a format you can never change.
Wastes bits08
Failure modes
Failure modes
A hypervisor migration resets the guest clock. The library sees time earlier than its last issued timestamp.
Small steps are absorbed by waiting or borrowing from the sequence. A step beyond the threshold makes the pod stop minting, release its slot and restart, while an alert names the host.A long garbage collection pause outlives the 30-second lease. Another pod takes the slot, and the paused one wakes up mid-mint.
Check the lease deadline on every mint with a 5-second margin, and give new holders the previous holder's last timestamp so they start strictly later.A large deploy doubles the pod count briefly, and crashed pods hold slots until their leases expire. New pods cannot start minting.
Size bits for peak plus deploy overlap, shorten TTLs during deploys, and release slots in the shutdown hook. Alert at 80% slot use so the format change is discussed years before it is needed.A network partition separates a region from its etcd cluster. Renewals fail everywhere at once.
Pods keep minting until their own lease deadline, which gives about 25 seconds to recover. New pods cannot start, so deploys pause. Run etcd across three zones and keep its quorum independent from the application network.A backfill job asks for 50,000 IDs in a tight loop. It fills 1,024 IDs per millisecond and starts waiting on every millisecond boundary.
This is correct behaviour, not a bug, but monitor wait time. Heavy jobs lease several worker slots and round-robin across them.Around 2095 the 41-bit field overflows and IDs would wrap to small values, breaking ordering and risking collisions with old IDs.
Record the overflow date in the format's documentation and set a reminder decades early. The fix is a new epoch with a version bit, planned well in advance.09
How to run the interview
How to run the interview
Ask about size and ordering first. Whether the ID must fit in 64 bits and how strictly it must be ordered decides the whole answer in two questions.
Draw the bits. Write the field layout with sizes and do the arithmetic for years of range and IDs per millisecond. Interviewers want to see you justify each split.
Explain how worker numbers stay unique. Static config is the common answer and the weak one. Leases with expiry, and what happens after a pause, show real depth.
Raise clock problems yourself. Describe what you do for a small backward step and for a large one. Saying "we refuse to mint" earns more trust than clever recovery.
Compare with UUID v7 honestly. It is a strong option when 128 bits are acceptable. Knowing when not to build this system is part of a good answer.
Point out that ordering is approximate. IDs from different workers in the same millisecond interleave. Do not use them to order events that need causality.
Mention the public URL problem. Time-ordered IDs leak creation time and rough volume. Encode them, or use a separate opaque public identifier where that matters.
10
Growing the design in stages
Growing the design in stages
The database hands out the next number on insert. Simple, dense and ordered, until you shard the table and two shards both create row 1001.
Each shard counts with a different step, or the team switches to UUID v4. The first breaks when you add a shard; the second bloats indexes and scatters inserts.
A ticket database hands out blocks of 10,000 numbers to each service. IDs stay short, but the allocator becomes a critical dependency.
The library packs time, leased worker number and sequence into 64 bits, and the allocator is retired.
New services that do not need 64-bit keys use UUID v7 and skip leases entirely. The 64-bit format stays for the high-volume tables where key size matters. The auto-increment column survives only in internal tools.
Watch and read
Try next
Free to read · better with landed
Whiteboard this with landed
landed runs it as a live system design round on the whiteboard and grades your trade-offs.