How Consistent Hashing Works
AdvancedConsistent hashing is a technique for distributing keys across a changing set of servers so that adding or removing a server moves as few keys as possible. Naive modulo hashing (hash(key) % N) reshuffles almost everything when N changes — catastrophic for a cache. Consistent hashing places both servers and keys on a ring; each key belongs to the next server clockwise. When a server joins or leaves, only its neighbouring keys move. It underpins distributed caches, Cassandra, and DynamoDB.
Think of a clock face with servers at hour marks
Imagine a clock face. Servers sit at certain hour positions, and each task is placed at its own position; the task is handled by the next server clockwise. If a server at 3 o clock leaves, only the tasks between 12 and 3 move to the next server — everything else stays put. With plain modulo hashing, removing one server is like renumbering the whole clock, sending every task somewhere new. The ring keeps disruption local.
Step by Step
Key Concepts
The Hash Ring
A circular hash space where both servers and keys are placed. A key is owned by the first server encountered clockwise from the key position.
Minimal Reshuffling
The defining benefit: when the server set changes, only about K/N keys (K keys, N servers) are remapped, versus nearly all keys with modulo hashing.
Virtual Nodes
Multiple ring positions per physical server. They even out key distribution and load, and make the impact of adding/removing a server smoother and more balanced.
Hotspot Avoidance
Without virtual nodes, servers next to a large arc get overloaded. Virtual nodes spread each server responsibility across the ring, preventing uneven hotspots.
Key Facts
- Consistent hashing turns a server change from "rehash everything" into "move one server share of keys" — essential for caches and stateful clusters.
- It powers real systems: Amazon DynamoDB, Apache Cassandra, and distributed caches like memcached client libraries.
- Virtual nodes are what make it practical — a handful of physical servers with hundreds of virtual points achieves near-uniform distribution.
Real-World Applications
A distributed cache cluster
When a cache node fails, consistent hashing ensures only that node keys are lost and redistributed, keeping the vast majority of the cache warm instead of triggering a cluster-wide miss storm.
Partitioning a database like Cassandra
Cassandra places nodes on a token ring and assigns each row to a node by consistent hashing, so scaling the cluster up or down moves only a slice of data rather than the whole dataset.
Frequently Asked Questions
Why not just use hash(key) % N to distribute keys?
Because when N changes — a server is added or fails — the modulo result changes for almost every key, remapping nearly all keys to different servers at once. For a cache, that means a near-total miss storm; for a database, a massive data migration. Consistent hashing avoids this by moving only a small fraction of keys.
How does consistent hashing minimise key movement?
Servers and keys are placed on a ring, and each key is owned by the next server clockwise. When a server is added or removed, only the keys in its immediate arc are reassigned — on average K/N keys — while every other key stays with the same server.
What are virtual nodes and why are they needed?
Virtual nodes give each physical server many positions on the ring instead of one. Without them, key distribution and load can be very uneven, and removing a server dumps all its keys onto a single neighbour. Virtual nodes spread each server responsibility across the ring for balanced load and smoother rebalancing.
Where is consistent hashing used in practice?
It underpins distributed caches (memcached client sharding), and databases like Amazon DynamoDB and Apache Cassandra, which use a hash/token ring to assign data to nodes so the cluster can scale up or down while moving only a fraction of the data.