Consistent Hashing

Imagine you run a big web cache. You have n servers, and for each key you decide where it lives with the obvious trick: server = hash(key) mod n. Cheap, fast, evenly spread. Then one server dies, or you add a new one — and n changes.

Now almost every key maps somewhere new. A cache that was warm goes cold all at once; databases stampede; users wait. Changing a single machine should not reshuffle the whole world, yet plain modulo hashing does exactly that.

Consistent hashing fixes this with one beautifully simple move: instead of dividing by n, place both servers and keys on a circle. Add or remove a server and only the keys in its immediate neighborhood — about 1/n of them — ever have to move.

Below is a hash ring. The colored wedges are servers; the small dots are keys. Each key belongs to the first server you meet going clockwise. Add or remove a server and watch the counter: only the keys that change owner light up, and there are surprisingly few of them.

<p class="hint">{{hint}}</p>
<div class="wrap">
  <svg id="ring" viewBox="0 0 320 320" width="300" height="300" aria-label="{{aria_ring}}"></svg>
</div>
<div class="status" id="status">3 servers, 30 keys.</div>
<div class="btns">
  <button id="add" type="button">{{btn_add}}</button>
  <button id="remove" type="button">{{btn_remove}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.wrap { display: flex; justify-content: center; }
svg { max-width: 100%; height: auto; }
.key { fill: #9aa0a6; transition: fill .2s, r .2s; }
.key.moved { fill: #e63946; }
.srv-dot { stroke: #fff; stroke-width: 2; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; text-align: center; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: not-allowed; }

// Code not found

Try adding several servers in a row. With plain $hash(key) \bmod n$, every add would relocate nearly 100% of keys. On the ring, each new server steals only the slice between it and its clockwise neighbor — on average about 1/n of all keys. That gap between "move everything" and "move a sliver" is the whole reason large systems can grow without falling over.

Consistent hashing is not an open problem or an impossibility result — it is a solved engineering idea with proven guarantees, introduced by David Karger and colleagues at MIT in 1997. Here is what it buys you:

• Minimal disruption. With K keys and n servers, adding or removing a server relocates only about K/n keys on average. Plain modulo hashing relocates almost all K.
• Fast lookups. Servers sit at sorted positions on the ring, so finding the owner of a key is a binary search: $O(\log n)$ per lookup.
• Monotonicity. When you add a server, keys only ever move to the new server, never bouncing between existing ones. That is the property plain hashing lacks.
• Balance via virtual nodes. A single point per server can leave the ring lumpy. The fix is to place each server at many random positions ("virtual nodes"), which evens the load to within a small factor with high probability.

None of this is NP-hard or undecidable. The depth is in the analysis: proving that random placement on a ring keeps loads balanced and key movement minimal is a clean probabilistic argument, the same flavor that powers load balancing and hashing-based pattern matching.

Once you can add and remove machines without reshuffling everything, you can build systems that grow elastically. Consistent hashing is the quiet workhorse behind much of the cloud:

• Distributed databases: Amazon Dynamo, Cassandra, Riak and ScyllaDB place data on a ring so nodes can join and leave with minimal data movement.
• Caching layers: memcached client libraries and Redis Cluster-style setups use the ring so a dead cache node only invalidates its own slice.
• Content delivery networks: CDNs route a URL to a cache server by hashing it onto a ring, keeping requests sticky as the fleet changes.
• Load balancers: ring hashing keeps a given client mapped to the same backend, preserving sessions and warm connections.

The common thread is the same shape as in load balancing: spread work fairly, and let the system absorb change gracefully instead of all at once.

Consistent hashing is a rare thing in computer science: a problem that looks like it should be hard — keep data placement stable as machines come and go — that turns out to have an elegant, provably good answer. Wrap the address space into a circle, walk clockwise to find an owner, and a single failed or added server disturbs only its own neighborhood.

It will not solve anything from P vs NP. But it is one of those ideas that quietly makes the impossible-seeming routine, letting a handful of servers grow into a planet-scale system without ever moving more than it has to.