Design a distributed unique ID generator

Clarifying questions

Ask before you draw anything. The answers pick the winning option.

1. 01What creates IDs: posts, chat messages, orders, uploads, events? How many per second at peak?
2. 02Unique across the whole platform, or only inside one service?
3. 03Ordered by time? Strictly, or roughly?
4. 04Must they fit in 64 bits, or are 128 bits fine?
5. 05Who reads an ID back, and do they need its timestamp or minting machine?
6. 06Must IDs be unguessable? Can a user enumerate them?
7. 07How many minting processes? One datacenter or several?
8. 08Is there a database already? Is sharding planned?

Requirements

Functional: every request gets a unique ID with no duplicates. IDs are roughly time-ordered, so a later ID usually sorts after an earlier one. Any ID can be split back into timestamp, machine, and sequence. Time windows map to ID ranges for scans.

Non-functional: about 100k IDs per second at peak. Minting stays well under 1 ms with no network call per ID. One dead worker or a short registry outage does not stop minting. Hundreds of processes across datacenters. Keys stay at 8 bytes.

Out of scope: strict global order across machines, which independent clocks cannot provide. Short human-readable codes, which belong to the URL shortener. Unguessable client-facing IDs, which call for the 128-bit schemes covered below.

Estimation

Two numbers shape the design. Under this case study's database-writer assumptions, 100k/s exceeds one writer's budget, yet leaves substantial headroom under the theoretical per-worker bit budget. Actual database and generator throughput must be measured. Key size adds up: assuming 35k IDs/s all year, 8-byte keys come to roughly 8.8 TB per year and 16-byte UUIDs to roughly 17.7 TB, before indexes and replication.

Ascending keys append to the right edge of a B-tree; random keys land everywhere and split pages. Time order is a storage win, not just a sorting convenience.

Good: UUIDv4 or database auto-increment

UUIDv4 is 128 bits with 122 of them random. No coordination, no single point of failure, and minting is not limited by any shared component. The cost: 16-byte keys, page splits from random inserts, no time order (latest-first needs a created_at index), and IDs that tell you nothing in logs.

Auto-increment lets one database hand out the next integer: 64-bit and increasing in allocation order, but not necessarily transaction commit order. One leader limits throughput, illustratively around 5k to 20k writes per second depending on hardware and configuration. Availability needs replication and failover; unsafe counter recovery can re-issue values, while rollbacks and range reservations can leave gaps.

Good is enough with one database, low volume, and no sharding plans: choose auto-increment. If 128 bits are fine and order does not matter, choose UUIDv4.

Better: a ticket server with pre-fetched ranges

The Flickr ticket-server idea: a worker requests a block of 1,000 IDs, hands them out locally, and asks again when the block runs dry. One round trip per block instead of per ID. Two databases with odd and even offsets keep it available if one fails. IDs are 64-bit and roughly ordered per server.

The cost: every block request hits one hot row. Blocks lost on restart leave harmless gaps. There is still a round trip per block, and the ceiling stays below Snowflake.

Better is enough below about 10k IDs per second, without a sub-millisecond latency need, and before multiple databases arrive.

Best: Snowflake with a 41 / 10 / 12 bit split

This answers the stated ask. Twitter published Snowflake in 2010. An ID fits in a signed 64-bit integer: one zero sign bit plus a 63-bit payload, so it stays non-negative in databases and Java longs.

The split gives 4,096 IDs per millisecond per worker, a theoretical 4.096M per second. 41 bits of milliseconds last about 69 years from a 2024 epoch, into the 2090s. 10 machine bits allow 1,024 workers.

The split is a budget. Instagram chose 41 bits of time, 13 of shard, and 10 of sequence, minted per shard inside Postgres by a PL/pgSQL function: 1,024 IDs per millisecond per shard, and the shard in the key routes reads with no lookup table.

Composing is two shifts and an OR; decomposing is two shifts and two masks. Run it below. JavaScript numbers lose precision past 2^53, so signed 64-bit IDs are not exact as JSON numbers: send them as strings.

Write path: lease a machine id once at start-up, then mint in memory with a clock read and a few integer operations, no network call. In the same millisecond, increment the sequence; in a new one, reset it to zero. Read path: decompose by shift and mask, and turn a time window into an ID range so the query is a range scan.

Trade-offs: no per-ID coordination, but clock steps and machine-id reuse can both cause duplicates without the guards below. Alert at 80% of the timestamp range. The sequence leaks minting rate, so hide raw IDs where that matters.

Options compared

Follow the decision flow in order.

1. 01Must IDs fit in 64 bits? No: need time order? No means UUIDv4; yes means UUIDv7, ULID, or KSUID.
2. 0264 bits, one database, no sharding planned: auto-increment.
3. 03Otherwise, under ~10k IDs/s and no sub-millisecond need: ticket server with ranges on two databases.
4. 04Otherwise: Snowflake.

