What is Consistent Hashing and Why Do Databases Use It?
Learn how consistent hashing minimizes data movement during resharding, with the ring model and virtual nodes explained.
Expected Interview Answer
Consistent hashing maps both shard keys and shard servers onto the same circular hash space, so each key is owned by the next server found clockwise on the ring, which means adding or removing one shard only remaps the keys between it and its neighbor instead of nearly all keys in the system.
In a plain hash-modulo scheme, changing the shard count from N to N+1 changes almost every key's modulo result, forcing a near-total data reshuffle. Consistent hashing avoids this by placing servers at positions on a ring (often using multiple virtual nodes per physical server to smooth out distribution) and assigning each key to the nearest server clockwise from its hash position. When a server is added or removed, only the keys that fall in the affected arc of the ring move, typically an average of K/N keys for K keys and N servers, leaving the rest of the mapping untouched. This makes consistent hashing the standard technique behind resharding in distributed databases, caches, and load balancers.
- Minimizes data movement when shards are added or removed
- Avoids the near-total reshuffle of plain modulo hashing
- Virtual nodes smooth out uneven load across physical servers
- Widely reusable for caching, load balancing, and sharding alike
AI Mentor Explanation
Imagine seating every player and every dressing-room attendant around a circular ground boundary by a scrambled ID, and each player is served by the nearest attendant found walking clockwise. If one attendant leaves, only the players between that spot and the next attendant need reassigning, everyone else keeps their same attendant. Consistent hashing works exactly this way: servers and keys sit on a ring, and removing a server only shifts the small arc of keys it used to own, not the whole boundary.
How Consistent Hashing Limits Remapping on Shard Changes
Shard A (ring position 10)
- owns keys hashed in (prev, 10]
Shard B (ring position 45)
- owns keys hashed in (10, 45]
Shard C (ring position 80)
- owns keys hashed in (45, 80]
Step-by-Step Explanation
Step 1
Hash servers onto a ring
Map each shard server (often via multiple virtual nodes) to a position on a fixed circular hash space.
Step 2
Hash each key
Compute the hash of each shard key to place it at a position on the same ring.
Step 3
Assign by clockwise lookup
Each key belongs to the first server found walking clockwise from the key's position.
Step 4
Remap only on change
Adding or removing a server only shifts the keys in the adjacent arc, leaving the rest of the ring intact.
What Interviewer Expects
- Clear explanation of the ring structure and clockwise ownership rule
- Understanding of why plain modulo hashing causes near-total reshuffles
- Awareness of virtual nodes and their role in smoothing distribution
- Ability to state the approximate K/N keys-moved guarantee
Common Mistakes
- Confusing consistent hashing with simple hash-modulo sharding
- Forgetting to mention virtual nodes for load smoothing
- Not explaining why only an arc of keys moves, not all keys
- Assuming consistent hashing eliminates all rebalancing work
Best Answer (HR Friendly)
“Consistent hashing places both servers and data on a circular hash space, so each piece of data belongs to the next server going clockwise. The big benefit is that adding or removing a server only reshuffles the small slice of data next to it, instead of reshuffling almost everything the way simple modulo-based hashing would.”
Code Example
-- Ring positions (0-359 degrees) for shard servers
-- shard_A -> 40, shard_B -> 150, shard_C -> 300
function getShardForKey(key) {
const pos = hash(key) % 360;
const ring = [ [40, 'shard_A'], [150, 'shard_B'], [300, 'shard_C'] ];
for (const [ringPos, shard] of ring) {
if (pos <= ringPos) return shard;
}
return ring[0][1]; // wrap around to the first server
}
-- Removing shard_B only remaps keys in (40, 150] to shard_C;
-- keys owned by shard_A and shard_C are untouched
SELECT * FROM Sessions WHERE session_id = 'abc123';Follow-up Questions
- What are virtual nodes and why are they added to the ring?
- How does consistent hashing compare to plain hash-modulo sharding for resharding cost?
- How do distributed caches like memcached use consistent hashing?
- What happens to availability while keys are being remapped after a node change?
MCQ Practice
1. What problem does consistent hashing primarily solve?
Plain modulo hashing remaps nearly all keys when the shard count changes; consistent hashing limits remapping to a small arc.
2. In consistent hashing, which server owns a given key?
Ownership is determined by walking clockwise from the key's ring position to the nearest server.
3. Why are virtual nodes commonly added in consistent hashing?
Multiple virtual node positions per physical server prevent any single server from owning a disproportionately large arc.
Flash Cards
What is consistent hashing? — A technique that maps servers and keys onto a ring, so each key is owned by the next server clockwise.
Why is consistent hashing better than modulo hashing for resharding? — It only remaps keys in the affected arc instead of nearly all keys.
What is a virtual node? — A duplicated ring position for a physical server, used to smooth out load distribution.
Roughly how many keys move when a server is added? — About K/N keys, for K total keys and N servers, versus nearly all keys in modulo hashing.