Consistent Hashing

The hash ring, virtual nodes, and why adding a node only moves 1/N of keys.

Consistent hashing answers a specific question: how do you spread keys across a changing set of nodes without moving most of the keys every time a node is added or removed? It underpins distributed caches, Cassandra, DynamoDB and many load balancers.

The problem with modulo hashing

The naive approach assigns a key to hash(key) % N, where N is the number of nodes. It distributes keys evenly — until N changes. Go from 4 to 5 nodes and roughly 80% of keys map to a different node. For a cache, that's a mass miss and a stampede on your database. For a datastore, it's a huge data migration.

The hash ring

Consistent hashing maps both nodes and keys onto the same circular hash space (say, 0 to 2³² − 1).

Hash each node's ID to a position on the ring.
Hash each key to a position on the ring.
Walk clockwise from the key's position; the first node you reach owns the key.

When you add a node, it takes over only the keys between it and its predecessor — about 1/N of the total. When a node is removed, its keys move to the next node clockwise. Everyone else is unaffected.

import bisect, hashlib

class HashRing:
    def __init__(self, nodes, vnodes=100):
        self.ring = []  # sorted list of (hash, node)
        for node in nodes:
            for i in range(vnodes):
                self.ring.append((self._hash(f"{node}#{i}"), node))
        self.ring.sort()

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

    def get_node(self, key):
        h = self._hash(key)
        idx = bisect.bisect(self.ring, (h,)) % len(self.ring)
        return self.ring[idx][1]

Virtual nodes

With only a few nodes, their random positions on the ring leave some nodes owning much bigger arcs than others. Virtual nodes fix this: each physical node is placed at many positions (often 100–256). This:

Evens out the load across nodes
Spreads a failed node's keys across *many* remaining nodes instead of dumping them all on one neighbor
Lets you give bigger machines more virtual nodes

Replication on the ring

For durability, store each key on the owning node and the next R−1 distinct nodes clockwise. That's exactly how Cassandra and Dynamo-style stores place replicas.

[!INTERVIEW] When to bring it up Mention consistent hashing when you're distributing a cache or a datastore across nodes and need to scale the cluster, or when you need "sticky" routing — for example, routing all edits to a document to the same server. You rarely need to implement it; you do need to explain why modulo hashing fails and what virtual nodes are for.