Chapter 16: Data Partitioning and Consistent Hashing
Consistent Hashing
Problem: simple hash(key) % N breaks when you add/remove servers (almost all keys remap). Consistent hashing minimizes remapping.
Hash Ring (0 to 2^32):
Server A (pos 1000)
/
────●────────────●──── Server B (pos 5000)
/ \
● ●── Server C (pos 8000)
\ /
────●────────────────
Key X (pos 3000) → maps to next server clockwise = Server B
Add Server D at pos 4000:
Key X (pos 3000) → now maps to Server D (only keys between A and D move!)
Most keys stay on same server. Minimal disruption.
Virtual Nodes
Problem: with few servers, distribution is uneven. Solution: each server gets multiple positions (virtual nodes) on the ring.
// Server A gets positions: hash("A-1"), hash("A-2"), ..., hash("A-150")
// Server B gets positions: hash("B-1"), hash("B-2"), ..., hash("B-150")
// More virtual nodes = more even distribution
// Used by: Cassandra, DynamoDB, Memcached, Redis ClusterWhen to Use Consistent Hashing
- Distributed caches (which cache server holds this key?)
- Database sharding (which shard holds this user?)
- Load balancing (sticky sessions without centralized state)
- CDN (which edge server caches this content?)
Key Takeaways
- Simple modulo hashing: adding/removing servers remaps almost everything
- Consistent hashing: only K/N keys remap (K=keys, N=servers)
- Virtual nodes ensure even distribution across servers
- Used in: Cassandra, DynamoDB, Memcached, Redis Cluster, CDNs