Consistent Hashing Basic
Core Concepts of Consistent Hashing
Traditional hashing uses the modulo operator: hash(key) % N, where N is the number of server nodes. This behaves poorly when servers are added or removed, since almost all keys re-map to new servers, causing a massive cache stampede.
Consistent hashing solves this problem by using a shared circular hash ring (from 0 to $2^{32}-1$).
1. Step-by-Step Distribution
1. Hash the Servers: Hash server IPs and map them to positions on the ring.
2. Hash the Keys: Hash client keys and map them on the same ring.
3. Route Requests: To locate a key's server, travel clockwise from the key's position until you hit the first server node.
2. Virtual Nodes (V-Nodes)
To prevent hot spots (uneven distribution), we hash each physical server multiple times using offsets (e.g., Node1#1, Node1#2). This guarantees a highly uniform key distribution across all active physical servers.
3. Real-World Case Studies & Corporate Optimization
- Amazon: Documented in their famous Dynamo paper, Amazon uses consistent hashing to partition data across a ring of storage nodes. Adding or removing storage nodes only shifts keys of direct neighbors, preventing write outages.
- Netflix: Utilizes consistent hashing in their distributed databases (Apache Cassandra and EVCache clusters) to partition user profiles globally, guaranteeing seamless playback resumes when servers shift.
- Microsoft: Azure Cosmos DB uses consistent hashing internally to distribute logical partition key spaces over physical servers automatically, enabling horizontal throughput scaling.
- Eternal (Zomato): Uses consistent hashing algorithms across their sharded database clusters and memcached/Redis fleets to route queries for food orders and restaurant reviews, ensuring load balance across database nodes.
4. References & Tech Blogs
Prerequisites
- Modular Math Basics
Evaluation Workbench
Test consistent hashing and rollout allocation in real time. Simulate how request routing decides if a client sees a new feature or replica.