Consistent hashing

You run a cache in front of a database. The cache has 4 nodes, and each client picks a node with hash(key) mod 4. Before a busy sale, you add a fifth node. A few seconds later, the database stops responding. At that moment, 80% of cache lookups started to miss.

Consistent hashing prevents this. It keeps each key on the same node while you add or remove nodes. Dynamo, Cassandra, memcached clients and the Envoy load balancer all use it to route keys.

Why hash mod N fails

hash(key) mod N is the obvious way to put keys on nodes. It needs no stored state, every client gets the same answer, and the load is even. The problem is that the answer depends on N. When N changes, almost every key goes to a different node.

A key stays on its node only when h mod N equals h mod (N+1). That is true for about one key in N+1. So when you go from N to N+1 nodes, about N/(N+1) of all keys move. With 4 to 5 nodes, that is 80%. With 100 to 101 nodes, it is 99%.

Step 1 of the Go build measures this with 100,000 keys:

modulo_test.go:24: load: max 1.018× mean, min 0.982× mean
modulo_test.go:38: 4 → 5 nodes: 80.1% of keys moved (ideal would be 20%)

The load is almost equal: every node is within 2% of the average. But 80.1% of keys move. The best result is that only the new node’s fair share moves (1/5, or 20%), and all of it moves to the new node.

The idea: put nodes and keys on one ring

Karger and his co-authors described the solution in 1997. Do not make the mapping depend on N. Instead, put nodes and keys in the same space, and let each key find its node by position:

1. Take all the values the hash can give, from 0 to 2⁶⁴−1. Join the two ends to make a circle, called the ring.
2. Hash the name of each node. The result is the node’s position on the ring.
3. Hash each key to a position on the ring. Then move clockwise until you reach a node. That node owns the key.

Step through it. Steps 5 and 6 show a node that joins and a node that leaves:

Step 5 shows the main benefit. Node D joins inside one arc, and it takes only the part of the arc between the previous node and itself. Keys move only to the new node. No key moves between two nodes that were already on the ring. When a node leaves, the opposite happens: only its keys move, to the next node clockwise. The Dynamo paper says it like this: “departure or arrival of a node only affects its immediate neighbors and other nodes remain unaffected.”

A lookup is a binary search over the sorted node positions, so it takes O(log n) time. If the search passes the last position, it goes back to the first one. Here is step 2 of the build. The complete ring is about 50 lines of Go:

package ringhash

import (
	"slices"
	"sort"
)

// Ring is a consistent-hash ring with one point per node. Nodes and keys are hashed onto
// the same 64-bit circle; a key belongs to the first node at or after it, clockwise.
//
// Not safe for concurrent use; wrap with a sync.RWMutex if nodes change while serving.
type Ring struct {
	points []uint64          // sorted node positions
	owner  map[uint64]string // position → node
}

func NewRing() *Ring {
	return &Ring{owner: make(map[uint64]string)}
}

// Add places node on the ring. Adding an existing node is a no-op.
func (r *Ring) Add(node string) {
	p := hash64(node)
	if _, ok := r.owner[p]; ok {
		return
	}
	r.owner[p] = node
	i, _ := slices.BinarySearch(r.points, p)
	r.points = slices.Insert(r.points, i, p)
}

// Remove takes node off the ring; its keys fall through to the next node clockwise.
func (r *Ring) Remove(node string) {
	p := hash64(node)
	if r.owner[p] != node {
		return
	}
	delete(r.owner, p)
	i, _ := slices.BinarySearch(r.points, p)
	r.points = slices.Delete(r.points, i, i+1)
}

// Get returns the node that owns key, or "" if the ring is empty. O(log n).
func (r *Ring) Get(key string) string {
	if len(r.points) == 0 {
		return ""
	}
	h := hash64(key)
	i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h })
	if i == len(r.points) {
		i = 0 // past the last point: wrap around to the first
	}
	return r.owner[r.points[i]]
}

// Nodes returns the nodes on the ring in ring order.
func (r *Ring) Nodes() []string {
	out := make([]string, len(r.points))
	for i, p := range r.points {
		out[i] = r.owner[p]
	}
	return out
}

