Consistent Hashing
Consistent Hashing is a distributed hashing scheme that operates independently of the number of servers or objects in a distributed hash table. It solves the problem of massive data reorganization when scaling up or down.
1. The Problem: Simple Hashing (Modulo)
In a traditional load balancing or sharding scenario, you might assign a key to a server using:
server_index = hash(key) % number_of_servers
- Scenario: You have 3 servers. Key 'A' hashes to 0, 'B' to 1, 'C' to 2.
- Failure: If Server 1 goes down, you now have 2 servers. The formula becomes
hash(key) % 2. - Result: Almost every key maps to a new server index. The cache is completely invalidated, causing a massive spike in database load (Thundering Herd).
2. The Solution: The Hash Ring
Consistent hashing maps both the data (keys) and the servers (nodes) to the same circular value space (e.g., 0 to $2^{32}-1$).
- Map Servers: Hash the server IP or ID to place it on the ring.
- Map Keys: Hash the data key to place it on the ring.
- Assign: To find the server for a key, move clockwise around the ring until you find a server.
3. Adding/Removing Nodes
- Adding a Node: Only keys that fall between the new node and its predecessor need to be remapped to the new node.
- Removing a Node: Only the keys belonging to the removed node are remapped to the next node clockwise.
- Impact: On average, only $k/n$ keys need to be remapped (where $k$ is total keys, $n$ is total nodes). This is minimal compared to the modulo approach.
4. Virtual Nodes (VNodes)
If servers are unevenly distributed on the ring, some might get too much data (hotspots). To fix this, we use Virtual Nodes.
- Instead of mapping a server to 1 point on the ring, we map it to multiple points (e.g., 100 positions) using different hash functions (e.g.,
ServerA_1,ServerA_2...). - This ensures a more uniform distribution of keys across physical servers.
5. Use Cases
- Distributed Caches: Memcached clients.
- NoSQL Databases: Apache Cassandra, Amazon DynamoDB, Riak.
- Load Balancers: Distributing requests based on session IDs.
programming/distributed-systems programming/hash-tables programming/load-balancing