The previous lesson left a problem hanging: with shard = hash(key) % n, adding a shard remaps almost all your data.
This lesson is about how bad that actually is, and the technique that fixes it — one of the few genuinely clever ideas in distributed systems, and a common interview question.
Watch modulo hashing fail
You have 4 cache servers and route keys with hash(key) % 4.
Traffic grows, so you add a fifth server. Now the same key routes with hash(key) % 5.
Consider a key hashing to 1,000:
- Before:
1000 % 4 = 0→ server 0 - After:
1000 % 5 = 0→ server 0. Unchanged, by luck.
And a key hashing to 1,001:
- Before:
1001 % 4 = 1→ server 1 - After:
1001 % 5 = 1→ server 1. Also unchanged.
Try 1,002:
- Before:
1002 % 4 = 2→ server 2 - After:
1002 % 5 = 2. Fine again.
It looks harmless on small numbers, so let us count properly across the whole key space. A key keeps its home only when h % 4 == h % 5, which happens rarely. Across all keys, roughly 80% move.
| Servers | Keys remapped when adding one |
|---|---|
| 4 → 5 | ~80% |
| 10 → 11 | ~91% |
| 100 → 101 | ~99% |
The pattern is brutal: with n servers, adding one moves about n/(n+1) of all keys. The bigger your cluster, the worse it gets.
For a cache, that means near-total cache miss — every request falls through to the database simultaneously, which is the avalanche from the caching lesson, self-inflicted. For a database, it means migrating almost your entire dataset to add 20% capacity.
The ring
Consistent hashing removes the dependence on n.
Imagine the output of your hash function arranged in a circle, from 0 to some large maximum, with the end wrapping around to the start.
Place the servers on the ring by hashing their names. Place the keys on the ring by hashing the keys. Then apply one rule:
A key belongs to the first server found moving clockwise from the key's position.
Diagram, as text
- Server A pos 10 leads to key: pos 25
- key: pos 25 leads to Server B pos 40
- Server B pos 40 leads to key: pos 60
- key: pos 60 leads to Server C pos 80
The key at position 25 walks clockwise and finds Server B. The key at 60 finds Server C.
Why adding a server is now cheap
Add Server D at position 50.
Which keys move? Only those between Server B (40) and Server D (50) — keys that used to walk past to Server C and now stop at D sooner. Every other key is unaffected, because the server it walks to has not changed.
With n servers, adding one moves roughly 1/n of the keys — not n/(n+1). For 100 servers that is 1% instead of 99%.
The same holds on removal: when a server disappears, only its keys move, to the next server clockwise. Everything else is untouched.
Virtual nodes
The basic ring has a real weakness. With only three servers hashed onto a huge circle, their positions are random and unlikely to be evenly spaced. One server might own 60% of the ring and another 10%.
Worse, when a server is removed, all its keys go to a single successor, which may then be badly overloaded — and if that one falls over, its keys cascade to the next.
The fix is elegant: give each physical server many positions on the ring instead of one.
Server A -> hash("A#1"), hash("A#2"), ... hash("A#150")
Server B -> hash("B#1"), hash("B#2"), ... hash("B#150")Each of those is a virtual node pointing back to a real machine. With 150 virtual nodes per server, the positions interleave and the law of large numbers takes over — each server ends up with a much more even share.
Two benefits follow:
Even distribution. Variance in load drops sharply as virtual node count rises.
Even redistribution. When a server is removed, its 150 virtual nodes are scattered around the ring, so its keys are spread across all remaining servers rather than dumped on one neighbour.
Virtual nodes also let you weight capacity: give a machine with twice the RAM twice as many virtual nodes.
Where you meet it
This is not academic — it is running underneath tools you use.
- Cassandra and DynamoDB place partitions on a ring; adding a node moves a bounded slice of data.
- Memcached clients use consistent hashing so adding a cache server does not wipe the cache.
- CDNs use it to decide which edge server caches which object.
- Load balancers use it for session affinity that survives adding a backend.
The honest limitations
It does not solve hot keys. Consistent hashing distributes keys evenly, but one enormously popular key still lands on one server. That is the hot-spot problem from the previous lesson, and it needs the same fixes: compound keys, salting, or dedicated handling.
Redistribution still costs something. Moving 1% of a 50TB dataset is still 500GB across the network.
Ordering is lost. Like any hash-based scheme, adjacent keys land nowhere near each other, so range queries must consult every node.
Replication needs a rule. For redundancy you typically store each key on the next N distinct servers clockwise — "distinct" matters, or virtual nodes can put all your replicas on one physical machine.
Check your understanding
Common mistakes
Implementing the ring without virtual nodes. With few servers the distribution is visibly lopsided, and removal dumps everything on one neighbour.
Too few virtual nodes. A handful barely improves on the naive ring. Real implementations use 100–500 per server.
Hashing the server's IP address. Then changing a machine's address moves all its data. Hash a stable logical name instead.
Assuming it prevents all data movement. It minimises movement; it does not eliminate it.
Reaching for it when you do not need it. If your shard count is fixed and you have no plan to change it, hash % n is simpler. Consistent hashing earns its complexity when membership changes — which, at scale, it always does.
Practice
You are told consistent hashing 'solves hot spots'. Explain precisely what it does and does not solve, using a concrete example of each.
Write your own answer first, on paper or in a note. Then compare.
Show a hint
Distinguish an uneven number of keys from an uneven amount of traffic to one key.
Show a strong answer
What it solves: rebalancing cost, and uneven key distribution.
Example: a cache cluster grows from 10 to 11 nodes. With modulo hashing nearly every key relocates and the cache is effectively emptied. With a ring plus virtual nodes, roughly 1/11 of keys move to the new node and the rest stay put — so capacity is added without a stampede against the database. This is the problem it was designed for, and it solves it well.
What it does not solve: skew in traffic to a single key.
Example: a product goes viral and one key receives 40% of all reads. Consistent hashing places that key on exactly one node, as it must — that is what a deterministic mapping means. The node holding it saturates while the others idle. No amount of virtual nodes helps, because virtual nodes spread keys, and here the problem is one key.
What actually addresses that case: replicating the hot key to several nodes and reading from any of them, adding a small local cache in front of the cluster so most requests never reach it, or appending a random suffix so one logical key becomes several physical ones — each with its own cost in write complexity.
The distinction worth carrying: consistent hashing is about the cost of change, not about fairness of load.
A node in your ring is twice as powerful as the others. How do you give it proportionally more work, and what breaks if you instead just point more traffic at it manually?
Write your own answer first, on paper or in a note. Then compare.
Show a hint
The ring decides placement from positions, so influence the positions.
Show a strong answer
The intended mechanism is weighting by virtual node count. If ordinary nodes get 150 positions on the ring, give this one 300. It then owns roughly twice as much arc, so roughly twice as many keys, so roughly twice the traffic and twice the storage — automatically, and consistently for every client that computes the ring.
The reason this works is that placement remains a pure function of the ring. Every client independently computes the same answer for a key, with no coordination and no lookup.
What breaks if you route manually instead. Suppose you leave the ring alone and add application logic that sends extra traffic to the powerful node.
- Reads and writes disagree. A write placed by the ring lands on node A; a read redirected by your logic looks at node B and misses. For a cache this is silent and merely wasteful; for a store it is data that appears to have vanished.
- Every client must implement the same override, identically, forever — including clients written later by other teams. The moment one does not, keys become unreachable.
- Rebalancing breaks. When a node is added or removed, the ring recomputes correctly and your manual overlay does not, so the exception has to be re-derived by hand each time.
The general principle: placement must have exactly one authority. Weighting inside the ring keeps it there; routing around the ring creates a second one that will disagree.
Key takeaways
- With
hash(key) % n, adding one server remaps about n/(n+1) of all keys — 91% at ten servers. For a cache that is a self-inflicted avalanche; for a database it is a full migration. - Consistent hashing places servers and keys on a ring, and a key belongs to the first server clockwise.
- This means adding or removing a server moves only about 1/n of keys, because a key's location depends on its neighbour rather than the total count.
- A naive ring distributes unevenly, and removal dumps all keys onto one successor. Virtual nodes — many ring positions per machine — fix both, and allow capacity weighting.
- It powers Cassandra, DynamoDB, memcached clients and CDNs.
- It does not solve hot keys, and it destroys key ordering, so range queries still fan out.
Next: some work should not happen inside the request at all. Handing it to a queue changes what your system can survive.
Further reading
- David Karger et al., "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" (STOC 1997) — the original paper.
- Giuseppe DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007) — virtual nodes and weighting in a production system.
- John Lamping and Eric Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm" (Google technical report, 2014) — jump consistent hashing.
- Ion Stoica et al., "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications" (SIGCOMM 2001) — the ring as a lookup structure.
- Vahid Mirjalili and Sebastian Raschka, "Bounded Loads with Consistent Hashing" (Google research blog, 2017) — capping how much any one node may own.