What is Consistent Hashing?
Understand consistent hashing, the hash ring, virtual nodes, and why it minimizes key remapping when servers scale in distributed systems.
Expected Interview Answer
Consistent hashing is a distribution technique that maps both data keys and servers onto the same hash ring, so that when a server is added or removed only a small fraction of keys need to be remapped instead of nearly all of them.
In naive hashing (like key modulo N servers), adding or removing a single server changes N and reshuffles almost every key, causing a massive cache stampede or data migration. Consistent hashing instead hashes both servers and keys onto a fixed circular ring; each key is owned by the first server encountered walking clockwise from the key’s position. When a server is added, it only takes over the keys immediately preceding it on the ring; when a server is removed, only its keys move to the next server, leaving everyone else untouched. Virtual nodes (multiple ring positions per physical server) are used in practice to smooth out uneven load distribution across servers.
- Minimizes key remapping when servers are added or removed (only ~1/N of keys move)
- Avoids cache stampedes and mass data migration on scaling events
- Enables smooth horizontal scaling of distributed caches and databases
- Virtual nodes give even load distribution across heterogeneous servers
AI Mentor Explanation
Consistent hashing is like assigning fielding positions around the boundary rope in a fixed circular arrangement instead of renumbering everyone every time a fielder is substituted. Each ball hit toward a spot on the rope is caught by whichever fielder is stationed next along the circle clockwise from that spot. If one fielder leaves the field, only the balls that would have gone to them get reassigned to the next fielder around the rope — everyone else keeps their exact position. That minimal, localized reassignment on a fixed ring is exactly what consistent hashing achieves when servers change.
Step-by-Step Explanation
Step 1
Build the ring
Hash each server (and typically several virtual nodes per server) onto positions on a fixed circular hash space.
Step 2
Hash each key
A data key is hashed with the same function to land at some point on that same ring.
Step 3
Walk clockwise to find owner
The key is owned by the first server position encountered walking clockwise from the key’s point.
Step 4
Handle membership changes
Adding/removing a server only affects keys between it and its neighbor on the ring — the rest stay put.
What Interviewer Expects
- Explains the problem with naive modulo hashing (mass remapping on resize)
- Describes the ring concept and clockwise ownership rule
- Mentions virtual nodes and why they smooth load distribution
- Names real-world uses: distributed caches (Memcached/Redis Cluster), DynamoDB, Cassandra
Common Mistakes
- Describing plain hash % N and calling it consistent hashing
- Forgetting to mention virtual nodes and uneven load without them
- Not explaining why only a fraction of keys move on scaling events
- Confusing consistent hashing with content-addressable storage or checksums
Best Answer (HR Friendly)
“Consistent hashing is a way of spreading data across servers so that when you add or remove a server, only a small slice of the data needs to move, instead of almost everything. It works by placing both servers and data on an imaginary circle and assigning each piece of data to the nearest server going around that circle.”
Code Example
class ConsistentHashRing {
constructor(virtualNodesPerServer = 100) {
this.ring = new Map() // hash -> serverId
this.sortedHashes = []
this.vnodes = virtualNodesPerServer
}
addServer(serverId) {
for (let i = 0; i < this.vnodes; i++) {
const h = hash(`${serverId}#${i}`)
this.ring.set(h, serverId)
this.sortedHashes.push(h)
}
this.sortedHashes.sort((a, b) => a - b)
}
removeServer(serverId) {
for (let i = 0; i < this.vnodes; i++) {
const h = hash(`${serverId}#${i}`)
this.ring.delete(h)
}
this.sortedHashes = this.sortedHashes.filter((h) => this.ring.has(h))
}
getServer(key) {
const h = hash(key)
// find first ring position >= h, wrapping around to the start
let idx = this.sortedHashes.findIndex((pos) => pos >= h)
if (idx === -1) idx = 0
return this.ring.get(this.sortedHashes[idx])
}
}Follow-up Questions
- Why do real systems use virtual nodes instead of one ring position per physical server?
- How does consistent hashing compare to rendezvous (highest random weight) hashing?
- How does DynamoDB or Cassandra use consistent hashing for data partitioning and replication?
- What happens to availability while keys are being rebalanced after a node join or leave?
MCQ Practice
1. What is the main problem consistent hashing solves compared to key modulo N hashing?
Naive modulo hashing reshuffles almost all keys when N changes; consistent hashing only remaps a small fraction.
2. What role do virtual nodes play in consistent hashing?
Virtual nodes give each physical server several positions on the ring, smoothing out uneven key distribution.
3. On a consistent hash ring, which server owns a given key?
Consistent hashing assigns each key to the first server position found by walking clockwise from the key’s hash on the ring.
Flash Cards
What is consistent hashing? — A technique that maps servers and keys onto a ring so scaling only remaps a small fraction of keys.
Why not use key % N? — Because changing N reshuffles nearly all keys, causing mass cache misses or data migration.
What are virtual nodes? — Multiple ring positions per physical server, used to distribute load more evenly.
Who owns a key on the ring? — The first server encountered walking clockwise from the key’s hashed position.