Back to 20 Concepts
distributed-data • Advanced
Consistent Hashing & Virtual Nodes (Dynamo Ring)
Consistent Hashing maps both servers and data keys to a 2^32-1 hash ring. When a node is added or removed, only K/N keys are migrated (where K is total keys and N is servers), preventing cluster-wide cache invalidation.
Intuitive Mental Model
The Carousel of Coat Checkers: Instead of re-assigning all 1,000 coats whenever 1 coat checker takes a lunch break, you place coat checkers evenly on a rotating carousel. Coats are handed to the next clockwise checker. If one leaves, only their coats shift to the neighbor.
Architecture Blueprint & CodeProduction Standard
class ConsistentHashRing {
private ring: Map<number, string> = new Map();
private sortedKeys: number[] = [];
private vNodes: number = 100; // Virtual nodes per server
addServer(server: string) {
for (let i = 0; i < this.vNodes; i++) {
const hash = this.hash(server + "#" + i);
this.ring.set(hash, server);
this.sortedKeys.push(hash);
}
this.sortedKeys.sort((a, b) => a - b);
}
getServer(key: string): string {
const hash = this.hash(key);
const idx = this.binarySearch(hash);
return this.ring.get(this.sortedKeys[idx % this.sortedKeys.length])!;
}
}Key Architectural Takeaways
- •Minimal Key Migration: Only K/N keys move when scaling out or handling node failure, compared to ~100% in key % N modulo hashing.
- •Virtual Nodes: Solves non-uniform key distribution and hot-spotting by mapping each physical server to 100+ virtual points across the ring.
- •Used in production: Apache Cassandra, Amazon DynamoDB, Akamai CDN, Discord gateway routing.
Common Architectural Pitfall
Using naive hash(key) % N modulo routing in distributed caches; adding a single server causes 100% cache misses across the fleet (thundering herd).
Production Best Practice
Always use Consistent Hashing with virtual nodes for distributed state and cache partitioning.