CS Fundamentals Trainer · Guides
Consistent hashing
Why hash mod N breaks when servers change, how the ring and virtual nodes fix it, with code and alternatives.
17 min read
Consistent hashing is a way to decide which server owns which key, so that when servers join or leave, only a small share of the keys has to move. It sits underneath caches, databases, load balancers and CDNs, and it is a staple of system design interviews. The idea is small enough to implement in thirty lines, and this guide does that in four languages.
1. The problem: spreading keys over servers
You have a cache or a database too big for one machine, so you split the keys over N servers. You need a rule that, given a key, always names the same server, from any client, without asking anyone. The obvious rule is:
server = hash(key) mod N
It spreads keys evenly and costs nothing. Its flaw appears the moment N changes.
What happens when N changes
Add a fifth server to four, and hash(key) mod 4 becomes hash(key) mod 5. For most keys the answer changes. I measured it with 100 000 keys:
| Servers | Keys that moved | Ideal minimum |
|---|---|---|
| 4 → 5 | 79.9 % | 20 % (1/5) |
| 9 → 10 | 90.0 % | 10 % (1/10) |
| 99 → 100 | 99.0 % | 1 % (1/100) |
The larger the cluster, the worse it gets: nearly all keys move for a single added machine. In a cache, that is a sudden wall of misses that lands on your database. In a database, it is a massive data migration. The ideal is that a new server takes only its fair share (1/(N+1) of the keys) and nothing else moves. Consistent hashing achieves that [1].
2. The ring
Picture the output range of the hash function, say 0 to 2^32 − 1, bent into a circle, so the largest value is next to 0. Then:
- Place each server on the ring by hashing its name (or address).
- Place each key on the ring by hashing the key.
- A key belongs to the first server found going clockwise from the key's position (wrapping around at the end).
Diagram: A ring with three servers and four keys (read clockwise)
Reading the picture: the keys at 25 and 40 go clockwise to the next server, B at 55. The key at 70 goes to C at 90. The key at 95 passes the end of the ring and wraps around to A at 10. Every server owns the stretch of the ring that lies between its predecessor and itself.
Adding and removing servers
Now add a server D at position 80:
Diagram: Adding Server D at 80 takes keys only from its neighbour
Only the keys between 55 and 80 (here, the key at 70) change owner, from C to D. Every other key stays where it was. If a server leaves, only its keys move, to the next server clockwise. With N servers, the expected share that moves is about 1/N. In my run, adding an 11th server to a ring of 10 moved 8.9 % of the keys, against the ideal 9.1 % (another set of names gave 10.0 %: the number is random, centred on 1/N); and every key that moved went to the new server and nowhere else.
3. Uneven load and virtual nodes
There is a catch. With one point per server, servers land at random places on the circle, and the gaps between them are very uneven. One server may own a gap three times larger than another's, and another may get almost nothing. I measured the load for 10 servers and 100 000 keys. Because the result depends on the luck of where the points fall, I repeated it with 12 different sets of server names and show the typical (median) run and the worst of the 12:
| Points per server | Busiest server vs average (median / worst) | Quietest server vs average (median / worst) |
|---|---|---|
| 1 | 2.68 × / 3.48 × | 0.09 × / 0.01 × |
| 10 | 1.42 × / 1.81 × | 0.60 × / 0.45 × |
| 100 | 1.15 × / 1.22 × | 0.85 × / 0.72 × |
| 200 | 1.12 × / 1.20 × | 0.89 × / 0.83 × |
| 500 | 1.07 × / 1.12 × | 0.94 × / 0.89 × |
| 1 000 | 1.04 × / 1.11 × | 0.95 × / 0.92 × |
With 100 servers the same test is a little worse (at 200 points: busiest 1.19 ×, quietest 0.81 ×; at 1 000 points: 1.11 × and 0.89 ×), because every server's share is smaller and the random differences matter more. Part of what you see is also the test itself: 100 000 keys over 100 servers is only 1 000 keys each, so the counts have their own noise of a few percent.
The fix is virtual nodes ("vnodes"): each server is placed on the ring many times, under names such as server-a#0, server-a#1, server-a#2... Its share becomes the sum of many small, random gaps, and sums of many small random pieces are close to even. The spread shrinks only with the square root of the number of points: ten times as many points makes it about three times tighter. So 100 to 200 points per server (a common default) gives load within roughly ±15 to 25 % of the average, and getting to ±10 % takes several hundred to a thousand. Pick the number from how much imbalance you can live with. Virtual nodes have a second benefit: when a server leaves, its load spreads over many other servers instead of falling entirely on one neighbour (which might then fail too, and so on). They also let you give a bigger machine more points than a smaller one, proportionally to its capacity.
The cost is memory and lookup time: 100 servers with 200 points each is 20 000 entries; with 1 000 points it is 100 000, still small. Looking up a key is a binary search over a sorted array, which is fast (about 15 steps).
4. A working implementation
The ring is a sorted array of positions. A lookup hashes the key and finds the first position greater than it with binary search; if there is none, it wraps to the first entry. Four versions follow (pick a language on the tabs; your choice is remembered). All use SHA-256 as the hash and keep its first 8 bytes (6 in JavaScript, to stay within what a number holds exactly). A fast non-cryptographic hash is fine too, as long as it spreads values well.
import bisect
import hashlib
def h(s):
return int.from_bytes(hashlib.sha256(s.encode()).digest()[:8], "big")
class Ring:
def __init__(self, vnodes=150):
self.vnodes = vnodes
self.hashes = [] # sorted positions on the ring
self.owner = {} # position -> server
self.points_of = {} # server -> how many points it has
def add(self, server, weight=1.0):
if server in self.points_of: # adding twice would store the points twice
return
count = round(self.vnodes * weight) # a bigger machine gets more points
for i in range(count):
pos = h(f"{server}#{i}")
self.owner[pos] = server
bisect.insort(self.hashes, pos)
self.points_of[server] = count
def remove(self, server):
count = self.points_of.pop(server, None)
if count is None:
return
for i in range(count):
pos = h(f"{server}#{i}")
del self.owner[pos]
self.hashes.remove(pos)
def get(self, key):
return self.get_n(key, 1)[0]
def get_n(self, key, n):
"""The owner and the next n-1 distinct servers clockwise (the replicas)."""
if n > len(self.points_of):
raise LookupError("not enough servers")
start = bisect.bisect_right(self.hashes, h(key))
found = []
for step in range(len(self.hashes)):
server = self.owner[self.hashes[(start + step) % len(self.hashes)]] # % wraps around
if server not in found: # skip the other points of a server we already have
found.append(server)
if len(found) == n:
break
return found
type Ring struct {
vnodes int
hashes []uint64 // sorted positions on the ring
owner map[uint64]string // position -> server
members map[string]bool // servers on the ring
}
func NewRing(vnodes int) *Ring {
return &Ring{vnodes: vnodes, owner: map[uint64]string{}, members: map[string]bool{}}
}
func hash(s string) uint64 {
sum := sha256.Sum256([]byte(s))
return binary.BigEndian.Uint64(sum[:8])
}
func (r *Ring) Add(server string) {
if r.members[server] {
return // adding twice would store the points twice
}
r.members[server] = true
for i := 0; i < r.vnodes; i++ {
pos := hash(fmt.Sprintf("%s#%d", server, i))
r.owner[pos] = server
r.hashes = append(r.hashes, pos)
}
sort.Slice(r.hashes, func(a, b int) bool { return r.hashes[a] < r.hashes[b] })
}
func (r *Ring) Remove(server string) {
if !r.members[server] {
return
}
delete(r.members, server)
kept := r.hashes[:0]
for _, pos := range r.hashes {
if r.owner[pos] == server {
delete(r.owner, pos)
continue
}
kept = append(kept, pos)
}
r.hashes = kept
}
// Get returns the server that owns key, or "" when the ring is empty.
func (r *Ring) Get(key string) string {
if len(r.hashes) == 0 {
return ""
}
x := hash(key)
i := sort.Search(len(r.hashes), func(i int) bool { return r.hashes[i] > x })
if i == len(r.hashes) {
i = 0 // wrap around
}
return r.owner[r.hashes[i]]
}
const crypto = require("node:crypto");
// 48 bits are plenty, and a JavaScript number holds them exactly
const h = (s) => crypto.createHash("sha256").update(s).digest().readUIntBE(0, 6);
class Ring {
constructor(vnodes = 150) {
this.vnodes = vnodes;
this.points = []; // { pos, server }, sorted by pos
this.members = new Set();
}
add(server) {
if (this.members.has(server)) return; // adding twice would store the points twice
this.members.add(server);
for (let i = 0; i < this.vnodes; i++) {
this.points.push({ pos: h(`${server}#${i}`), server });
}
this.points.sort((a, b) => a.pos - b.pos);
}
remove(server) {
if (!this.members.delete(server)) return;
this.points = this.points.filter((p) => p.server !== server);
}
get(key) {
if (this.points.length === 0) throw new Error("no servers");
const x = h(key);
let lo = 0;
let hi = this.points.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.points[mid].pos > x) hi = mid;
else lo = mid + 1;
}
return this.points[lo % this.points.length].server; // % wraps around
}
}
using System.Buffers.Binary;
using System.Security.Cryptography;
using System.Text;
public sealed class Ring
{
private readonly int _vnodes;
private readonly List<(ulong Pos, string Server)> _points = new(); // sorted by Pos
private readonly HashSet<string> _members = new();
public Ring(int vnodes = 150) => _vnodes = vnodes;
private static ulong Hash(string s) =>
BinaryPrimitives.ReadUInt64BigEndian(SHA256.HashData(Encoding.UTF8.GetBytes(s)));
public void Add(string server)
{
if (!_members.Add(server)) return; // adding twice would store the points twice
for (int i = 0; i < _vnodes; i++) _points.Add((Hash($"{server}#{i}"), server));
_points.Sort((a, b) => a.Pos.CompareTo(b.Pos));
}
public void Remove(string server)
{
if (_members.Remove(server)) _points.RemoveAll(p => p.Server == server);
}
public string Get(string key)
{
if (_points.Count == 0) throw new InvalidOperationException("no servers");
ulong x = Hash(key);
int lo = 0, hi = _points.Count;
while (lo < hi)
{
int mid = (lo + hi) / 2;
if (_points[mid].Pos > x) hi = mid; else lo = mid + 1;
}
return _points[lo % _points.Count].Server; // % wraps around
}
}
add ignores a server that is already on the ring (adding twice would store its points twice, and one remove would leave orphaned positions that no server owns). These are sketches: a real one protects the ring with a read-write lock (reads are far more common than changes), and swaps in a whole new ring instead of editing the live one. Remove is linear in the number of points, which is fine for a handful of changes a day.
Try it yourself: add 10 servers, map 100 000 keys, add an 11th server and count how many keys changed owner. You should see about 9 to 10 %, and every changed key should now belong to the new server. (The exact figure changes with the server names: I saw 8.9 % in one run and 10.0 % in another, against the ideal 9.1 %.)
5. Replication: more than one owner
Real systems keep several copies of each key. With a ring, the natural rule is: the owner is the first server clockwise, and the replicas are the next servers clockwise after it, skipping virtual nodes that belong to a server already chosen (otherwise two copies could land on the same machine). Amazon's Dynamo calls this the preference list [2]. In the Python version above, get_n(key, 3) returns it: the owner and the next two distinct servers. Cassandra works the same way. If a server dies, the next one in the list already has a copy and takes over, and the ring gives each remaining server a small, equal share of the extra work.
6. When the ring is not the answer
Consistent hashing has several relatives, and knowing why they exist is a good interview answer.
| Technique | Idea | Good at | Limits |
|---|---|---|---|
| Ring with vnodes | Described above | Arbitrary joins and leaves, replication | Memory for the points; load still not perfectly even |
| Rendezvous (highest random weight) hashing | For a key, compute hash(key, server) for every server and pick the highest | Very simple, even, no ring to store | Lookup costs O(N); fine for tens of servers [3] |
| Jump consistent hash | A tiny function (a few lines, no memory) maps a key to a number from 0 to N − 1 | Very even and extremely fast | Servers must be numbered 0..N−1; you can only add or remove at the end, so it suits sharded storage, not caches where any node may fail [4] |
| Hash slots (Redis Cluster) | Fixed 16 384 slots; each key maps to a slot with CRC16; a table assigns slots to servers | Explicit, easy to rebalance one slot at a time | You manage the slot table [5] |
| Bounded loads | A ring, but a server that is already above a load cap passes the key to the next one | Prevents hot spots on skewed data | Extra bookkeeping [6] |
| Maglev hashing | A lookup table filled so that every server gets an equal share and few entries change | Load balancers: fast lookups and very even load | Table rebuilt on change; a bit of disruption on removal [7] |
Two of them are only a few lines (Python again; h is the hash function from above):
def rendezvous(key, servers):
# every server "bids" for the key; the highest bid wins, and a removed server only loses its own keys
return max(servers, key=lambda s: h(f"{s}|{key}"))
def jump_hash(key, buckets):
# key is a 64-bit integer; returns a bucket number from 0 to buckets - 1
b, j = -1, 0
while j < buckets:
b = j
key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF
j = int((b + 1) * (1 << 31) / ((key >> 33) + 1))
return b
Note that none of them fixes a hot key: if one key gets half of all requests, whoever owns it is overloaded, however well the keys are spread. For that you replicate the key, cache it in front, or split it into several keys.
7. Where you meet it
- Distributed caches: memcached clients commonly use a ring (known as ketama) so that losing a cache node does not empty the whole cache.
- Databases: Dynamo, Cassandra, and Riak partition data on a ring.
- Load balancing: sending the same user or key to the same backend (so its local cache is warm), without keeping a table of assignments.
- CDNs and object stores: choosing which node stores which object.
- Sharding in your own app: a library decides which database holds a customer. URL shorteners and caches use it for this.
8. Questions interviewers like to add
"Why not just keep a table of key → server?"
A table works when the number of keys is small, but then it is itself a big shared piece of state that every client needs and that must stay consistent. Hashing needs no shared state beyond the list of servers.
"How do clients learn that a server joined?"
The server list has to reach every client: through a coordination service (ZooKeeper, etcd, Consul), a gossip protocol (Dynamo and Cassandra), or a config pushed out. For a short time clients may disagree about the ring. A read can then go to the old owner and miss. That is acceptable for a cache. For a database, the system must hand data over carefully: copy first, switch ownership after.
"What happens to the data on a server that is removed?"
On a crash, replicas have it. On a planned removal, the departing server streams its ranges to the new owners before leaving. When a server is added, it must fetch its ranges from the current owners, and until it has them the old owners still answer.
"How many virtual nodes?"
Enough that the spread is acceptable. In my tests 100 to 200 per server left the busiest server 12 to 25 % above average, and about 1 000 brought it to 4 to 11 %. More points even out load further, at the price of memory and slower rebuilds. Weight them by machine size, and measure on your own keys, because the result changes from run to run.
"How do you handle a server that is slow, not dead?"
The ring does not know about health. Add health checks and remove failing servers from the ring (or skip them and use the next replica). To avoid flapping, require several failed checks before removal.
9. Things to mention in an interview
- Start with
hash mod Nand show why it breaks: nearly everything moves. - Draw the ring and say a key goes to the next server clockwise.
- Say that only about 1/N of the keys move when a server changes.
- Bring up uneven spread yourself, and fix it with virtual nodes and weights.
- Mention replication along the ring, and how clients find out about changes.
- Name an alternative (rendezvous, jump hash, hash slots) and when you would prefer it.
Quick recap
hash(key) mod Nmoves almost every key when N changes.- A ring assigns each key to the next server clockwise; adding or removing a server moves only about 1/N of the keys.
- One point per server gives uneven load; 100 to 200 virtual nodes per server make it nearly even.
- Lookup is a binary search over a sorted array of positions.
- Replicas are the next distinct servers along the ring.
- Rendezvous hashing, jump hash, hash slots and Maglev solve the same problem with different trade-offs.
- A hot key is not a hashing problem; cache or split it.
Sources
- Karger et al., Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, STOC 1997. The original idea.
- DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. The ring, virtual nodes, and preference lists.
- Wikipedia, Rendezvous hashing. Thaler and Ravishankar's highest random weight scheme.
- Lamping and Veach, A Fast, Minimal Memory, Consistent Hash Algorithm, 2014. Jump consistent hash.
- Redis documentation, Redis cluster specification. The 16 384 hash slots.
- Mirrokni, Thorup and Zadimoghaddam, Consistent Hashing with Bounded Loads, 2016.
- Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, NSDI 2016.
Practise this topic: System Design System Design › Distributed systems