In Database Sharding & Partitioning we ran an experiment: with shard = hash(key) mod N, growing from 4 to 5 shards moved 80% of all keys. For a cache cluster that means a sudden flood of cache misses hitting the database; for a database cluster it means copying most of your data across the network while serving live traffic.
Consistent hashing fixes this. When a server is added or removed, only a small, fair share of keys move, roughly 1/N of them. It is one of the most frequently asked system design concepts, and it is used inside Amazon's Dynamo, Apache Cassandra, Riak, distributed caches and load balancers.
Consistent hashing is a technique that maps both keys and servers onto the same circular hash space (a "ring"), and assigns each key to the first server found moving clockwise from the key's position. Adding or removing a server only affects the keys in that server's neighbouring segment of the ring.
It was introduced by Karger and colleagues at MIT in 1997, originally for distributing web caches, the work that led to Akamai's CDN (see Content Delivery Networks (CDN)).
Why mod N Breaks
With hash(key) mod N, a key's server depends on N itself. Change N and almost every key's remainder changes:
hash(key) = 17
N = 4 → 17 mod 4 = 1 → server 1
N = 5 → 17 mod 5 = 2 → server 2 (moved!)
hash(key) = 20
N = 4 → 0 → server 0
N = 5 → 0 → server 0 (stays, but only by luck)
Only about 1/(N+1) of keys need to move to keep the load balanced when a server is added (the new server should end up with its fair share and no more). mod N moves far more than necessary. The goal of consistent hashing is to move only that minimum.
The Hash Ring
Take the output range of a hash function, for example 0 to 232 − 1, and bend it into a circle so that the largest value wraps around to 0.
Place servers on the ring: hash each server's name or IP (
hash("server-A")) to get its position.Place keys on the ring: hash each key (
hash("user:42")) with the same function.Lookup rule: from the key's position, walk clockwise until you meet a server. That server owns the key.
Let us use a tiny ring of 0–99 to make it concrete. Servers hash to A = 20, B = 50, C = 80. Four keys hash to 15, 35, 60 and 90.
0 / 100
k4(90) • • k1(15)
C(80) ■ ■ A(20)
| |
| • k2(35)
k3(60)• |
■ B(50)
k1 (15) → clockwise → A (20)
k2 (35) → clockwise → B (50)
k3 (60) → clockwise → C (80)
k4 (90) → clockwise → passes 99, wraps to 0 → A (20)
Each server owns the arc from the previous server (exclusive) up to itself (inclusive):
| Server | Owns positions | Keys |
|---|---|---|
| A (20) | 81–99 and 0–20 (wraps) | k1, k4 |
| B (50) | 21–50 | k2 |
| C (80) | 51–80 | k3 |
Adding a Server
Server D hashes to 65. It lands inside C's arc (51–80) and takes over the part 51–65.
Before: B(50) ──── 51..80 owned by C ──── C(80)
After: B(50) ── 51..65 → D ── D(65) ── 66..80 → C ── C(80)
k3 (60): was C, now D ← the ONLY key that moves
k1, k2, k4: unchanged
Only keys between B and D move, and they all move to D. No key ever moves between two old servers. That is the whole magic.
Removing a Server
If B (50) crashes, its arc (21–50) is absorbed by the next server clockwise, D (65). Key k2 moves to D; everything else stays where it is.
The Problem with One Point per Server
With only a few servers placed by a hash, the arcs are very unlikely to be equal. One server might own half the ring. And when a server dies, its entire load lands on a single neighbour, which might then overload and fail too (a cascading failure).
Virtual Nodes (vnodes)
The fix: place each physical server on the ring many times, by hashing "A#0", "A#1", ..., "A#99". Each of these points is a virtual node that maps back to physical server A.
Ring with 3 vnodes per server (real systems use dozens to hundreds):
A#2 B#0 C#1 A#0 C#0 B#2 A#1 B#1 C#2 (positions in ring order)
■────■────■────■────■────■────■────■────■────(wraps)
Many small arcs per server → load averages out
If B dies: B#0's arc goes to C, B#2's to A, B#1's to C
→ B's load is shared by all survivors, not dumped on one server
Benefits of virtual nodes:
Even load: many small random arcs average out (law of large numbers).
Smooth failure handling: a failed server's load spreads over many servers.
Weighted capacity: give a server with twice the RAM twice as many vnodes.
The cost is a bigger ring in memory (servers × vnodes entries), which is tiny in practice: 100 servers × 256 vnodes = 25,600 entries.
Implementation in Python
We keep a sorted list of ring positions and a dictionary from position to server. Lookup is a binary search for the first position greater than the key's hash, wrapping to index 0 if we fall off the end. The hash is the first 4 bytes of MD5, giving a ring of size 232. MD5 is fine here because we need a well-spread, stable hash, not security.
import bisect
import hashlib
from collections import Counter
def ring_hash(s: str) -> int:
"""Position on a ring of size 2^32 (first 4 bytes of MD5)."""
return int.from_bytes(hashlib.md5(s.encode()).digest()[:4], "big")
class ConsistentHashRing:
def __init__(self, vnodes=100):
self.vnodes = vnodes
self.positions = [] # sorted ring positions
self.owner = {} # position -> physical node
def add_node(self, node):
for i in range(self.vnodes):
pos = ring_hash(f"{node}#{i}")
self.owner[pos] = node
bisect.insort(self.positions, pos)
def remove_node(self, node):
for i in range(self.vnodes):
pos = ring_hash(f"{node}#{i}")
del self.owner[pos]
self.positions.remove(pos)
def get_node(self, key):
pos = ring_hash(key)
i = bisect.bisect_right(self.positions, pos) # first position clockwise
if i == len(self.positions): # wrap around
i = 0
return self.owner[self.positions[i]]
keys = [f"user:{i}" for i in range(100_000)]
for v in (1, 100):
ring = ConsistentHashRing(vnodes=v)
for n in ("A", "B", "C"):
ring.add_node(n)
load = Counter(ring.get_node(k) for k in keys)
print(f"vnodes={v:<3} load:", dict(sorted(load.items())))
ring = ConsistentHashRing(vnodes=100)
for n in ("A", "B", "C"):
ring.add_node(n)
print("user:42 ->", ring.get_node("user:42"))
before = {k: ring.get_node(k) for k in keys}
ring.add_node("D")
after = {k: ring.get_node(k) for k in keys}
moved = [k for k in keys if before[k] != after[k]]
print(f"add D: {len(moved)} keys moved ({len(moved)/len(keys):.1%}),",
"all to D:", all(after[k] == "D" for k in moved))
ring.remove_node("B")
after_rm = {k: ring.get_node(k) for k in keys}
moved = [k for k in keys if after[k] != after_rm[k]]
print(f"remove B: {len(moved)} keys moved ({len(moved)/len(keys):.1%}),",
"all were on B:", all(after[k] == "B" for k in moved))
Output:
vnodes=1 load: {'A': 3057, 'B': 56737, 'C': 40206}
vnodes=100 load: {'A': 32113, 'B': 33766, 'C': 34121}
user:42 -> B
add D: 24281 keys moved (24.3%), all to D: True
remove B: 24845 keys moved (24.8%), all were on B: True
This output is worth studying line by line:
vnodes = 1: server A got only 3% of the keys while B got 57%. One point per server is badly unbalanced.
vnodes = 100: every server is within about 4% of the ideal 33,333.
Adding D moved 24.3% of keys, close to the ideal 1/4 = 25% (compare with 80% for mod N), and every moved key went to the new server D.
Removing B moved only B's own keys (24.8%); nothing else was disturbed.
The Same Ring in Java
Java's TreeMap is a sorted map (a red-black tree), and higherEntry(k) returns the first entry with a key strictly greater than k, exactly the "walk clockwise" step. This version uses the same hash, so it gives the same answers as the Python one.
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Map;
import java.util.TreeMap;
public class ConsistentHashRing {
private final int vnodes;
private final TreeMap<Long, String> ring = new TreeMap<>(); // position -> node
public ConsistentHashRing(int vnodes) { this.vnodes = vnodes; }
// Position on a ring of size 2^32: first 4 bytes of MD5 as an unsigned number
static long ringHash(String s) {
try {
byte[] d = MessageDigest.getInstance("MD5")
.digest(s.getBytes(StandardCharsets.UTF_8));
return ((long) (d[0] & 0xFF) << 24) | ((d[1] & 0xFF) << 16)
| ((d[2] & 0xFF) << 8) | (d[3] & 0xFF);
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e);
}
}
public void addNode(String node) {
for (int i = 0; i < vnodes; i++) ring.put(ringHash(node + "#" + i), node);
}
public void removeNode(String node) {
for (int i = 0; i < vnodes; i++) ring.remove(ringHash(node + "#" + i));
}
public String getNode(String key) {
if (ring.isEmpty()) throw new IllegalStateException("ring is empty");
// first position strictly greater than the key's position (clockwise)
Map.Entry<Long, String> e = ring.higherEntry(ringHash(key));
return (e != null ? e : ring.firstEntry()).getValue(); // wrap around
}
public static void main(String[] args) {
ConsistentHashRing r = new ConsistentHashRing(100);
for (String n : new String[]{"A", "B", "C"}) r.addNode(n);
int total = 100_000;
String[] before = new String[total];
for (int i = 0; i < total; i++) before[i] = r.getNode("user:" + i);
System.out.println("user:42 -> " + r.getNode("user:42"));
r.addNode("D");
int moved = 0, movedToD = 0;
for (int i = 0; i < total; i++) {
String now = r.getNode("user:" + i);
if (!now.equals(before[i])) { moved++; if (now.equals("D")) movedToD++; }
}
System.out.printf("add D: %d keys moved (%.1f%%), all to D: %b%n",
moved, 100.0 * moved / total, moved == movedToD);
}
}
Output (javac ConsistentHashRing.java && java ConsistentHashRing, Java 17):
user:42 -> B
add D: 24281 keys moved (24.3%), all to D: true
Note the (long) cast on the first byte: without it, (d[0] & 0xFF) << 24 is an int and becomes negative when the top bit is set, breaking the ordering of the ring.
Complexity
| Operation | Time (N servers, V vnodes each) |
|---|---|
| Lookup a key | O(log(N·V)) binary search |
| Add / remove a server | O(V log(N·V)) with a balanced tree (the Python list version pays O(N·V) per insert for shifting, fine for small rings) |
| Memory | O(N·V) |
| Keys moved when adding the (N+1)th server | about K/(N+1) out of K keys |
Replication on the Ring
Consistent hashing also tells us where to put copies (see Database Replication). To store each key on 3 servers, walk clockwise from the key and take the first 3 distinct physical servers, skipping extra vnodes of a server already chosen.
key k ─► A#7 ─► A#2 (skip, A already chosen) ─► C#4 ─► B#9
replicas of k = [A, C, B]
Dynamo calls this list the key's preference list. Cassandra additionally tries to place replicas on different racks and data centres so that one rack failure does not take out every copy.
Where Consistent Hashing Is Used
Amazon Dynamo (2007 paper, the system whose ideas later shaped DynamoDB): partitioning plus replication on the ring with virtual nodes.
Apache Cassandra / ScyllaDB: partition keys are hashed to tokens on a ring (Murmur3 in Cassandra). Since Cassandra 4.0 the default is
num_tokens: 16vnodes per node, combined with a token-allocation algorithm that keeps the ring balanced (older versions used 256 random tokens).Distributed caches: memcached client libraries (such as the "ketama" algorithm) choose the cache server with a ring, so adding a cache server invalidates only a fraction of the cache.
Load balancers: sticky routing of a user or connection to the same backend (see Load Balancing). Google's Maglev load balancer uses its own consistent-hashing lookup table.
CDNs and object stores: choosing which cache or storage node holds a given URL or object.
Not Everything Uses a Ring
Redis Cluster is often mistaken for consistent hashing. It actually uses 16,384 fixed hash slots: slot = CRC16(key) mod 16384, and each node is assigned a set of slots. Adding a node means moving some slots to it. This is the "fixed number of logical partitions" approach from the previous chapter. It achieves the same goal (minimal movement) by a different mechanism.
Alternatives Worth Knowing
Rendezvous (Highest Random Weight) Hashing
For each key, compute a score hash(key, server) for every server and pick the server with the highest score. No ring, no vnodes, and naturally even.
import hashlib
from collections import Counter
def score(key, server):
return int.from_bytes(hashlib.md5(f"{key}|{server}".encode()).digest()[:8], "big")
def pick(key, servers):
return max(servers, key=lambda s: score(key, s))
keys = [f"user:{i}" for i in range(100_000)]
servers = ["A", "B", "C"]
before = {k: pick(k, servers) for k in keys}
print("load:", dict(sorted(Counter(before.values()).items())))
after = {k: pick(k, servers + ["D"]) for k in keys}
moved = [k for k in keys if before[k] != after[k]]
print(f"add D: {len(moved)/len(keys):.1%} moved, all to D: {all(after[k] == 'D' for k in moved)}")
Output:
load: {'A': 33330, 'B': 33292, 'C': 33378}
add D: 25.2% moved, all to D: True
Same minimal-movement property, but each lookup costs O(N) hash computations, so it suits a small or moderate number of servers.
Jump Consistent Hash
Published by Google engineers (Lamping and Veach, 2014): a few lines of arithmetic map a key to a bucket number 0..N−1 with no memory and near-perfect balance. Its limitation is that buckets must be numbered sequentially and can only be added or removed at the end, so it fits numbered storage shards better than a pool of servers that can fail at random.
| Ring + vnodes | Rendezvous | Jump hash | Fixed slots | |
|---|---|---|---|---|
| Lookup cost | O(log(N·V)) | O(N) | O(log N), no memory | O(1) table lookup |
| Balance | Good with enough vnodes | Very good | Very good | Depends on slot assignment |
| Remove arbitrary server | Yes | Yes | No (only the last) | Yes (reassign its slots) |
| Example | Cassandra, Dynamo | Some CDNs and distributed caches | Sharded storage | Redis Cluster |
Common Mistakes
Explaining the ring without virtual nodes. Our run showed one-point-per-server can give one server 57% of keys. Always mention vnodes.
Saying "no keys move" when a server is added. About 1/(N+1) of the keys must move; consistent hashing makes it the minimum, not zero.
Using a non-deterministic hash (Python's built-in
hash()for strings, Java'sObject.hashCode()for objects without a stable implementation). Every client must compute identical positions.Forgetting the wrap-around when the key's position is past the last server.
Choosing replicas as "next 3 positions" instead of "next 3 distinct physical servers", which can put all copies on one machine.
Thinking consistent hashing fixes hot keys. It balances many keys; one extremely popular key still lands on one server (see the celebrity problem in the previous chapter).
Interview Questions
1. What problem does consistent hashing solve?
With hash(key) mod N, changing the number of servers remaps most keys, causing massive data movement or cache misses. Consistent hashing remaps only about 1/N of the keys, and only to or from the server that joined or left.
2. Explain how a key is assigned to a server.
Servers and keys are hashed onto the same circular space. The key belongs to the first server found moving clockwise from the key's position, wrapping around past the maximum value to the beginning.
3. Why are virtual nodes needed?
With one position per server, arcs are uneven, so load is unbalanced, and a failed server's whole load goes to a single neighbour. Many virtual nodes per server average out the arcs, spread a failed server's load across all others, and allow weighting by capacity.
4. A ring has 4 servers holding 1 million keys. Roughly how many keys move when a 5th server is added?
About 1/5 of them, roughly 200,000 keys, all moving to the new server. With mod N, about 800,000 would move.
5. What data structure would you use to implement the ring?
A sorted structure supporting "smallest key greater than x": a TreeMap in Java (higherEntry/ceilingEntry), a sorted list with binary search (bisect) in Python, or std::map::upper_bound in C++. Lookup is O(log(N·V)).
6. Does Redis Cluster use consistent hashing?
Not a hash ring. It hashes keys with CRC16 into 16,384 fixed slots and assigns slots to nodes; resharding moves slots between nodes. It shares the goal of limited movement, but uses fixed logical partitions rather than a ring.
Summary
mod N hashing remaps most keys when N changes; consistent hashing moves only about 1/N.
Servers and keys share a hash ring; a key belongs to the next server clockwise.
Virtual nodes balance load, spread failures and support different server capacities.
Implement it with a sorted map and binary search: O(log(N·V)) lookups.
Replicas go on the next distinct physical servers clockwise (the preference list).
Alternatives: rendezvous hashing, jump hash, and fixed hash slots (Redis Cluster).
Consistent hashing turns "add a server" from a full reshuffle into a small, local handover, which is what makes elastic scaling of caches and databases practical.