# Consistent Hashing Explained: Add a Server Without Moving Everything (2026)
> With key mod N, adding one server moves most keys. Consistent hashing puts servers and keys on a ring so only about 1/(N+1) of keys move. A simulation shows the ring, why virtual nodes are needed, and what consistent hashing does not fix.
*Source: https://www.infowok.com/consistent-hashing-explained/ · Sukhveer Kaur · Published October 20, 2026*
---
A cache cluster has three servers and is doing fine. Traffic grows, so the team adds a fourth. Within seconds, three out of every four requests miss the cache and fall through to the database, which was sized for a cache that worked. The dashboard turns red.
Nothing was broken. The routing rule, `key mod N`, simply gave a different answer for most keys the moment N changed. This lesson shows a routing rule that does not: consistent hashing. It is one of the few system design ideas you can explain with a circle and a pencil.
- [Database sharding and replication explained](/database-sharding-and-replication-explained/), where `hash mod N` first appears.
- [Caching strategies](/caching-strategies/), since caches are the classic home of this technique.
Going from N to N+1 servers with `key mod N` moves N out of every N+1 keys, as the [sharding lesson](/database-sharding-and-replication-explained/) showed. From 3 to 4 servers, call it **75% of keys changing owner.** The ideal would move only the new server's fair share.
- Hash servers and keys onto the same ring. A key belongs to the first server found going clockwise.
- Adding a server takes keys only from the arc just before it. Removing one hands its arc to the next server.
- One point per server gives a lopsided ring. Virtual nodes, many points per server, even it out.
- Replicas go on the next distinct servers clockwise.
- Consistent hashing fixes data movement, not hot keys.
Place servers and keys on a ring, say which server owns a key, show that adding a server moves only one arc, and explain why virtual nodes are needed.
## The Problem With Key Mod N
Apache Cassandra's documentation describes the naive scheme in one sentence. In [naive data hashing](https://github.com/apache/cassandra/blob/trunk/doc/modules/cassandra/pages/architecture/dynamo.adoc), you allocate keys to buckets by taking a hash of the key modulo the number of buckets, and "adding a single node might invalidate almost all of the mappings".
For a cache that is a stampede, and for a sharded database it is a migration of most of the data. The sharding lesson measured it: N out of every N+1 keys move. Consistent hashing is built so that the number is closer to 1 out of every N+1.
## The Ring
Picture the output of a hash function as a circle. The smallest value sits at the top and the values grow clockwise until they wrap around to the top again. Now do two things:
1. **Hash each server** onto the circle, using its name or address.
2. **Hash each key** onto the same circle.
A key belongs to **the first server you meet going clockwise** from the key's position. Envoy's ring hash load balancer works exactly this way: each host is mapped onto a circle by hashing its address, and each request is routed by [finding the nearest host clockwise](https://github.com/envoyproxy/envoy/blob/main/docs/root/intro/arch_overview/upstream/load_balancing/load_balancers.rst) around the ring.
A key past the last server simply wraps around to the first, which is why k6 above belongs to server A. Nobody keeps a table of key locations. Anyone who knows the servers' positions can work out the owner.
## Adding a Server
Add server D between B and C in the picture above. Which keys change owner?
Only the keys between B and D. Those used to belong to C, because C was the first server clockwise. Now D sits in front of them and takes them. Every other key still meets the same server first.
Removing a server is the mirror image. Its keys go to the next server clockwise, and nobody else is touched.
### How much really moves?
A simulation is more convincing than an argument. Assume ten servers, 100,000 keys, an MD5 hash, and 100 points per server on the ring. Then add an eleventh server and count the keys whose owner changed.
| Routing rule | Keys that moved (10 to 11 servers) |
|---|---|
| `key mod N` | 90.8% |
| Hash ring | 10.4% |
| Ideal minimum | 9.1% (1 in 11) |
The ring is close to the ideal, and every moved key went to the new server. The `mod N` figure matches the sharding lesson's formula, 10 out of 11.
## The Catch: A Lopsided Ring
Three evenly placed servers make a tidy circle. Real hashes are random, so real servers land at random spots, and the arcs between them differ in length. A server with a long arc owns more keys.
Assume ten servers, one point each, and 100,000 keys. How much more than an even share does the busiest server hold?
In the simulation, about **three times** the even share, while the quietest held 0.13 times. The fix is to give each server many points on the ring, called virtual nodes.
Many small arcs average out. Cassandra's documentation makes the same point: with evenly spaced tokens and a small number of physical nodes, incremental scaling is difficult because there are [no token selections for new nodes that leave the ring balanced](https://github.com/apache/cassandra/blob/trunk/doc/modules/cassandra/pages/architecture/dynamo.adoc), and virtual nodes let a single physical node take many positions, so one added node takes many small pieces from many neighbours.
Virtual nodes also handle machines of different sizes. Give a larger server more points and it takes a larger share.
## The Whole Thing in Code
The ring is a sorted list and a binary search. This is the code used for the simulation above:
```python
import bisect, hashlib
def h(s):
d = hashlib.md5(s.encode())
x = d.hexdigest()[:8]
return int(x, 16)
def build(servers, v=100):
ring = sorted(
(h(f"{s}#{i}"), s)
for s in servers
for i in range(v)
)
ps = [p for p, _ in ring]
return ps, ring
def owner(ring, key):
ps, pairs = ring
p = h(key)
i = bisect.bisect_left(ps, p)
i %= len(pairs)
return pairs[i][1]
```
`bisect_left` finds the first point at or after the key, and `i %= len(pairs)` is the wrap-around. That is the entire idea. Production systems add membership changes and failure handling on top.
## Replicas on the Ring
Copies of a key, called replicas, go on the next servers clockwise. In Cassandra, with a replication factor of 3, you hash the key and ["walk" the ring in a clockwise fashion until we encounter three distinct nodes](https://github.com/apache/cassandra/blob/trunk/doc/modules/cassandra/pages/architecture/dynamo.adoc), and those are the replicas.
With virtual nodes the next three points might belong to the same physical server, so the walk skips points until it has three different machines. Cassandra's documentation says replicas are always chosen to be distinct physical nodes by skipping virtual nodes if needed.
## Other Ways to Do It
Ring hashing is not the only answer to "add a server without moving everything".
| Approach | How it limits movement |
|---|---|
| Hash ring with virtual nodes | only the arcs next to new points move |
| Fixed slots (Redis Cluster) | keys map to 16384 slots, and whole slots move between nodes |
| Lookup table (Maglev) | a fixed-size consistent-hashing table, 65537 entries in Envoy's version |
Redis Cluster's [specification](https://github.com/redis/docs/blob/main/content/operate/oss_and_stack/reference/cluster-spec.md) maps keys with `CRC16(key) mod 16384` and gives each master a subset of the slots. Resharding moves slots, not an arbitrary share of keys. Envoy offers [Maglev](https://github.com/envoyproxy/envoy/blob/main/docs/root/intro/arch_overview/upstream/load_balancing/load_balancers.rst) as a drop-in replacement for ring hash, with a fixed table size of 65537.
In an interview, naming the ring and virtual nodes is enough. Mentioning that Redis moves fixed slots is a bonus.
## What Consistent Hashing Does Not Fix
- **Hot keys.** A hot key lands on one server, however even the ring is. Cache it, split it or replicate it.
- **The data still has to move.** The new server owns an arc, but someone must copy that arc's data to it.
- **Everyone must agree on the ring.** Clients or a coordinator need the same list of servers, or two parties will route the same key differently.
- **Failures.** A dead server's keys fall to its neighbour, which can overload it.
## Try It: Walk the Ring
A ring has positions 0 to 99. Server A sits at 10, B at 40 and C at 70. Six keys hash to 5, 25, 45, 65, 85 and 95.
1. Which server owns each key? (First server clockwise, wrapping from 99 to 0.)
2. Add server D at 55. Which keys move?
3. What fraction of the keys moved?
Look at the gap before D, between B at 40 and D at 55. Only keys in that gap used to belong to the next server, C.
```text
Before (first clockwise):
5 -> A 25 -> B
45 -> C 65 -> C
85 -> A 95 -> A
After adding D at 55:
45 -> D others the same
1 of 6 keys moved
```
Key 45 sits between B (40) and D (55), so D now meets it first. Keys 85 and 95 wrap past 99 and land on A at 10, as before. With `key mod N`, adding a fourth server would typically move about three quarters of the keys.
Expect: "How do you add a cache server without a stampede?" Say: "Place servers and keys on a hash ring so a key belongs to the first server clockwise. Adding a server moves only the arc just before it. I would use many virtual nodes per server to even out load, and I would warm the new server or let it fill gradually." Then say what it does not fix: hot keys.
## Check Yourself
About 91% with key mod N (10 out of 11) and about 9 to 10% with a ring, which is roughly 1 in 11.
Random positions make arcs of different lengths, and a longer arc owns more keys. Virtual nodes give each server many points, so the arcs average out.
The first server on the ring. Positions wrap around from the top, so the key goes to the lowest-positioned server.
Start at the key's position and walk clockwise, collecting servers until you have three distinct physical machines, skipping extra virtual nodes of a machine you already have.
Draw a circle on paper, mark three servers and five keys, and decide the owners. Then add a fourth server and cross out only the keys that moved. Do it once more tomorrow with different positions, from memory.
## In One Picture
```text
Ring servers + keys, one circle
Owner first server clockwise
Add moves one arc (~1/(N+1))
Skew fix with many points each
Replica next distinct servers
Limit hot keys still hot
```
**Hash onto a ring, give each server many points, and only the arc next to a change moves.**
- **Back to sharding:** [database sharding and replication](/database-sharding-and-replication-explained/) shows where this routing rule is used.
- **The cache this protects:** [caching strategies](/caching-strategies/) covers what happens when the cache misses.
- **Where servers are spread:** [load balancers explained](/load-balancers-explained/) covers hash-based routing for requests.
Next in the course: [monolith vs microservices](/monolith-vs-microservices/), the start of the async and messaging module.