What is Consistent Hashing and Why is it Used?
Learn what consistent hashing is, why it beats modulo hashing for scaling, and how virtual nodes balance load.
Expected Interview Answer
Consistent hashing maps both keys and servers onto the same circular hash ring so that when a server is added or removed, only the keys between it and its neighbor need to move, instead of nearly every key remapping as with simple modulo hashing.
In naive hashing, a key's server assignment is computed as hash(key) % N, so changing N (adding or removing a server) reshuffles almost every key-to-server mapping, causing a cache stampede. Consistent hashing instead places both servers and keys onto positions on a fixed-size ring (using a hash function), and a key is owned by the first server found walking clockwise from its position. Adding or removing one server only affects the keys in the arc between it and its immediate neighbor, leaving the rest of the ring untouched. Real implementations add virtual nodes — each physical server gets many positions on the ring — to smooth out uneven load distribution that a single point per server would otherwise cause.
- Only ~1/N of keys remap when a node changes
- Avoids cache stampedes on scaling events
- Virtual nodes balance load across heterogeneous servers
- Core to distributed caches, CDNs, and sharded databases
AI Mentor Explanation
Consistent hashing is like assigning fielding positions around a circular boundary rope instead of numbering fielders 1 to 11 and reassigning everyone whenever a player is subbed. Each fielder and each likely ball-landing spot gets a position on the rope, and a ball is fielded by whichever player sits clockwise-nearest to where it lands. When a fielder is subbed out, only the balls that would have landed in their small arc need a new fielder — everyone else keeps their original zone. This is far better than renumbering all eleven positions and reshuffling the whole field for one substitution.
Step-by-Step Explanation
Step 1
Hash servers onto the ring
Compute a hash for each server (or many virtual node hashes per server) and place them on a fixed circular hash space.
Step 2
Hash keys onto the same ring
Compute the same hash function for each key to find its position on the ring.
Step 3
Assign key to next clockwise server
A key belongs to the first server encountered walking clockwise from the key's position.
Step 4
Handle node changes locally
Adding or removing a server only remaps the keys in the arc adjacent to that node, not the whole ring.
What Interviewer Expects
- Explain the ring structure and clockwise-nearest assignment rule
- Contrast with modulo hashing and its cache-stampede problem on resize
- Mention virtual nodes and why they balance uneven load
- Name real systems that use it: DynamoDB, Cassandra, memcached client libraries, CDNs
Common Mistakes
- Describing plain hash(key) % N and calling it consistent hashing
- Forgetting virtual nodes, leading to a naive claim that load is always perfectly balanced
- Not explaining why only ~1/N of keys move on a node change
- Confusing consistent hashing with simple round-robin load balancing
Best Answer (HR Friendly)
“Consistent hashing places both servers and data on a circular ring so that when I add or remove a server, only a small slice of the data needs to move instead of almost everything. It is why distributed caches and databases can scale up or down without a massive, disruptive reshuffle.”
Code Example
import bisect
import hashlib
class ConsistentHashRing:
def __init__(self, nodes=None, virtual_nodes=100):
self.virtual_nodes = virtual_nodes
self.ring = {}
self.sorted_keys = []
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}")
self.ring[h] = node
bisect.insort(self.sorted_keys, h)
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):
h = self._hash(key)
idx = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
return self.ring[self.sorted_keys[idx]]Follow-up Questions
- Why do real implementations use hundreds of virtual nodes per physical server?
- How does consistent hashing compare to rendezvous (highest random weight) hashing?
- What happens to availability if a node fails but is not yet removed from the ring?
- How would you use consistent hashing to build a distributed cache client?
MCQ Practice
1. What is the main problem consistent hashing solves compared to hash(key) % N?
With modulo hashing, changing N reshuffles almost all key-to-server mappings; consistent hashing only remaps keys in the arc near the changed node.
2. What problem do virtual nodes solve in consistent hashing?
A single point per physical server can create very uneven arcs; many virtual node positions per server average out the load distribution.
3. In consistent hashing, which server owns a given key?
A key belongs to the nearest server clockwise from its position on the hash ring.
Flash Cards
What structure does consistent hashing place servers and keys on? — A circular hash ring.
How much of the keyspace remaps when one server is added or removed? — Only the keys in the arc adjacent to that node — roughly 1/N of all keys.
Why are virtual nodes used? — To balance load evenly, since a single ring position per server can create very uneven arcs.
Name a real system that uses consistent hashing. — DynamoDB, Cassandra, or memcached client-side sharding.