BOOK DEEP READ · System Design Interview Vol 1 · Ch 5

Design Consistent Hashing

System Design Interview: An Insider's Guide · Vol 1 · Ch 5 · Alex Xu · 2020

What is this chapter about?

Your parcels pass through a sorting hub. A handful of warehouses sit there, and every parcel is routed to one of them by its tracking number. The sorting rule has to do two things: be fast (one glance at the number tells you the warehouse — no ledger lookup) and be stable (next time you look for that parcel, the rule sends you to the same warehouse). This chapter is about that rule, and about what happens to it when the number of warehouses changes.

Something strange first

You would assume that going from four warehouses to five means moving roughly a fifth of the goods into the new one. With the most common rule, you have to physically move about eighty percent of everything — and not into the new warehouse, but from one old warehouse to a different old warehouse. Open one building, and the whole city's freight has to move.

Why the old world was hard

That common rule is: divide the tracking number by the number of warehouses and look at the remainder. Four warehouses, remainders 0 to 3, one each. Simple and fast. The trouble is that "the number of warehouses" is baked into the formula. Go from four to five and the divisor changes, so nearly every parcel gets a different answer. They do not mostly stay put with a few moving to the new building — they all shuffle at once.

The consequence is immediate, because the sorting hub is really a cache. Normally almost everyone is served nearby; the moment the warehouse count changes, everybody looks in the wrong place, and the requests slam into the slow, expensive central store behind it. What kills the system is not the machine you added — it is the move itself.

The core idea: stand the warehouses in a circle

Try another way. Imagine every possible tracking number laid out on a circular running track whose end joins its start. Each parcel lands somewhere on the track according to its number; each warehouse also lands somewhere according to its name. The rule becomes one sentence: walk forward from where the parcel landed, and the first warehouse you meet owns it.

The beauty is that "how many warehouses" has vanished from the formula. Opening one is just dropping a new point onto the track — only the parcels lying in the short stretch behind that new point have to move, and everything else on the track stays exactly where it is. Closing one is the mirror image: its stretch is handed forward to the next warehouse, and nobody else notices.

It still needs a patch

That alone is not even enough. Warehouses land on the track at random, so three may cluster together and leave one enormous gap belonging to the fourth — which then gets crushed. The patch is crude and effective: let every warehouse open dozens or hundreds of "branches" on the track, each with a numbered name and its own landing spot. With enough branches, the long and short stretches get chopped up and averaged out, so each warehouse ends up with roughly its fair share. Those branches are called virtual nodes.

One honest cost: more branches is not simply better — the more little stretches a warehouse's goods are scattered across, the more neighbours it is entangled with, so the day two warehouses fail together, the damage reaches further.

Remember this one line

The old rule wrote "number of warehouses" into the formula, so changing that number moves the whole city. Consistent hashing stands the warehouses in a circle and lets each parcel take the nearest one clockwise, so adding or removing one disturbs a single stretch. Then give every warehouse a pile of branches to even out the uneven arcs.

Want the algorithm, the numbers and the diagrams? → Switch to the deep read

In one sentence

You think consistent hashing is "a better hash function." In fact it does not make data any more evenly distributed — that job belongs to the patch bolted on afterwards (virtual nodes). It buys exactly one thing: it drops the amount of data you must move when the cluster resizes from "nearly all of it" to "1/N." This is the most algorithm-like chapter in the book, and the idea worth keeping is broader than the algorithm: any scheme that writes the machine count into its routing formula detonates the moment you add a machine.

Glossary

Hash function — squeezes any input (a string, a key) into a fixed-length number. The same input always yields the same output, and different inputs spread out as widely as possible.
Key — the name of a piece of data, e.g. user:8613. The system uses it to decide which machine holds that data.
Sharding / partitioning — when one dataset no longer fits or no longer copes, you cut it into pieces, one per machine. "Routing" means deciding which piece a key belongs to.
Modulo — the remainder of a division, written %. hash(key) % 4 means "divide by 4, take the remainder," always 0–3.
Rehashing — recomputing every key's owner and physically relocating the data after the machine count changes.
Cache hit rate — the share of requests served straight from cache. When it drops, the pressure passes through to the database untouched.
SHA-1 — a common hash function producing 160 bits (a number between 0 and 2^160-1). This chapter borrows only its "spreads out well" property.
Virtual node — one physical machine's multiple stand-in positions on the ring, used to chop its share into many small arcs. Cassandra calls them tokens.
Standard deviation — how far apart a set of numbers sit. Here it measures how unequal the machines' data volumes are; smaller is more even.
Replica — the same data stored on several machines so a single failure does not lose it.
Hot key — one single key hammered by traffic, like a celebrity's profile. There is only ever one copy of it.

