Data Systems
Consistent Hashing
When adding or removing nodes from a distributed system, naive hashing forces massive key redistribution. Consistent hashing minimizes key movement, making scaling operations efficient.
- Hash Ring â A circular key space mapped to nodes
- Virtual Nodes â Multiple positions per physical node for balance
- Minimal Disruption â Only K/N keys move when a node is added
Consistent hashing is the foundation of distributed caches, databases, and CDNs.
The Problem with Simple Hashing
With standard modulo hashing, adding a new node invalidates nearly every key's mapping.
Hash Ring
Consistent hashing maps both keys and servers onto a circular ring using a hash function.
How Keys Are Assigned
Each key hashes to a position on the ring. Travel clockwise from that position until you hit a server â that server owns the key.
Impact of Node Changes
Virtual Nodes
Physical servers are mapped to multiple positions on the ring to improve load distribution.
Load Distribution Analysis
Range-Based Consistent Hashing
Some systems use range-based approaches for ordered data.
Real-World Applications
| System | Use Case | Virtual Nodes |
|---|---|---|
| Amazon DynamoDB | Partition assignment | ~1000 per partition |
| Apache Cassandra | Data distribution | 256 per node |
| Memcached | Client-side sharding | Configurable |
| Akamai CDN | Request routing | millions of positions |
| Riak | Distributed KV store | 64 per node |
Implementation Considerations
Replication
Consistent hashing naturally supports replication by assigning keys to V consecutive servers clockwise on the ring.
Practice Exercises
-
Calculation: Draw a hash ring with 4 servers at positions 10, 50, 120, 200 (ring size 256). Where do keys at positions 5, 55, 150, 210 map to?
-
Design: Design a consistent hashing scheme for a cache cluster with 5 servers having weights 3, 2, 2, 1, 1. How many virtual nodes should each server have?
-
Analysis: Compare the key redistribution when removing a node with 100 vs 1000 virtual nodes. What are the trade-offs?
-
Implementation: Implement a simple consistent hash ring in Python with virtual nodes. Test that adding/removing nodes moves approximately 1/N of keys.
What to Learn Next
-> Data Partitioning Horizontal partitioning, range vs hash partitioning, and rebalancing.
-> Data Replication Leader-follower, multi-leader, and conflict resolution.
-> CAP Theorem Consistency models, availability, and partition tolerance.
-> Databases SQL vs NoSQL, indexing, replication, and sharding.
-> Load Balancing Distribution algorithms and L4 vs L7 load balancing.
-> Distributed Consensus Raft, Paxos, and leader election algorithms.