Consistent hashing with one random range per node leaves the busiest of 10 nodes owning 2.8× its fair share — "random boundaries, so roughly even" is wrong. Give each node V small random ranges (virtual nodes) and the imbalance falls to 1.38× at V=16 (Cassandra) and 1.10× at V=256 (ScyllaDB). The relative spread shrinks like 1/√V.
Consistent hashing places node boundaries at random points on a hash ring. The original scheme gives each of 10 nodes one random range; the intuition is "random boundaries, so roughly even load." Run it and the busiest node owns 2.8× its fair share. Now give each node V small random ranges instead — virtual nodes ("vnodes") — and the lumps average out: at V=16 (Cassandra's default) the busiest node is only 1.38× over, at V=256 (ScyllaDB) only 1.10×. The relative spread (coefficient of variation) shrinks like 1/√V — the law of large numbers averaging V independent range-widths per node. Same random boundaries, same uniform keys; the only knob is how many slices each node owns.
Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 7 — Sharding, §"Sharding by hash range" (Figure 7-6):
Cassandra splits the hash range into contiguous ranges with randomly chosen boundaries [...] Since these random boundaries are unlikely to split the load perfectly evenly, Cassandra assigns several ranges (16 by default) to each node; ScyllaDB uses 256. Having many small ranges per node means the imbalances even out.
This exercise measures exactly that evening-out: the load imbalance and its coefficient of variation as the number of ranges per node climbs 1 → 256.
The whole result is one fact about sums of random variables. Each line notes where it shows up.
[0, 2**32); a node owns the ring arc up to the next boundary. It shows up as the sorted random boundary points forming contiguous ranges. (Carries the setup, not the surprise.)CV column that shrinks with V. (This is the axis the result lives on.)Var(sum of n iid) = n·Var(one), so std ∝ √n while mean ∝ n. If only one is new, make it #4 — that √n-vs-n split is the entire mechanism.
[0, 2**32), ranges assigned round-robin over the sorted ring boundaries. Imbalance and CV averaged over a fixed list of 20 seeds (SEEDS = range(20)) to tame single-sample noise; nothing is process-random, so every run prints the same table.
Keys are uniform over the ring, so a node's load is simply the total width of the hash ranges it owns. The fair share is 1/10 of the ring for every node. Two ways to slice:
10·V random boundaries, forming 10·V small ranges, and give each node V of them. A node's load is now the sum of V independent widths. Fat slices and thin slices land in the same node and cancel; the more you sum, the closer each node sits to the mean.We measure two things per V: imbalance = max_node_load / mean_node_load (how far over fair share the busiest node is — the one that determines whether the cluster tips over) and CV = std/mean (the relative spread across all nodes). The whole thing is one script, code/vnodes_variance.py.
cd study/ddia/ch07
python3 code/vnodes_variance.pyDo not read the output yet — make each prediction first.
Predict. 10 nodes, each owning one random slice of the hash ring (V=1). Keys are uniform, so load = width owned. Random boundaries feel fair — so how far above its 10% fair share is the busiest node? (imbalance = max/mean, where 1.0 would be perfectly even)
2.804 — the busiest node owns nearly 2.8× its fair share. "Random boundaries → roughly even" is wrong. With a single slice per node the load is one draw of a high-variance width (CV = 0.846), so some node reliably ends up hoarding almost three nodes' worth of keys. That is precisely why nobody ships V=1.
Predict. Same ring, same random boundaries, but now each node owns 16 small ranges instead of one. The busiest node's load is the sum of 16 widths. Does its imbalance drop to near 1.0, or is 16 slices still lumpy? Read the V=16 row.
1.378 — the busiest node is now only 38% over fair share, and the spread has collapsed from 0.846 to 0.212. Summing 16 independent widths lets fat and thin slices cancel. It is not perfect — 16 is a deliberate compromise — but it turns a 2.8× hot node into a 1.4× one for the price of tracking 16 ranges instead of 1.
Predict. Push to V=256 (ScyllaDB's default). Look at the last two columns of the full table: the measured CV and the printed 1/√V. Will CV keep tracking 1/√V — i.e. does every 4× in V roughly halve the spread? What is CV at V=256?
CV = 0.058 at V=256 — a 6% relative spread, and the busiest node is only 1.10× over. Trace the CV column: 0.846 → 0.439 → 0.212 → 0.058 as V goes 1 → 4 → 16 → 256. Each 16× in V (which should give 1/4 the CV) does almost exactly that. The measured CV isn't literally 1/√V — it's about 0.85/√V, the 0.85 set by the 10-node geometry — but it has the same shape: CV·√V stays flat (~0.85–0.95) across every row. That flat product is the law.
CV·√V stays ~0.85–0.95 across all six rows, so quadrupling V halves the spread.Start from what a node's load is. With V ranges per node, its load is the sum of V range widths, L = w_1 + w_2 + ... + w_V. Random boundaries make each width a random variable with mean μ ≈ HASH_SPACE / (NODES·V) — smaller as V grows, because you're cutting the ring into more pieces. The mean load is V·μ, which is constant in V (it's always HASH_SPACE / NODES, the fair share — every node owns 1/10 of the ring no matter how you slice it).
The spread is where V bites. Treat the V widths as roughly independent. Variance of a sum of independent terms adds: Var(L) ≈ V·σ², so the standard deviation grows like √V·σ. Each individual width also shrinks as V grows (σ ∝ μ ∝ 1/V), so put it together:
CV = std / mean ≈ (√V · σ) / (V · μ) = (√V / V) · (σ/μ) ∝ 1/√VThe σ/μ of a single width is a constant (~0.85 for this 10-node ring), and √V / V = 1/√V. That's the whole result: the mean load is pinned to fair share, but the relative wobble around it falls off as 1/√V. More, smaller ranges per node = more independent terms in the sum = the law of large numbers grinding the lumps flat. This is exactly why the vendors picked what they picked: V=16 buys CV ≈ 0.85/4 ≈ 21% (a decent 1.4× worst case), and V=256 buys CV ≈ 0.85/16 ≈ 5% (a nearly flat 1.1× worst case) — quadrupling V for each halving of spread, paying only in the number of ranges each node has to track.
trending=true sentinel — it hashes to exactly one point on the ring and lands on exactly one vnode on one node, and slicing that node's territory into 256 pieces doesn't split a single key. That node still eats all the traffic. Hot keys are a different problem with different fixes (add a random suffix to spread the key, or cache/replicate it) — see the hot-key exercise. Vnodes flatten the map; they can't flatten a spike.
σ/μ prefactor depends on cluster size — the spacings of 10 uniform points aren't the same as 100. Re-run with NODES = 100 and watch the V=1 imbalance and the CV prefactor shift, while the 1/√V slope stays put.i % NODES for a fixed random permutation of range→node. Predict whether it changes the CV (it shouldn't materially — the sum of V random widths has the same variance however you pick which V) and confirm.CV·√V per row. It should hover around a constant. When it stops being constant (very large V, where widths get correlated because they must sum to the whole ring), you've found the edge of the independence assumption.Sources: DDIA 2e, Ch. 7, §"Sharding by hash range" (Figure 7-6) · Karger et al., "Consistent Hashing and Random Trees" (1997) · Blitzstein & Hwang, Introduction to Probability (variance of sums, law of large numbers).