A node's share of a ring is the total length of the arcs it owns, and with one token a node those arcs are nothing like equal — the largest node in an eight-node ring took 28.29% where an equal share is 12.50%. Giving each node V tokens averages V independent arcs together, and the relative spread falls like 1/√V. That is a real improvement and a slow one: a hundred times the tokens buys ten times the evenness.
Core ideas
One measurement and one rate. The measurement is the surprise; the rate is the thing that decides how many tokens a real fleet runs.
With one token a node, the ring is cut at N uniformly random positions and each node owns the arc ending at its cut. Uniform cut points do not give equal arcs: across eight seeded rings of eight nodes, max/mean averaged 3.349, and on the drawn ring the largest node held 28.29% of the key space while the smallest held 2.95%. The property consistent hashing gives is stability under growth, not balance.
Give each node V tokens and its share is the sum of V arcs drawn from the same distribution instead of one. Sums of independent draws concentrate: the relative spread of the shares falls, and it falls like 1/√V rather than like 1/V. The lab measures 1.0370, 0.3309 and 0.0959 at V = 1, 10, 100 against a stated 1.0000, 0.3162, 0.1000.
To halve the spread you need four times the tokens; to get a tenth of it you need a hundred times. Tokens are not free — each one is a ring entry every router and every client caches, and the lookup structure grows with N · V — so V in a real system is a few hundred rather than a few thousand, and the spread it leaves is a cost that has to be planned for rather than eliminated.
The material
What a node's share actually is, how badly one token a node does, what V tokens buy, and the difference between a spread going to zero and a ratio going to one.
A virtual node, or token, is one position a physical node occupies on the ring. A node with V tokens owns the union of the V arcs ending at them, and its share is the total length of that union as a fraction of the ring. Keys are assigned by successor ownership: a key belongs to the first token at or after its position, clockwise, wrapping at the end.
The quantity to measure is the shares, and the two ways of describing how uneven they are answer different questions. max/mean is what the fullest node costs you, and it is the number a capacity plan needs. The relative spread — the root-mean-square deviation of the shares divided by the mean share — is what falls at a clean rate, and it is the number that tells you what another token is worth.
The spread goes to zero and max/mean goes to one, and reading the wrong one as the other makes V look either better or worse than it is. At V = 100 the spread is 0.0959 — about a tenth of what it was — while max/mean is 1.141, still 14% of extra capacity on the fullest node. A tenth of the spread is not a tenth of the imbalance, because max/mean has a floor of 1 that it approaches and never passes.
The 1/√V rate is stated on this page and measured in the lab, and the square roots printed beside the measurements are rounded — 1/√10 = 0.3162… is irrational, and the lab labels it as rounded where it prints it. Measurement and statement sit in adjacent columns on purpose: 0.3309 against 0.3162 is agreement to about five per cent on eight seeds, which is what a rate claim is entitled to, and it is not the same as an identity.
An eight-node ring at V = 1 gave a largest share of 28.29%. If that ring were serving 100 000 requests a second, the busiest node would take 28 290 /s against a fair 12 500 /s, so every node has to be built for well over twice its share or one of them saturates. At V = 100 the same fleet's worst node averages 1.141 times the mean, which is a 14% margin rather than a 126% one. The tokens did not change the number of machines; they changed how much of each machine is reachable.
Every token is a row in the ring that routers, clients and the membership protocol all carry, and the ownership lookup is over N · V entries rather than N. At N = 8 and V = 100 that is 800 rows, which is nothing; at N = 1 000 and V = 1 000 it is a million, which is a data structure with its own operational behaviour. The square-root rate is what makes this a real trade: since the next halving of the spread costs four times the tokens, there is always a point where buying evenness stops being worth the ring.
Two things this lesson does not change. Tokens do not affect what moves when a node joins — that is still the arcs the newcomer took, as in “Rehashing When N Changes”, and it is still roughly 1/(N+1) of the keys. And tokens do not help at all against a single key that is hot, because that key sits in exactly one arc however finely the ring is cut. “Hot Keys and Salting” is where that is priced.
Interactive
A node's share is the arc it owns, and V tokens shrink the spread like 1/√V
Method
Measure before you tune. The first two steps say how bad it is; the last two say what fixing it costs.
A node's share is the total arc it owns. Take max/mean and the relative spread, and take both over several seeds — a ring is one draw of N · V positions, and one draw is no more representative here than one placement was in “Hash Partitioning and Imbalance”.
max/mean is the multiple of the mean your fullest node must be built for. The spread is the quantity that falls like 1/√V, and it is the one to watch when deciding whether another token is worth buying.
Halving the spread costs four times the tokens. Write down the ring size that implies — N · V entries — and whether the membership and routing layers carry it comfortably. This is where the decision actually gets made.
Tokens do not reduce what moves when a node joins, and they do nothing about a hot key. If the imbalance you measured is one shard far above the others rather than a spread across all of them, more tokens is the wrong tool and the next two lessons have the right ones.
One ring measured, then the same ring with more tokens, then the rate checked against what was stated.
The two right-hand columns are the lesson. The measured ratios track the stated 1/√V closely enough to believe the rate and not closely enough to call it an identity, which is exactly the standing a rate claim should have when it has been measured on eight seeds rather than proved.
For a faded rehearsal, stay at eight nodes and take V to 25. The supplied first move is the stated rate, 1/√25 = 0.2000. Predict the relative spread the lab will report, then read it, then say how far off your prediction was as a percentage — and separately predict whether max/mean at V = 25 will be nearer to 1.520 or to 1.141, and why that question has a different answer from the first one.
You should be able to compute a node's share from its arcs, measure max/mean and the relative spread over several seeds, state the rate at which the spread falls and that it is stated rather than proved, and say what V does not fix.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.