Where it sits

The second case study of Part II, and the shortest, most component-like chapter in the book: no API, no data model, just an algorithm. It picks up exactly where Ch4's rate limiter left off — dozens of stateless limiters, and the question of how their quota state is spread across several caches. Looking forward, it is the first brick of Ch6, "Design a Key-Value Store": the whole Dynamo kit is built on this ring. In the real world: data partitioning in Dynamo and Cassandra, edge-node selection in CDNs, Google's Maglev load balancer, and any multi-node cache tier.

The problem it solves

It is one sentence: the number of machines changes, and the most intuitive routing formula cannot survive that.

That formula is serverIndex = hash(key) % N — N servers, one remainder, done. It is fast, it is stable (no routing table to maintain), and it distributes evenly. Its only flaw: N appears in the formula.

Do the arithmetic on how big that flaw is. Four cache servers, one dies, N goes from 4 to 3: only about 1/4 of keys still land on their original machine, so the other 75% change owners — when ideally only the dead machine's own share, 25%, should have moved. Adding is just as bad: 4 servers to 5 relocates roughly 80% of keys, against an ideal of 20%.

What if you do not solve it? Cost it out. A cache tier absorbing 100,000 QPS at a 99% hit rate lets only 1,000 requests per second through to the database. One cache dies, clients recompute the modulo against the new N, and instantly ~75% of keys are asking the wrong machine. The hit rate collapses toward 25% and database traffic becomes 75,000 requests per second — roughly a 75× amplification. Connection pools fill, latency climbs, timeout retries pile a second wave on top: the cache has not even recovered and the backend is already down. The book calls this a cache miss storm. What kills the system is not the machine that died — it is the global reshuffle that follows.

The core, explained properly

1. Take N out of the formula

This is the chapter's only real idea; everything else is engineering around it. Use a locating scheme that does not need to know how many machines exist: put both machines and keys at positions in the same fixed coordinate space, and let ownership follow from relative position rather than from the total. Adding or removing a machine is then just adding or removing one point — every other point stays exactly where it was.

Fig 1 · The same 4-to-3 event. Modulo relocates about three quarters of all keys; consistent hashing touches only the dead machine's share. Those 50 percentage points are the distance between a cache stampede and a quiet scale-down.

2. The hash ring: swap division for "find the neighbour"

That fixed coordinate space is the hash ring. Take a hash function (the book uses SHA-1) whose output spans 0 to 2^160-1, then join the two ends of that line into a circle. Three steps follow:

Place the servers — hash each server's IP or hostname to a point on the ring.
Place the keys — hash each key to a point on the ring too. Note that there is no modulo here: keys land on the ring, not on a machine.
Look up the owner — walk clockwise from the key's position; the first server you meet owns it.

Add a server s4 and it slots into some position on the ring. Only the keys in the range running counter-clockwise from s4 back to the previous server change hands; the rest of the ring is untouched. Removal is the mirror image: the departing server's range is handed clockwise to the next one.

This is precisely the property Karger et al. gave in their 1997 paper: when the hash table is resized, only k/n keys need to be remapped on average (k keys, n slots) — in plain terms, "add a machine, move 1/n of the data."

Fig 2 · Left: a key walks clockwise to its first server. Right: inserting s4 disturbs only the range running counter-clockwise from s4 to the previous server — the same formula real systems use to compute a migration range.

3. Two flaws in the basic ring

Use the ring exactly as described and you hit two problems, both rooted in randomness. The book names them side by side:

Flaw one: partitions are not the same size. Server positions come out of a hash, which amounts to scattering points at random, so the arcs between neighbours differ wildly. Worse, it degrades as the cluster changes: remove a server and its arc merges into its neighbour, which may suddenly carry twice what anyone else carries.

Flaw two: keys are not evenly distributed either. Even with perfectly equal arcs, the keys themselves can cluster into one small stretch. In the extreme, one machine owns a densely populated range while another is handed no keys at all.

Notice these are two faces of one fact: basic consistent hashing guarantees only that moving is cheap. It never guaranteed even distribution. Conflating those two is the most common misreading of this chapter.

4. Virtual nodes: crush the variance with volume

The patch: one physical server no longer occupies a single point on the ring, but many. Server s0 sends out s0_0, s0_1, s0_2… each hashed and placed independently. The lookup rule is unchanged (walk clockwise to the first virtual node), except that at the end you map the virtual node back to the physical machine behind it.

