Aliases: Hash Ring
Consistent Hashing
A hashing scheme where adding or removing a node reshuffles only a small fraction of keys — the distribution primitive behind sharded databases, caches, and CDNs.
What is consistent hashing?
Consistent hashing solves a specific, painful problem: how to distribute keys across N nodes such that changing N doesn’t reshuffle almost everything. Naive hash(key) % N distributes evenly — but change N (add or remove a node) and the modulus changes for nearly every key, forcing a near-total redistribution: catastrophic for a sharded database or a distributed cache (every cache miss at once → database meltdown). Consistent hashing arranges nodes and keys on a conceptual ring; each key belongs to the next node clockwise, so adding or removing a node only reassigns the keys in that node’s arc — roughly 1/N of keys move, not all of them.
Why it’s foundational infrastructure
This “minimal disruption on membership change” property is exactly what elastic distributed systems need, so consistent hashing (or a descendant) sits under a remarkable amount of infrastructure: Cassandra and DynamoDB partition data with it, distributed caches use it to spread keys across nodes without mass invalidation on scale events, load balancers use it for session stickiness, and CDNs and anycast-adjacent systems use it to map content to edge caches. Whenever a system scales nodes up and down without reshuffling all its data, consistent hashing (or rendezvous hashing, its cousin) is usually why.
Virtual nodes — the fix for uneven load
Plain consistent hashing has a flaw: with few nodes, the ring arcs are uneven, so load is lopsided, and losing one node dumps all its keys onto a single neighbor. The universal fix is virtual nodes — each physical node claims many small arcs scattered around the ring, so load evens out and a departing node’s keys redistribute across many survivors rather than crushing one. Every production implementation (Cassandra’s vnodes, Dynamo-style systems) uses this; it’s what makes consistent hashing practical rather than merely elegant.
What people get wrong
- Plain modulo hashing for distributed caches — then watching a single node addition invalidate the whole cache and stampede the database.
- Skipping virtual nodes: raw consistent hashing gives lumpy load and dangerous single-neighbor failover.
- Assuming it balances perfectly — it balances statistically; hot keys (one popular item) still need separate handling.
Primary source: Consistent Hashing and Random Trees (Karger et al., 1997)
Historical figures and technical concepts for informational purposes only. Not technical, professional, legal, or financial advice. Sources: Official Documentation.