# 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$).

1.  **Map Servers:** Hash the server IP or ID to place it on the ring.
2.  **Map Keys:** Hash the data key to place it on the ring.
3.  **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]]