The intuition in one line: a machine no longer bets its whole existence on the length of one arc; it bets on the average of two hundred small ones. One bet has enormous variance; two hundred bets get flattened by the law of large numbers. The book cites an experiment: with 100 virtual nodes the standard deviation of load is about 10% of the mean, and with 200 it is about 5%. The cost the book gives is storage — more points on the ring means a bigger mapping table and slightly slower lookups. (The costlier one it omits is in "Pitfalls" below.)

Virtual nodes also solve a problem the Dynamo paper stresses and the book leaves aside: heterogeneity. Machines in a cluster are rarely equal, and virtual nodes make "give the strong one more work" trivial — hand it more stand-ins. Weight is expressed purely as a count, and not a line of routing logic changes.

Fig 3 · Left: one point per server, arc length left to luck, and the busiest machine can carry nearly double the lightest. Right: many interleaved stand-ins per server let long and short arcs cancel out, so shares converge.

5. Computing the affected key range

The book gives this its own section, because "knowing how much moves" and "knowing which keys move" are different things. The rule is short: when adding a node, the affected range runs counter-clockwise from the new node's position back to the previous node; when removing one, it runs counter-clockwise from the departing node back to the previous node, and those keys are handed clockwise to the next node.

Why get it exactly right? Real systems move data by range-scanning a token interval and streaming it — that is precisely what a Cassandra bootstrap does. Compute the range too narrow and you skip keys, losing data permanently; compute it too wide and you have a full scan that can saturate cluster I/O for hours.

Key trade-offs

Table 1 · Three routing schemes: movement, evenness, control

Scheme	Data moved per node change	Evenness	Metadata cost	Handles heterogeneity?	Fits
Modulo `hash % N`	≈ everything (4→3 moves 75%)	Good	Zero; the client just computes it	No	A shard count that never changes, or a rebuild you can take downtime for
Consistent hashing + virtual nodes	1/N, the theoretical optimum	Depends on stand-in count (100 ≈ 10% std dev)	V tokens per node, gossiped across the cluster	Yes — hand out more stand-ins	Peer-to-peer clusters with no coordinator: Dynamo, Cassandra, cache tiers
Central lookup table (fixed slots)	Move whichever block you like — fully controlled	Best; you can rebalance deliberately	One authoritative map plus a way to distribute it	Yes, by slot allocation	Precise placement control: Redis Cluster (`16384` slots), Vitess

The third row deserves a second look: consistent hashing is not the only answer, and plenty of mature systems chose "a big pile of fixed slots plus a mapping table" instead. The price is a control plane — who owns that table, how it reaches every client — and what you buy is that placement is decided by a human: hot blocks can be moved by hand, expansions can be staged. Consistent hashing's advantage is that it needs no centre; its cost is that you cannot direct it either.

