Adding a machine without moving the data
A Socratic walk-through of adding a machine without moving the data — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #How do you add one more server to a cluster without having to relocate almost everything?
You have ten cache servers and a simple rule for finding things: hash the key, take the remainder modulo ten, and that is the server holding it. Clean, stateless, every client computes the same answer without coordinating.
Now buy an eleventh machine. The rule becomes modulo eleven. Ask yourself what fraction of keys now live somewhere different — and resist the intuition that it should be about a tenth, since only a tenth of the capacity is new.
Work one out. A key hashing to 25 was on server 5; now it is on server 3. A key stays put only when its hash agrees modulo ten and modulo eleven, which happens for about one key in eleven. So roughly ninety-one percent of your data is suddenly on the wrong machine, and every one of those keys is a cache miss arriving at once. Why is a small change to the cluster causing an almost total reshuffle?
Reasoning it through
REASONING #The clue is in what the modulus does. It is not describing where each key lives; it is describing a global partition of the whole key space, and the divisor appears in the calculation for every key. Change it and you have not adjusted one boundary — you have redrawn every boundary simultaneously.
So the design question sharpens: is there an assignment rule in which adding a server changes the answer for a small, local region rather than for all of them?
Before hunting for one, work out the floor. How many keys must move? The new machine has to end up holding something, and by symmetry its fair share of n+1 machines is one part in n+1. Those keys have to come from somewhere, so they must move. That is unavoidable. But nothing forces any other key to move. The ideal, then, is a scheme where exactly the newcomer's share relocates and nothing else does — and notice that the guarantee we are after is about the fraction of keys that move, not about where any particular key ends up.
Can we get there? Yes, by giving up on arithmetic that mentions the number of servers. Hash the keys into a large space, and hash the servers into the same space, treating it as a circle. A key belongs to the first server you meet going clockwise from it. Now no formula mentions n at all; a server simply owns the arc between itself and its clockwise-nearest predecessor.
What happens when a server joins? It lands at one point on the circle and takes over one arc — the portion of its successor's territory that now falls behind the new point. Every other arc is untouched. On average the newcomer's arc is one part in n+1 of the circle, which is exactly the floor we computed. And when a server leaves, its arc merges into its successor's and nothing else changes.
There is a stronger property here worth naming, because it is what makes the scheme safe rather than merely economical: keys only ever move to the new server, never between two existing ones. So no key is in flight between two old machines, and a client using a slightly stale view of the ring is wrong about a bounded region rather than about everything.
Is the picture finished? Not quite, and the gap is a real one. If each server is a single random point, the arcs are not equal — random points on a circle leave very uneven gaps, and with n servers the largest arc is likely to be several times the average. One machine gets far more than its share. The fix is to place each physical server at many points on the ring — a hundred or two is typical — so that its territory is the sum of many small arcs, and the law of large numbers flattens the imbalance. That is what "virtual nodes" means, and it also lets you weight a bigger machine simply by giving it more points.
The analogy
THE ANALOGY #Think of a circular table with people seated around it and dishes placed around the rim. Each person is responsible for whatever sits between them and the neighbour on their left. Seat one more guest, and that guest takes over part of exactly one neighbour's stretch. Nobody else's responsibilities change, and no dish is picked up and carried across the table.
guests at a real table shuffle round to make even gaps, whereas ring positions are fixed by a hash and cannot be nudged — the unevenness is genuinely there, and the only remedy is to seat each guest in many places at once so their share averages out.
Clarifying the model
THE MODEL #The refinement that connects the reasoning: what consistent hashing buys is not fewer moves in some absolute sense, it is minimal disruption. Some keys have to move — the new machine must be given work. The scheme's claim is that only that share moves, roughly one key in n+1, instead of nearly all of them.
The misconception to correct is that this is about keeping particular keys on particular servers. It is not, and it does not promise that. A key's home can change on any membership change; the guarantee is statistical and about proportions.
It also does not, on its own, make anything durable or available. Consistent hashing decides placement. Replicating a key onto the next few distinct servers clockwise is a separate decision layered on top, and so is deciding what to do while a node is only temporarily unreachable — treat a brief outage as a departure and you trigger a real reshuffle for nothing.
Finally, the ring is not the only answer. Rendezvous hashing scores every server for a key and takes the highest, giving the same minimal-movement property without a ring, at the cost of checking every server. Jump consistent hashing achieves it with almost no memory, but only for consecutively numbered servers, so it suits sharding a fixed range better than a cluster whose members come and go.
A picture of it
THE PICTURE #How to readBoth schemes start with the same hundred keys and the same event — a tenth server becoming an eleventh. Follow each source band rightward and compare the widths where they land. Modulo hashing sends the overwhelming majority into the "move" band because the divisor appears in every key's calculation; the ring sends only about one key in eleven, which is the new machine's fair share and the smallest quantity any scheme could move. The nine and ninety-one are not approximations for effect: under modulo hashing a key survives exactly when its hash agrees modulo ten and eleven, which is one case in eleven.
What became clearer
WHAT CLEARED #The reshuffle was never caused by the size of the change; it was caused by the assignment rule mentioning the number of servers. Once placement is decided by relative position on a circle instead of by arithmetic on n, a membership change is a local event. Some movement is unavoidable — the newcomer must be given its share — and the point of consistent hashing is that it moves that share and nothing else, with virtual nodes doing the separate job of making the shares roughly equal.
Where to go next
ONWARD #- How many virtual nodes per server you actually need to bring load imbalance within a few percent.
- How replication factors and failure detection interact with placement in a real distributed store.
Key terms
TERMS #| Term | What it means |
|---|---|
| Consistent hashing | placing keys and servers in one circular hash space, each key owned by the first server clockwise; introduced in 1997 by Karger and colleagues. |
| Minimal disruption | the property that a membership change relocates only about one key in n. |
| Virtual node | one of many ring positions given to a single physical server, to even out arc sizes and express weighting. |
| Rendezvous hashing | an alternative scoring each server for a key and picking the maximum. |
Every term the collection defines is gathered in the glossary.