Consistent Hashing Explained — How It Powers Distributed Systems

The problem consistent hashing solves#

You have 4 cache servers. You hash each key and use hash(key) % 4 to pick a server. Works great — until you add or remove a server.

With % N hashing, adding a 5th server changes % 4 to % 5. Almost every key maps to a different server. Your cache hit rate drops to near zero. Every request hits the database.

Consistent hashing fixes this: when you add or remove a server, only ~1/N of keys need to move.

How it works#

Imagine a ring (circle) numbered 0 to 2^32.

Step 1: Hash each server name to a position on the ring.

hash("server-A") → position 1000
hash("server-B") → position 4000
hash("server-C") → position 7000

Step 2: To find which server owns a key, hash the key and walk clockwise until you hit a server.

hash("user:123") → position 2500 → walks clockwise → Server B (4000)
hash("user:456") → position 5000 → walks clockwise → Server C (7000)
hash("user:789") → position 9000 → walks clockwise → Server A (wraps to 1000)

Step 3: When a server is added or removed, only the keys between it and the previous server are affected. Everything else stays put.

Adding a server#

Add Server D at position 5500:

Before: keys 4001-7000 → Server C
After:  keys 4001-5500 → Server D
        keys 5501-7000 → Server C (unchanged)

Only keys in the 4001-5500 range moved. Servers A and B are completely unaffected.

Virtual nodes#

The problem: With few servers, the ring is unbalanced. One server might own 60% of the key space while another owns 10%.

The fix: Give each physical server multiple positions on the ring (virtual nodes):

Server A → hash("A-0")=1000, hash("A-1")=3500, hash("A-2")=8000
Server B → hash("B-0")=2000, hash("B-1")=5500, hash("B-2")=9500
Server C → hash("C-0")=4000, hash("C-1")=6500, hash("C-2")=7800

With 100-200 virtual nodes per server, the distribution becomes nearly uniform. When a server is removed, its keys spread evenly across the remaining servers.

Where it's used#

Amazon DynamoDB — Partitions data across storage nodes. When capacity changes, minimal data moves between partitions.

Apache Cassandra — Each node owns a range on the token ring. Adding nodes splits ranges with minimal data movement.

Memcached — Client libraries use consistent hashing to distribute keys. Adding a server doesn't invalidate the entire cache.

CDNs (Akamai, CloudFlare) — Route requests to edge servers. When a server goes down, only its traffic redirects — the rest is unaffected.

Load balancers — Sticky sessions. Same client always routes to the same backend (unless that backend is removed).

Consistent hashing vs. rendezvous hashing#

Rendezvous (HRW) hashing is an alternative:

• Hash each key with every server: score = hash(key + server)
• Pick the server with the highest score
• No ring needed, simpler implementation

Trade-off: Rendezvous is O(N) per lookup (check all servers), consistent hashing is O(log N) with a sorted ring. For small N (under 100 servers), rendezvous is simpler. For large N, consistent hashing wins.

Implementation sketch#

import hashlib
from bisect import bisect_right

class ConsistentHash:
    def __init__(self, nodes, vnodes=150):
        self.ring = {}
        self.sorted_keys = []
        for node in nodes:
            for i in range(vnodes):
                key = self._hash(f"{node}-{i}")
                self.ring[key] = node
                self.sorted_keys.append(key)
        self.sorted_keys.sort()

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get_node(self, key):
        h = self._hash(key)
        idx = bisect_right(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

Visualize your distributed system#

See how consistent hashing fits into a distributed cache or database cluster — try Codelit to generate an interactive architecture diagram.

Key takeaways#

1. % N hashing breaks when N changes — almost all keys remap
2. Consistent hashing remaps only ~1/N keys when a node changes
3. Virtual nodes fix the unbalanced distribution problem
4. Used everywhere — DynamoDB, Cassandra, Memcached, CDNs
5. O(log N) lookup with sorted ring + binary search