Table 2 · Choosing the number of virtual nodes (figures from Apache Cassandra's production guidance)

Tokens per node	Evenness	Expansion flexibility	Availability impact	What Cassandra says
1	Worst	Poor: you must double the cluster to stay balanced	Best — data shared with the fewest peers	"Maximum availability, maximum cluster size, fewest peers"
4	Medium	Good: roughly +20% nodes per step	Good	Recommended for clusters that will exceed 30 nodes
8	Better (~10% variance)	Good	Fairly good	"Minimal impact on performance"
16 (current default)	Good	Best, for clusters that grow and shrink often	Weaker	"Not recommended for clusters over 50 nodes"

Table 3 · What consistent hashing solves, and what it does not

	Content
Solves	Cuts data movement on resize to 1/N; gives coordinator-free routing — every client computes the owner locally, asking nobody; expresses machine weight through stand-in counts
Does not solve	A single hot key (there is one copy; whichever machine holds it burns); cross-shard queries and transactions; replica placement (skipping same-rack, same-datacentre); where reads and writes go mid-migration

Why it matters / in real systems

This algorithm is the entry ticket to coordinator-free distributed storage: if you want a system where the client alone can work out where data lives, you cannot avoid it. It is also a very high-frequency interview follow-up — and what separates candidates is never the phrase "ring plus virtual nodes," but how you compute the affected range, and why more virtual nodes is not simply better.

EVIDENCE FROM THE FIELD · these are the companies' own public claims, not the book's

Amazon states plainly in the Dynamo paper that basic consistent hashing has two problems — the random position assignment of each node on the ring leads to non-uniform data and load distribution, and the basic algorithm is oblivious to the heterogeneity in node performance — and that the fix is assigning each node multiple positions on the ring, i.e. virtual nodes. The paper adds a third benefit: how many virtual nodes a machine takes can be decided by its capacity. This is the original source of both "flaws" and the patch in this chapter. Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007 ↗
Apache Cassandra's production guidance supplies the half-sentence the book omits: vnodes make expansion smoother, "however, more tokens leads to sharing data with more peers, and results in decreased availability," and the two must be balanced against the cluster's read/write profile. Its current default is num_tokens: 16, and it says outright that 16 is "not recommended for clusters over 50 nodes." That is the most direct rebuttal available to "more virtual nodes is better." Apache Cassandra docs, "Production recommendations · Tokens" ↗
Discord published its own scale and its own pain: 12 Cassandra nodes holding billions of messages in 2017 grew to 177 nodes and trillions of messages by early 2022, and the worst problem was the hot partition — one very active channel in a large public server overwhelming a single partition, making latency unpredictable and paging on-call repeatedly. Consistent hashing spreads keys evenly; it cannot spread the traffic on one key. Here is the live counterexample. Discord Blog, "How Discord Stores Trillions of Messages" ↗
Google's Maglev — the software network load balancer that has carried Google's public traffic since 2008 — took a different route: it implements consistent hashing with a fixed-size lookup table, aiming beyond "minimal disruption when nodes change" at better evenness than a naive ring gives. The ring is not the only implementation; "minimal disruption" and "evenness" can be balanced with another structure. Eisenbud et al., "Maglev: A Fast and Reliable Software Network Load Balancer," USENIX NSDI 2016

Pitfalls and open questions

Mistaking "cheap to move" for "evenly spread." The basic ring guarantees only the former. Evenness comes from virtual nodes, and only probabilistically — at 100 stand-ins the standard deviation is still 10%, so the busiest machine routinely carries a tenth more than average. Capacity-plan against the busiest node, not the mean.
Assuming more virtual nodes is always better. The book mentions only the storage cost and misses the expensive one: the more stand-ins, the more peers a machine's data is entangled with, so any two simultaneous failures are likelier to take out every replica of some piece of data — availability drops. Cassandra walking its default down from 256 to 16 is exactly this. "More is more even" holds on paper and traps you in production.
Thinking consistent hashing cures hot spots. The book says it mitigates the hot-key problem and cites celebrity accounts; read that carefully. What it evens out is the distribution of many keys. If traffic concentrates on one single key, that key has one home and that home burns. The real fixes live elsewhere: split the hot key into N with a random suffix, or add a client-side local cache.
Agonising over the hash function. SHA-1 is just an example; MD5 and MurmurHash work and are faster. Nothing here needs cryptographic properties — only that the output spreads well and that every client computes the same value. The iron rule runs the other way: changing the hash function means moving everything, just as painful as changing N in a modulo, so it is a near-irreversible decision.
Forgetting replicas. Real storage does not use "the first server clockwise" but "the next N clockwise, skipping the same host and the same rack" — that is what Dynamo's preference list does. Without it the ring is a routing algorithm, not a system that can hold data.
Forgetting the migration window. The book explains which keys move but not where reads and writes go while they are moving. The new node has not finished syncing — who serves the read? Cassandra uses pending ranges so requests hit both old and new locations during a migration. The most laborious step between algorithm and system sits just outside the book's frame.

Takeaways

1. The root cause in one line: hash(key) % N writes the machine count into the routing formula, so changing N relocates almost every key. Four servers down to three moves about 75% of keys; the ideal is 25%.

2. The cost is a stampede, not an inconvenience: at 100,000 QPS and a 99% hit rate, one global rehash takes database traffic from 1,000 to 75,000 requests per second — roughly 75×.

3. One idea fixes it: take N out of the formula. Join the hash space into a ring, place servers and keys on it, and let the first server clockwise own the key. Adding or removing one moves 1/N — the k/n property from Karger's 1997 paper, and the theoretical optimum.

4. The basic ring has two flaws, both from random placement: uneven arcs (a neighbour can double its load when a node leaves) and key clustering. Remember: the ring guarantees cheap movement, never even distribution.

5. Virtual nodes are the patch: many stand-ins per machine, variance crushed by the law of large numbers. 100 stand-ins gives ~10% standard deviation, 200 gives ~5%; as a bonus it expresses machine strength — stronger boxes get more stand-ins.

6. The ring is not the only answer: Redis Cluster uses 16384 fixed slots plus a mapping table, paying for a control plane and buying full control over what moves where.

7. But stand-ins are not free: Cassandra states that more tokens reduce availability, its default is 16, and it does not recommend that even for clusters above 50 nodes. The production answer is in the teens, not the hundreds.

8. What it does not solve: a single hot key (Discord's hot partitions are the live case), cross-shard transactions, replica placement, and routing during migration. Being able to state how the affected range is computed and what virtual nodes cost in availability is what "understanding this chapter" means in an interview.