Suppose you run a cache cluster of 24 nodes and each application server picks a node with the simplest rule imaginable: node = hash(key) % 24. It works beautifully — keys spread evenly, lookups are instant. Then a node dies and you reroute with hash(key) % 23. Almost every key now maps to a different node than before. Your hit rate does not dip, it evaporates, because the entire point of a cache is that the mapping is stable across topology changes. Going from 24 nodes to 25 remaps about 96% of keys; shrinking back to 24 does it again. A cluster that scales by adding machines pays for every scaling event with a full cache flush.
Consistent hashing exists to break that dependency. The idea: instead of dividing hash space by node count, place both nodes and keys on the same hash ring, and give each key to the first node you encounter walking clockwise. Node count disappears from the formula, which means adding or removing a node only relocates the keys that live in that node’s slice of the ring — roughly 1/N of them, not nearly all of them. This is the mechanism underneath partitioned stores in the Dynamo lineage, Cassandra’s token ring, and a surprising number of load balancers, including the software load balancer that fronts Google’s infrastructure.
The ring, implemented
A hash ring is genuinely small. You hash every node into a uint32 space, keep the points sorted, and resolve a key by finding the first point at or after the key’s hash, wrapping around at the end. Here is a complete implementation in Go:
package main
import (
"fmt"
"hash/crc32"
"sort"
)
const virtualNodes = 150
type HashRing struct {
replicas int
sorted []uint32
nodeOf map[uint32]string
}
func NewHashRing(replicas int) *HashRing {
return &HashRing{
replicas: replicas,
nodeOf: make(map[uint32]string),
}
}
func (h *HashRing) hash(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
func (h *HashRing) Add(node string) {
for i := 0; i < h.replicas; i++ {
point := h.hash(fmt.Sprintf("%s#%d", node, i))
h.nodeOf[point] = node
h.sorted = append(h.sorted, point)
}
sort.Slice(h.sorted, func(i, j int) bool { return h.sorted[i] < h.sorted[j] })
}
func (h *HashRing) Remove(node string) {
filtered := h.sorted[:0]
for _, p := range h.sorted {
if h.nodeOf[p] == node {
delete(h.nodeOf, p)
} else {
filtered = append(filtered, p)
}
}
h.sorted = filtered
}
func (h *HashRing) Get(key string) string {
if len(h.sorted) == 0 {
return ""
}
point := h.hash(key)
idx := sort.Search(len(h.sorted), func(i int) bool {
return h.sorted[i] >= point
})
if idx == len(h.sorted) {
idx = 0 // wrap around the ring
}
return h.nodeOf[h.sorted[idx]]
}
func main() {
ring := NewHashRing(virtualNodes)
for _, node := range []string{"cache-a", "cache-b", "cache-c"} {
ring.Add(node)
}
for _, key := range []string{"user:42", "user:43", "session:9f"} {
fmt.Printf("%-12s -> %s\n", key, ring.Get(key))
}
}
The lookup is a binary search — O(log N) over ring points, where N is the number of points rather than the number of physical machines. The hash function matters more than it looks, in two ways. It must be stable across process restarts, deploys, and library versions, because the moment two application servers disagree on the hash of a key, they disagree on where that key lives. And it must actually spread input evenly: common general-purpose hashes like FNV-1a have known weak spots with structured inputs — strings that differ only in their trailing characters can land in a narrow slice of the hash space, which quietly turns your even ring into a lopsided one. This is easy to check in a test: hash 150 point names into 16 buckets and look at the histogram. Go’s CRC-32 IEEE implementation in the standard library passes that check comfortably and costs almost nothing.
Why bare rings cluster badly: virtual nodes
There is a catch visible in the code above: each machine gets exactly one point on the ring. With three machines, the ring is cut into three arcs, and random arc lengths are wildly uneven. It is entirely possible for one node to own half the ring while another owns a sliver. At small cluster sizes the variance swamps the guarantee.
The fix is the loop in Add: place each physical node at many points — typically 100 to 200 — by hashing composite keys like cache-a#0, cache-a#1, and so on. Each virtual point claims an independent random arc, and by the law of large numbers the total arc length per machine converges toward an even share. Virtual nodes also give you a second lever for free: assign more points to beefier machines so they shoulder proportionally more of the ring, turning the algorithm into a weighted balancer without changing anything else. The cost is memory and lookup time linear in the number of points, which is negligible at realistic scale.
Rendezvous hashing: the no-ring alternative
For smaller clusters there is an even simpler scheme. Instead of maintaining any shared data structure, every client computes a score for each node — a hash of the key and the node name combined — and picks the highest scorer:
package main
import (
"fmt"
"hash/crc32"
)
func score(key, node string) uint32 {
return crc32.ChecksumIEEE([]byte(key + "|" + node))
}
func pick(key string, nodes []string) string {
best := ""
var bestScore uint32
for _, n := range nodes {
if s := score(key, n); s > bestScore {
bestScore = s
best = n
}
}
return best
}
func main() {
nodes := []string{"cache-a", "cache-b", "cache-c"}
fmt.Println(pick("user:42", nodes))
}
This is known as rendezvous (or highest-random-weight) hashing, and it has two attractive properties. Every client computes the same answer from the same node list, so there is no ring to synchronize and no directory service to consult. And when a node disappears, every key it owned moves to its own second-choice node — still only a 1/N fraction of total keys. The trade-off is that resolution is O(N) per lookup and requires the full node list on every client, which makes it a great fit for clusters of tens of nodes and a poor one for thousands. Many teams start with rendezvous hashing and graduate to a ring when the cluster or the client population grows.
Balancing load, not just keys
Consistent hashing balances key ownership, which is not the same as balancing load. A few “hot” keys — one celebrity user, one viral session — can direct disproportionate traffic at a single node even when arcs are perfectly even. The ring has no mechanism to notice this. A refinement called the bounded-loads variant adds a cap: a key is assigned to its ring owner only if that node’s load stays under a small multiple of the average; otherwise the key walks clockwise to the next node with capacity. You get the stability of the ring with an explicit escape hatch for skew, at the price of tracking per-node load somewhere all resolvers can see.
What consistent hashing does not fix
- Data migration. The ring tells you which keys should move; moving them is still your job. Until the data actually lands on the new node, readers get misses, so production systems pair the ring with a transfer process and treat the old node as a fallback during the move.
- Hash stability. Changing the hash function — even upgrading a library that changes its output — remaps everything, exactly like the mod-N scheme you were escaping. Freeze the hash choice per key space and treat it as a wire format.
- Node identity churn. Points keyed off ephemeral pod names like
cache-7f9d2silently reshuffle the ring on every restart. Hash on stable identity (a service-persistent hostname or a fixed node ID), not on instance name.
The deeper lesson is about where instability comes from. The mod-N scheme couples key placement to a cluster size that changes; the ring decouples them by inserting a shared, stable coordinate space. That trick — route through an indirection that does not move when the things behind it do — shows up far beyond caching, in consistent snapshots, in log compaction, anywhere a mapping has to outlive the fleet it describes. If your cache currently falls over every time it scales, this is usually a one-afternoon fix, and it is one of the highest-leverage afternoons you can spend.