Consistent hashing: how many keys move when the membership changes

What this question is really about

The ladder looks like this:

1. "How do you spread keys across nodes?" — a warm-up, answered with modulo.
2. "What happens when you add a node?" — the substance starts here, and "some of the keys move" is already wrong by magnitude.
3. "What is consistent hashing?" — a question about the mechanism.
4. "What are virtual nodes for?" — the question that shows whether the skew was computed or repeated.
5. "What do virtual nodes cost?" — a question about the trade.
6. "Where does this scheme stop helping?" — a question about the limits.

The numbers come from running bench/hashring/ring.py and bench/hashring/practice.py. This is not a model and not a simulation: the assignment of keys to nodes is computed exactly, and the share that moves comes from recounting. The only random thing here is the keys, and they come from a fixed seed.

Base: how you find out which node holds a key

When there is more data than fits on one machine, it is spread across several nodes. And immediately the question this lesson is about appears: to read a value by its key you have to know which node holds it.

Keeping that as a list — "this key lives there" — will not do: the list would be the size of the data itself, and everyone who fetches keys would have to hold it. So the owner of a key is not stored but computed: take the key, hash it into a number that comes out the same for everyone and always, and name a node from that number.

The simplest way to name a node from a number is division with a remainder. The remainder of the hash divided by the number of nodes is the node's index: eight nodes, remainders from zero to seven, every key with its own node, no table at all. It costs one operation, and the keys land evenly.

And that is exactly where the trouble is, visible if you look at the recipe once more: the index of the node depends not only on the key but on the number of nodes. While the membership does not change, nobody notices. But add a node and the divisor is different — which means the answer changes for every key at once, including keys the new node has nothing to do with. Removing a node does the same.

Hence the main question of this lesson: can keys be laid out so that adding a node moves only the keys that node is going to own? The answer is yes, and schemes with that property are called consistent hashing: in them the owner of a key is tied to the key itself rather than to the current number of nodes.

That is already enough to answer the basic interview question. Everything below is about how large the difference actually is, how the best-known such scheme is built, and what is paid for it.

Mechanism 1: modulo moves almost everything

Now the same thing in numbers. Here is what happens under modulo when a node is added:

1. MODULO SHARDING: ADDING ONE NODE MOVES ALMOST EVERYTHING
-----------------------------------------------------------
         nodes   -> nodes    keys moved   ideal share
             8          9        88.9%        11.1%
             8         10        80.2%        20.0%

  times more than the minimum, +1 node           8.0

Read the two columns side by side, and read the first row with its assumptions stated. That row describes the move from eight nodes to nine: one node just like the others joins the eight, and the keys are spread evenly. Under those assumptions ideal share is the necessary minimum: the ninth node should receive roughly a ninth of the keys, so 11.1 % have to move under any scheme that keeps the layout even. What moved was 88.9 % — eight times more. Both numbers belong to that particular move: another membership, or another number of nodes added, has its own — which is what the second row shows.

Why. Under modulo, a key's node is not a property of the key but a property of the current node count. Change the divisor and the answer changes for everyone at once: a key with hash 17 lived on node one with eight nodes and lives on node eight with nine, and that has nothing to do with the new node appearing.

This consequence is why the section exists in the conversation: adding a node to such a scheme means moving almost all the data. For a cache it means that nearly nine keys in ten will ask the wrong node and miss; for a store, that nearly the whole set of data has to travel over the network. Both happen exactly when a node is being added because capacity ran short.

Note the second row too: adding two nodes moved 80.2 % — less than adding one. "The more you add, the more moves" is not a rule here. The share follows from the arithmetic of remainders rather than from the size of the change, and it cannot be guessed in advance — only computed.

Mechanism 2: a ring moves close to the minimum

The idea of consistent hashing is to stop the owner of a key from depending on the number of nodes. The best-known construction that does it is a ring: the hash of the key and the hashes of the nodes go onto one circle, and a key belongs to the nearest node clockwise.

A new node then takes over only the arc that happens to lie right before it. Every other key-to-node pair is unchanged: there is nothing to recompute for them.

2. A RING MOVES ONLY WHAT IT HAS TO
-----------------------------------
    vnodes per node   keys moved, +1 node   ideal share
                  1                11.5%        11.1%
                 16                10.9%        11.1%
                128                10.7%        11.1%

The same eight nodes, the same ninth, the same keys. With one point per node the ring moved 11.5 % against 88.9 % under modulo — that is, practically the necessary minimum. The lower rows run ahead of the story: there a node holds several points on the ring rather than one — why that is done comes later, and it barely affects the share that moves.

The difference is not in "algorithmic efficiency" but in what counts as the answer. Under modulo the answer is recomputed for every key at once; on a ring the owner of a key is the nearest point to its right, and a new point changes the answer only for the keys lying just left of it.

Hence the name: the scheme is consistent in the sense that the answer for a given key does not change without a reason concerning that key.

And one caveat worth carrying from here: a ring is a way, not a synonym. Consistent hashing is a requirement on a layout scheme — the owner of a key must not depend on the number of nodes, so a change of membership touches only the keys next to the change. A circle with points on it is the best-known construction that meets that requirement, which is why it is the one drawn at interviews. But it is not the only one that meets it: several constructions with the same property are known, built in different ways, and every number in this lesson belongs to the ring.

