How Consistent Hashing with Virtual Nodes Minimizes Cache Key Remapping
Build a deterministic SHA-256 hash ring with virtual replicas and bisect_right clockwise routing.
Consistent hashing maps both storage nodes and keys onto a circular integer ring [0, 2^32 - 1]. A key routes to the first node whose hash position is >= the key's hash (wrapping around to index 0). Adding or removing a node among N nodes remaps only K/N keys on average instead of ~100% under hash(key) % N.
Interactive Runnable CodeSandbox
ConsistentHashRing with Virtual Replicas
Expected Key Migration & Load Variance Bound
Assigning V virtual replicas per physical node reduces load standard deviation inversely with sqrt(V).
Step-by-Step Implementation Breakdown
Place V Virtual Nodes per Physical Host on the [0, 2^32) Ring
With only 3 physical points on a circle, arc lengths vary wildly. Using 100-200 virtual nodes per server interleaves arcs uniformly.
Use Binary Search (bisect_left) with Wrap-Around to Index 0
Maintain a sorted array of ring positions. If bisect_left returns len(ring), wrap around to index 0.
Production Edge Cases & Interview Traps
- For replication factor R > 1, walk clockwise until you collect R distinct physical nodes (skipping virtual nodes belonging to the same host).
Frequently Asked Questions
How do heterogeneous servers with 2x RAM get 2x traffic on a hash ring?
Assign virtual node counts proportional to hardware capacity (e.g., 200 vnodes for a 64GB node vs. 100 vnodes for a 32GB node).