Understanding Consistent Hashing in Distributed Systems

The Partitioning Problem in Distributed Databases

In a distributed database or caching cluster, data keys must be distributed across multiple physical server nodes.

A simple approach is modulo-based partitioning: $\text{Node} = \text{Hash}(key) \pmod N$ where $N$ is the number of servers in the cluster.

While simple, this method is highly inefficient when scaling. If a server is added or removed, $N$ changes, which changes the output of the modulo operation for almost every key. This triggers a massive data migration across the cluster, overloading the network and causing cache misses.

---

The Consistent Hashing Ring

Consistent Hashing resolves this by mapping both servers (nodes) and keys to a shared 360-degree virtual circle, or hash ring.

1. Ring Space Mapping: The hash ring represents a range of integer values (e.g. from 0 to $2^{32}-1$ using MD5 or SHA-1).
2. Server Placement: Physical servers are hashed based on their identifier (e.g., IP address) and placed at specific coordinates on the ring.
3. Key Assignment: To store or look up a key, the system hashes the key and finds its position on the ring. It then moves clockwise until it encounters the first server. That server is responsible for storing the key.

graph TD
    subgraph Hash Ring Coordinates
        NodeA[Node A at 12:00] --> Key1[Key 1 clockwise to Node B]
        Key1 --> NodeB[Node B at 04:00]
        NodeB --> Key2[Key 2 clockwise to Node C]
        Key2 --> NodeC[Node C at 08:00]
        NodeC --> NodeA
    end

---

Adding and Removing Nodes

When a node is added or removed, consistent hashing minimizes the number of keys that must be migrated.

• Removing a Node: If Node B fails, only the keys that were clockwise of Node A and assigned to Node B are affected. These keys are reassigned to Node C (the next node clockwise), while keys on other parts of the ring remain untouched.
• Adding a Node: If a new node is inserted between Node B and Node C, it only takes over a subset of keys from Node C. Other nodes do not need to migrate any data.

---

Virtual Nodes (Vnodes)

A basic consistent hashing ring has one main drawback: data can be distributed unevenly, leading to “hotspots” where one server handles significantly more traffic than others.

To solve this, consistent hashing implementations use Virtual Nodes (Vnodes).

Instead of mapping a physical server to a single location on the ring, the system hashes multiple virtual representations of the server (e.g., Node-A#1, Node-A#2, Node-A#3) to distribute them across the ring.

This offers two main benefits:

1. Balanced Distribution: The keys are distributed more evenly across all physical servers.
2. Fair Rebalancing: If a physical server fails, its virtual nodes are spread across the ring, so its load is shared among all remaining servers rather than shifting entirely to a single neighbor.