Consistent hashing

What it is

Consistent hashing maps both keys and servers onto a fixed ring (0 to 2⁶⁴−1); each key belongs to the first server clockwise from its hash. When a server joins or leaves, only the keys in the affected arc move — roughly K/N of them — instead of nearly everything, which is what hash mod N does: going from 10 to 11 servers remaps over 90% of keys, and against a cache that is a self-inflicted miss storm.

This is the canonical "do you know distributed systems" concept. It is the answer to "how do you add a cache or database node without a stampede", and it sits inside systems I can cite by name: DynamoDB, Cassandra, Memcached client libraries, Discord's guild routing, Akamai, and ring-hash load balancers. In a distributed cache or key-value store design, the interviewer is waiting for it.

Say this out loud

I'd place nodes on a consistent-hash ring with a few hundred virtual nodes each, so adding capacity moves about 1/N of the keys instead of reshuffling nearly all of them.

The picture

keys and nodes share one ring; each key belongs to the first node clockwise. when a node joins, only its arc moves — the coloured segments are ownership, the dots are keys.

The variants and when to pick each

The ring — only the affected arc moves

Hash servers onto the ring; hash each key and walk clockwise to the first server. A node joining claims one arc from its successor; a node leaving hands its arc to its successor. Either way the blast radius is ~1/N of the keyspace, versus (N−1)/N for mod-N.

For a cache tier this is the difference between a small dip in hit rate and the whole fleet missing at once while the database absorbs the stampede.

Trade-offThe naive ring buys minimal remapping but places nodes randomly, so arcs are uneven — some nodes run hot, and a dead node dumps its entire range on one unlucky successor.

Virtual nodes fix the lumpy ring

Give each physical server 100–1,000 points on the ring instead of one. Arcs average out (a few hundred vnodes gets load within a few per cent of even), a beefier server gets proportionally more vnodes, and when a node dies its load scatters across many successors instead of crushing one. Cassandra shipped 256 vnodes per node by default; newer versions use 16.

Trade-offVnodes multiply ring metadata and make range operations (repair, streaming) touch many small slices instead of one big one — cheap for caches, more operationally noticeable for databases.

Replication on the ring

Store each key on the next R distinct physical nodes clockwise — the preference list. This composes directly with quorum reads and writes: N replicas from the ring walk, W and R tuned per the consistency story. Skipping vnodes belonging to the same physical machine is the detail that shows I've thought about it — two replicas on one box is one failure away from zero.

Trade-offRing-walk replication is simple and decentralised, but a node's failure shifts read and write load onto its ring neighbours specifically — vnodes are what turn that from a hotspot into a smear.

Alternatives worth naming

Rendezvous (HRW) hashing: for each key pick the node with the highest hash(node, key) — no ring state, excellent for small clusters. Jump consistent hash (Google): no state at all, but nodes must be numbered, so it suits fixed pools. Redis Cluster pre-quantises the ring into 16,384 hash slots with explicit slot migration. Maglev builds a lookup table for load balancing. One sentence on any of these signals breadth; the ring plus vnodes remains my default answer.

Trade-offSimpler schemes shed the ring's bookkeeping but give up something each: rendezvous costs O(N) per lookup, jump hash can't name nodes, fixed slots make migration an explicit operation you now own.

Numbers worth memorising

mod-N, 10 → 11 servers	>90% of keys remap
Consistent hashing, same change	~1/11 ≈ 9% of keys remap
Virtual nodes per physical node	100–256 typical (Cassandra default 256, newer 16)
Load evenness with vnodes	a few hundred vnodes → within a few % of even
Ring space	2⁶⁴ common today (2¹⁶⁰ SHA-1 in the Dynamo paper)

Where the interviewer pushes

First push: "one node is still hot even with consistent hashing — why?" Because the skew is in the keys, not the ring: vnodes even out arc sizes, but a single celebrity key hashes to exactly one place no matter how the ring is drawn. The fixes live above the ring — replicate the hot key across several nodes and fan reads out, put a small local cache in front of the cache, or split the key (user:123#1..8). Saying "vnodes don't fix a hot key" unprompted is the differentiator.

Second push: "a node joins — what happens to the keys mid-flight?" For a cache, mostly nothing: the remapped arc goes cold and misses rebuild it from the source of truth — which is why I'd add nodes gradually rather than double the fleet at once. For a datastore, the new node must stream its arc from the old owner (range handoff); until handoff completes, reads for that range are served by the old owner or by both, and Cassandra-style systems mark the range as pending so quorums stay correct during the transfer.