Scaling Data · lesson 4 of 7 · about 30 min
How to give every row, order or message an ID across many machines: why auto-increment stops working, how likely random IDs are to collide, what random IDs do to a database index, how a real Snowflake generator is built from time, worker and sequence, how the options compare, and what happens when a clock steps backwards. Tap any for a plain-language card.
The problem
The standard patch is to give each database a different offset and step: with 4 databases, one counts 1, 5, 9, ..., another 2, 6, 10, ... Nothing collides, but you have traded a problem for others. Adding a fifth database means re-configuring all of them. IDs are no longer in time order (the busier database races ahead). And the counter must live in a database, so every new row needs a trip to it.
A last, quieter problem: counters leak. If order #10000 arrives on Monday and order #10500 the next Monday, any customer or competitor can work out your sales: 500 a week, about 71 a day. Sequential IDs in URLs also invite people to try the next number.
Try 4 databases, naive: about half the rows get an ID someone else already has. Then switch to stepped IDs and check the ordering.
4 counters all starting at 1: 520 of 1,000 rows share an ID with another row (only 480 IDs are unique). This is a data-corruption bug, not a performance issue.
…a week after seeing #10,000. From two numbers anyone infers 500 orders a week: about 71 a day. (1,000 seeded inserts spread unevenly over the databases.)
Random IDs
So 32-bit random IDs collide after only tens of thousands (hopeless). 64 bits last until about 5 billion. 122 bits last until about 2.7 × 1018 IDs, a number so large that at a million new IDs a second you would wait roughly 86,000 years for a 50% chance. For practical purposes UUID v4 never collides; its drawbacks are elsewhere (size, and what it does to an index, next scene).
Try 64-bit with a trillion IDs: certain collision. Then UUID v4 with the same trillion: about one in ten trillion.
The chance of any duplicate among 10^12 IDs is 1 in 1.1 × 10^13. Safe in practice: a hardware fault is far more likely than this.
Computed from the exact birthday formula 1 − e^(−n(n−1) ÷ 2^(b+1)). UUID v4 has 122 random bits, because 6 of its 128 bits fix the version and variant.
IDs and the index
The simulation inserts 20,000 keys into the leaf level of a real B-tree model: the number of pages and how full they end up, and the number of distinct pages the last 100 inserts touched, which is how much of the index must be hot in memory. Then set how much of the index fits in the buffer pool and see how many disk reads per 1,000 inserts that implies. The effect is mild on a small table and brutal on one that no longer fits in RAM.
Compare Random with Auto-increment on the pages touched, then shrink the buffer pool to 5%.
Distinct index pages touched by the last 100 inserts.
Random keys: 279 pages (40% more than sequential), only 72% full, and the last 100 inserts touched 83 different pages. With 20% of the index in memory, about 800 of every 1,000 inserts must first read a page from disk.
Computed from a B-tree leaf-level model (20,000 inserts, seeded). The disk-read estimate assumes inserts into the hot edge are cached and random ones hit the cache in proportion to the share of the index in memory.
Snowflake
The bit budget is a design choice. 41 bits of milliseconds last 241 ms ≈ 69.7 years from the start date. The remaining 22 bits are split between workers and the sequence: more worker bits means more machines, fewer sequence bits means fewer IDs per millisecond each. Twitter's original split was 10 and 12; slide it and see what each setting allows. This page runs a real generator with 64-bit integers (BigInt) and decodes the results.
Mint a few IDs, then mint 5,000 in one go with 12 sequence bits to see the generator borrow milliseconds.
Worker 3 can mint 4,096 IDs in any one millisecond (4.1M a second), all unique and increasing. The current simulated time is millisecond 34560123456 after the epoch.
Real 64-bit arithmetic. The epoch (1 Jan 2024) is an illustrative custom start; Twitter used its own. The clock here only moves when you press “Next millisecond”.
The options
The time-first random schemes have a small risk the pure random ones do not: two IDs minted in the same millisecond must differ by their random part alone (74 random bits in UUID v7, 80 in ULID). The first slider shows how likely a clash is inside one millisecond at your system's rate. The second shows the hi/lo trade: the bigger the block, the fewer trips to the counter, and the more IDs wasted when a server restarts holding an unused block.
Even at a million IDs per millisecond the in-millisecond risk is tiny. The practical differences are size, ordering and who must coordinate.
| Scheme | Size | Sorts by time | At your rate |
|---|---|---|---|
| DB auto-increment needs one counter | 32 or 64 bit | yes (one DB) | every ID is a trip to the DB: 10M/s |
| Hi/lo blocks central counter, local hand-out | 64 bit | roughly | 10K counter calls/s; a restart wastes up to 1,000 IDs |
| UUID v4 no coordination | 128 bit | no | clash over all time: practically 0 (122 random bits) |
| UUID v7 time + random | 128 bit | yes | clash in one ms: 1 in 3.8 × 10^14 |
| ULID time + random | 128 bit | yes | clash in one ms: 1 in 2.4 × 10^16 |
| Snowflake time + worker + sequence | 64 bit | yes | never, if each worker mints at most 4,096 per ms (2.44 workers needed at this rate) |
At 10K IDs per millisecond: Snowflake needs at least 3 workers and is collision-free by construction; UUID v7 risks 1 in 3.8 × 10^14 of a clash inside any single millisecond; a hi/lo block of 1,000 turns 10M IDs a second into 10K counter calls.
Collision probabilities are the exact birthday formula over the random bits (UUID v7: 74, ULID: 80). Snowflake sequence limit: 4,096 per worker per millisecond (12 bits).
Pick the ID scheme
Each scheme is right somewhere. Read the situation, then choose the cheapest ID that does the job. Each answer is worth 20 XP.
Ask: who creates the ID? Must it sort by time? Must it be unguessable?
An internal admin tool on one Postgres database with a single writer. The IDs are never shown outside.
Tip: press 1 to 3 to answer, Enter for the next one.
Who lives by this
Four real ID schemes and what their authors have written about them.
time + worker + sequence → 64-bit id
Twitter open-sourced Snowflake in 2010 to generate unique IDs for tweets across many machines without a central counter. An ID is 64 bits: a 41-bit millisecond timestamp, a 10-bit machine number and a 12-bit sequence, so a worker can mint up to 4,096 IDs per millisecond, and IDs are roughly sorted by time. Its generator refuses to issue IDs if the clock moves backwards.
ms timestamp + shard id + sequence → bigint
Instagram's engineering blog describes generating 64-bit IDs inside each PostgreSQL shard with a PL/pgSQL function: 41 bits of milliseconds since a custom epoch, 13 bits for the logical shard number and 10 bits from a per-shard sequence, up to 1,024 IDs per shard per millisecond. The shard number inside the ID tells you where the row lives.
app → one of two MySQL ticket servers → odd or even id
Flickr's 2010 write-up of its ticket servers describes two dedicated MySQL databases whose only job is to issue 64-bit IDs from a one-row table, one handing out odd numbers and the other even, with the application alternating between them. Simple, small IDs, and an extra pair of services to keep running.
42-bit time + 5 worker + 5 process + 12 increment
Discord's developer documentation states that its IDs are Snowflakes: a 42-bit timestamp counted from the first millisecond of 2015, a 5-bit internal worker, a 5-bit internal process and a 12-bit increment. Because the creation time is inside the ID, anyone can read when a message, user or channel was created from its ID alone.
Interview angle
Six questions, each worth 20 XP. “How do you generate unique IDs in a distributed system?” is a staple of design interviews (it is the first step of the URL shortener and every feed or chat design).
Mention the requirements first (sortable? size? unguessable?), then Snowflake's three parts, then the clock problem before you are asked.
Two databases each use AUTO_INCREMENT starting at 1 and you merge their rows. What goes wrong?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Three policies. Trust the clock: simple, and wrong. Refuse (what Twitter's original Snowflake did: throw an error): no duplicates, but the worker cannot mint IDs for as long as the clock is behind, so writes fail. Never go below the last timestamp: keep using the highest time seen, advancing the sequence, until real time catches up. IDs stay unique and ordered, at the price of slightly wrong timestamps for a moment.
Here one worker mints IDs for 1,000 ms; at ms 400 its clock is set back.
Leave “Trust the clock” on with 100 ms back and 5 IDs per ms, then switch to the other two.
| Policy | Duplicates | Refused | Out of order |
|---|---|---|---|
| Trust the clock | 500 | 0 | 1 |
| Refuse until it catches up | 0 | 495 | 0 |
| Never go below the last timestamp | 0 | 0 | 0 |
After the clock stepped back 100 ms, the worker re-minted the same millisecond values and produced 500 duplicate IDs (5 per ms × 100 ms). Each is a primary-key conflict or, worse, two rows silently overwriting one another.
A real Snowflake generator (64-bit arithmetic) run for 1,000 ms per setting. Duplicates are counted by comparing every ID to all earlier ones.
Where to go next