Why naive hashing breaks at scale
Imagine you're building a caching web proxy that must distribute cached URLs across multiple servers. The obvious approach is to hash each URL and assign it to a server using modular arithmetic: compute the hash, then take the remainder when dividing by the number of servers N.
hash := calculateHashFunction(url) nodeId := hash % N
This works fine when N is fixed. But in real systems, the cluster isn't static. Nodes crash, get taken offline for maintenance, or are added to handle load spikes. The moment N changes, virtually every key gets remapped to a different server, causing a wave of cache misses exactly when you can least afford them — during peak traffic.
To see how severe this is, consider a concrete implementation using Go's md5 package:
// hashItem computes the slot an item hashes to, given a total number of slots.
func hashItem(item string, nslots uint64) uint64 {
digest := md5.Sum([]byte(item))
digestHigh := binary.BigEndian.Uint64(digest[8:16])
digestLow := binary.BigEndian.Uint64(digest[:8])
return (digestHigh ^ digestLow) % nslots
}
Starting with 32 slots, hashing the strings "hello", "consistent", and "marmot" yields:
hello (n=32): 4 consistent (n=32): 14 marmot (n=32): 5
Adding just one more slot (33 total) changes every mapping:
hello (n=33): 23 consistent (n=33): 18 marmot (n=33): 31
This is the core problem: adding or removing a node invalidates nearly all cached items. Every query hits the origin server until the cache repopulates.
The consistent hashing approach
Consistent hashing sidesteps this by changing the assignment rule. Instead of computing a slot number directly, both nodes and items are mapped onto a circular interval — think of a unit circle. An item is assigned to the first node encountered when moving clockwise from the item's position on the circle.
In the diagram, item Ix maps to node N1, Iy to N2, and Iz to N3. Now suppose N3 is removed. Iz simply shifts clockwise to N5. The mappings for Ix and Iy remain untouched. Adding a node has the same property: if a new node N6 lands between Iy and N2, only Iy remaps; everything else stays put.
With M items and N nodes, naive hashing remaps all M items whenever the cluster size changes. Consistent hashing remaps only a fraction proportional to the change. This is the monotonicity property from the original paper:
If items are initially assigned to a set of buckets, and then some new buckets are added, an item may move from an old bucket to a new bucket, but not from one old bucket to another.
A practical implementation
Implementing consistent hashing requires sorting node positions and searching for the closest node clockwise from any item's hash. A balanced binary search tree is one option; a sorted array with binary search works just as well and is simpler in Go.
Two practical decisions shape the implementation. First, instead of a continuous [0, 1) interval, we quantize to [0, ringSize), where ringSize is large enough to make collisions negligible. Second, we treat the circle like a clock face: position 0 is "north" (12 o'clock), ringSize/4 is 3 o'clock, and so on. When a node is added, its location is computed by hashing its name with nslots=ringSize.
type ConsistentHasher struct {
// nodes is a list of nodes in the hash ring; it's sorted in the same order
// as slots: for each i, the node at index slots[i] is nodes[i].
nodes []string
// slots is a sorted slice of node indices.
slots []uint64
ringSize uint64
}
// NewConsistentHasher creates a new consistent hasher with a given maximal
// ring size.
func NewConsistentHasher(ringSize uint64) *ConsistentHasher {
return &ConsistentHasher{
ringSize: ringSize,
}
}
Node positions live in a sorted slice called slots, with the corresponding node names in nodes. For each index i, nodes[i] sits at position slots[i] on the circle. Finding the node for an item is a binary search for the first slot at or after the item's hash:
// FindNodeFor finds the node an item hashes to. It's an error to call this
// method if the hasher doesn't have any nodes.
func (ch *ConsistentHasher) FindNodeFor(item string) string {
if len(ch.nodes) == 0 {
panic("FindNodeFor called when ConsistentHasher has no nodes")
}
ih := hashItem(item, ch.ringSize)
// Since ch.slots is a sorted list of all the node indices for our nodes, a
// binary search is what we need here. ih is mapped to the node that has the
// same or the next larger node index. slices.BinarySearch does exactly this,
// by returning the index where the value would be inserted.
slotIndex, _ := slices.BinarySearch(ch.slots, ih)
// When the returned index is len(slots), it means the search wrapped
// around.
if slotIndex == len(ch.slots) {
slotIndex = 0
}
return ch.nodes[slotIndex]
}
Adding and removing nodes follow the same binary-search pattern — see the full source for details.
Virtual nodes for balanced load
Even with a perfect hash function, distributing nodes around the circle leads to uneven gaps. With N nodes uniformly distributed on a circle, the gap sizes follow a Beta distribution with parameters (1, N-1). The variance is significant: with 20 nodes, the standard deviation of the gap is about 17 degrees, comparable to the average gap of 18 degrees.
In one simulation with 20 random node positions, the smallest gap was just 1.04 degrees while the largest was 42 degrees. That means the busiest node can receive roughly 40 times more items than the least busy one — a serious imbalance for capacity planning.
Virtual nodes fix this. Instead of mapping each node to a single point on the circle, map it to V points by varying the node name:
for i := range V {
vnodeName = fmt.Sprintf("%v@%v", node, i)
// ... now add vnodeName to the nodes/slots slices
}
When looking up an item, you find whichever virtual node is closest clockwise, then strip the @<number> suffix to get the real node name. Averaging the positions of a node's V virtual replicas dramatically reduces variance. In a simulation with 10 virtual nodes per node, the smallest gap grew to 11 degrees and the largest shrank to 26, with the average still at 18 degrees.
The user-facing API stays identical; only the internals change. The repository includes a ConsistentHasherV type demonstrating this variant, along with the full simulation experiments in demo.go.
