Intermediate LevelSoftware Engineering Principles
How does Consistent Hashing work in distributed caching and database sharding (DynamoDB, Cassandra)?
❓ Interview Prompt: Explain Consistent Hashing, Hash Ring, Virtual Nodes, minimizing data remapping during node additions/removals, and load balancing.
Standard modulo hashing ('hash(key) % N') causes 99% of keys to remap whenever a node is added or removed from a $N$-node cluster!
Consistent Hashing Solution:
Maps both keys and server nodes onto a virtual Hash Ring ($0$ to $2^{32}-1$):
•
A key is assigned to the first server node encountered moving clockwise on the ring.
•
Node Addition/Removal: When a node is added or removed, ONLY $1/N$ of keys are remapped, preserving cache stability!
•
Virtual Nodes: Assigns multiple ring locations per physical node to ensure uniform load distribution.
Code Implementation Example
typescript
// Conceptual Consistent Hash Ring placement lookup
class HashRing {
getNodeForKey(key: string): string {
const hash = computeHash(key);
// Find first server node clockwise on Hash Ring >= hash
return this.ring.find(node => node.hash >= hash)?.name || this.ring[0].name;
}
}💡Finding target node on a Consistent Hashing ring.
🎯 Interview Key Takeaway
Use Consistent Hashing in distributed cache clusters to minimize key remapping when adding or removing server nodes.
#Consistent Hashing#Distributed Systems#Sharding#Intermediate
Back to all Software Engineering Principles Questions→