Back to System design
Consistent Hashing
mediumYou have 10 cache servers and millions of keys. You need a rule that says which server holds which key.
ScaleO(log V) lookup with sorted ring (V = vnodes); ring size 2^32 typical
StorageO(V) tokens stored; usually small (KB-MB)
Key Concepts
1
The obvious rule is
hash(key) % 10. It works until a server dies. Now the rule is % 9, and almost every
key maps somewhere new — about 90% of your keys move. For a cache, that means nearly every request
misses at once. For a database, you are copying nine tenths of your data during an outage.90% of your keys movehash(key) % 10% 9
2
Consistent hashing is the fix. When a server joins or leaves, only about
1/N of the keys move.1/N
3
How the ring works. Picture a circle numbered 0 to 4 billion. Hash each server to a point on the
circle. Hash each key to a point too. A key belongs to the first server you meet going clockwise from it.
How the ring works.
4
Now remove a server. Only the keys sitting between it and the previous server need a new home, and they go
to the next server clockwise. Everything else stays exactly where it was.
5
Add a server and the same thing happens in reverse: it takes a slice from one neighbour, and nobody else
is affected.
6
Why virtual nodes are needed. Ten random points on a circle are not evenly spaced. Some gaps are three
times larger than others, so one server ends up holding three times its share.
Why virtual nodes are needed.
7
The fix is to place each server at many points — typically 100 to 200 — instead of one. Its share is now
the sum of many small slices, and those even out. The gap between the busiest and quietest server drops
from roughly 3x to about 10%.
8
Virtual nodes help when a server dies, too. Its 200 slices are spread across all the survivors, rather
than dumping everything on one unlucky neighbour.
9
What it does not fix. Consistent hashing spreads keys evenly. It does not spread traffic
evenly. One extremely popular key lives on exactly one server, no matter how good the hashing is. If 30%
of requests are for one key, that server is overloaded and rebalancing will not help.
What it does not fix.keystraffic
10
The fixes for that are different: store the hot key under several names and pick one at random, or cache
it in the application's own memory for a few seconds. Knowing this limit is usually what an interviewer is
listening for.
11
Where it is used. Cache fleets deciding which server holds a key. Databases like Cassandra and DynamoDB
deciding which servers hold the copies of a row. Load balancers that want the same user to land on the same
server without a shared session store.
Where it is used.
12
What the interviewer is probing.
What the interviewer is probing.
13
1. "How do you decide which server holds a key?" Probing: whether you get past modulo. Stalls:
"hash mod the number of servers." Moves up: that works until the count changes, then ~90% of keys move;
the ring keeps it to about
1/N.1. "How do you decide which server holds a key?"1/N
14
2. "Why virtual nodes?" Probing: whether you know the plain ring is uneven. Stalls: "Better
distribution." Moves up: random points cluster, so one server can hold 3x its share; 100-200 points each
brings that within about 10%.
2. "Why virtual nodes?"
15
3. "A server is added. What moves?" Probing: precision. Stalls: "Some keys." Moves up: the keys
in the arc it claims, taken from one neighbour per virtual node — about
1/N in total.3. "A server is added. What moves?"1/N
16
4. "One key gets 30% of the traffic." Probing: the limit. Stalls: "Consistent hashing balances
it." Moves up: it balances keys, not traffic; one key lives on one server. Replicate it under several
names, or cache it locally.
4. "One key gets 30% of the traffic."
17
5. "How do database copies work on the ring?" Probing: beyond caching. Stalls: "Copy it
somewhere." Moves up: walk clockwise and use the next few distinct servers, skipping extra virtual nodes
of a server that already has a copy.
5. "How do database copies work on the ring?"
Components
- Ring data structure (sorted token list / TreeMap).
- Token assignment policy (random, hashed-id, weighted, manual).
- Replica placement strategy (simple-walk, rack-aware, datacenter-aware).
- Bootstrap / decommission protocol to migrate keys.
- Gossip / membership service to keep nodes' rings in sync.
- Hot-key handling — bounded loads, key replication, or local in-process cache.
Keys moved, worked
Keys 1,000,000 Servers before 10 Servers after 11 (one added)
Modulo hashing (hash % N)
A key stays only if hash % 10 == hash % 11
Keys that stay ~91,000 (~9%)
Keys that move ~909,000 (~91%) Consistent hashing
Keys move only from the arc the new server claims.
Expected share 1/11 = ~9% moved
Keys moved ~91,000 Ratio 909,000 / 91,000 = 10x less
movement On a cache fleet this is the difference between
- a 91% miss rate for as long as it takes to refill, and
- a 9% miss rate that recovers in seconds.On a data store it is the difference between copying 909 GB and 91 GB out of a terabyte, while already one node down.
Virtual nodes and distribution
Plain ring, 10 servers, one position each
Positions are 10 random points on a circle. The gaps follow an
exponential distribution, so the largest arc is typically ~3x the
smallest.
Load spread (busiest : quietest) ~3 : 1 With virtual nodes
Each server takes V positions; its share is the sum of V arcs, and
the sum of many random arcs concentrates around the mean. V = 10 spread ~1.6 : 1
V = 100 spread ~1.15 : 1
V = 200 spread ~1.10 : 1 Cost of more vnodes
Ring size 10 servers x 200 = 2,000 entries
Lookup binary search over ring = O(log 2000) ~ 11
comparisons
Memory 2,000 x ~16 B = 32 KB
-- negligible, which is why 100-200 is the common default. Removal behaviour
Plain ring: one neighbour absorbs everything the dead server held.
With vnodes: its 200 slices are spread across all survivors, so no
single machine takes a 2x jump.Failure modes in production
Hot key, evenly hashed
Symptom: one server saturates; key distribution looks perfect.
Cause: consistent hashing balances keyspace, not request volume.
Fix: bounded-load variant, replicate the hot key across several
positions, or cache it in the client for a few seconds.
Ring disagreement between clients
Symptom: two clients route the same key to different servers; cache
hit rate halves.
Cause: clients holding different membership views during a change.
Fix: version the ring, distribute membership through one control
plane, and make a miss survivable rather than assuming agreement. Vnode count changed in a deploy
Symptom: a mass remap that looks like data loss.
Cause: V is part of the hash placement; changing it moves everything.
Fix: treat V as immutable for the life of the cluster, or migrate
deliberately with dual reads. Weak hash function
Symptom: clustering on the ring despite vnodes.
Cause: a hash with poor avalanche (e.g. naive string hashes).
Fix: use a well-distributed non-cryptographic hash such as MurmurHash
or xxHash; cryptographic strength is unnecessary, uniformity is not.