The Design Playbook
Consistent hashing
It is 3 a.m. and one of your ten cache servers dies. Annoying — you still have nine. But with the textbook routing rule, the death just remapped almost every key in your cache. Hit rate falls off a cliff, and the database underneath takes the full read storm while the caches warm back up. One machine failed; the whole fleet shuddered. There is a routing scheme where losing one node costs you exactly that node's share and nothing more.
The naive rule is server = hash(key) mod N. It is simple, deterministic, and perfectly balanced — until N changes. Go from 10 servers to 11 and the divisor changes, so hash(key) mod 10 and hash(key) mod 11 disagree for roughly 90% of all keys. Every key that disagrees must move: cache misses everywhere, or a massive data migration in a sharded database. Adding capacity — the thing you do when you are already under load — is exactly when this reshuffle hurts most.
- Take the output space of your hash function — say 0 to 2³²−1 — and bend it into a circle.
- Hash each server (by IP or name) onto the circle. Hash each key onto the same circle, with the same function.
- Each key belongs to the first server you meet walking clockwise from the key's position.
- To find a key's home: hash it, then binary-search the sorted server positions for the next point clockwise — O(log N).
Add an eleventh server to the ring and it lands at one point on the circle. It claims only the arc between itself and the previous server counterclockwise — roughly 1/11 of the keyspace on average. The other ten servers keep every key they had. Remove a server and its arc hands over to the next server clockwise: again about 1/N of keys move, and they move to exactly one neighbor. Nine servers' worth of mappings stay untouched either way.
A raw ring with a handful of servers is lumpy: random placement gives one server an arc several times larger than another's, and every server is treated as equally strong. The fix is virtual nodes — hash each physical server at 100–200 points (server1#1, server1#2, …) sprinkled around the circle. The arcs average out statistically, so load per server lands within a few percent of fair. Bonus: give a beefier machine more virtual nodes and it absorbs proportionally more keys — capacity weighting for free.
Want three copies of each key? From the key's position, walk clockwise and take the next three distinct physical servers — skipping virtual nodes that belong to a machine you already picked. Two copies on the same box are not replication; they are a shared funeral. This is how Dynamo-style systems place replicas, and it has a side benefit: when a node dies, its virtual nodes are scattered, so its load is absorbed in thin slices by many survivors instead of crushing one neighbor.
Mod-N hashing makes every membership change a global event — one server moves, every key reshuffles. Consistent hashing makes it a local event: a node change touches only the arcs adjacent to that node on the ring. You traded a global reshuffle for a local handoff, and the price was a sorted list and a binary search.
You run 4 servers with 100 virtual nodes each. One server is removed. Roughly what fraction of keys must move, and why? (About a quarter — 1/N. Each physical server owns ~100 of the 400 points on the ring, so it governs ~25% of the arcs. Removing it orphans exactly its arcs, each of which slides to the next virtual node clockwise — so ~25% of keys move, spread across the three surviving servers instead of dumped on one.)
Remember three moves. Servers and keys on the same circle; a key walks clockwise to its server. Membership changes cost ~1/N of the keyspace, not ~all of it. Virtual nodes buy balance, weighted capacity, and graceful failure absorption. That is why this idea sits inside Memcached clients, Cassandra, DynamoDB's partitioner, CDNs, and modern load balancers.
Find where your stack already uses consistent hashing — your cache client, your sharded database, your load balancer's routing mode. Read its config and check whether virtual nodes are enabled and how many each server gets. If the count is tiny or zero, write down what the next scale-out will cost you in moved keys, and bring that number to your next architecture review.
The Design Playbook