HLD · Distribution
Consistent Hashing
Distribute keys across nodes with minimal remapping when nodes join or leave.
hash(key) % 10, adding an 11th cache node reshuffles most keys; with a hash ring, only keys near the new node need to move.1. The problem with simple hash mod
With server = hash(key) % N, changing N changes the calculation for most keys. Adding one server can therefore cause many cache misses and a large data move.
Example: A Memcached cluster adds a node. If most product keys move to new locations at once, requests miss the cache and can overload the product database.
2. Consistent hashing idea
Hash servers and keys onto a ring (0 to 2³²-1). Key belongs to first server clockwise on the ring.
When a server is added/removed, only keys between that server and its predecessor move — not all keys.
3. Virtual nodes (vnodes)
Each physical server gets many points on the ring (e.g., 150 virtual nodes) for even distribution.
Without vnodes, uneven arc lengths cause hot spots.
Example: Three servers with 100 virtual nodes each get many positions around the ring, which usually spreads randomly distributed keys more evenly than one position per server.
4. Where it's used
- Distributed caches and cache clients, such as Memcached clients
- CDNs routing requests to edge groups
- Distributed databases and Dynamo-style partition placement
- Load balancers (consistent hash on user_id for sticky routing)
Important distinction: Redis Cluster uses 16,384 fixed hash slots rather than a classic consistent-hashing ring, though both approaches reduce full-cluster remapping.
5. Walkthrough example
Ring with servers A, B, C. Key "user:42" hashes to position 75 → clockwise first server is B.
Server D joins at position 70. Only keys between 70–75 (previously on B) move to D. Keys on A and C unchanged.
6. Replication on the ring
A ring-based store can place replicas on the next distinct clockwise nodes for fault tolerance. The exact placement rule depends on the system.
Server B fails → copies stored on C and D keep the data available.
7. Hot spots still possible
Viral key "celebrity:1" hashes to one vnode. Fix: Application-level sharding of hot keys, random suffix celebrity:1:0..7 spread across nodes.
8. Interview comparison
| Method | On node add/remove |
|---|---|
| hash % N | ~all keys remap |
| Consistent hash | About one node's share remaps when distribution is balanced |
| Range partitioning | Manual split; risk of hot range |
Quick revision
- Problem: mod N reshuffles everything on scale.
- Solution: Hash ring; key → next server clockwise.
- Vnodes: Even load per physical machine.
- Redis Cluster: Uses fixed hash slots, not a classic hash ring.
- Used in: Cache clusters, Cassandra, LB stickiness.
- Hot keys: Still need app-level splitting.