Consistent Hashing & Virtual Nodes: Distributing Keys Without Mass Resharding

Why You Need This in Real Life

A major social media platform once ran a cluster of 10 Memcached nodes using simple modulo hashing to distribute user session keys:

$\text{Node Index} = \text{hash}(key) \pmod N$

Where $N = 10$ servers.

During peak traffic, Server 4 suffered a hardware failure. The site reliability team removed Server 4, reducing the active server count $N$ from 10 to 9.

Instantly, $90\%$ of all incoming session keys mapped to entirely different server indices! Every active user session in the cache became unreachable.

Within seconds, millions of incoming HTTP requests bypassed the cache cluster and slammed the primary database directly, triggering a complete database failure and a 3-hour global outage.

Consistent Hashing was created by Karger et al. at MIT to solve this exact resharding catastrophe.

Part 1: The Failure of Simple Modulo Hashing

Under traditional modulo hashing ( $\text{hash}(k) \pmod N$ ), changing the server count $N$ by adding or removing a single node forces nearly every key in the system to remap:

N = 4 Servers:
key_1 -> hash(key_1) % 4 = Node 1
key_2 -> hash(key_2) % 4 = Node 2

N = 3 Servers (Node 4 Crashes):
key_1 -> hash(key_1) % 3 = Node 2  <-- Key Moved! Cache Miss!
key_2 -> hash(key_2) % 3 = Node 0  <-- Key Moved! Cache Miss!

When $N$ changes, $\frac{N}{N+1}$ of all keys must be remapped to new servers. For a 100-node cluster, adding one node invalidates $99\%$ of the cache.

Part 2: How Consistent Hashing Works

Consistent Hashing maps both keys and servers to a shared 360-degree mathematical ring using a uniform hash function (e.g., MD5 or MurmurHash3) outputting values in the range $[0, 2^{32} - 1]$ .

                             Hash Ring (0 to 2^32 - 1)
                                      [Node 0]
                                    /          \
                                   /            \
                              [Key C]          [Node 1]
                                 |                |
                              [Node 3]         [Key A]
                                   \            /
                                    \          /
                                      [Node 2]

Key Lookup Rule

To find which server owns a specific key:

Hash the key string to find its position on the ring: $p = \text{hash}(key)$ .
Travel clockwise around the ring starting from position $p$ .
The first server node encountered is the owner of that key.

Adding or Removing Nodes

When Node 1 is removed from the ring, only keys that mapped directly to Node 1 are reassigned to Node 2 (the next clockwise server). All other keys on all other nodes remain completely untouched!

$\text{Keys Moved on Scale Event} = \frac{1}{N}$

For a 100-node cluster, adding or removing a node affects only $1\%$ of the key space.

Part 3: Solving Hotspots with Virtual Nodes (VNodes)

In a simple hash ring with 3 physical servers, nodes can end up unevenly spaced on the ring, creating hotspots where one server owns $60\%$ of the key space while another owns $10\%$ .

UNEVEN RING:
[Node 0] ------------ (60% of keys) ------------> [Node 1] -- (10%) --> [Node 2]

The Virtual Node Solution

Instead of mapping a physical server to a single point on the ring, Consistent Hashing assigns each physical server 100 to 250 Virtual Nodes (VNodes) distributed randomly across the ring.

Physical Server A -> [NodeA#1, NodeA#2, NodeA#3, ..., NodeA#200]
Physical Server B -> [NodeB#1, NodeB#2, NodeB#3, ..., NodeB#200]

BALANCED VNODE RING:
[NodeA#1] -> [NodeB#4] -> [NodeC#2] -> [NodeA#12] -> [NodeC#88] -> [NodeB#3]

With VNodes:

Keys are distributed uniformly across physical hardware ( $\pm 5\%$ variance).
If a powerful server has $2\times$ RAM, you can assign it $400$ VNodes while smaller servers receive $200$ .

Part 4: Runnable Java Consistent Hashing Engine

package com.example.hashing;

import java.nio.charset.StandardCharsets;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;

public class ConsistentHashRing<T> {

    private final int numberOfReplicas; // Number of VNodes per physical node
    private final SortedMap<Long, T> circle = new TreeMap<>();

    public ConsistentHashRing(int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        for (T node : nodes) {
            add(node);
        }
    }

    public synchronized void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            String vNodeKey = node.toString() + "-VN" + i;
            circle.put(hash(vNodeKey), node);
        }
    }

    public synchronized void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            String vNodeKey = node.toString() + "-VN" + i;
            circle.remove(hash(vNodeKey));
        }
    }

    public synchronized T get(String key) {
        if (circle.isEmpty()) {
            return null;
        }
        long hash = hash(key);
        if (!circle.containsKey(hash)) {
            // Find the tail map (all hashes >= key hash)
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            // If empty, wrap around to the first key on the ring
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }

    // MurmurHash / MD5 32-bit integer hash mapping
    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes(StandardCharsets.UTF_8));
            return ((long) (digest[3] & 0xFF) << 24) |
                   ((long) (digest[2] & 0xFF) << 16) |
                   ((long) (digest[1] & 0xFF) << 8)  |
                   ((long) (digest[0] & 0xFF));
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 unavailable", e);
        }
    }

    public int getRingSize() {
        return circle.size();
    }
}

Part 5: Real-World Use Cases

System	Implementation	Purpose
Amazon DynamoDB	Consistent Hashing with VNodes	Partitioning key-value records across storage nodes.
Apache Cassandra	Token Ring (Murmur3Partitioner)	Routing row partition keys to replica nodes.
Akamai CDN	Consistent Hashing	Routing edge web cache requests to edge proxy servers.
Discord Messaging	Consistent Hashing Ring	Distributing guild voice channels across Erlang worker nodes.

Next Steps

Now that we understand Consistent Hashing and Virtual Nodes, we will explore database sharding strategies and dynamic rebalancing in Part 5.

References & Further Reading

Karger, D., et al. (1997). Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. ACM STOC ‘97, 654–663.
Das, A., et al. (2002). SWIM: Scalable Weakness-oriented Process Group Membership Protocol. IEEE DSN ‘02.