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

Source: https://skills101.in/learn/system-design/system-design-consistent-hashing — Skills101 free tutorial (System Design). Updated 2026-11-18.

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**.

```python
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%})")
```

```text
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](https://skills101.in/learn-img/system-design/hash-ring.svg)

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.

```python
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()))
```

```text
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.

```python
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))
```

```text
  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](https://skills101.in/learn-img/system-design/vnode-balance.svg)

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

| System | What is being placed on the ring |
|---|---|
| Distributed caches (Memcached clients, Redis client-side sharding) | cache keys → cache servers |
| Dynamo-style databases, Cassandra | rows (by partition key) → storage nodes |
| Load balancers that need stickiness | users or sessions → app servers, with little reshuffling when servers change |
| CDNs | URLs → 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 quiz and free certificate: https://skills101.in/learn/system-design/system-design-consistent-hashing