System designCore11 min3 things to try
Consistent hashing
Spread keys over servers so that adding or losing one moves only that server's share of the keys, instead of nearly all of them.
1 · The problem
With hash mod N, adding one server moves almost every key
An online game caches 10 million player profiles on 4 cache servers. To find a profile's server, the game computes hash(player id) % 4. It spreads the profiles evenly, and it works until a tournament weekend, when the team adds a fifth server and the formula becomes % 5.
A key stays put only if its hash gives the same remainder for 4 and for 5, and that is true for 1 hash in 5. The other 80%, 8 million profiles, now map to a server that doesn't have them. Every one of those reads misses and falls through to the database, all at once, at the moment the team was adding capacity. A crowd of requests all hitting the same backend together like that is a thundering herd.
- hash mod N: N ÷ (N + 1)
- Ring: 1 ÷ (N + 1)
With mod N, the bigger the cluster, the more of it moves when it grows. With a ring, only the new server's fair share moves.
The ideal is the opposite: when a fifth server joins, it should take a fifth of the keys, and nothing else should move. That is the promise of consistent hashing.
2 · The idea
Put keys and servers on one ring, and each key belongs to the next server clockwise
Hash the servers and the keys into the same range of numbers, and bend that range into a circle, the hash ring. A key belongs to the first server found by walking clockwise from the key's position. When a server joins, it takes only the keys between itself and the server before it; every other key keeps its owner.
- S1 owns 7 keys
- S2 owns 13 keys
- S3 owns 4 keys
Ring
0
keys moved
Modulo, same change
0
keys moved
A ring numbered 0 to 99 shows the whole rule. Servers A, B and C sit at 10, 45 and 80. Then server D joins at 60:
Key at | Owner before | Owner after D joins at 60 |
|---|---|---|
5 | A, the first server after 5 | A |
30 | B | B |
50 | C | D: the only key that moves |
70 | C | C |
90 | A, wrapping past 99 to 10 | A |
Only the arc from 45 to 60, which used to be C's, changes hands. Losing a server works the same way in reverse: its arc goes to the next server clockwise, and no other key moves.
3 · How a lookup works
Every client finds a key's server with a binary search, and agrees without asking
- Hash the key
To a position on the ring, often a 32-bit or 64-bit number.
- Find the next server position
Clients keep the server positions sorted, so this is a binary search: O(log N).
- Wrap around
A key after the last position belongs to the first server on the ring.
- Place copies
To keep copies, keep walking clockwise to the next distinct servers.
Building a ring and finding a key's owner
const ring = servers
.flatMap((s) => Array.from({ length: vnodes }, (_, i) => ({ pos: hash(`${s}#${i}`), server: s })))
.sort((a, b) => a.pos - b.pos);
function owner(key: string) {
const h = hash(key);
let lo = 0, hi = ring.length; // binary search: first position at or after h
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ring[mid].pos < h) lo = mid + 1; else hi = mid;
}
return ring[lo % ring.length].server; // past the last position: wrap to the first
}Every client with the same server list builds the same ring, so they all agree on every key's owner without asking a coordinator. Databases use the same walk for copies. In Cassandra, a key's replicas are found by walking clockwise from its position until enough distinct nodes are collected; another placement strategy also tries to choose them from different racks.
Walking clockwise for three copies. A second point belonging to B is skipped, or two copies would sit on one machine.
4 · The catch
One point per server gives lopsided arcs, so give each server many
With one point per server, the gaps between points are random. One server can own twice its fair share of the ring and another almost none. Worse, when a server dies its whole arc goes to the single next server clockwise, which suddenly carries two servers' load.
The fix is to give each server many points on the ring, called virtual nodes. A server's share becomes the sum of many small arcs, which averages out, and a dead server's arcs are scattered among all the others:
With points placed at random, a server's share is the sum of v random arcs, and its standard deviation is about 1 ÷ √v of the fair share: ±100% with one point, ±25% with 16, ±6% with 256.
Random placement needs many points to even out: Cassandra used to default to 256 per node. Since version 4.0 it defaults to 16, because it can place them with an allocator that picks positions to balance the ring instead of at random. Virtual nodes also give a simple way to weight servers: a machine with twice the memory gets twice the points.
5 · The alternatives
A ring is one answer to placing keys, and not always the best one
Approach | How it places a key | Good at | Watch out for |
|---|---|---|---|
hash mod N | The remainder of the hash | A server count that never changes | Almost every key moves when the count changes |
Ring with virtual nodes | The next server point clockwise | Caches and stores whose nodes come and go | Needs many points, or an allocator, for even load |
Rendezvous hashing | Score every server for the key and pick the highest | Even spread with no ring to keep | Each lookup scores every server: O(N) |
Jump consistent hash | A short computation from the key and the server count | Even spread, no memory, very fast | Servers are numbered, so only the last can be removed |
Range partitioning | Sorted key ranges, split as they grow | Scans of neighboring keys, like a day's orders | Hot ranges, and a rebalancer to run |
Hashing of any kind scatters neighboring keys, so a scan of everything created today touches every server. Stores that need range scans split by key range instead, and Sharding & partitioning compares the two in depth.
6 · In real systems
Databases, caches and content networks all route keys around a ring
The idea spread from web caching to most systems that spread keys over machines that come and go:
System | What goes on the ring |
|---|---|
Amazon's Dynamo | Keys, with virtual nodes and copies on the next distinct nodes |
Apache Cassandra | Partition keys, with token ranges per node and replicas walked clockwise |
Memcached clients | Cache keys: the client picks the server, so the servers never coordinate |
Akamai's content delivery network | URLs, spreading cached files across many cache servers |
The common thread is the property from the first section: when the cluster changes, only a fair share of the keys moves. For a cache, that is the difference between a fifth of the profiles missing for a while and four fifths of them hitting the database at once.
Check yourself
5 questions
Takeaways
Remember this
- hash mod N moves almost every key when the server count changes; a ring moves only about 1 ÷ (N + 1) of them when a server joins.
- A key belongs to the first server clockwise, and copies go to the next distinct servers.
- One point per server gives lopsided shares and dumps a dead server's load on one neighbor; virtual nodes spread both.
- A server's share varies by about 1 ÷ √v of the fair share with v random points, which is why rings use many points or an allocator.
- Hashing scatters neighboring keys; when range scans matter, partition by key range instead.