5.14 Consistent Hashing

Problem

You need to distribute keys across a changing set of nodes so that when nodes are added or removed, only a small fraction of keys move.

A standard hash table uses:

index = hash(key) mod n

When n changes, most keys are reassigned. This is unacceptable in systems like caches, distributed storage, or sharded services where moving data is expensive.

Solution

Map both keys and nodes onto a logical ring, then assign each key to the next node on the ring.

position = hash(x) on [0, MAX)

For nodes:

node_position = hash(node_id)

For a key:

key_position = hash(key)
assign key to first node with position >= key_position
if none, wrap to first node on ring

Discussion

Consistent hashing replaces modulo arithmetic with an ordered space. Nodes occupy positions on a ring. Keys are placed by walking clockwise until a node is found.

The key property is stability under change. When a node is added, only keys that fall between the new node and its predecessor move. When a node is removed, only its assigned keys move to the next node. All other keys remain unchanged.

This sharply reduces data movement compared to modulo-based hashing.

Load balance is a concern. If nodes are placed unevenly, some nodes receive more keys than others. To mitigate this, each physical node is represented by multiple virtual nodes.

for each node:
    for i from 1 to V:
        add hash(node_id, i) to ring

This spreads each node’s responsibility across the ring and smooths distribution.

Correctness

Every key is assigned to exactly one node because the ring is totally ordered and wraparound is defined.

For a key k, define:

k_pos = hash(k)

Let N be the set of node positions. The assigned node is:

first n in N such that n >= k_pos
or the smallest n in N if none exists

This rule always selects a unique node.

When a node is added at position p, only keys in the interval (prev(p), p] are reassigned to the new node. All other keys continue to map to the same successor node as before. This preserves stability.

Complexity

Let m be the number of node positions (including virtual nodes).

Lookup requires finding the successor of a key position in the ordered set. Using a balanced tree or sorted array, this takes O(log m) time.

Insertion and deletion of nodes also take O(log m) time.

Space usage is O(m).

Example

Suppose nodes are placed at positions:

10, 40, 70

Keys map as follows:

key 15 -> node 40
key 65 -> node 70
key 85 -> wrap -> node 10

If a new node is added at position 50:

10, 40, 50, 70

Only keys in (40, 50] move to the new node. For example:

key 45 -> node 50 (moved)
key 15 -> node 40 (unchanged)
key 65 -> node 70 (unchanged)

Implementation Notes

Use a sorted structure to store node positions. Binary search on a sorted array is often sufficient when node changes are infrequent.

Use virtual nodes to improve load balance. A common choice is dozens or hundreds of virtual nodes per physical node.

Hash both keys and node identifiers using the same hash function to ensure consistent placement.

Store node identifiers alongside positions to allow lookup results to return the actual node.

In distributed systems, ensure all participants use the same ring definition. Differences in hash function, seed, or node list lead to inconsistent routing.

Common Mistakes

Using simple modulo hashing in a dynamic cluster.

Using too few virtual nodes, leading to uneven load.

Failing to keep the ring sorted.

Using different hash functions for keys and nodes.

Ignoring wraparound at the end of the ring.

Assuming perfect balance without measuring actual key distribution.