Consistent Hashing

Consistent hashing assigns keys to nodes so that when the set of nodes changes, most keys stay on the same node. Only keys that belonged to a removed node—or a slice of keys claimed by a new node—move. That property makes it the default placement strategy for distributed caches, partition routers, and many sharded data stores.

Distributed systems rarely have a fixed forever cluster size. Nodes fail, capacity is added, and hot partitions are split. A placement scheme that reshuffles everything on every change creates thundering herds of data movement and cold caches. Consistent hashing exists to keep remapping proportional to the change.

The rehashing problem

The naive way to map a key to one of N nodes is:

node = hash(key) % N

When N becomes N+1 or N-1, the modulus changes for almost every key. Empirically, most keys change owners—even keys whose logical “bucket” did not need to move. Caches miss en masse; databases stream nearly the full dataset.

Remapping

The fraction of keys that must move to a different node after a membership change. Ideal remapping is roughly 1/N of keys when adding or removing one of N equal nodes.

int NodeFor(string key, int nodeCount){  // Almost all keys change owners when nodeCount changes  return Math.Abs(Hash(key)) % nodeCount;}

string NodeFor(string key, SortedDictionary<uint, string> ring){  var h = Hash(key);  foreach (var (point, node) in ring)  {      if (h <= point) return node;  }  return ring.Values.First(); // wrap around}

How the ring works

Imagine the output space of the hash function as a circle—values from 0 to 2^32-1 wrapping around. Each node is hashed onto that circle (one or more points). Each key is hashed onto the same circle. Ownership rule:

Walk clockwise from the key’s position until you hit a node point. That node owns the key.

Equivalently: a node owns the arc from the previous node (exclusive) to itself (inclusive), wrapping at zero.

In the diagram, foo sits between A and B, so walking clockwise assigns it to B. bar lands on C.

When you add node D on an arc that B previously owned, only keys on the arc now ending at D move from B to D. Keys elsewhere stay put. When you remove B, its arc is absorbed by the next clockwise neighbour—only B’s keys move.

Virtual nodes

With one hash point per physical node, placement is coarse. Random hash positions leave some nodes with larger arcs than others—load imbalance. Virtual nodes (vnodes) place many points per physical server on the ring (e.g. 100–200). Each point still maps to the same physical node.

Effects:

• Arcs become many small slices → load averages out
• When a node is removed, its keys fan out to many neighbours instead of dumping onto one successor
• Heterogeneous capacity can be modeled by giving stronger machines more vnodes

void AddNode(SortedDictionary<uint, string> ring, string node, int virtualNodes)
{
    for (var i = 0; i < virtualNodes; i++)
    {
        var point = Hash($"{node}#{i}");
        ring[point] = node;
    }
}

Key remapping and operations

Lookup is O(log V) with a sorted structure over V virtual points (binary search for the first point ≥ key hash), or O(1) expected with careful bucketization.

Membership change workflow:

1. Update the ring (add/remove vnode points)
2. Compute keys (or ranges) whose owner changed
3. Stream only those keys to new owners
4. Serve reads with a strategy during migration (e.g. check old and new, or freeze a shard briefly)

For caches, remapped keys simply miss and refill—acceptable if remapping is small. For databases, controlled migration and dual-writes during cutover matter; see database sharding.

Comparison to related techniques

Consistent hashing pairs with scaling writes: partition write load across nodes without reshuffling the world when capacity changes. In event-driven architecture, similar ideas assign partitions to consumers.

Implementation notes

• Prefer a stable, uniform hash (e.g. well-distributed 32- or 64-bit); cryptographic hashes work but are often unnecessary for placement
• Store the ring in a structure shared by all routers, or compute deterministically from a membership list
• Handle wrap-around explicitly in code—off-by-one bugs send traffic to the wrong node
• For sticky sessions or shard affinity, document whether clients hash on user id, tenant id, or entity id

Failure and replication

The basic ring assigns a primary owner. Production systems often place replicas on the next R distinct physical nodes clockwise (or via a separate replica strategy). Failures then promote a successor without global reshuffle. Replication and quorum protocols build on top of placement; they are not solved by the ring alone.