STANDARDwalkthrough
Ring Placement with Virtual Nodes
500 nodes hold 100 billion keys. Which node owns which key, and what happens when node 217 dies on a Tuesday?
Adding one node changes the modulus and remaps nearly every key in the cluster, a full-cluster reshuffle to add capacity. Option two: a central lookup table mapping key ranges to nodes.
“Option one: modulo placement: .”
Now placement needs a strongly consistent metadata service on the critical path of every request (this is the direction CockroachDB-style systems take, at real complexity cost). Option three: consistent hashing: hash both keys and nodes onto a ring; a key belongs to the first node clockwise from its hash.
Adding or removing a node remaps only 1/N of the keys, the arc it gains or loses. Raw rings distribute badly (a 500-node ring can see 250%+ load variance), so each physical node projects 256 virtual nodes onto the ring, smoothing variance to under 10% and letting a beefier machine carry more vnodes.
This is the same machinery as our consistent-hashing topic, applied: the KV store's replication rides directly on it. A key's preference list is the next N distinct physical nodes clockwise from its position, so replica placement falls out of the ring for free, no separate placement service.
The coordinator for a request is any node: it hashes the key, finds the preference list, and fans out. The trade-off: ring metadata must be gossiped and agreed (a joining node must not serve reads before it owns its arcs), and vnode counts are a tuning knob: more vnodes smooth load but grow the ring table and slow rebalancing bookkeeping.
What if the interviewer asks: who moves the data when the ring changes? The arc's new owner streams it from the old owner in the background while the old owner keeps serving, then ownership flips atomically per arc.
Related concepts