=== RUN   TestHashSpreadsSimilarInputsAcrossTheSpace
--- PASS: TestHashSpreadsSimilarInputsAcrossTheSpace
=== RUN   TestHashAvalanche
    hash_test.go:31: average bits flipped between neighbouring names: 32.0 / 64
--- PASS: TestHashAvalanche
=== RUN   TestModuloIsDeterministic
--- PASS: TestModuloIsDeterministic
=== RUN   TestModuloEmpty
--- PASS: TestModuloEmpty
=== RUN   TestModuloSpreadsLoadEvenly
    modulo_test.go:24: load: max 1.018× mean, min 0.982× mean
--- PASS: TestModuloSpreadsLoadEvenly
=== RUN   TestModuloAddingANodeMovesMostKeys
    modulo_test.go:38: 4 → 5 nodes: 80.1% of keys moved (ideal would be 20%)
--- PASS: TestModuloAddingANodeMovesMostKeys
=== RUN   TestRingEmpty
--- PASS: TestRingEmpty
=== RUN   TestRingSingleNodeOwnsEverything
--- PASS: TestRingSingleNodeOwnsEverything
=== RUN   TestRingOwnerIsFirstNodeClockwise
--- PASS: TestRingOwnerIsFirstNodeClockwise
=== RUN   TestRingAddIsIdempotent
--- PASS: TestRingAddIsIdempotent
=== RUN   TestRingAddingANodeOnlyMovesKeysToIt
    ring_test.go:79: 4 → 5 nodes: 10.9% of keys moved (modulo moved ~80%)
--- PASS: TestRingAddingANodeOnlyMovesKeysToIt
=== RUN   TestRingRemovingANodeOnlyMovesItsKeys
--- PASS: TestRingRemovingANodeOnlyMovesItsKeys
=== RUN   TestRingLoadIsUneven
    ring_test.go:104: load: max 2.47× mean, min 0.01× mean
--- PASS: TestRingLoadIsUneven
PASS
ok  	shardedmind/builds/hash-ring/02-ring

The test confirms the main benefit: when 4 nodes become 5, no key moves between two existing nodes. But the test also shows a new problem:

ring_test.go:79:  4 → 5 nodes: 10.9% of keys moved (modulo moved ~80%)
ring_test.go:104: load: max 2.47× mean, min 0.01× mean

The new node got only 10.9% of the keys, not its fair share of 20%. With 10 nodes, the busiest node holds 2.47 times its fair share, and the quietest node holds almost no keys.

Why one point for each node is not enough

Each node is at one random position, so the arc that each node owns has a random length. Some arcs are long and some are short. The Dynamo paper names two problems with this basic ring. First, random positions give “non-uniform data and load distribution”. Second, the ring does not know that some nodes are more powerful than others.

There is a third problem, shown at the end of the ring stepper. When a node fails, all of its keys go to one neighbour. If the failed node had 2 times the average load, the neighbour now has its own load and all of that extra load too.

Virtual nodes

The fix is to give each node many points on the ring. Hash A#0, A#1, A#2 and so on, and put each result on the ring. Each point is a virtual node. All the virtual nodes of A send their keys to the real node A. Dynamo calls these points tokens. This lesson calls them virtual nodes.

This works because a node’s share is now the sum of many random arcs, not one arc. A sum of many random lengths varies much less than one random length. With v virtual nodes, a node’s share has a standard deviation of about 1/√v of the average. So 100 virtual nodes give about ±10%, and 10,000 give about ±1%.

The Jump Consistent Hash paper from Google measured this for the classic ring. The standard error was 0.998 with 1 point for each node and 0.315 with 10 points. It was 0.0997 with 100 points and 0.0316 with 1000 points.

Step 3 of the build adds virtual nodes. The only change from step 2 is in Add. It now puts vnodes points on the ring for each node, not one:

package ringhash

import (
	"slices"
	"sort"
	"strconv"
)