Deep dive: backwards clocks and the drift guard

A naive generator resets its sequence whenever the clock reading changes. After a backwards step from an NTP correction, VM live migration, or leap-second smear, it reuses old milliseconds and mints duplicates.

The fix is a logical millisecond the wall clock can only push forward. Inside one logical millisecond the sequence increments. On overflow the generator borrows the next millisecond instead of spinning. If the logical clock gets more than max_drift_ms ahead of the wall clock, it raises ClockDriftError. Small steps are absorbed; large ones become incidents.

The drift guard only bounds how far the logical clock runs into the future. Uniqueness still depends on exclusive machine-id ownership and restart discipline. Skew between different machines only blurs cross-worker order, because their machine bits differ.

Restarts are the trap. Persisting the last timestamp once a second is not safe: a crash can lose up to a second of minted IDs, and a restarted process with a slow clock would repeat them. Instead, durably reserve a high-water mark ahead of use (for example, write now plus a reservation window before minting inside it) and refuse to start until the wall clock passes it. Or start under a fresh machine id and quarantine the old one until the wall clock is past its previous logical maximum. Twitter also compared clocks with peers at start-up and refused to join when too far off.

Deep dive: machine-id leases and fencing

Two workers sharing a machine id mint duplicates once their clocks line up. The lease prevents that; the primary-key constraint detects it, so alert on violations.

Registration claims the lowest free id as an ephemeral node in ZooKeeper or etcd. The lease is 30 seconds and is renewed every 10 seconds. A lost race retries the next free id. When a session expires, the node is deleted and the id can be reused.

Fencing rule: a worker that cannot renew must stop minting before its lease expires. Check a conservative monotonic deadline on every mint, account for whether the platform clock advances during suspension, and refuse on uncertain ownership after wake-up. Lease expiry alone cannot stop a paused process that later resumes. Where protected writes use fencing tokens, the storage resource must reject stale tokens; checking a token only at the registry cannot fence an offline minter. Safe machine-id reuse also needs a durable timestamp high-water mark or quarantine beyond the previous holder's maximum logical time, including borrowed future milliseconds.

Coordination stays cheap: one registration per process start plus a renewal every 10 seconds, about 100 small writes per second at 1,024 workers. Minting never touches the registry.

Deep dive: sequence overflow

4,096 IDs per millisecond is a theoretical 4.096M per second from one worker. Hitting it means a benchmark, or one process minting for the whole platform.

Treat saturation as a capacity signal and add workers. Do not move bits from machine to sequence: that shrinks the fleet to fix a problem more workers already solve. On overflow, borrow the next millisecond under the drift guard rather than spinning.

Deep dive: ULID, KSUID, and UUIDv7

With 128 bits or more allowed, these keep time order with no infrastructure. High bits are time, so B-tree locality survives. The cost is bigger keys: 16-byte schemes double an 8-byte key (roughly 8.8 TB more per year at the 35k/s sizing assumption), and KSUID's 160 bits are 20 bytes, 2.5x. None orders across machines beyond clock skew.

The timestamp in ULID and KSUID is readable, not secret. Their unguessability comes only from the random part, which must use a cryptographically strong generator.

Pick Snowflake for 8-byte keys on a fleet you control. Pick UUIDv7 when your database and drivers support it. Pick ULID or KSUID when clients create IDs that must be hard to guess.

Scaling and failure modes

Return IDs as JSON strings. Cross-datacenter order is approximate; splitting machine bits per datacenter keeps uniqueness intact.

Trade-offs summary

Each choice and what the alternative would cost.

Interviewer follow-ups

Why not UUIDv4 everywhere? 16-byte keys, page splits, and no time order. UUIDv7 fixes the last two if 128 bits are acceptable.

Two workers share a machine id? Duplicates once clocks agree. The lease with fencing prevents it; the primary key detects it.

More than 4,096 IDs in one millisecond? Add workers. Taking machine bits shrinks the fleet.

Strict order across machines? Not with independent clocks. Snowflake is k-sortable within skew; strict order needs one sequencer per stream.

How is Instagram different? 41 / 13 / 10 minted per shard in Postgres, so the shard in the key routes reads.

Two datacenters? Split machine bits and run a registry per datacenter. Uniqueness holds; order is approximate.

Is a mint lock slow? In real CPython the mint path takes a threading.Lock around the clock read and shifts. It is short, but its cost depends on the runtime and contention, so measure rather than assume.

Try it live

Build the generator yourself in the Snowflake ID generator problem: compose and decompose IDs in the browser compiler, with the clock guard included.

The URL Shortener problem also needs unique codes; this guide is its distributed version. For the round itself, read what to expect in a low-level design round.

• Snowflake ID generator problem
• URL Shortener problem
• What to expect in an LLD round

45-minute pacing

A schedule that leaves time for deep dives.