Section 5: The Resize That Moves Everything - Partitioning: Consistent Hashing & the Ring

Executive Summary: This section answers the question Section 4 left hanging: when a client calls get(cart:8842), which of 64 nodes owns that key? We start where weak candidates end — with mod-N hashing — and compute its catastrophic failure at resize. From that failure we derive the consistent-hashing ring, fix the ring's own two flaws with virtual nodes, build the preference list (including the subtle same-node bug that trips real implementations), and walk a node join end to end with real data-movement numbers. We close by defending the choice against range partitioning and naming when that verdict flips.

The fleet from Section 3 exists: 64 commodity nodes, 300TB on disk, roughly 100 billion keys. The interviewer points at your API box and asks the question that separates the Single-Node Thinker from everyone else: "A client calls get(cart:8842). Which machine answers?"

Start With the Obvious Answer, and Kill It With Arithmetic

Every candidate's first instinct is correct for a static world: hash(key) mod 64. Deterministic, stateless, perfectly balanced. So say it aloud — and then do what the Paper Reciter never does: compute why it dies.

Section 3 warned that throughput, not storage, is our binding constraint — growth is not hypothetical; we will add node 65. The moment we do, every key's home becomes hash(key) mod 65. A key keeps its old home only when hash(k) mod 64 happens to equal hash(k) mod 65 — and for a good hash, that coincidence occurs for roughly 1 in 65 keys, about 1.5%. The other ~98.5% of keys change owners. That is ~295TB of our 300TB replicated dataset in motion, saturating every disk and NIC in the fleet, trashing the p99 ≤ 10ms read SLO for hours — because we added one machine. Mira's pager does not survive that deploy.

Key Insight: Mod-N doesn't fail because the math is wrong; it fails because the modulus couples every key's placement to the total node count. The fix is to make placement a property of the keyspace itself, so membership changes touch only the keys adjacent to the change. That reframing — decouple placement from fleet size — is the entire idea of consistent hashing, and deriving it beats naming it.

Quick check before moving on: