6. Consistent Hashing

title: 6. Consistent Hashing

Consistent hashing is a distributed hashing technique that minimizes the number of keys that need to be remapped when nodes are added or removed from a cluster. It is a fundamental building block for distributed caches, databases, and load balancers.

The Problem with Simple Hashing

With naive modular hashing, a key is mapped to a server using:

Where is the number of servers.

Example with 4 servers:

hash("user:1") % 4 = 2   → Server 2
hash("user:2") % 4 = 0   → Server 0
hash("user:3") % 4 = 1   → Server 1
hash("user:4") % 4 = 3   → Server 3

Problem: When changes (add/remove a server), almost all keys get remapped.

With 4 servers: hash("user:1") % 4 = 2 → Server 2
With 5 servers: hash("user:1") % 5 = 3 → Server 3  ← REMAPPED!

On average, when going from to servers, of all keys must move. For , adding one server remaps ~99% of keys. This causes:

Cache avalanche: When keys move, the old cache is useless; all requests hit the database.
Data rebalancing storms: Massive data migration across nodes.

How Consistent Hashing Works

Step 1: The Hash Ring

Imagine the output space of a hash function as a circular ring from to :

                    0
                  /    \
               /          \
            /                \
         /                      \
       /                          \
    2^32-1                          2^31
       \                          /
         \                      /
            \                /
               \          /
                  \    /
                    2^32/2

Step 2: Place Servers on the Ring

Hash each server to a position on the ring:

hash("Server A") → position 10
hash("Server B") → position 50
hash("Server C") → position 80

            0
           .|.
         .  |  .
       A(10)|    .
      .     |      .
     .      |       .
    .       |        C(80)
     .      |       .
      .     |      .
       .    |    .
         B(50) .
           '.'

Step 3: Map Keys to Servers

Each key is hashed to a position on the ring and is assigned to the first server encountered moving clockwise.

hash("key1") → position 15 → Server B (next clockwise is 50)
hash("key2") → position 55 → Server C (next clockwise is 80)
hash("key3") → position 85 → Server A (wraps around to 10)

Step 4: Adding/Removing Servers

Adding Server D at position 30:

Only keys between A(10) and D(30) need to move — from B to D.
All other keys remain unchanged.

Removing Server B:

Only keys that were on B (between A(10) and B(50)) move to C(80).
All other keys remain unchanged.

Key insight: On average, only keys need to be remapped when a node is added or removed, where is the total number of keys and is the number of nodes.

The Non-Uniformity Problem

With only a few servers on the ring, key distribution can be very uneven:

         0
        .|.
      .  |  .
    A(5) |    .
     .   |      .
      .  |       B(10)    ← A and B are close together
       . |      .          ← C handles most of the ring!
        .|    .
          . .
         C(80)

Server C would be responsible for most keys. This creates hot spots.

Virtual Nodes (Vnodes)

The solution is to map each physical server to multiple positions on the ring using virtual nodes.

Server A → hash("A-vnode0") = 10
           hash("A-vnode1") = 45
           hash("A-vnode2") = 75

Server B → hash("B-vnode0") = 25
           hash("B-vnode1") = 60
           hash("B-vnode2") = 90

Server C → hash("C-vnode0") = 35
           hash("C-vnode1") = 55
           hash("C-vnode2") = 85

            0
           .|.
         .  |  .
      A0(10)|    .
      .   B0(25)   .
     .    C0(35)     .
    A1(45)  |      C2(85)
     .  C1(55)     B2(90)
      . B1(60)   .
       .    |  .
        A2(75)
           '.'

Benefits of virtual nodes:

More uniform distribution: Each server gets multiple points on the ring, averaging out the load.
Proportional assignment: A more powerful server can have more virtual nodes.
Smoother rebalancing: When a node is added or removed, its load is distributed across many other nodes rather than just one.

Number of virtual nodes: Typically 100-200 vnodes per physical server provides good distribution.

Handling Replication

For fault tolerance, each key is replicated to consecutive nodes on the ring (clockwise).

Key X → Primary: Node A → Replica 1: Node B → Replica 2: Node C

Replication with virtual nodes: Walk clockwise on the ring, but skip virtual nodes belonging to the same physical server.

Key X at position 15:
  → Vnode: A0 (position 10) ← Primary (physical Server A)
  → Skip: A1 (position 45) ← Same physical server, skip
  → Vnode: B0 (position 25) ← Replica 1 (physical Server B)
  → Vnode: C0 (position 35) ← Replica 2 (physical Server C)

Algorithm Complexity

Operation	Complexity
Key lookup (find server)	with sorted list / binary search
Add node	key movements + to insert vnodes
Remove node	key movements + to remove vnodes

Where:

= number of physical nodes
= total keys
= virtual nodes per physical node

Consistent Hashing Variants

Jump Consistent Hashing

A fast, minimal-memory algorithm that maps keys to buckets uniformly.

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: Zero memory, perfectly uniform, very fast.
Cons: Only supports sequential bucket IDs (0 to N-1); can't handle arbitrary node names or weights.
Best for: Sharding with known, sequential shard IDs.

Rendezvous Hashing (Highest Random Weight)

For each key, hash the key with every server and pick the server with the highest hash value.

For key K:
  score_A = hash(K + "Server A") = 0.73
  score_B = hash(K + "Server B") = 0.91  ← highest → choose Server B
  score_C = hash(K + "Server C") = 0.42

Pros: Simple, no ring structure needed, perfectly uniform.
Cons: per lookup (must hash with every server).
Best for: Small number of servers.

Maglev Hashing (Google)

A lookup-table-based approach for connection-consistent load balancing.

Fixed-size lookup table populated with a permutation-based algorithm.
lookup time.
Designed for network load balancers.

Real-World Usage

System	How It Uses Consistent Hashing
Amazon DynamoDB	Partitions data across storage nodes
Apache Cassandra	Maps partition keys to nodes in the cluster
Memcached	Client-side consistent hashing for cache distribution
Redis Cluster	Hash slots (16384 slots) — a variant of consistent hashing
Akamai CDN	Maps URLs to edge servers
Discord	Routes users to specific servers/shards
Netflix	EVCache ring for distributed caching

Redis Cluster: Hash Slot Approach

Instead of a continuous hash ring, Redis divides the keyspace into 16384 fixed slots:

Slots are assigned to nodes. When nodes change, only slots (not individual keys) are migrated.

Node A: Slots 0-5460
Node B: Slots 5461-10922
Node C: Slots 10923-16383

Consistent Hashing vs Simple Hashing

Aspect	Simple Hash ()	Consistent Hashing
Keys remapped on node change	~ (almost all)	~ (minimal)
Distribution uniformity	Good	Good (with vnodes)
Complexity
Implementation	Trivial	Moderate
Use case	Fixed-size clusters	Dynamic clusters

Implementation Sketch

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, nodes=None, num_vnodes=150):
        self.num_vnodes = num_vnodes
        self.ring = {}          # hash_value → node
        self.sorted_keys = []   # sorted hash positions
        if nodes:
            for node in nodes:
                self.add_node(node)

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        for i in range(self.num_vnodes):
            vnode_key = f"{node}:vnode{i}"
            hash_val = self._hash(vnode_key)
            self.ring[hash_val] = node
            bisect.insort(self.sorted_keys, hash_val)

    def remove_node(self, node):
        for i in range(self.num_vnodes):
            vnode_key = f"{node}:vnode{i}"
            hash_val = self._hash(vnode_key)
            del self.ring[hash_val]
            self.sorted_keys.remove(hash_val)

    def get_node(self, key):
        if not self.ring:
            return None
        hash_val = self._hash(key)
        idx = bisect.bisect_right(self.sorted_keys, hash_val)
        if idx == len(self.sorted_keys):
            idx = 0  # wrap around
        return self.ring[self.sorted_keys[idx]]

Summary

Concept	Key Point
Problem	Naive hashing remaps almost all keys on node changes
Solution	Consistent hashing — keys map to ring, walk clockwise
Virtual nodes	Multiple ring positions per server for uniform distribution
Key movement	Only keys move when a node is added/removed
Replication	Replicate to next distinct physical nodes on the ring
Variants	Jump hash (fast, sequential), Rendezvous (simple), Maglev (Google LB)

Rule of thumb: Use consistent hashing whenever you need to distribute data across a dynamic set of nodes — caches, databases, or load balancers.