The algorithm that makes distributed caches and NoSQL databases possible. One clever idea that turns “moving 100% of your data” into “moving 1/N of it.”
Prerequisites: Sharding, Caching Time to read: ~20 minutes
You have 4 cache servers. You distribute keys the obvious way:
server = hash(key) % 4
Even distribution, O(1) lookup, no coordination. Perfect — until a server dies.
Now you have 3 servers, so hash(key) % 3:
key "user:1001" hash = 1001
% 4 = 1 → server 1
% 3 = 2 → server 2 ← moved
key "user:1002" hash = 1002
% 4 = 2 → server 2
% 3 = 0 → server 0 ← moved
key "user:1003" hash = 1003
% 4 = 3 → server 3
% 3 = 1 → server 1 ← moved
📐 Going from N to N−1 servers remaps roughly (N−1)/N of all keys. From 4 to 3, about 75% of your keys now point at the wrong server.
The consequence is worse than it sounds. Every one of those keys is now a cache miss. Your cache hit rate collapses from 95% to ~25% instantly, and the database — sized to handle 5% of read traffic — receives 75%. It falls over. Which makes everything slower, which triggers more traffic, and you have an outage caused by losing one cache node.
The same problem applies to sharded databases, except there the data doesn’t just miss — it has to be physically moved, terabytes of it, while serving traffic.
Imagine a clock face — but instead of 12 hours, it has 2³² positions. Both servers and keys get placed on this circle by hashing.
The rule: each key belongs to the first server found going clockwise.
0
╭─────┴─────╮
[Server A] │
╱ │
key1 ● ● key2
╱ ╲
... [Server B]
╲ ╱
key3 ● ● key4
╲ ╱
[Server C] ──────╯
Now remove Server B. Which keys move?
Only the keys that were between Server A and Server B. They now walk clockwise past B’s old position to Server C. Every other key is completely unaffected — key3, key4, and everything mapping to A or C stays exactly where it was.
That’s the entire idea. Adding or removing a node only disturbs keys in one arc of the circle, instead of reshuffling everything.
📐 The result: removing one of N nodes moves ~1/N of the keys, not (N−1)/N.
4 servers, lose one:
Modulo hashing: ~75% of keys move → cache hit rate collapses
Consistent hashing: ~25% of keys move → 75% of the cache still works
With 100 servers, losing one moves 1% of keys. The difference is between an outage and a non-event.
import hashlib
from bisect import bisect_right
class ConsistentHash:
def __init__(self, nodes=None, virtual_nodes=150):
self.virtual_nodes = virtual_nodes
self.ring = {} # hash position -> node name
self.sorted_keys = [] # sorted positions, for binary search
for node in (nodes or []):
self.add_node(node)
def _hash(self, key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def add_node(self, node):
for i in range(self.virtual_nodes):
h = self._hash(f"{node}#{i}") # V positions per physical node
self.ring[h] = node
self.sorted_keys.append(h)
self.sorted_keys.sort()
def remove_node(self, node):
for i in range(self.virtual_nodes):
h = self._hash(f"{node}#{i}")
del self.ring[h]
self.sorted_keys.remove(h)
def get_node(self, key):
if not self.ring:
return None
h = self._hash(key)
idx = bisect_right(self.sorted_keys, h) # first position clockwise
if idx == len(self.sorted_keys):
idx = 0 # wrap around the circle
return self.ring[self.sorted_keys[idx]]
Lookup is O(log N) via binary search over the sorted positions — with a few thousand entries, that’s microseconds. Fast enough that it’s never the bottleneck.
🚨 Plain consistent hashing has a serious flaw, and knowing it separates people who’ve read about it from people who understand it.
With only a few nodes, hash positions land unevenly on the circle:
Server A at position 100
Server B at position 110 ← A and B are adjacent
Server C at position 3,000,000,000
C owns nearly the entire circle. A and B own almost nothing.
Random placement of 3 points on a circle is not an even division. You can easily end up with one node holding 60% of the keys.
And a second problem: when a node dies, all of its keys go to exactly one successor — which now has double the load and probably falls over too. A cascading failure.
Virtual nodes fix both. Each physical server is placed at many positions (typically 100–200):
Server A → positions from hash("A#0"), hash("A#1"), ... hash("A#149")
Server B → positions from hash("B#0"), hash("B#1"), ... hash("B#149")
Now:
📐 The variance improvement:
| Virtual nodes per server | Load standard deviation |
|---|---|
| 1 | ~100% (wildly uneven) |
| 10 | ~30% |
| 100 | ~10% |
| 200 | ~7% |
🎙️ Mentioning virtual nodes unprompted is the differentiator here. Many candidates can describe the ring; far fewer explain why it doesn’t work without vnodes.
For a distributed database, you don’t want one copy — you want N.
The rule: walk clockwise and take the next N distinct physical nodes.
key → position P
1st node clockwise = primary
2nd distinct node = replica 1
3rd distinct node = replica 2
🚨 “Distinct physical” matters — with virtual nodes, the next three positions might all belong to the same machine, which would give you three copies on one box. Real implementations skip duplicates.
Better still, they’re rack- and AZ-aware: skip positions until you find a node in a different
failure domain, so your three replicas aren’t in one rack that shares a power supply. Cassandra calls
this a NetworkTopologyStrategy, and it’s the difference between surviving a rack failure and not.
This ring-with-replication is exactly how Dynamo, Cassandra, and Riak place data. → Quorums
| System | How |
|---|---|
| Memcached clients | Client-side consistent hashing across the cache fleet |
| Cassandra / DynamoDB / Riak | Data placement and replica selection on the ring |
| Redis Cluster | 🚨 Not consistent hashing — 16,384 fixed hash slots (see below) |
| CDN / Akamai | Which edge server caches which object |
| Envoy, Nginx | ring_hash / hash load balancing for cache locality |
| Google Maglev | A consistent-hashing variant for connection stability across LB fleet changes |
Redis Cluster’s approach is worth knowing as the alternative: instead of a hash ring, it defines
16,384 fixed hash slots. Keys map to slots (CRC16(key) % 16384), and slots map to nodes.
⚖️ It achieves the same goal — adding a node moves slots, not all keys — with different trade-offs: simpler to reason about and to administer (you can move exactly the slots you choose), but requires an explicit slot→node mapping that must be distributed to clients, whereas the ring is computed independently by anyone who knows the node list.
This is essentially the same “virtual shards” idea from Sharding. If an interviewer asks about rebalancing, either answer is good, and knowing both is better.
🚨 Hot keys. This is the most important limitation and a common follow-up question.
Consistent hashing distributes keys evenly. It does nothing about load being uneven. One celebrity’s profile key maps to exactly one node, and if that key gets a million requests per second, that node saturates regardless of how beautifully balanced your ring is.
Fixes (none of which are consistent hashing): replicate the hot key with a random suffix and read a random copy; cache it in-process on every client; or serve it from a CDN. → Hot Keys
It doesn’t move data for you. The ring says where a key belongs. For a cache, that’s enough — misses repopulate naturally. For a database, adding a node means physically transferring data while serving traffic, which is its own substantial problem (streaming, throttling, and consistency during the move).
It doesn’t give you consistency. Different clients may have different views of the node list during a membership change, and briefly disagree about where a key lives. Real systems solve this with gossip or a coordination service.
| Gain | Cost | |
|---|---|---|
| Consistent hashing vs modulo | Only ~1/N keys move on membership change | More complex; O(log N) lookup instead of O(1) |
| More virtual nodes | Even distribution; failure load spreads | More memory for the ring; slightly slower lookup |
| Replication on the ring | Fault tolerance | Must skip duplicate physical nodes and respect failure domains |
| Fixed slots (Redis style) | Explicit, controllable migration | Must distribute the slot map to clients |
| Client-side ring | No extra hop | Every client needs the node list and must agree on it |
% N is a problem. Be able to state the ~(N−1)/N figure and, more importantly,
the consequence: a cache hit rate collapse that takes down the database.1. Prove the modulo problem. This is a five-minute exercise with a memorable result:
import hashlib
def h(key):
return int(hashlib.md5(key.encode()).hexdigest(), 16)
keys = [f"user:{i}" for i in range(10000)]
moved = sum(1 for k in keys if h(k) % 4 != h(k) % 3)
print(f"modulo: {moved / len(keys):.0%} of keys moved") # ~75%
2. Compare with a ring. Implement the ConsistentHash class above, build a ring with 4 nodes,
record where every key lands, remove one node, and count how many moved. It’ll be ~25%.
3. See why virtual nodes matter. Build the ring with virtual_nodes=1 and count keys per node.
Then try 10, then 150. Print the distribution each time:
from collections import Counter
for v in (1, 10, 150):
ring = ConsistentHash(["A", "B", "C", "D"], virtual_nodes=v)
counts = Counter(ring.get_node(k) for k in keys)
print(v, dict(counts))
With v=1 you’ll likely see something like 60/25/10/5. With v=150 it’ll be close to even. This
single output makes virtual nodes intuitive in a way no explanation does.
4. Simulate a node failure’s load impact. With v=1, remove a node and see which single node
absorbed all its keys. With v=150, see the load spread across all remaining nodes.
hash(key) % N a problem when N changes, and what's the real-world consequence?