Layer 3 · Go deeper · 9 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.
With one token each, how overloaded is the unluckiest of 10 servers?
How big is a ring of 100 servers with 256 tokens each?
Build-up · 5 steps
Put servers and keys on one ring
Four servers, four keys and one clockwise rule. Then add a server, or remove one, and watch exactly which keys move.
Step 1 of 5
Bend the hash space
Hash outputs from 0 to 2⁶⁴ − 1 become positions on a circle, so the largest value wraps to 0. Each server sits at the hash of its name, like hash("cache-7").
4 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 4
Interviewer
“Your four-node cache must grow to five before a Big Billion Days–style sale. How do you map keys to nodes?”
Your move. Pick an approach:
Deep dive 2 of 4
Interviewer
“Your busiest node must stay within your headroom. How many virtual nodes does each server get?”
Your move. Pick an approach:
Deep dive 3 of 4
Interviewer
“A session node restarts: up to 500,000 sessions look up about 5 guilds each, 2.5 million ring lookups. Where does each read the ring?”
Discord maps each guild to a node with a consistent hash ring.
Your move. Pick an approach:
Deep dive 4 of 4
Interviewer
“During an IPL final, the live-score key takes 10% of all requests and its node is overloaded. What do you do?”
Your move. Pick an approach:
Build-up · 5 steps
Place three copies on the ring
Four servers with two tokens each, and N = 3 copies of key k. Walk clockwise and count servers, not tokens.
Step 1 of 5
Give each server two tokens
Virtual nodes. Each server hashes several names, like node-3#0 and node-3#1, and owns several small arcs. Here four servers have two tokens each, interleaved around the ring.