Skills101

AdvancedSystem Design · Lesson 11 of 12 · Updated ·

Consistent Hashing — Why hash % N Breaks and How the Hash Ring Fixes It

You have 4 cache servers and millions of keys (user:42, course:91). Every app server must agree on which cache server holds which key, without asking a central directory each time. The obvious answer — hash(key) % 4 — works until the day you add a fifth server. Then almost everything moves, the caches become useless at once, and the database gets crushed.

Consistent hashing is the standard fix. It is used for partitioning data in Amazon Dynamo-style databases and Apache Cassandra, in cache clients for Memcached, and in some load balancers.

1. The problem with hash % N

A hash function turns any key into a big number, the same number every time for the same key. hash(key) % N then picks one of N servers. It spreads keys evenly — but the answer depends on N.

import hashlib

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % 2**32

keys = [f"user{i}" for i in range(10000)]
moved = sum(1 for k in keys if h(k) % 4 != h(k) % 5)
print(f"4 -> 5 servers: {moved} of {len(keys)} keys move ({moved / len(keys):.0%})")
4 -> 5 servers: 8010 of 10000 keys move (80%)

Adding one server moved about 80% of the keys. For a cache, a moved key is a miss: 80% of reads suddenly fall through to the database at the same moment. For a sharded database, 80% of the data must be copied between machines. Removing a crashed server is just as bad.

What we want: when a server is added or removed, only about 1/N of the keys should move — the share that the new server takes over, or the share the dead server owned.

2. The hash ring

Imagine the hash space 0 … 2³² − 1 bent into a circle, so the largest value sits next to 0.

  1. Hash each server's name to a point on the ring.
  2. Hash each key to a point on the ring.
  3. A key belongs to the first server you meet going clockwise from the key.

A hash ring with servers C, B, D and A placed at 48, 86, 186 and 298 degrees; keys user1 and user5 sit just before D and belong to D, user2 and user6 belong to A, and user3 and user4 wrap past 360 degrees to C

The positions in the picture are the real MD5 positions from the code below. user3 is at 317°, past the last server, so it wraps around to the first server, C.

Now add server E. It lands at one point on the ring and takes over only the keys between the previous server and itself. Every other key keeps its server. Remove a server, and only its keys move — to the next server clockwise.

3. Building the ring in Python

A sorted list of (position, server) points and a binary search (bisect) is all we need.

import hashlib, bisect
from collections import Counter

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % 2**32

class Ring:
    def __init__(self, servers, vnodes=1):
        self.vnodes, self.points = vnodes, []
        for s in servers:
            self.add(s)

    def add(self, server):
        for i in range(self.vnodes):
            bisect.insort(self.points, (h(f"{server}#{i}"), server))

    def get(self, key):
        i = bisect.bisect(self.points, (h(key),))       # first point clockwise
        return self.points[i % len(self.points)][1]     # wrap past the end to the start

keys = [f"user{i}" for i in range(10000)]
ring = Ring(["A", "B", "C", "D"])
before = {k: ring.get(k) for k in keys}
ring.add("E")
after = {k: ring.get(k) for k in keys}
moved = [k for k in keys if before[k] != after[k]]
print("moved:", len(moved), f"({len(moved) / len(keys):.0%})")
print("all moved keys went to E:", all(after[k] == "E" for k in moved))
print("load before:", sorted(Counter(before.values()).items()))
moved: 1723 (17%)
all moved keys went to E: True
load before: [('A', 3102), ('B', 1044), ('C', 2958), ('D', 2896)]

Two things to notice:

  • Only about 17% of keys moved, and every one of them went to E. No key moved between the old servers. Compare that with 80% for hash % N.
  • The load is uneven: B has about 1,000 keys while A has about 3,100. With only 4 random points on the ring, some servers own long arcs and some own short ones.

4. Virtual nodes fix the imbalance

Instead of one point per server, put each server on the ring many times — A#0, A#1, … A#99. These are virtual nodes. Each server now owns many small arcs scattered around the ring, and the random lengths average out.

import hashlib, bisect
from collections import Counter

def h(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % 2**32

class Ring:
    def __init__(self, servers, vnodes=1):
        self.vnodes, self.points = vnodes, []
        for s in servers:
            self.add(s)

    def add(self, server):
        for i in range(self.vnodes):
            bisect.insort(self.points, (h(f"{server}#{i}"), server))

    def get(self, key):
        i = bisect.bisect(self.points, (h(key),))
        return self.points[i % len(self.points)][1]

keys = [f"user{i}" for i in range(10000)]
for v in (1, 100):
    ring = Ring(["A", "B", "C", "D"], vnodes=v)
    load = Counter(ring.get(k) for k in keys)
    print(f"{v:>3} vnode(s):", sorted(load.items()), "max/min =", round(max(load.values()) / min(load.values()), 2))
  1 vnode(s): [('A', 3102), ('B', 1044), ('C', 2958), ('D', 2896)] max/min = 2.97
100 vnode(s): [('A', 2471), ('B', 2403), ('C', 2456), ('D', 2670)] max/min = 1.11

Keys per server out of 10,000: with 1 point per server the counts range from about 1,000 to 3,100; with 100 virtual nodes each server holds close to 2,500

Virtual nodes give two more benefits:

  • Different-sized servers: give a server with twice the RAM twice as many virtual nodes, and it takes twice the keys.
  • Smoother failures: when a server dies, its many small arcs are spread over all the remaining servers, instead of dumping its whole load on one neighbour.

5. Replication on the ring

Databases such as Cassandra store each key on several servers for safety. With a replication factor of 3, a key is stored on the first server clockwise and the next two different servers after it. If one fails, the other two still have the data, and the ring already tells every client where to look.

6. Where you will meet it

SystemWhat is being placed on the ring
Distributed caches (Memcached clients, Redis client-side sharding)cache keys → cache servers
Dynamo-style databases, Cassandrarows (by partition key) → storage nodes
Load balancers that need stickinessusers or sessions → app servers, with little reshuffling when servers change
CDNsURLs → cache servers inside a location

Redis Cluster uses a related idea: a fixed set of 16,384 hash slots assigned to nodes; adding a node moves some slots, not all keys. Mentioning this in an interview shows you know that fixed slots are another common answer to the same problem.

Common mistakes

  • Using hash % N for caches or shards and being surprised when scaling empties the cache.
  • Forgetting the wrap-around: a key after the last server belongs to the first one.
  • Using one point per server and getting very uneven load.
  • Using a hash that changes between runs or languages (Python's built-in hash() for strings is randomised per process). Use a stable hash such as MD5, MurmurHash or xxHash.

Quick recap

  • hash % N moves most keys whenever N changes (about 80% going from 4 to 5 servers).
  • Consistent hashing puts servers and keys on a ring; a key belongs to the next server clockwise.
  • Adding or removing a server moves only the keys in its arc.
  • Virtual nodes spread each server around the ring for even load and smoother failures.
  • Used in distributed caches, Dynamo-style databases and Cassandra; Redis Cluster uses fixed hash slots.

Practice what you learned

📝 Quiz: Consistent Hashing5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →