Architectural Breakdown & AnalysisFAANG Aligned
Traditional hashing (hash(key) % N) fails when node count $N$ changes: nearly 100% of keys hash to new servers, invalidating caches and crashing backends.
1. The Hash Ring
- Maps both server IP addresses and item keys onto a shared circular hash space ($0$ to $2^{32}-1$).
- To route a key: locate its position on the ring and move clockwise to the first server node encountered.
2. Node Additions & Removals
- Adding a new Node X only re-allocates keys located between Node X and its immediate counter-clockwise neighbor.
- Only $1/N$ of keys are relocated during node changes.
3. Virtual Nodes (V-Nodes)
- Prevents hotspots by mapping each physical server to 100-200 virtual positions (
ServerA-1,ServerA-2) on the ring. - Ensures uniform load distribution across heterogeneous hardware.
NOTE — Industry Usage
Consistent Hashing powers routing in Apache Cassandra, Amazon DynamoDB, Discord Gateway Routers, and Memcached clients.
Key Architectural Comparison
| Hash Partitioning Scheme | Keys Migrated on Node Add/Remove | Load Distribution Uniformity | Node Failure Impact | Production Standard |
|---|---|---|---|---|
| Naive Modulo (`hash % N`) | $\approx \frac{N-1}{N}$ (almost 100% of dataset). | Clustered hot spots. | Complete cache eviction avalanche. | Single-node only. |
| Naive Consistent Hashing | $\approx \frac{1}{N}$ keys (only neighbor slice). | Poor without uniform ring placement. | Neighbor node absorbs double load. | Academic prototype. |
| Consistent Hashing with V-Nodes | $\approx \frac{1}{N}$ keys (distributed across all nodes). | Excellent (150–250 virtual nodes per server). | Load distributed evenly across all surviving nodes. | Cassandra, DynamoDB, Redis Cluster. |