// Ring is a consistent-hash ring with virtual nodes: each physical node is hashed onto
// the circle `vnodes` times (as "node#0", "node#1", ...). Many small arcs per node average
// out the randomness of one big arc, so load evens out, and a departing node's keys
// scatter across many neighbours instead of landing on one.
//
// Not safe for concurrent use; wrap with a sync.RWMutex if nodes change while serving.
type Ring struct {
	vnodes int
	points []uint64          // sorted vnode positions
	owner  map[uint64]string // position → physical node
	nodes  map[string]bool
}

// NewRing returns an empty ring that places `vnodes` points per node (minimum 1).
func NewRing(vnodes int) *Ring {
	return &Ring{vnodes: max(vnodes, 1), owner: make(map[uint64]string), nodes: make(map[string]bool)}
}

func vnodeKey(node string, i int) string { return node + "#" + strconv.Itoa(i) }

// Add places node's vnodes on the ring. Adding an existing node is a no-op.
// O(v log P) for v vnodes and P points, plus a re-sort.
func (r *Ring) Add(node string) {
	if r.nodes[node] {
		return
	}
	r.nodes[node] = true
	for i := range r.vnodes {
		p := hash64(vnodeKey(node, i))
		if _, taken := r.owner[p]; taken {
			continue // 64-bit collision: astronomically rare; first owner keeps the point
		}
		r.owner[p] = node
		r.points = append(r.points, p)
	}
	slices.Sort(r.points)
}

// Remove takes all of node's vnodes off the ring.
func (r *Ring) Remove(node string) {
	if !r.nodes[node] {
		return
	}
	delete(r.nodes, node)
	r.points = slices.DeleteFunc(r.points, func(p uint64) bool {
		if r.owner[p] == node {
			delete(r.owner, p)
			return true
		}
		return false
	})
}

// Get returns the node that owns key, or "" if the ring is empty. O(log P).
func (r *Ring) Get(key string) string {
	if len(r.points) == 0 {
		return ""
	}
	h := hash64(key)
	i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h })
	if i == len(r.points) {
		i = 0
	}
	return r.owner[r.points[i]]
}

// Len is the number of points (vnodes) on the ring.
func (r *Ring) Len() int { return len(r.points) }

@@ -3,44 +3,63 @@
 import (
 	"slices"
 	"sort"
+	"strconv"
 )
 
-// Ring is a consistent-hash ring with one point per node. Nodes and keys are hashed onto
-// the same 64-bit circle; a key belongs to the first node at or after it, clockwise.
+// Ring is a consistent-hash ring with virtual nodes: each physical node is hashed onto
+// the circle `vnodes` times (as "node#0", "node#1", ...). Many small arcs per node average
+// out the randomness of one big arc, so load evens out, and a departing node's keys
+// scatter across many neighbours instead of landing on one.
 //
 // Not safe for concurrent use; wrap with a sync.RWMutex if nodes change while serving.
 type Ring struct {
-	points []uint64          // sorted node positions
-	owner  map[uint64]string // position → node
+	vnodes int
+	points []uint64          // sorted vnode positions
+	owner  map[uint64]string // position → physical node
+	nodes  map[string]bool
 }
 
