Consistent Hashing: The Million Dollar Algorithm

The “Modulo” Problem

In Database Sharding, we used Hash(Key) % N. This works great until you change N.

  • If N goes from 4 to 5, the result of % N changes for almost every key.
  • This triggers a Resharding Storm: 80% of your data must move between servers instantly. Your database crashes.

The Solution: The Ring

Consistent Hashing maps both Data and Nodes onto a circle (0 to 360 degrees).

  1. Map Nodes: Hash the Server IP to place it on the ring.
  2. Map Keys: Hash the User ID to place it on the ring.
  3. Find Owner: To find where a key lives, go clockwise on the ring until you hit a Node.

Result: When you add a Node, it only “steals” a small portion of keys from its neighbor. 90% of keys stay put.

Example Calculation

Imagine the Ring is the range [0, 100].

  • Node A hashes to 20.
  • Node B hashes to 60.
  • Node C hashes to 90.

Where does a Key go?

  1. Key 1 hashes to 10.
    • Walk clockwise from 10. First node hit is Node A (20).
    • → Owner: Node A.
  2. Key 2 hashes to 50.
    • Walk clockwise from 50. First node hit is Node B (60).
    • → Owner: Node B.
  3. Key 3 hashes to 95.
    • Walk clockwise from 95. Hit 100 (End). Wrap around to 0. First node is Node A (20).
    • → Owner: Node A.

Deep Dive: Virtual Nodes (VNodes)

Problem: What if Node A is placed at 12 o’clock and Node B is at 1 o’clock? Node B gets very little data (the gap is small), while Node A gets almost everything (the gap is huge). This is Data Skew.

Solution: Virtual Nodes. Don’t map a physical server to just 1 point. Map it to 100 random points on the ring.

  • Physical Node A -> Virtual Nodes: A1, A2, A3…
  • Physical Node B -> Virtual Nodes: B1, B2, B3…

This statistically guarantees an even distribution of data, even with few servers.

Interactive Demo: The Ring Visualizer

Adjust the number of Virtual Nodes to see how the distribution evens out.

  • Low VNodes: High Skew (One node takes all).
  • High VNodes: Low Skew (Balanced).
1
Nodes: 3
Keys: 20
Std Dev (Skew): High
KEYS MAP CLOCKWISE
System Ready. Add Keys to start.

Deep Dive: Jump Consistent Hash

Google introduced “Jump Consistent Hash” (2014). It is incredibly simple (5 lines of code) and uses no memory (no ring structure).

How it works: It uses a pseudo-random generator to “jump” between buckets.

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}
  • Pros: Fast, Minimal Memory, Perfect Balance.
  • Cons: You can only add/remove buckets at the tail (e.g., reduce N from 10 to 9). You cannot remove “Node 5” specifically. Best for data storage where nodes are numbered sequentially.

The “Celebrity” Problem (Hot Keys)

Consistent Hashing balances keys, not traffic. If one key (justin_bieber) gets 10M requests/sec, the node owning that key will melt, even if it only has 1 key. Solution:

  1. Split the Key: Append a random suffix (justin_bieber_1, justin_bieber_2).
  2. Scatter: Distribute these sub-keys across the ring.
  3. Gather: The application reads from all sub-keys and aggregates the result.