Consistent Hashing

A cache fleet of four nodes routes every key with hash(key) % 4. Add a fifth node and the formula turns into hash(key) % 5, and about four of every five keys suddenly belong somewhere else. All of them miss at once, and the system behind the cache takes the full wave. This remap storm fires on every scale-out, every deploy, and every crashed node.

Consistent hashing keeps the routing idea and drops the divisor. Nodes and keys hash onto the same circle, and each key belongs to the first node it meets walking clockwise. The figure above runs one with four nodes and twelve keys. Press play: node D goes down, and only the keys in D's arc go looking for a new home.

The divisor is the problem

hash(key) % N has one flaw baked in: the N. Every routing decision depends on the total node count, so any change to that count reshuffles every key.

The figure below routes the twelve demo keys both ways, with the fleet already at four nodes and the moved keys highlighted. Under hash(key) % N, 10 of the 12 keys change owner, and every highlighted chip is a cache miss. On the ring, 3 of 12 move, exactly the keys in the arc the fourth node claims. Switch the fleet back to three nodes and every highlight clears.

Put nodes and keys on one ring

The ring removes the N from the formula. Hash each node once and place it on a circle. (The figures use 0° to 359°. Real systems use 0 to 2³².) Hash each key with the same function onto the same circle. To find a key's owner, walk clockwise from the key and stop at the first node. That node serves the key.

No node's position depends on how many nodes exist, and that is the whole trick. A key's walk can change only when the ring changes near the key: a node arriving or leaving inside its walking path. Nothing else reaches the walk.

The stretch of the circle a node answers for, from its predecessor clockwise to its own position, is its arc. C's arc runs from B at 312° around through 39°, wrapping across the top of the ring. The ring has no edges, so every walk eventually meets a node.

Walk one lookup. doc:a1 hashes to 326°. Clockwise from there the walk crosses the top of the ring, where the count wraps from 359° back to 0°, and meets C at 39°. C owns the key. The figure below replays this walk. Type a key of your own and it takes its walk too.

One node leaves, one arc moves

Now the payoff. When D leaves the ring, only the keys inside D's arc lose their owner, because every other key still meets the same first node it met before. The orphaned keys do what any lookup does: they keep walking clockwise, past D's empty spot, and stop at A. Three keys move out of twelve. The other nine never notice.

Adding a node is the mirror image. A new node claims the arc between its predecessor and itself, stealing that slice from its clockwise successor, the only node whose keys can move. To watch both directions, scroll back to the first figure and click any node to remove or restore it: the counts on the node chips show one arc's share changing hands, and nothing else.

A fair ring gives each node about 1/N of the keys, so growing from N to N+1 nodes moves about 1/(N+1) of them. The modulo column below comes from routing 1,000 keys; the ring column is the expected share:

The code is a sorted list and a binary search

The whole routing structure fits in two parallel arrays. points holds the node positions in sorted order, and nodes records who owns each point. A lookup hashes the key, finds the first point at or past the key's hash with a binary search, and wraps the index around the end of the array. That wrap is the ring closing.

import bisect

class HashRing:
	def __init__(self):
		self.points = []  # node positions, kept sorted
		self.nodes = []   # nodes[i] owns points[i]

	def _hash(self, value):
		h = 2166136261  # FNV offset basis
		for ch in value:
			h = (h ^ ord(ch)) * 16777619 % (1 << 32)
		return h

	def add_node(self, node):
		point = self._hash(node)
		index = bisect.bisect_left(self.points, point)
		self.points.insert(index, point)
		self.nodes.insert(index, node)

	def remove_node(self, node):
		index = self.nodes.index(node)
		self.points.pop(index)
		self.nodes.pop(index)

	def owner(self, key):
		index = bisect.bisect_left(self.points, self._hash(key))
		return self.nodes[index % len(self.nodes)]  # the ring closes

Adding or removing a node is one sorted insert or delete. A lookup costs O(log n) in the number of points, the same probe loop as binary search run over node positions instead of array cells. The _hash here is FNV. Any stable hash works in its place, but Python's own hash() is salted per process, so two runs would build two different rings. The implementation panel below grows this skeleton with virtual nodes, which the next section motivates.

Real rings are lumpy

Hash positions are random, and four random points do not quarter a circle. In the demo ring the arcs span 64° to 108°, and the twelve keys land 4, 3, 3, 2 across A, B, C, D. More keys even out within an arc, but the arc sizes stay uneven, and the arc sizes set the shares.

The fix is to stop betting on one point per node. Each node plants many points on the ring, called virtual nodes, by hashing A#0, A#1, and so on. The points of all four nodes interleave, the arcs shrink and average out, and the load converges on the fair share. The figure below routes 4,000 keys for real. With one point per node, the busiest node holds 2.2 times the average while the quietest holds almost nothing. With 128 points per node, every node sits within a few percent of the mean.

The cost is memory, and it is small: 128 points per node is still only 512 sorted numbers here. Virtual nodes also buy a second dial: give a bigger server more points and it takes a bigger share.

Where it earns its keep

Reach for the ring when keys must route to a changing set of owners and a remap is expensive:

• Distributed caches. Memcached clients have shipped this as ketama hashing for years. A crashed server costs its own arc of keys instead of the whole cache.

• Partitioned databases. DynamoDB and Cassandra place rows on the ring with virtual nodes, then replicate around it.

• Balancers. CDN edge selection and connection load balancing route by key so the same client keeps landing on the same machine.

Skip the ring when the fleet is fixed and small: hash(key) % N is one line and everyone understands it. Skip the ring also when the routing table must carry state: the ring decides placement and nothing more.

The practice problems below are routing in miniature. Build the bucket table first, then ask what happens to every key when the bucket count changes. That question is the whole lesson.