-func NewRing() *Ring {
-	return &Ring{owner: make(map[uint64]string)}
+// NewRing returns an empty ring that places `vnodes` points per node (minimum 1).
+func NewRing(vnodes int) *Ring {
+	return &Ring{vnodes: max(vnodes, 1), owner: make(map[uint64]string), nodes: make(map[string]bool)}
 }
 
-// Add places node on the ring. Adding an existing node is a no-op.
+func vnodeKey(node string, i int) string { return node + "#" + strconv.Itoa(i) }
+
+// Add places node's vnodes on the ring. Adding an existing node is a no-op.
+// O(v log P) for v vnodes and P points, plus a re-sort.
 func (r *Ring) Add(node string) {
-	p := hash64(node)
-	if _, ok := r.owner[p]; ok {
+	if r.nodes[node] {
 		return
 	}
-	r.owner[p] = node
-	i, _ := slices.BinarySearch(r.points, p)
-	r.points = slices.Insert(r.points, i, p)
+	r.nodes[node] = true
+	for i := range r.vnodes {
+		p := hash64(vnodeKey(node, i))
+		if _, taken := r.owner[p]; taken {
+			continue // 64-bit collision: astronomically rare; first owner keeps the point
+		}
+		r.owner[p] = node
+		r.points = append(r.points, p)
+	}
+	slices.Sort(r.points)
 }
 
-// Remove takes node off the ring; its keys fall through to the next node clockwise.
+// Remove takes all of node's vnodes off the ring.
 func (r *Ring) Remove(node string) {
-	p := hash64(node)
-	if r.owner[p] != node {
+	if !r.nodes[node] {
 		return
 	}
-	delete(r.owner, p)
-	i, _ := slices.BinarySearch(r.points, p)
-	r.points = slices.Delete(r.points, i, i+1)
+	delete(r.nodes, node)
+	r.points = slices.DeleteFunc(r.points, func(p uint64) bool {
+		if r.owner[p] == node {
+			delete(r.owner, p)
+			return true
+		}
+		return false
+	})
 }
 
-// Get returns the node that owns key, or "" if the ring is empty. O(log n).
+// Get returns the node that owns key, or "" if the ring is empty. O(log P).
 func (r *Ring) Get(key string) string {
 	if len(r.points) == 0 {
 		return ""
@@ -48,16 +67,10 @@
 	h := hash64(key)
 	i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h })
 	if i == len(r.points) {
-		i = 0 // past the last point: wrap around to the first
+		i = 0
 	}
 	return r.owner[r.points[i]]
 }
 
-// Nodes returns the nodes on the ring in ring order.
-func (r *Ring) Nodes() []string {
-	out := make([]string, len(r.points))
-	for i, p := range r.points {
-		out[i] = r.owner[p]
-	}
-	return out
-}
+// Len is the number of points (vnodes) on the ring.
+func (r *Ring) Len() int { return len(r.points) }

=== RUN   TestHashSpreadsSimilarInputsAcrossTheSpace
--- PASS: TestHashSpreadsSimilarInputsAcrossTheSpace
=== RUN   TestHashAvalanche
    hash_test.go:31: average bits flipped between neighbouring names: 32.0 / 64
--- PASS: TestHashAvalanche
=== RUN   TestModuloIsDeterministic
--- PASS: TestModuloIsDeterministic
=== RUN   TestModuloEmpty
--- PASS: TestModuloEmpty
=== RUN   TestModuloSpreadsLoadEvenly
    modulo_test.go:24: load: max 1.018× mean, min 0.982× mean
--- PASS: TestModuloSpreadsLoadEvenly
=== RUN   TestModuloAddingANodeMovesMostKeys
    modulo_test.go:38: 4 → 5 nodes: 80.1% of keys moved (ideal would be 20%)
--- PASS: TestModuloAddingANodeMovesMostKeys
=== RUN   TestRingEmpty
--- PASS: TestRingEmpty
=== RUN   TestRingSingleNodeOwnsEverything
--- PASS: TestRingSingleNodeOwnsEverything
=== RUN   TestRingPlacesVnodesPerNode
--- PASS: TestRingPlacesVnodesPerNode
=== RUN   TestRingAddingANodeOnlyMovesKeysToIt
    ring_test.go:58: 4 → 5 nodes: 18.4% of keys moved (ideal 1/5 = 20%)
--- PASS: TestRingAddingANodeOnlyMovesKeysToIt
=== RUN   TestRingRemovalSpreadsKeysAcrossSurvivors
    ring_test.go:82: node-2's keys went to: map[node-0:6311 node-1:3968 node-3:3575 node-4:8010]
--- PASS: TestRingRemovalSpreadsKeysAcrossSurvivors
=== RUN   TestRingVnodesEvenOutLoad
    ring_test.go:91: 160 vnodes/node: max 1.14× mean, min 0.89× mean
--- PASS: TestRingVnodesEvenOutLoad
=== RUN   TestRingVnodeSweep
    ring_test.go:104: vnodes=1    points=10    max 2.24× min 0.08×
    ring_test.go:104: vnodes=10   points=100   max 1.26× min 0.61×
    ring_test.go:104: vnodes=50   points=500   max 1.25× min 0.85×
    ring_test.go:104: vnodes=100  points=1000  max 1.16× min 0.82×
    ring_test.go:104: vnodes=200  points=2000  max 1.11× min 0.84×
    ring_test.go:104: vnodes=500  points=5000  max 1.11× min 0.89×
--- PASS: TestRingVnodeSweep
PASS
ok  	shardedmind/builds/hash-ring/03-vnodes

This table shows the effect on 10 nodes and 100,000 keys. TestRingVnodeSweep measured it:

The other two problems are also fixed:

ring_test.go:58: 4 → 5 nodes: 18.4% of keys moved (ideal 1/5 = 20%)
ring_test.go:82: node-2's keys went to: map[node-0:6311 node-1:3968 node-3:3575 node-4:8010]

The new node gets close to its fair share of 20%, and it gets keys from every existing node. When node-2 is removed, its keys go to all four other nodes. For more powerful machines, add more virtual nodes. The Dynamo paper (§4.2) lists these same three benefits.

Now try the real code. This panel runs step 3 of the build, compiled to WebAssembly, with 20,000 keys. Start with 1 virtual node. Add or remove a node. Then move the slider up:

The numbers

How many virtual nodes do you need? The 1/√v rule changes a balance target into a number of virtual nodes. It also shows why more virtual nodes soon start to cost a lot:

What does it cost to add a node? This shows the main benefit in bytes and minutes, and compares it with mod N:

Lookups are not the slow part. Step 3’s benchmark (go test -bench=.) does one lookup on a ring of 1,600 points in about 32 ns on a recent laptop. The real costs are memory for each point, the work for each change of nodes, and the data that moves.

In real systems

Trade-offs and failure modes

These are the problems that occur in real systems:

• Clients with different node lists. If two clients have different node lists, they find different owners for the same key. A cache then holds the same key twice, and a store writes to the wrong node. Real systems share the node list with gossip, as Dynamo and Cassandra do. Others use one source of truth, such as the control plane that gives endpoints to Envoy.
• Busy keys. Consistent hashing balances the keys, not the traffic. One very popular key is still the problem of one node. The fix is outside the ring: copy busy keys to more nodes, add a local cache, or split one key into several keys.
• Too many virtual nodes make failures worse. The Cassandra docs say that each token adds up to 2 × (RF − 1) neighbours on the ring. With many tokens, almost any two failed nodes share a range. This is one reason why Cassandra changed from 256 random tokens to fewer tokens that it places on purpose.
• Failures that spread. With one point for each node, all the load of a failed node goes to one neighbour. That neighbour can then fail too.

When you do not need a ring. Sometimes shards have the numbers 0 to N−1 and you only add shards at the end. Data stores that only grow are an example. Then Jump Consistent Hash gives an almost perfect balance, uses no memory and is about 5 lines of code. Its limit, in the words of the paper, is that “buckets must be numbered sequentially”. So it suits data shards better than a set of cache hosts that can change in any order.

Recap

• hash mod N gives equal load. But when N changes, N/(N+1) of the keys move. Use it only if N never changes.
• A ring puts nodes and keys in one space. A key belongs to the first node clockwise. When a node joins or leaves, only its arc moves, which is about 1/N of the keys.
• With one point for each node, the arcs have very different sizes. In our build, the busiest node had 2.47 times the average. A failed node gives all its keys to one neighbour.
• A virtual node is one of many points for the same node. Virtual nodes make the difference about 1/√v, spread failures over all nodes, and let large machines hold more.
• Avalanche means one changed input bit changes about half the output bits. Use a hash with good avalanche (murmur3, xxhash), not FNV-1a alone.
• Real systems went further. Dynamo used fixed partitions, and Cassandra places its tokens on purpose instead of at random.