Consistent Hashing Explained

Consistent hashing is the technique that lets a distributed cache or database add and remove servers without reshuffling nearly all of its data. It appears in Cassandra, DynamoDB, Memcached clients, Riak and most CDN routing layers, and it shows up in system design interviews whenever sharding is discussed.

In this article we will learn what consistent hashing is, why the obvious modulo approach falls apart the moment you add a server, how the hash ring works step by step, what problem virtual nodes solve, and where the technique is used in practice.

What is consistent hashing?

Why not just use modulo?

The obvious way to spread keys over n servers is:

server_index = hash(key) % number_of_servers

With four servers this works fine. Now add a fifth.

# Before: hash(key) % 4
# After:  hash(key) % 5

Every key whose hash modulo 4 differed from its hash modulo 5 now maps to a different server — which is roughly 80% of all keys. In a cache, that means an 80% miss rate and a stampede of traffic onto your database at exactly the moment you were trying to add capacity. In a database, it means moving 80% of your data across the network.

The pattern is brutal: modulo remaps (n-1)/n of keys, while consistent hashing remaps only 1/n.

How does the hash ring work?

Imagine the output range of your hash function — say 0 to 2³² − 1 — bent into a circle so the largest value sits next to zero.

Three steps:

1. Place the servers. Hash each server's identifier and place it at that position on the ring.
2. Place the keys. Hash each key the same way to get its position on the ring.
3. Assign ownership. Walk clockwise from the key's position; the first server you meet owns that key.

Now add a fourth server, D, landing at position 180. Only keys sitting between B at 120 and D at 180 change hands — they used to walk clockwise to C, and now they stop at D. Every other key on the ring is untouched.

Removing a server is the mirror image: its keys walk clockwise to the next server, and nothing else moves.

Why do we need virtual nodes?

The basic ring has a problem. With only a handful of servers hashed onto it, their positions are unlikely to be evenly spaced. One server can end up responsible for a 40% arc of the ring while another owns 10%.

Worse, when a server is removed, its entire arc transfers to a single neighbour, which can double that neighbour's load and cascade into a failure.

Virtual nodes fix both. Instead of hashing each server once, hash it many times with different suffixes:

def build_ring(servers, replicas=150):
    ring = {}
    for server in servers:
        for i in range(replicas):
            position = hash_fn(f"{server}#{i}")
            ring[position] = server
    return dict(sorted(ring.items()))

Each physical server now occupies 150 scattered positions around the ring. Two things improve:

• Distribution evens out. With 150 virtual nodes per server, the law of large numbers takes over and each server's total share converges close to its fair fraction.
• Removal spreads out. When a server leaves, its 150 arcs are inherited by many different neighbours rather than one, so no single server absorbs the whole load.

How is a key looked up?

Store the sorted virtual node positions in an array and binary search it:

import bisect
 
def get_server(ring_positions, ring, key):
    position = hash_fn(key)
    index = bisect.bisect_right(ring_positions, position)
    if index == len(ring_positions):
        index = 0                       # wrap around the circle
    return ring[ring_positions[index]]

That is O(log n) per lookup where n is the number of virtual nodes — a few microseconds even with thousands of them.

Where is it used?

Most of these systems also replicate. Each key is stored on the next N distinct physical servers clockwise, skipping any virtual node that belongs to a machine already holding a copy:

Common mistakes

• Confusing it with sharding in general. Range-based and directory-based sharding are also valid; consistent hashing is one strategy with a specific benefit.
• Using too few virtual nodes. Below about 100 per server, imbalance is visible in production.
• Assuming it solves hot keys. It balances key distribution, not per-key popularity.
• Forgetting replication. Real systems store each key on the next N distinct physical servers clockwise, not just the first one, so a node failure does not lose data.
• Using a weak hash function. Clustered hash output defeats the whole mechanism. MD5 or MurmurHash are the usual choices — cryptographic strength is not required, but good distribution is.

Conclusion

Consistent hashing maps servers and keys into the same circular hash space and assigns each key to the first server clockwise from it. Adding or removing a server moves only that server's share of keys — roughly 1/n — instead of the (n-1)/n that modulo hashing would remap.

Virtual nodes, typically 100 to 200 per physical server, are what make it work in practice: they even out the distribution and spread a failed server's load across many neighbours rather than one.

It is the default answer whenever a design interview reaches the question "what happens when you add a server?"