Layer 3 · Go deeper · 11 min
Go deeper
Size it, build it, then make the calls an interviewer will push you on.
Back of the envelope
Size it up
Tap through each step of the arithmetic.
How long do 41 bits of milliseconds last?
How many ID service pods does each region need?
What does a 64-bit ID save over a 128-bit UUID?
Build-up · 5 steps
Build the high-level design
One functional requirement at a time, ending with a design that works in every region but isn’t yet hardened against bad clocks or zombie pods.
Step 1 of 5
Get an ID, or a batch
Each ID service pod builds IDs from its clock, its worker number and a counter, all in memory with no call to anyone. For now, worker numbers come from a config file.
6 interview moments
You’re the candidate
The interviewer pushes on the hard parts. Pick an approach and see how it holds up.
Deep dive 1 of 6
Interviewer
“Every team needs IDs, 2M a second at peak, unique forever, roughly sorted by time, and they must fit a
bigint. Which scheme?”Your move. Pick an approach:
Deep dive 2 of 6
Interviewer
“Pods autoscale, restart and reschedule all day. How do you make sure no two live generators ever share a worker number?”
Your move. Pick an approach:
Deep dive 3 of 6
Interviewer
“The time daemon finds a pod’s clock 25 ms fast and steps it back. What does the generator do?”
Your move. Pick an approach:
Deep dive 4 of 6
Interviewer
“About 3,000 application pods across the company need IDs. Where do the generator’s few dozen lines run?”
Your move. Pick an approach:
Deep dive 5 of 6
Interviewer
“You move the messages table to Spanner, keyed by Snowflake ID. One server takes every insert while the rest sit idle. What do you do?”
In PostgreSQL, the same rising IDs append cheaply at the right edge of the B-tree.
Your move. Pick an approach:
Deep dive 6 of 6
Interviewer
“Order pages put the ID in the URL:
/orders/108421920055775237. Is that fine, and if not, what do you do?”Your move. Pick an approach:
Build-up · 7 steps
Follow one order through it
The hot path is an application, a service and one ID pod’s memory. The registry and the time service sit beside it, not on it.
Step 1 of 7
Lease
A starting pod claims a free worker number in its region’s etcd by compare-and-swap, takes the previous valid_until as its floor, and gets a lease that runs 10 minutes ahead.