The problem with hash(key) % N is not that it is unfair.

It is often beautifully fair.

The problem is that it has no memory for the fleet.

If there are 12 cache servers, a key goes to hash(key) % 12. Add one server, and the rule becomes hash(key) % 13. Almost every key gets a new answer. The cluster did the smallest possible operational thing, adding one box, and the hash function responded by evicting the world.

Consistent hashing is the opposite contract:

when one server is added, only about 1/(N+1) of keys should move

The new server should receive its fair share. The old servers should keep the keys that still belong to them. That is the whole magic. Not perfect balance. Not cryptographic mystery. Minimal disruption.

Karger, Lehman, Leighton, Panigrahy, Levine, and Lewin introduced consistent hashing in the context of distributed caching and hot-spot relief on the web.1 Thaler and Ravishankar’s highest-random-weight mapping, now usually called rendezvous hashing, solved a closely related request-mapping problem without a ring: score every server for a key and choose the highest score.2 Later systems kept adapting the same idea because membership churn is a systems fact, not an edge case.

Fair Today, Forgetful Tomorrow

Modulo hashing is a good static assignment rule. With a decent hash function and many keys, each bucket gets roughly the same number.

But a distributed cache is not static. Servers fail. Autoscalers add capacity. Load balancers drain machines. Storage systems rebalance tablets. Operators replace hardware. Membership changes are part of the workload.

So the real assignment rule has two jobs:

  1. spread keys across the current fleet,
  2. preserve as many assignments as possible when the fleet changes.

Modulo hashing optimizes the first job and largely ignores the second. When (N) changes to (N+1), the residue classes are rebuilt. A key that was bucket 7 modulo 12 has no reason to remain bucket 7 modulo 13.

This is why cache clusters using naive modulo assignment can suffer a stampede after resize. The new server receives traffic, yes, but so does every backing database, object store, or origin service behind the cache, because warm keys have been scattered away from their old homes.

The assignment function became an outage amplifier.

Ring Lets Only Its Neighbors Notice

The classic consistent-hashing picture puts both servers and keys on a circle. Hash each server to points on the ring. Hash each key to one point. The key is owned by the first server point clockwise from the key.

If a new server joins, it inserts new points into the ring. It steals arcs from its clockwise neighbors. Keys outside those arcs do not move.

That locality is the contract:

membership changes only affect nearby arcs

Virtual nodes make balance less lumpy. Instead of one point per server, give each server many points. More virtual nodes approximate a smoother partition of the ring. Fewer virtual nodes are cheaper to store and update, but produce noisier load.

This is the first useful distinction:

minimal movement and perfect balance are not the same metric

A ring can be wonderfully stable and still temporarily imbalanced if the arcs are uneven. More virtual nodes buy a better balance distribution.

No Ring, Same Courtesy

Rendezvous hashing removes the ring table. For a key (k) and server (s), compute a score (h(k,s)). Assign the key to the server with the highest score.

If a new server joins, every key compares its current winner with the new server’s score. The key moves only if the new server wins. Existing servers do not reshuffle among themselves.

That means rendezvous hashing has the same monotonicity property:

adding a server moves only keys assigned to the new server

It is simple and elegant. The cost is lookup work: in the direct version, each key must score every server. That can be fine for small server sets or control planes. For very large fleets or very hot data paths, systems use variants, tables, trees, jump hashing, or other indexing tricks.

Lamping and Veach’s jump consistent hash is a particularly compact later point in this design space: it maps a key to one of a sequentially numbered set of buckets with minimal memory and a tiny algorithm, though it assumes bucket numbers are dense and sequential.3

Add One Server and Watch the Damage

The lab below compares three assignment rules:

  1. modulo hashing,
  2. a consistent hash ring with virtual nodes,
  3. rendezvous hashing.

It generates keys, assigns them to (N) servers, adds one server, and measures which keys move. It also tracks count balance and hot-key weighted balance. The “hotness” slider makes the workload more skewed: a small number of keys carry more traffic.

modulo hashing virtual-node ring rendezvous hashing highlighted ring node

The movement metric is key count movement after adding one server. Hot-load max is traffic-weighted and can be high even when key counts are balanced.

