BOOKS DEEP-READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 7
System Design Interview Vol 1 · Ch 7 · Alex Xu · 2020
Every order you place and every message you send needs a number — one that is never handed out twice, and ideally one you can glance at to tell what came first. On a single machine this is a non-problem: the database just counts up from 1. This chapter is about what happens when the back end becomes a few hundred machines, why "just count up by 1" collapses, and how to rebuild it.
Think of a ticket dispenser in a chain of shops. With one shop, the dispenser counts 1, 2, 3 and never gets it wrong. Open 32 branches and the trouble starts: if every branch counts from 1, the country now has 32 different customers holding ticket "3", and the clerk has no idea which one to serve.
One: make every branch phone head office for a number. No duplicates — but every single ticket now costs a phone call, which is slow, and if head office loses power, all 32 branches stop dispensing.
Two: let each branch pick a very long random string. Collisions become vanishingly unlikely, but the string is long and tells you nothing about order — you cannot look at two of them and say which came first.
Three: have each branch count in steps. Branch 1 counts 1, 33, 65…; branch 2 counts 2, 34, 66…. Clever — until you open a new branch or close one, at which point the whole country has to be renumbered.
Twitter's answer was to stop asking anyone for a number and instead assemble one on the spot out of three things that are already unique: the first piece records what time it is, down to the millisecond; the middle piece records which branch I am; the last piece records how many I have handed out during this particular millisecond.
Put the three together and nobody has to ask anybody: different millisecond, the first piece differs; same millisecond but different branch, the second differs; same branch and millisecond, the third differs. And because time sits at the front, sorting the numbers from small to large is roughly sorting them from earliest to latest — the ordering comes for free. This dispenser can hand out 4,096 tickets per millisecond per branch, and the scheme lasts 69 years.
The whole thing rests on every machine's clock moving forward: if one machine's time gets nudged backwards, it will live that millisecond over again and hand out numbers it has already given away.
The hard part of distributed IDs was never "don't repeat" — any long random number does that. The hard part is being unique and short and visibly ordered, without machines ever talking to each other. The answer is to cut the ID into time + who I am + which one this instant, trading a clock for a conversation.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
You think the hard part of distributed unique IDs is avoiding duplicates. In fact uniqueness is the easiest of the four constraints — a long enough random number settles it. The hard part is satisfying all four at once: unique, short enough to fit in 64 bits, roughly ordered by time, and generated without talking to any other machine. This chapter puts four approaches on the table, eliminates them one by one, and lands on Twitter's Snowflake: treat 64 bits as a budget and spend it on timestamp + machine id + sequence. Ordering comes free from putting the timestamp in the high bits; uniqueness comes from "same machine, same millisecond, different sequence"; the price is that correctness now rests entirely on the machine's clock.
9.2×10¹⁸. "How do I spend these 64 zeroes and ones" is the design question of this chapter.09c93e62-50b4-468d-bf8a-c07e1040bfb2.This is the fourth case study of Vol 1's Part II. It follows Ch5 (consistent hashing) and Ch6 (key-value store) — those two answer "which machine does this row live on", while this one answers "what is this row called" — and all three share one spine: getting something done without a central coordinator. It sets up Ch8, the URL shortener, which takes the ID produced here and base62-encodes it. In the real world this is order numbers, message ids, feed item ids, trace ids — anywhere you still want one global primary key after sharding the database.
The requirements pinned down during clarification are five: unique, numeric only, fits in 64 bits, ordered by date, 10,000 IDs per second. Those five narrow the answer space brutally, and they are exactly what knocks out the two most obvious candidates.
Why auto_increment fails. That counter is private state inside one database instance. Shard the database and both shards start at 1, so order number 10001 exists twice. Left unsolved: a primary key collision means the later write silently overwrites the earlier one, and two customers' orders point at one row — an error that raises no alarm and simply loses data.
Why not just use UUIDs? The collision risk really is negligible — with v4's 122 random bits you need roughly 10¹⁸ of them before there is a 50% chance of one clash. But UUIDs violate the other three requirements: 128 bits not 64, hyphenated not numeric, and completely unordered. That last one is the expensive part: a random primary key has no temporal locality, so every insert stabs a random spot in the B-tree, triggering page splits and random I/O. This is not purism — the measured gap in insert throughput is an order of magnitude (see RFC 9562's own words under "In real systems" below).
① Multi-master replication. Let k databases all auto-increment, but set the step to k with staggered starts: server 1 counts 1, 4, 7…; server 2 counts 2, 5, 8…. It works, and it is unique. It dies on elasticity: adding one machine forces you to re-plan every server's step and offset, and across data centres the numeric order of IDs has nothing to do with real time. Fundamentally it is still using the database as the dispenser, so the write ceiling never moved.
② UUID. Every machine generates independently — zero coordination, zero single point. It is the only option here that never communicates, and conceptually it is closest to the right answer. But it throws away "short" and "ordered" entirely.
③ Ticket server. Flickr's approach: one dedicated MySQL box that does nothing but hold a single auto_increment column, and everyone comes to it for a number. The IDs are short and strictly increasing, and the implementation is a few dozen lines. It dies on being a single point: when it stops, nothing in the site can mint an ID; make it an active/standby pair and you are back to "how do these two not collide". It also spends one network round trip per ID, putting milliseconds of latency on every checkout.
④ Snowflake. Ask nobody. Assemble an ID from three facts that are already unique on their own: the current instant, who I am, and how far I have counted this instant.
Each field answers a concrete question. The sign bit stays 0 because a long is signed in languages like Java, and flipping the top bit turns your primary key negative. The 41-bit millisecond timestamp counts not from the Unix epoch but from a custom epoch (Twitter used 1288834974657, i.e. 2010-11-04), which reclaims the four decades before the service launched — 2⁴¹ milliseconds is only 69.7 years. The 5+5 machine bits cap you at 32 data centres × 32 machines = 1024 nodes, and they are assigned statically at startup and never changed at runtime, because renumbering mid-flight risks colliding with someone else. The 12-bit sequence increments within one machine within one millisecond, tops out at 4096, and resets on the next millisecond; if you really exhaust it, you spin until the clock ticks.
The key insight is one line: the timestamp sits in the high bits, so sorting by numeric value is approximately sorting by generation time — the "ordered" requirement is satisfied for free, without a single network message. But state it accurately: the result is only k-sorted. Two machines minting IDs in the same millisecond are ordered by machine id, which has nothing to do with what actually happened first. Twitter's own README promises exactly this: k-sorted within one second.
Here is the layer worth taking away: 1 / 41 / 10 / 12 is not a standard answer, it is a budget sheet. Timestamp bits buy service lifetime, machine bits buy cluster size, sequence bits buy per-node peak rate — and the three always sum to 63, so any bit you give one is taken from the others.
Do the arithmetic: 12 sequence bits mean a theoretical ceiling of 4096 × 1000 = 4.096 million IDs per second per node, while the chapter's stated requirement is 10,000 per second — a factor of 400 in slack. Anyone who copies 12 sequence bits verbatim is throwing away 8 bits. Move those 8 into the timestamp and the lifetime goes from 69 years to over ten thousand; move them into the machine id and the cluster ceiling goes from 1,024 nodes to 262,144. Being able to do that arithmetic in an interview is worth far more than reciting the layout.
The ticket server does not have to be discarded — its fatal flaw is "one round trip per ID", and that flaw can be treated on its own. The segment (number-range) model switches from retail to wholesale: the application claims a whole range [8001, 9000] from the database in one call, keeps it in local memory, and mints the next 999 IDs in-process before coming back for another range.
State the cost honestly: a restart throws away the unused half of the range, leaving gaps in the ID sequence; and once several instances hold ranges concurrently, IDs are ordered only within an instance and unordered across them — the "ordered" requirement has been quietly discounted.
Snowflake's uniqueness proof is one sentence: "within one machine within one millisecond the sequence never repeats, and across milliseconds the timestamp differs." That sentence only holds while the clock moves forward. NTP corrections, leap seconds, VM clock drift and someone setting the time by hand can all push a local clock backwards — and the moment it does, the machine relives a millisecond it has already used, with the sequence back at 0, and emits an ID identical to one it minted before.
Three engineering responses exist, and they point in different directions: ① detect the rollback and refuse to mint, throwing an exception (better unavailable than wrong); ② if the rollback is tiny, spin and wait until real time catches up; ③ persist "the largest timestamp this machine has used" outside the process (Meituan's Leaf records it in ZooKeeper) so a restart cannot walk backwards. Note what option ① implies: when the clock misbehaves, Snowflake sacrifices availability to preserve correctness — the exact opposite of the leaderless key-value store in Ch6, which writes first and converges later.
Table 1 · Five ways to mint an ID, and when each one is right
| Approach | Mechanism in one line | Shape | Time-ordered | Coordination | Main cost |
|---|---|---|---|---|---|
| Multi-master | k databases auto-increment with step k, staggered starts | 64-bit numeric | No (unordered across shards) | None at runtime (but statically planned) | Adding or removing a node forces a full renumbering; write ceiling still the DB |
| UUID v4 | each machine draws 122 random bits | 128-bit, hyphenated | No | None at all | Twice as long, not numeric; random keys wreck index locality |
| Ticket server | one dedicated MySQL running auto_increment | 64-bit numeric | Strictly increasing | one round trip per ID | SPOF plus milliseconds of latency on every request |
| Segment model | claim 1000 at a time, mint locally from memory | 64-bit numeric | Within an instance | one round trip per 1000 | Restart drops half a range (gaps); unordered across instances |
| Snowflake | assemble timestamp + machine id + sequence on the spot | 64-bit numeric | k-sorted | None when minting (moved to machine-id assignment at startup) | Correctness rests on the clock; machine ids need managing; 69-year lifetime |
Table 2 · The same 63 bits, budgeted three different ways (defaults from each project's public repository)
| Implementation | Time bits | Machine bits | Sequence bits | Lifetime | Cluster ceiling | Per-node peak |
|---|---|---|---|---|---|---|
| Twitter Snowflake | 41 (ms) | 10 | 12 | ≈ 69 years | 1,024 nodes | 4.096M/sec |
| Sony Sonyflake | 39 (10 ms units) | 16 | 8 | ≈ 174 years | 65,536 nodes | 25,600/sec |
| Baidu UidGenerator | 28 (seconds) | 22 | 13 | ≈ 8.5 years | 4.19M nodes | 8,192/sec |
Three companies took the same 64 bits and re-budgeted them for their own business: Sony wanted more machines and a longer life, so it cut per-node peak rate to about 1/160; Baidu runs containers, where instances come and go constantly, so it spent 22 bits on worker ids and accepted a lifetime of 8.5 years and a periodic epoch change. That table is the chapter's real answer: the bit split is a design parameter, not a constant.
Snowflake is the shortest, most teachable example of coordination-free design. It demonstrates a general move: when you need global uniqueness but not global communication, decompose "globally unique" into several facts that are already locally unique and concatenate them. The same move shows up in idempotency keys, distributed-tracing trace ids and object-storage key naming.
Its fingerprints are everywhere in production today: every Discord object id is a snowflake (42-bit timestamp + 5-bit worker + 5-bit process + 12-bit increment, with the epoch set at 2015), and MongoDB's ObjectId is the same idea in 12 bytes (4-byte second-resolution timestamp + 5-byte per-process random value + 3-byte incrementing counter). The standardisation step matters more: UUIDv7 landed in RFC 9562 in 2024, turning "put the timestamp in the high bits" from a field trick into an industry standard, and PostgreSQL 18 ships uuidv7() built in — still at the price of 128 bits rather than 64.
2¹⁶ rather than 2¹⁰ machines, at the cost of only 256 ids per 10 ms — direct confirmation that the bit split is an adjustable budget. sony/sonyflake ↗uuidv7() and skip the whole home-built generator plus machine-id management, at the cost of 128 bits instead of 64. "You must build your own Snowflake" is no longer the default answer.1. The real problem is not "no duplicates" but unique + short (64 bits) + time-ordered + coordination-free, all at once. The four constraints fight, so any answer is a trade-off.
2. auto_increment dies because the counter is private state in one database instance; UUID survives that but breaks the other three requirements, above all by destroying B-tree index locality.
3. The ticket server (Flickr) is short and strictly increasing but dies on a single point plus one round trip per ID; the segment model cuts the round trips to 1/1000 and recovers half of it, paying with dropped ranges and no cross-instance order.
4. Snowflake = 1 sign + 41 timestamp + 5 datacenter + 5 machine + 12 sequence: 69 years, 1,024 nodes, 4,096 ids per machine per millisecond.
5. All the ordering comes from the timestamp occupying the high bits, at zero communication cost — but it is only k-sorted, never strictly monotonic.
6. The bit split is a budget, not a constant: time bits buy lifetime, machine bits buy scale, sequence bits buy peak rate, and the three share 63 bits. Sony (39/16/8, 174 years) and Baidu (28/22/13, 4.19M nodes) are two different answers.
7. The deepest weakness is clock rollback: push the clock back and the machine replays a millisecond with a zeroed sequence, emitting identical IDs. The responses are refuse-to-mint, spin-and-wait, or persist the high-water timestamp — the first being availability traded for correctness.
8. Coordination did not disappear; it moved from every mint to assigning machine ids at startup — a bill that got more expensive with containers, and the one most often ignored.
9. The general move: decompose global uniqueness into locally unique facts and concatenate. UUIDv7 in RFC 9562 (2024) and uuidv7() in PostgreSQL 18 show that instinct becoming a standard.