Mechanism 3: removing a node touches nobody else's keys

Adding a node we have seen. Now the reverse operation — the one the scheme exists for. Take one node away from eight:

5. REMOVING A NODE MOVES ITS KEYS AND NOBODY ELSE'S
---------------------------------------------------
  share of keys the removed node owned           11.7%
  share of keys that moved in total              11.7%
  share of OTHER nodes' keys that moved          0.0%

Three rows, and the whole point is in the third. Exactly as many keys moved as the departing node held, and not one belonging to anybody else.

That is the property modulo sharding does not have: there, a node leaving changes the divisor and therefore the answer for everyone. Here, a node leaving erases its points from the ring, and the keys that pointed at them pass to the neighbours on the right. Every other key still resolves to the same position on the ring, and the change of membership never reaches it.

In this computation each node holds not one point on the ring but a hundred and twenty-eight. That number does not affect the property in question: all that matters is that the departing node's points disappear while everybody else's stay where they were. Why many points are used is a separate conversation.

Hence what the scheme is kept in production for: when a node leaves, only its share of the keys has to be asked for again — the other seven eighths of the membership answer the same questions they did before. Where that share comes back from is a matter of replication, and that topic is not part of this one.

Deeper: skew and virtual nodes

What follows is the price of a ring and the setting it is paid with. None of it changes the basic answer: a ring moves close to the minimum and touches nobody else's keys regardless of what is written below. But this is where the usual retelling stops — and where an interview keeps going.

Spread the keys across eight nodes with one point per node on the ring:

3. WITHOUT VIRTUAL NODES THE RING IS BADLY SKEWED
-------------------------------------------------
    vnodes per node   smallest share   largest share   max/min
                  1            0.4%          33.3%     90.5x
                 16            8.7%          16.3%      1.9x
                128           11.0%          15.1%      1.4x
                512           12.1%          13.6%      1.1x

One node received a third of all the keys, another four tenths of a percent. A factor of 90.5, with eight nodes, where "evenly" would mean an eighth each.

Why. Eight points placed by hashing the node names divide the circle into eight arcs: a hash scatters them the way a random choice would, and such a partition is uneven. Here those eight arcs fell so that one took a third of the circle and another almost nothing. That is a property not of these particular names but of any partition of a circle by a few independent points; the computation shows one instance of it.

Virtual nodes are the cure: instead of one point a node gets many, and its share is the sum of many small arcs. Many small random pieces average out; eight large ones do not. At 128 points the skew falls to 1.4x.

This is what separates someone who has read about the scheme from someone who has computed it. A ring without virtual nodes solves the migration problem and immediately creates an evenness problem — and one severe enough that a node can hold ninety times more than another.

What virtual nodes cost

4. WHAT VIRTUAL NODES COST
--------------------------
    vnodes per node   points on the ring   max/min
                  1                    8     90.5x
                 16                  128      1.9x
                128                 1024      1.4x
                512                 4096      1.1x

The points on the ring are not an abstraction: they are the structure searched to find the owner of every key, and every participant that knows the layout has to hold it. Eight nodes at 512 points is a ring of 4096 entries.

What matters is the shape of the trade. Going from 1 to 16 points removes almost all the skew: 90.5x becomes 1.9x. Going from 128 to 512 quadruples the structure for the last few percent of evenness: 1.4x against 1.1x.

Hence the answer to "how many virtual nodes should there be": enough that the skew becomes acceptable, and not one point more. That number depends on how many nodes you have and how much skew you will tolerate — and it is computed rather than taken from an article.

How to answer in an interview

Short answer: modulo ties the owner of a key to the number of nodes, so any change of membership recomputes everything; a ring ties the owner to the position of the key, so only the keys next to the change move. Computed over 100,000 keys: adding a ninth node to eight moves 88.9 % of the keys under modulo and 11.5 % on a ring with one point per node.

That is enough for a correct answer. What follows is what you add when the interviewer digs.

If the interviewer digs deeper

Three things separate a good answer. First, you explain the cause rather than the name: under modulo a key's node depends on the number of nodes, on a ring on the position of the key. Second, you name the price yourself: a ring without virtual nodes is skewed, and in this computation the skew was 90.5x. Third, you say what virtual nodes cost — the size of a structure every participant holds — and give the shape of the trade: from 1 to 16 points buys almost all of it, from 128 to 512 the last few percent.

It is also worth not equating the ring with the property itself: consistent hashing is the requirement that a key's owner does not depend on the number of nodes, and a ring is a well-known construction meeting it — not the only one.

What not to say: "consistent hashing moves only 1/N of the keys". That is true for adding one equal node to an even layout and false as a general statement — and it hides the skew, which in this computation mattered more.

Next they ask

Common misconceptions

Practice

Two exercises. Answer first, then check against the real output: in both, the correct answer is what the computation script prints.

print(f"{modulo:.1%}")
print(f"{ring_moved:.1%}")
print(f"{others:.1%}")

88.9%
11.7%
0.0%

11.1%
11.7%
0.0%

88.9%
11.7%
11.7%

88.9%
88.9%
0.0%

Knowledge check