Consistent Hashing Explained (With Examples)

The Problem Consistent Hashing Solves

Say you spread cached data across 4 servers with a simple rule:

server = hash(key) % 4

It works, until you add a 5th server. Now it's hash(key) % 5, and almost every key maps to a different server. Your cache misses everywhere at once, and the database behind it gets flooded.

Consistent hashing fixes this. When a server is added or removed, only a small fraction of keys move. That's why it sits at the heart of distributed caches and databases.

🎯 Quick Answer (30-Second Read)

• Problem: with hash(key) % N, changing N remaps most keys.
• Idea: place servers and keys on the same hash ring. Each key belongs to the next server clockwise.
• Result: adding or removing a server moves only about 1/N of the keys, the ones near it on the ring.
• Virtual nodes: each server takes many positions on the ring for a more even spread.
• Used in: Amazon's Dynamo design, Apache Cassandra, memcached client libraries, and load balancers that need stable routing.

Why hash % N Breaks

With modulo hashing, a key's server depends on N. Change N, and the answer changes for most keys. For example, going from 4 to 5 servers keeps only about 1 in 5 keys on the same server. The other ~80% move.

How the Hash Ring Works

1. Imagine the range of hash values as a circle (0 at the top, wrapping round to the maximum).
2. Hash each server (for example its name) to a point on the circle.
3. Hash each key to a point on the circle.
4. A key belongs to the first server clockwise from it.

Adding a server D between A and B: only the keys between A and D (which used to go to B) move to D. Everything else stays put.

Removing server B: only B's keys move, to the next server clockwise (C). Nobody else is affected.

Virtual Nodes: Fixing Uneven Load

With only a few servers on the ring, the gaps between them can be very uneven, so one server ends up with far more keys.

The fix is virtual nodes: each physical server is placed on the ring many times (A#1, A#2, … A#100).

• Load spreads far more evenly.
• When a server leaves, its keys spread across many servers, not just one neighbour.
• Bigger servers can get more virtual nodes, so they take a bigger share.

Simple Implementation (Python)

import bisect, hashlib

def h(value: str) -> int:
    return int(hashlib.md5(value.encode()).hexdigest(), 16)

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.ring = {}              # position -> server
        self.positions = []
        for s in servers:
            self.add(s, vnodes)

    def add(self, server, vnodes=100):
        for i in range(vnodes):
            pos = h(f"{server}#{i}")
            self.ring[pos] = server
            bisect.insort(self.positions, pos)

    def remove(self, server, vnodes=100):
        for i in range(vnodes):
            pos = h(f"{server}#{i}")
            del self.ring[pos]
            self.positions.remove(pos)

    def get(self, key: str) -> str:
        pos = h(key)
        i = bisect.bisect(self.positions, pos) % len(self.positions)  # next clockwise, wrap around
        return self.ring[self.positions[i]]

ring = HashRing(["cache-a", "cache-b", "cache-c"])
print(ring.get("user:42"))

Add ring.add("cache-d") and compare key assignments before and after. Only a fraction of keys change server.

Where Consistent Hashing Is Used

Trade-offs and Alternatives

• Still not perfectly even: it needs enough virtual nodes to balance well.
• Hot keys: one very popular key still lands on one server. Use replication or caching to handle it.
• Replication: systems often store each key on the next R servers clockwise for fault tolerance.
• Alternatives: rendezvous (highest random weight) hashing and jump consistent hash give similar "minimal movement" properties with different trade-offs.

Frequently Asked Questions

Conclusion

Consistent hashing maps keys and servers onto a ring so each key goes to the next server clockwise. Adding or removing a server then moves only about 1/N of keys instead of nearly all of them. Add virtual nodes for even load, and you have the foundation that distributed caches and databases like Dynamo and Cassandra are built on.

Sources

• Karger et al., "Consistent Hashing and Random Trees" (1997), the original paper
• DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (2007)
• Apache Cassandra docs: Dynamo-style architecture

Last verified: 14 October 2026.

Related reads: Load Balancer Explained · Rate Limiter Explained · Redis Explained · How Discord Scaled

I write about system design and how real products are built. Follow on LinkedIn or X, or invite me to speak.