Day 12: Consistent Hashing - Scale Caches with Less Key Movement
Subham Chand
Sep 2, 20265 min read3 views
Consistent Hashing: Change the Cluster Without Scrambling Every Key
Learning outcome: By the end of Day 12, you will be able to place servers and keys on a hash ring, find a key's owner, and identify exactly which keys move when a server joins.
This lesson is part of Korshub's System Design in 30 Days roadmap.
Advertisement
The problem with changing the bucket count
A common first attempt distributes a key with a formula such as hash(key) mod N, where N is the current number of servers. When N changes, the formula changes for every key. Many keys can therefore receive a different result even though only one server was added or removed.
That churn matters for a distributed cache. A key sent to a new owner may not be warm there yet, so requests fall through to the backing store until the cache fills again. Consistent hashing reduces this movement by changing the mapping model.
The ring mental model
Imagine the hash space as a circle:
Hash each server to a position on the ring.
Hash each key into the same space.
Walk clockwise from a key.
The first server you reach owns that key.
If you pass the largest position, wrap around to the beginning.
When a server joins, it claims only the interval between the previous server and its own position. Keys outside that interval keep their existing owners.
Consistent hashing is a family of algorithms, not one universal implementation. Production systems may use virtual nodes, fixed partitions, replication, or implementation-specific balancing strategies.
Worked example: six keys on a 0-99 ring
Assume an integer ring from position 0 through 99.
Initial servers:
Server | Ring position |
|---|---|
A | 20 |
B | 50 |
C | 80 |
Keys: 10, 25, 40, 55, 70, 85.
Using the first-server-clockwise rule:
Key position | Initial owner | Reason |
|---|---|---|
10 | A | A at 20 is first clockwise |
25 | B | B at 50 is first clockwise |
40 | B | B at 50 is first clockwise |
55 | C | C at 80 is first clockwise |
70 | C | C at 80 is first clockwise |
85 | A | The walk wraps around to A at 20 |
Now add server D at position 65. D claims the interval (50, 65].
Key position | Before | After | Moved? |
|---|---|---|---|
10 | A | A | No |
25 | B | B | No |
40 | B | B | No |
55 | C | D | Yes |
70 | C | C | No |
85 | A | A | No |
Exactly one of six keys moves, while five stay with their previous owners. As a percentage, the moved share in this deliberately small example is:
1 / 6 x 100 = 16.7%, rounded to one decimal place.
The percentage is specific to these toy positions. It is not a guarantee for every real cluster. The general benefit is limited, local remapping when membership changes.
Why virtual nodes matter
One physical server at one ring position can receive a large or unlucky interval. A common technique is to give each physical server multiple virtual positions. Those virtual nodes spread ownership around the ring, which can improve balance and make node changes smoother.
Virtual nodes do not remove every operational risk. Teams still need to watch for:
hot keys that receive disproportionate traffic;
uneven capacity between servers;
replication and failover behavior;
membership updates reaching clients consistently;
cache warm-up pressure on the backing database.
Try this today
Use the same six keys, but place D at position 45 instead of 65.
Identify D's newly claimed interval.
List every key inside that interval.
Compare each key's owner before and after the change.
Completed example you can copy
D at 45 sits between A at 20 and B at 50, so D claims (20, 45]. Keys 25 and 40 fall inside that interval. Both move from B to D. Keys 10, 55, 70, and 85 keep their original owners.
Two independent checks agree:
Interval check:
(20, 45]contains 25 and 40.Owner comparison: only 25 and 40 change from B to D.
Common mistakes
Treating the ring as a physical network
The ring is a logical mapping of a hash space. Servers do not need to be arranged physically in a circle.
Forgetting wrap-around
A key after the last server position belongs to the first server on the ring.
Assuming one position per server always balances load
Real key distributions and traffic can be skewed. Virtual nodes or fixed partitions are commonly used to improve distribution.
Claiming zero remapping
Consistent hashing minimizes movement; it does not eliminate it. A new node must acquire some keys, and a removed node's keys need new owners.
Ignoring hot keys
Even a balanced key count does not guarantee balanced traffic. One popular key can dominate a server's workload.
Knowledge check
How do you find a key's owner on the ring? Walk clockwise from the key to the first server, wrapping around if necessary.
Which interval does a newly added server claim? The interval after the previous server and through the new server's position.
In the worked example, which key moves when D joins at 65? Only key 55.
Why use virtual nodes? To distribute each physical server across multiple ring positions and reduce uneven ownership.
Does consistent hashing solve hot keys? No. Hot-key traffic still requires monitoring and mitigation.
Download the notes
day-12-handwritten-notes.pdfContinue learning with Korshub
If you want to connect hashing, caching, replication, sharding, and failover into complete interview-ready designs, explore Rocking System Design. Course details can change, so check the current course page for the latest information.
Navigation
Previous: Day 11 - Strong vs Eventual Consistency
Roadmap: System Design in 30 Days
Next lesson: Day 13 - Message Queues
