Consistent Hashing: Scaling Without the Chaos
In a distributed system, you need a way to map data keys to specific servers. The naive approach—server = hash(key) % N—works until you need to add or remove a server (N changes). When it does, nearly every key maps to a different server, causing a "cache miss storm" or massive data migration.
Consistent Hashing solves this.
1. The Hash Ring
Imagine all possible hash values form a circle (a ring).
- Servers on the Ring: Each server is hashed and placed at a specific point on this ring.
- Keys on the Ring: Each data key is hashed and placed on the same ring.
- The Mapping: To find which server stores a key, you move clockwise from the key's position until you hit the first server.
2. Why it Scales
When a new server joins:
- Only the keys between the new server and its counter-clockwise neighbor need to move.
- On average, only
1/Nof the keys are redistributed, compared to nearly 100% in the naive approach.
3. Virtual Nodes (vnodes)
In the real world, servers aren't identical, and a simple ring can lead to "hot spots" (unbalanced load).
- The Solution: Instead of placing a server once on the ring, we place it multiple times (e.g., 200 "virtual nodes") using different hash functions.
- Benefits:
- Load Balancing: Data is distributed more uniformly.
- Heterogeneity: A powerful server can be assigned more vnodes than a weaker one.
- Speedy Recovery: If a node fails, its load is spread across many peers instead of just one.
4. Real-World Applications
- Cassandra & DynamoDB: Use consistent hashing to partition data across the cluster.
- Akamai CDN: Uses it to distribute content across edge servers.
- Discord: Uses it to route millions of users to the correct gateway servers.
Summary
Consistent Hashing is one of the most elegant algorithms in distributed systems. By decoupling the number of servers from the data mapping, it enables the elastic, "infinite" scale that modern cloud infrastructure requires.
