Consistent Hashing Explained: Distributed Routing Without Hot Spots
When you add or remove a server from a cache cluster, you want to move as few keys as possible. Consistent hashing solves exactly this problem by placing both keys and servers on a circular ring, so membership changes only affect the keys adjacent to the changed node.
Published June 30, 2026The Problem with Naive Hashing
The simplest way to route a key to a server is server = hash(key) % n where n is the number of servers. This distributes keys evenly and is fast to compute. The problem appears the moment n changes.
If you have 3 servers and add a fourth, the formula changes from hash(key) % 3 to hash(key) % 4. A key that previously mapped to server 1 might now map to server 3. In a cache cluster, this means a cache miss for almost every key — because the right server for each key has changed. At scale, a sudden wave of cache misses can overwhelm the underlying database. This is a cache avalanche, and naive modular hashing makes every scaling event a potential incident.
How Consistent Hashing Works
- Define a ring: Imagine the output space of the hash function (say, 0 to 232 - 1) arranged as a circle rather than a line. The last position wraps around to connect with the first.
- Place servers on the ring: Hash each server identifier (by IP address or name) and place each server at the resulting position on the ring.
- Place keys on the ring: Hash each key and place it at the resulting position on the ring.
- Assign keys to servers: For each key, walk clockwise around the ring until you hit the first server. That server owns the key.
- Add a server: Hash the new server, place it on the ring. Only keys between the new server's predecessor and the new server's position need to move — on average, 1/n of total keys.
- Remove a server: The keys the removed server owned are reassigned to the next server clockwise. Again, only 1/n keys are affected.
This property — that adding or removing one node only displaces 1/n of keys — is what makes consistent hashing "consistent." In a 10-node cluster, adding one node moves roughly 10% of keys instead of nearly 100%.
Virtual Nodes: Solving Uneven Distribution
With only a few real servers, random placement on the ring can create uneven load. One server might end up responsible for 40% of the key space while another handles only 5%. Virtual nodes (vnodes) fix this by placing each physical server at multiple positions on the ring.
Instead of hashing "server1" to one ring position, hash "server1-0", "server1-1", ..., "server1-99" to 100 positions. The key space is divided into many small segments, and each server owns a random mix of them. With enough virtual nodes, the distribution converges on uniform regardless of how servers happen to hash.
Virtual nodes also make it easy to give higher-capacity servers more weight: a server with twice the capacity gets twice the virtual nodes and handles roughly twice the keys. Cassandra uses this mechanism to support heterogeneous hardware in the same ring.
Systems That Use Consistent Hashing
| System | How It Uses Consistent Hashing |
|---|---|
| Amazon DynamoDB | Partitions data across storage nodes; each item's partition key is hashed onto the ring to determine its node |
| Apache Cassandra | Uses a configurable partitioner (Murmur3 by default) to place rows on a token ring; virtual nodes are on by default |
| Memcached (client-side) | Client libraries like libketama use consistent hashing to route cache keys so adding a server does not invalidate the whole cache |
| CDN edge routing | Some CDN providers use ring-based routing to map content to edge nodes, minimizing object movement when edges are added or fail |
| Riak | Pioneered vnode-based consistent hashing; every node in the cluster participates in a fixed 160-position ring |
Conclusion
Consistent hashing trades a small amount of complexity in the routing layer for enormous stability when cluster membership changes. The ring abstraction is elegant: keys and servers share the same coordinate space, and the ownership rule (nearest server clockwise) is simple enough to explain in one sentence. Virtual nodes address the distribution skew that arises with small numbers of physical servers. Together, these two ideas underpin the data distribution layer of most modern distributed databases and cache systems.
When you see a distributed system that claims to add nodes without dropping cache hit rates or rebalancing all data, consistent hashing (or a closely related scheme) is almost certainly the mechanism underneath.