Scaling Data · lesson 3 of 7 · about 30 min
How to add or remove a server without reshuffling everything: why hash mod N fails, how the ring works (with a real one you can poke), why virtual nodes are essential, how replicas and weights are placed, how rendezvous, jump and fixed slots compare, and how a ring with too few points can cascade. Tap any for a plain-language card.
The problem
was designed to fix exactly this. Adding or removing one server out of n moves only about 1 ÷ n of the keys: the unavoidable minimum, because the new server must own something. The simulation below hashes 8,000 real keys and counts how many change owner when going from n to n + 1, for both rules.
At 8 servers: mod moves about 89% of keys, the ring about 11%. Watch the database load multiplier.
Adding the 9th server with mod 9: 88% of keys change server, the hit ratio falls from 95% to about 11%, and the database sees 17.8× its normal miss traffic. With a ring only 10.9% move and the database sees 3.1×.
Measured with 8,000 hashed keys. The ring uses 100 points per server. Hit ratio after = before × (1 − share of keys moved), since moved keys start cold.
The ring
Now see why this moves so little. Adding server D puts a new point on the ring. It takes over only the keys between itself and the previous server, and every other key stays where it is. Removing a server hands its keys to the next one clockwise, and nobody else is touched. Try it: add and remove servers and read the “keys moved” count below the ring. Keys are coloured by the server that owns them.
The real hash (a 32-bit hash of the name) is used for every position, so the layout is genuine, not drawn by hand. Try typing your own key in the box.
With 3 servers, add a fourth: about a quarter of the 60 keys move, and all of them go to the newcomer.
Add or remove a server and the verdict appears here.
Positions come from a real 32-bit hash, so adding the same server always lands in the same place.
Balance
The fix is the : place each physical server on the ring many times (node-1#0, node-1#1, ... node-1#99). Now each server owns many small arcs scattered all round the ring. Individual arcs are random but their sum is close to fair, and the imbalance shrinks roughly like 1 ÷ √(points). A dead server's many small arcs go to many different neighbours, so no one is crushed. Dynamo, Cassandra and many caches work this way.
The cost is memory and lookup time: the ring has n × v points, and a lookup is a binary search over them.
Start at 1 point per server, 10 servers. Then slide to 100 and watch the spread tighten.
With 1 point per server, the busiest of 10 servers holds 2.99× its fair share and the idlest 0.02×. A single point leaves some servers nearly idle and others overloaded.
Measured over 20,000 hashed keys against a real ring. The dashed line is each server's fair share.
Replicas and weights
Machines are not all equal. Giving a bigger server proportionally more virtual nodes makes it own proportionally more keys. Below, node-1 can be made up to 4× bigger. And when a server dies, only the keys that had a copy on it must be re-copied: about R ÷ n of all the data, spread over many source servers.
Pick key 7, kill one of its replicas, and watch the list shift. Then make node-1 four times bigger.
Preference list of item:7: #2 (a) → #3 (b) → #5 (c)
Fail a server and see what has to be re-copied.
Rings use 64 virtual nodes per unit of weight. Shares and re-copy volumes are measured over 4,000 hashed items.
The family
All five are implemented below for real, with the same 8,000 keys. The table shows what happens when you go from n to n + 1 servers: the share of keys that move (the ideal is 1 ÷ (n + 1)) and how evenly keys are spread afterwards. Google's Maglev load balancer, from the Load balancers lesson, uses a table-based variant for the same job.
Look at the “moved” column: one row is far from the ideal. Then look at the cost columns for why you might not always pick the cheapest.
| Algorithm | Moved (10 → 11) | Busiest ÷ fair | Lookup cost | Memory |
|---|---|---|---|---|
| hash mod N Trivial, but resizing moves nearly everything. | 90.8% | 1.03× | 1 hash | none |
| Ring + 100 virtual nodes Flexible: any node can join or leave; virtual nodes give weights. | 9.4% | 1.09× | ~10 comparisons | 1,000 points |
| Rendezvous (HRW) No state at all, but one hash per node on every lookup. | 8.9% | 1.06× | 10 hashes | none |
| Jump consistent hash No memory, fastest, but nodes can only be added or removed at the end. | 9.3% | 1.05× | ~2 loop steps | none |
| 1,024 fixed slots Fixed table of slots mapped to nodes; moving a slot is explicit (Redis Cluster). | 11.2% | 1.23× | 1 table read | 1,024-entry table |
Ideal movement for 10 → 11 is 9.1%. hash mod N moves 91%; the other four land within a point or two of the ideal. They differ in what they cost per lookup and what flexibility they keep: only the ring and slots allow arbitrary nodes to leave; only jump needs no memory at all.
Measured with 8,000 real keys on each algorithm. “Busiest ÷ fair” is after adding the server. Jump hash and rendezvous are implemented from their published definitions.
Which technique?
There is no single best hash scheme, only the one that fits how often nodes change and who needs control. Each answer is worth 20 XP.
Ask: how often does the node set change? and who decides where data lives?
A cache tier of 6 nodes that autoscales up and down through the day, where a wave of misses would hurt the database.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four systems that use consistent hashing, and what they have published about it.
web cache → many servers → hash that survives churn
Consistent hashing comes from a 1997 paper by David Karger and colleagues at MIT, written to spread web-cache load over a changing set of servers. Akamai, founded by some of the same researchers, built its content delivery network on the idea, so a request for a page finds the same cache even as servers join and fail.
key → ring → N successors hold replicas
The Dynamo paper describes partitioning with consistent hashing, giving each node multiple virtual positions, and replicating each key on the next N distinct nodes clockwise (the preference list). It is the template that Cassandra, Riak and others followed.
partition key → token → node(s)
Cassandra places nodes on a token ring and uses virtual nodes (num_tokens) so that each machine owns many small ranges. Its documentation notes that the default number of virtual nodes per node was lowered from 256 to 16 in version 4.0, because fewer tokens with a smarter allocation algorithm give good balance with less overhead for repair and streaming.
5-tuple → lookup table → backend
Google's Maglev paper (2016) describes a software load balancer that uses a variant of consistent hashing driven by a lookup table, designed so that when backends change, connections stay on their old backend as much as possible while load stays evenly spread. It is consistent hashing where lookup speed and even balance matter most.
Interview angle
Six questions, each worth 20 XP. “What is consistent hashing?” is among the most common fundamentals questions, and a strong answer mentions virtual nodes.
Say what goes wrong with mod N, draw the ring, then add virtual nodes before the interviewer asks about imbalance.
You use hash(key) mod 10 across 10 cache servers and add an 11th. Roughly what share of keys changes server?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
With many , the dead server's keys scatter over all the survivors in small pieces, each of which gains only about 1 ÷ (n − 1) more load: well within headroom. Same hash, same servers, same failure: the only difference is how many points each server owns.
The simulation kills the first server and then, each round, removes the most overloaded server if any is above capacity, recomputing real key ownership on a real ring.
Start with 1 point per server and 1.5× capacity: watch it unravel. Then raise the points to 100.
Total collapse: one failure became 10 failures. After the first server died, the busiest neighbour carried 2.99× its fair share, over the 1.5× it could take, and each loss pushed the next over.
Real ring, real hashing, 20,000 keys. Load is measured against the original fair share (20,000 ÷ n).