Consistent Hashing in Go: Why hash(key) % N Breaks and How a Ring Fixes It

You run a cache with 10 nodes. To decide where a key lives, you do the obvious thing: hash(key) % 10. It is fast, stateless, and every client computes the same answer. Then traffic grows and you add an 11th node.

Now hash(key) % 11 gives a different answer for almost every key. Nearly the whole cache is suddenly in the wrong place, every lookup misses, and your database takes the full load at the worst possible moment.

This is the first article of a series on the mathematics behind distributed systems. We start with the structure that fixes this problem: consistent hashing. The code is Go, and the numbers below come from running it.

The problem: modulo ties every key to N

With hash(key) % N, a key's owner depends on N itself. Change N and the whole mapping shifts. I hashed 100,000 keys and went from 10 nodes to 11:

modulo 10->11 moved: 91.0%

For a key to keep its owner after going from N to N+1 nodes, its hash must give the same remainder mod N and mod N+1. That is rare, so about N/(N+1) of all keys move. The ideal answer is much smaller: the new node should take roughly 1/(N+1) of the keys, and nobody else should lose anything they did not have to give up.

The idea: put keys and nodes on the same ring

Hash the space of possible values onto a circle, say 0 to 2^32 - 1, where the end wraps to the start. Then:

1. Hash each node to a position on the ring.
2. Hash each key to a position on the ring.
3. A key belongs to the first node clockwise from its position.

Now a node owns only the arc between its predecessor and itself. Add a node and it takes over a slice of one neighbour's arc. Remove a node and its arc falls to the next one clockwise. Every other key stays exactly where it was. On average only K/N keys move, where K is the number of keys and N the number of nodes. That is the mathematical content: ownership depends on relative order on a circle, not on the count of nodes.

Implementation in Go

The ring is a sorted slice of positions plus a map from position to node. Lookup is a binary search for the first position >= hash(key), wrapping to index 0 past the end.

type Ring struct {
    replicas int
    points   []uint32          // sorted ring positions
    owner    map[uint32]string // position -> node
}

func hash32(s string) uint32 {
    sum := sha256.Sum256([]byte(s))
    return binary.BigEndian.Uint32(sum[:4])
}

func (r *Ring) Add(node string) {
    for i := 0; i < r.replicas; i++ {
        p := hash32(fmt.Sprintf("%s#%d", node, i))
        r.owner[p] = node
        r.points = append(r.points, p)
    }
    sort.Slice(r.points, func(a, b int) bool { return r.points[a] < r.points[b] })
}

func (r *Ring) Get(key string) string {
    h := hash32(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
    }
    return r.owner[r.points[i]]
}

Lookup costs O(log P) where P is the number of points on the ring. Adding or removing a node costs a re-sort here for clarity. A production version would insert in place, and guard the ring with a sync.RWMutex since lookups are far more frequent than membership changes.

The replicas field is the next idea, and it matters more than it looks.

Virtual nodes: fixing the uneven ring

With one point per node, positions are random, and random points on a circle make arcs of very different lengths. One node can own a huge arc by luck. Rather than hash each node once, hash it replicas times (node-3#0, node-3#1, ...). Each node now owns many small arcs scattered around the ring, and by the law of large numbers its total share converges toward 1/N.

I ran 100,000 keys over 10 nodes, then added an 11th, for several virtual node counts:

Two things stand out. Movement on node addition sits near the ideal 9.1% (versus 91% for modulo) at every setting, so the ring's stability does not depend on vnodes. Balance does: with a single point the busiest node carries three times its fair share, and you need on the order of 100 or more virtual nodes to get within about 20% of even. The cost is memory and a larger sorted slice, which is cheap.

Virtual nodes also let you do weighted placement for free: give a node with twice the capacity twice the replicas.

The mistake that quietly wrecks it: a weak hash

My first run used hash/fnv, a fast non-cryptographic hash that feels like the right tool. The numbers were bad:

vnodes= 10  max/mean=3.96  std dev=102%     (FNV-1a)
vnodes= 10  max/mean=1.38  std dev=24.7%    (SHA-256, first 4 bytes)

Same code, same keys, same 10 virtual nodes. The difference is the hash. Node labels like node-3#7 are highly similar strings, and FNV-1a mixes similar inputs poorly, so the virtual nodes cluster instead of spreading. The ring's guarantees assume positions that look uniformly random. If your hash does not deliver that, adding virtual nodes will not save you.

Use a hash with good avalanche behaviour. SHA-256 truncated works and is plenty fast for this. In production you will often see MurmurHash3 or xxHash, which are fast and mix well. Whatever you pick, measure the load spread as above before trusting it.

Where this runs in real systems

• Distributed caches (memcached client libraries such as ketama, Redis clients) pick a shard per key this way, so scaling the cache does not flush it.
• Dynamo-style databases (Cassandra, Riak, DynamoDB's lineage) place data on a token ring and replicate to the next nodes clockwise.
• Load balancers use it for sticky routing. The load balancing article covers the same structure from the request-routing angle: Load Balancing Algorithms.

Limits and alternatives

• Hot keys. The ring balances keys, not traffic. One very popular key still overloads one node, and no amount of hashing fixes that. You need replication or caching in front.
• Rebalancing is still real work. Only K/N keys move, but they do move, and something must actually copy that data.
• Rendezvous (highest random weight) hashing scores every node per key and picks the top one. It needs no ring or vnodes and balances well, at O(N) per lookup.
• Jump consistent hash needs no memory at all and balances nearly perfectly, but nodes can only be added or removed at the end of a numbered list, which suits sharded storage better than a cache whose nodes fail at random.

Takeaways

• hash(key) % N makes ownership depend on N, so changing N moves about N/(N+1) of the keys (91% from 10 to 11 nodes in my run).
• A hash ring makes ownership depend on position on a circle: adding or removing a node moves only about K/N keys.
• One point per node gives lopsided arcs. Use roughly 100 or more virtual nodes per node to even out load.
• The ring assumes a well-mixing hash. A weak one like FNV-1a on similar labels erased the benefit of vnodes in my test, so measure.
• It balances keys, not traffic. Hot keys need a different answer.

Next in the series: how distributed systems order events without a shared clock, with Lamport and vector clocks.