# DDIA Ch. 7: one random range per node is lumpy (busiest owns 2.8× its share); 16 vnodes flatten it, 256 nearly perfect

## Concept

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.

## Provenance

*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.

## Prerequisites

The whole result is one fact about sums of random variables. Each line notes
where it shows up.

1. **Consistent hashing puts nodes on a ring** — keys and nodes hash to points
   on `[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.)*
2. **Uniform hashing → load ∝ width owned** — a good hash spreads keys
   uniformly over the ring, so the fraction of keys a node gets equals the
   fraction of the ring it covers. It shows up as "load = total width of a
   node's ranges" — no key distribution needed, just geometry.
3. **Coefficient of variation (CV = std/mean)** — the *relative* spread of a
   distribution, unitless, so you can compare spread across different V. It
   shows up as the `CV` column that shrinks with V. *(This is the axis the
   result lives on.)*
4. **Variance of a sum / law of large numbers** — for V roughly-independent
   range widths, the sum's mean grows like V but its standard deviation grows
   like √V, so CV = std/mean ∝ √V/V = 1/√V. **This is the load-bearing one** —
   it *is* the 1/√V law and the reason vnodes work.

### Where to learn the prerequisites

- **Consistent / ring hashing (#1–#2):** DDIA §"Sharding by hash range"; Karger
  et al., "Consistent Hashing and Random Trees" (1997) for the ring and the
  vnode ("virtual node") idea.
- **CV, variance of a sum, LLN (#3–#4):** any intro-probability text — e.g.
  Blitzstein & Hwang, *Introduction to Probability* (the full book is free as a
  PDF), the "expectation and variance" and "law of large numbers" chapters. The
  one identity to hold: `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.

## Environment

Deterministic, so the numbers reproduce exactly:

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Python 3.15.0a8, standard library only — no Docker, no deps
- 10 nodes, hash space `[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

## Mental model

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:

- **V=1, the original scheme** — 10 random boundaries cut the ring into 10
  ranges, one per node. A node's whole load rides on the width of its *single*
  slice, and random slices are wildly uneven: some node draws a fat arc, another
  a sliver. One draw, high variance.
- **V per node (vnodes)** — place `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`.

## Setup

```
cd study/ddia/ch07
python3 code/vnodes_variance.py
```

Do **not** read the output yet — make each prediction first.

## Steps

### Step 1 — one random range per node

**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)

**Observe.**

```
10 nodes on a 2**32 hash ring; keys uniform, so load = width owned.
Each node owns V random ranges (V=1 is the original single-boundary scheme).
Averaged over 20 fixed seeds. Fair share per node = 10% of the ring.

     V | imbalance max/mean | CV (std/mean) | 1/sqrt(V)
  -----+--------------------+---------------+----------
     1 |              2.804 |         0.846 |     1.000
     2 |              2.372 |         0.651 |     0.707
     4 |              1.858 |         0.439 |     0.500
    16 |              1.378 |         0.212 |     0.250
    64 |              1.216 |         0.123 |     0.125
   256 |              1.105 |         0.058 |     0.062
```

**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.

### Step 2 — 16 vnodes (Cassandra's default)

**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.

**Observe.**

```
    16 |              1.378 |         0.212 |     0.250
```

**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.

### Step 3 — 256 vnodes, and the 1/√V law

**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?

**Observe.**

```
   256 |              1.105 |         0.058 |     0.062

Read it down the last two columns: CV tracks 1/sqrt(V) closely.
V=1 busiest node ~ its imbalance above the fair share; V=16 (Cassandra)
CV ~ 25%; V=256 (ScyllaDB) CV ~ 6%. More, smaller ranges -> flatter load.
```

**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.

## What you should see

- **V=1:** imbalance **2.804**, CV **0.846** — the busiest node owns ~2.8× fair
  share. The naive prediction ("random → even") is wrong.
- **V=16** (Cassandra): imbalance **1.378**, CV **0.212** — busiest node 38% over.
- **V=256** (ScyllaDB): imbalance **1.105**, CV **0.058** — busiest node 10% over.
- CV shrinks like **1/√V**: `CV·√V` stays ~0.85–0.95 across all six rows, so
  quadrupling V halves the spread.

## Why

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/√V
```

The `σ/μ` 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.

**The boundary — vnodes fix data skew, not load skew.** The 1/√V law assumes
keys are **uniform** over the hash space. Vnodes cure *boundary-placement* skew:
the unevenness that comes from where the random cuts happen to fall. They do
**nothing** for *request* skew. If one key is red-hot — a celebrity's user id, a
`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*.

### Go deeper

1. **Change NODES.** The `σ/μ` 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.
2. **Assign ranges randomly instead of round-robin.** Swap `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.
3. **Plot `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.