In the default run, modulo hashing moves 92.1% of keys after adding one server, but only 7.5% of keys land on that new server. Most of the churn is old servers trading keys with one another. The ring moves 8.4% and rendezvous moves 8.2%, close to the 7.7% minimal target for growing from 12 to 13 servers. More important, every moved key under those two rules goes to the new server.

The Invariant Is Where the Moved Keys Land

The important invariant is not the exact percentage in one run. It is where the moved keys go.

For the ring and rendezvous hashing, every moved key after adding a server is a key assigned to the new server. Old servers do not reshuffle keys among themselves. The new server takes its share; the rest of the fleet stays warm.

Modulo hashing fails that monotonicity test. Most moved keys are not moving because the new server claimed them. They are moving because every residue class was renumbered.

That is the difference between:

resize changed the ownership boundary

and

resize changed the meaning of every bucket number

The virtual-node slider shows a second issue. With few virtual nodes, the ring can be lumpy: some servers own long arcs and some own short arcs. Increasing virtual nodes improves balance but increases ring metadata. Rendezvous hashing often has good balance without storing a ring, but direct lookup scores every server. There is no free implementation. There is a contract and a cost model.

A Fair Key Count Can Still Burn

Key-count balance is not traffic balance.

If all keys are equally popular, a server with 8% of keys receives roughly 8% of traffic. But caches and load balancers rarely see uniform traffic. A few objects or flows can dominate. Then a perfectly fair assignment by key count can still put too much work on one server.

Consistent hashing does not solve hot keys by itself. Karger et al.’s original paper was also about hot spots, but consistent hashing is only one tool in that larger problem.1 Real systems add replication, request coalescing, adaptive load shedding, power-of-two choices, lease protocols, or application specific splitting.

This is why the lab reports hot-load max separately. A hash function can keep remapping small and still leave you with a hot shard.

The assignment rule answers:

where should this key go?

Hot-key mitigation asks:

what if one key is too much for one server?

Those are different problems.

Choose the Assignment Contract

The answer depends on the shape of the fleet.

Use a virtual-node ring when membership is arbitrary, weights matter, and a shared ring table is acceptable. This is the mental model many engineers learn first, and it remains useful.

Use rendezvous hashing when the server set is moderate or when the simplicity of stateless membership scoring is more valuable than lookup cost. It handles arbitrary server names naturally and has a clean monotonicity property.

Use jump consistent hash when buckets are dense integers and you want a compact, fast, minimal-memory mapping.3 Its constraints are real, but so is the elegance.

Use a specialized load-balancer table, such as Maglev’s permutation-based approach, when packet-level speed, near-even backend distribution, and bounded disruption matter together.4

Use modulo only when the bucket count is genuinely stable, or when remapping is cheap enough that you do not care.

That last clause is not a joke. Sometimes remapping is cheap. If the data is ephemeral, recomputable, or already replicated everywhere, the simple rule may win. Consistent hashing is not morally superior. It is a specific answer to a specific pain:

membership changed, but most keys should not notice

The Cache Remembers Yesterday’s Function

The reason this topic matters is not that hashes are clever. It is that caches, connections, tablets, and shards accumulate history.

A cache line is warm because yesterday’s assignment function sent the same key to the same machine. A TCP flow is sticky because every packet in the flow keeps landing on the same backend. A storage shard is useful because replicas know which range or hash partition they own.

Change the assignment function and you change the meaning of that memory.

Consistent hashing protects the memory. It lets the system grow or shrink while disturbing only the part of the key space whose owner actually changed.

That is the hidden contract behind the ring:

new capacity should absorb load, not erase history

The key should notice the new server only when the new server is now its home.

  1. David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, and Daniel Lewin, “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”, STOC 1997. ↩ ↩2

  2. David G. Thaler and Chinya V. Ravishankar, “Using Name-Based Mappings to Increase Hit Rates”, IEEE/ACM Transactions on Networking, 1998. ↩

  3. John Lamping and Eric Veach, “A Fast, Minimal Memory, Consistent Hash Algorithm”, 2014. ↩ ↩2

  4. Daniel E. Eisenbud et al., “Maglev: A Fast and Reliable Software Network Load Balancer”, NSDI 2016. ↩