Consistent Hashing

In technical terms

A key belongs to the first node clockwise from its hash. Without virtual nodes, real hash variance leaves some nodes overloaded, so each physical node publishes many ring positions (dozens to hundreds). Expected movement per membership change: roughly k/n keys, versus nearly all keys for plain modulo hashing.

Why it appears in interviews

Sharded cache and store questions probe it directly (“what moves when a node dies?”) because the alternative answer (rehash everything) is the failure mode that takes the fleet down with the node.

The common misconception

That it solves hot keys: a celebrity key lands on exactly one arc no matter how elegant the ring. Whale handling (sub-key splitting, read-through replicas, edge caches) is separate work. And that it is the same thing as consistent replication; one is placement, the other is agreement.

Trade-offs & when it hurts

Buys bounded rebalancing, easy joins, and per-key locality; costs ring-metadata indirection, more memory for virtual nodes, and no locality for range queries (that is range partitioning’s job). Alternatives: modulo hashing for fixed clusters, range partitioning with the hot-tail tax, directory-based routing with its hop cost.

How to show it in an interview

Lead with the failure you are avoiding: “With plain modulo, losing one of fifty nodes rehashes nearly every key. The whole cache goes cold at once. The ring moves about two percent, two hundred virtual nodes per physical node to even out the variance, and a whale key still needs its own plan.” The k/n sentence plus the hot-key caveat is the full mark.

Questions this concept earns

• Walk the rebalance when one of fifty nodes leaves. Exactly what moves and what gets served while it moves?
• Your ring is elegant but one node is on fire: why, and what is the fix?
• What metadata does every client need to route, and how stale can it be before the design breaks?

Related