Consistent Hashing (Key Rebalancing)

How to add a new server to a distributed database without moving every single piece of data.

The idea

If you have 3 database nodes, a standard way to decide where to put user data is hash(user_id) % 3. But what happens if you add a 4th node? The formula changes to % 4. Suddenly, almost every single user hashes to a different number! You have to move 75% of your data across the network, crashing your system. Consistent Hashing fixes this by placing nodes and data on a circular "ring". When you add a new node, it just slots into the ring and takes a small chunk of data from its immediate neighbor. Only a fraction of data moves.

Step 1: The Ring. 3 Database Nodes (A, B, C) are placed on a circle using their hash. Data keys (dots) are assigned to the first Node they hit moving clockwise.

How it works (The Hash Ring)

Imagine a massive circle of numbers from 0 to 359 (like degrees on a compass). You hash Node A's IP address, and it maps to 0. Node B maps to 120, Node C to 240. When saving user:alice, you hash "alice" and get 150. You walk clockwise around the circle from 150 until you hit a Node (Node C at 240). Alice is saved on Node C.

// Finding the correct node on the Consistent Hash Ring
function getNodeForKey(key, sortedNodesList) {
    let keyHash = hashStringToInt(key);
    
    // Walk clockwise: Find the first node whose hash is greater than the key's hash
    for (let node of sortedNodesList) {
        if (node.hash >= keyHash) {
            return node;
        }
    }
    
    // If we passed the last node, wrap around to the first node (it's a ring!)
    return sortedNodesList[0];
}

Cost

If a new Node D is added at position 60, it sits between Node A (0) and Node B (120). Node D "steals" the data between 0 and 60 that previously belonged to Node B. Node B has to send that data to Node D over the network. However, Nodes A and C do absolutely nothing. Their data doesn't move. You achieved scaling with minimal network cost.

Watch out for