Consistent Hashing

Overview

Consistent hashing is a technique for distributing keys across a changing set of nodes so that adding or removing a node remaps only a small fraction of keys instead of nearly all of them. It maps both keys and nodes onto the same circular hash space and assigns each key to the next node found clockwise.

🧠 Mental model: Musical chairs where removing one chair only displaces the person in that seat - everyone else stays put. Compare that to normal chairs-in-a-row, where removing one shifts everyone down.

Key Concepts

Picture a ring numbered from 0 to 2^32-1. Each node is hashed to a point on the ring, and each key is hashed to a point too. A key belongs to the first node encountered when moving clockwise from the key's position.

When a node is added or removed, only the keys between it and its predecessor on the ring change ownership, roughly K/N keys for K keys and N nodes, rather than all K. A refinement called virtual nodes hashes each physical node to many points on the ring, which smooths out uneven key distribution and lets heterogeneous machines carry proportional load.

Approach	Keys remapped when a node is added	Load balance
Modulo hashing (`hash % N`)	Almost all keys	Even, but unstable under change
Consistent hashing	About `K/N` keys	Uneven without virtual nodes
Consistent hashing + virtual nodes	About `K/N` keys	Even and tunable per node

Trade-offs

Consistent hashing dramatically reduces churn during scaling, but a plain ring can distribute keys unevenly because node positions are random. Virtual nodes fix the imbalance at the cost of more metadata and bookkeeping per node. The technique also does not, by itself, replicate data; production systems place each key on the next few distinct nodes clockwise to add redundancy.

Interview Tips

Contrast it with hash % N first; the pain of modulo rehashing motivates the whole idea.
Mention virtual nodes as the standard fix for skew and for weighting larger machines.
State the headline result: only about K/N keys move when the cluster size changes by one.
Note that replication is layered on top by walking clockwise to the next distinct nodes.

Summary

Consistent hashing maps keys and nodes onto one ring and assigns each key to the next node clockwise.
Adding or removing a node remaps only about K/N keys instead of nearly all of them.
Virtual nodes spread each physical node across many ring points to balance load.
It underpins distributed caches, partitioned datastores, and key-pinning load balancers.
The ring itself handles placement; replication is added by using the next distinct nodes clockwise.