05 — Design Consistent Hashing

“Design a scheme that maps keys to servers so that adding a server does not move everything.”

Consistent hashing is a rule for deciding which server stores which piece of data. It is chosen so that adding or removing a server moves as little data as possible.

It is best learned as a derivation, not as a picture. You will work out three things:

• why the obvious rule moves 94% of your data when the fleet grows by one machine,
• why the ring moves 5.9%, and why no scheme of any kind can beat that,
• what virtual nodes — placing each server at many points around the ring instead of one — actually buy, which is not what most people say.

By the end you should be able to derive both percentages on a whiteboard, put a number on how uneven the load will be, and name the cost of virtual nodes that almost nobody mentions.

What goes in, and what comes out. The input is a key: the identifier of one piece of data, such as user:8842 or a photo’s filename. The output is the name of the server that owns it, and — because real storage systems keep several copies — an ordered list of the R distinct servers that should hold those copies:

lookup("user:8842")                 ->  "s11"
preference_list("user:8842", r=3)   ->  ["s11", "s4", "s15"]

Two properties make that function hard rather than trivial. It must be computed locally — every client works it out from a small table in its own memory, with no network call and no coordinator to ask — and every client must get the same answer. And when the set of servers changes, the answers must change as little as possible, because every changed answer is a byte that has to move across the network.

A hash function underlies all of this: a function that turns a string of any length into a number that looks random but is completely determined by the input, so every machine computing it gets the same result. Writing hash(k) below always means the same fixed, agreed-upon function.

This is not really a system design question. It is a derivation question wearing one, and the interviewer already knows the answer — they are watching whether you can produce the two numbers that justify it. Almost every candidate can draw the ring; almost none can say what virtual nodes actually buy.

The whole chapter is one argument in five steps. Each row of the table below names the number you should walk out able to reproduce, and the section that derives it.

A sixth part, What each scheme assumes and what breaks when it does not hold, collects what every scheme here assumes about the world and marks which assumptions cannot be tuned around.

Symbols and terms used throughout

Four symbols appear on almost every page. Fix them now, because the derivations below use them without re-introducing them.

Two more words are easy to blur together, and this chapter needs them kept apart. Latency is how long one operation takes. Throughput is how many operations complete per second.

They are different quantities, and this chapter cares about both in different places. A lookup is a latency question, measured in nanoseconds. A migration is a throughput question, measured in bytes per second off a network card.

A note on the numbering, because this file has two levels of it. The six parts of the deep dive are headed 1. through 6. inside Deep dive, and the top-level sections are also numbered 1 through 6 — so a bare “§4” would be ambiguous. Throughout this chapter, a dotted number means a deep-dive part (What v costs memory lookup gossip and durability is “what V costs”) and a plain number always carries its title (Failure modes). Same convention as ch 06.

One claim elsewhere in the repo that this chapter contradicts

Hash vs range and why resharding hurts states the 94% and 5.9% results as facts, because that chapter is about databases rather than about partitioning. This chapter derives both, and then derives the durability cost that follows from them.

One sentence there is worth disagreeing with out loud, since you will meet the same claim in interviews. It says “consistent hashing with virtual nodes exists entirely to turn (N-1)/N into 1/N”, which credits virtual nodes with the movement result.

Virtual nodes buy variance not mean shows that is false. V cancels out of the movement exactly, and a plain ring at V = 1 already moves 1/(N+1). The ring turns (N-1)/N into 1/(N+1); virtual nodes buy variance, and that is the whole distinction this chapter exists to make.

1. Framing: what decision, and what breaks

Before choosing a scheme, pin down what is actually being designed and why the difficulty lives in one specific event. The short version: the goal is measured in bytes moved across the network, not in elegance.

You have N servers and a key space — the full set of possible keys, which for a 64-bit hash means every number from 0 up to 2^64 - 1. Something has to answer the question “which server owns key k”: a client library, a proxy in front of the fleet, or a coordinator node inside it. The design decision is what that function is.

The function must survive three events, and only the third is hard:

The thing that breaks is not correctness, it is the migration.

A rehash — recomputing every key’s owner after the server set changes — can be perfectly correct and still move 94% of a 10 TB corpus, meaning the whole body of stored data. That is a multi-day outage in slow motion.

Hash vs range and why resharding hurts walks the four-step sequence a real migration requires: dual-write every update to both the old and the new location, backfill the history across, verify that the two agree, then flip readers over to the new location. Every one of those four steps has a window in which a bug loses data.

So the design goal is stated in bytes moved, not in elegance.

Requirements

Functional

• lookup(key) -> node — total, meaning it returns an answer for every possible key with no gaps; deterministic, meaning the same key always gives the same answer; and identical on every client.
• preference_list(key, R) -> [node_1 .. node_R] — an ordered list of R distinct physical nodes, meaning real separate machines rather than several ring points belonging to the same machine, so that the layer above can keep R copies of the data (ch 06 — Design a Key-Value Store consumes exactly this).
• add(node) / remove(node) — and the resulting movement must be bounded and derivable.
• Weighting: a node with twice the disk should own about twice the key space.

Non-functional

Four terms in that table need defining before the rest of the chapter uses them:

• us is a microsecond, a millionth of a second. So the lookup budget is a thousandth of the 0.5 ms network round trip it precedes.
• The information-theoretic floor is a lower bound proved from the structure of the problem rather than measured from an implementation. No scheme can do better, so there is no cleverer algorithm waiting to be found.
• Gossip is how nodes learn about membership changes without a central authority. Each node periodically tells a few random peers what it knows, and the news spreads exponentially. Convergence is the moment every node has heard it — about three seconds at these fleet sizes.
• Mean is the arithmetic average across nodes. So “peak node < 1.2x mean” says the busiest machine holds no more than 20% above the average share.

Back-of-envelope: what a bad answer costs

The two percentages in the table above only become real in the units anyone operating the system cares about: bytes on the wire, and hours of degraded service. Those two do not move together, and the gap between them is the most-misquoted thing in this chapter.

The standing numbers

This chapter and ch 06 — Design a Key-Value Store share one workload. Every figure below is priced against it.

RF is the replication factor, the number of copies kept of every key. RF 3 means three servers hold each piece of data.

The 10.88 TB is not a round number pulled from the air — it is the product of the two rows above it, 10e9 x 1,088 B = 10.88e12 B. But the 10 billion objects is a premise. Neither this chapter nor ch 06’s back-of-envelope derives it, and it is the one workload assumption both rest on, so it is the first thing to challenge if the numbers below look wrong.

Two words carry the rest of this subsection. Egress is data leaving a machine. Ingress is data arriving at one. The distinction between them is the entire point of what follows.

The two migrations, priced

The block below counts logical bytes throughout. The ring places replicas as well as primaries, so at RF 3 a join actually hands the new node 1/(N+1) of the replicated corpus — 32.64 TB, not 10.88 TB — and every elapsed time here triples.

The ratio between the two schemes is what the block exists to show, and that ratio is unchanged by the factor of 3. So the simpler number is the one worked.

The block below prices the same event — growing from 16 servers to 17 — twice, once under mod N and once under the ring. Each estimate starts from bytes moved, divides by how many machines share the work, then divides by the 125 MB/s a network card can push. The divisor on the last line of each is where the two schemes differ.

corpus, logical                                          10.88 TB
  (at RF 3 the real figure is 3x this:                    32.64 TB)

-- mod-N rehash, N: 16 -> 17 ------------------------------------------
bytes moved         10.88 TB x 94%                    =  10.23 TB
who carries it      all 16 nodes send AND all 16 receive,
                    so each node handles 1/16 of it
per node            10.23e12 B / 16                   =   639 GB
time per node       6.39e11 B / 125e6 B/s             =  5,115 s
                                                      =   1.42 h   at line rate

-- ring rehash, N: 16 -> 17 -------------------------------------------
bytes moved         10.88 TB x 5.9%                   =   0.64 TB
EGRESS side         16 incumbents each send a slice
per incumbent       0.64e12 B / 16                    =    40 GB
time per incumbent  4.0e10 B / 125e6 B/s              =    320 s
                                                      =   5.3 min
INGRESS side        ONE receiver -- the joiner --
                    because a join is inbound to one node
time for the joiner 0.64e12 B / 125e6 B/s             =  5,120 s
                                                      =   1.42 h   through one card

The two 1.42-hour figures are the honest headline: the wall-clock times are the same.

It is tempting to divide the ring’s 0.64 TB by 16 the way the mod-N figure is divided by 16, and report five minutes. That is wrong. For mod N the division is right — every node both sends and receives, so the work is genuinely spread sixteen ways.

For a ring join it is not. The ring and why 1n1 is not just small but optimal states the reason as a property of the scheme: on a join the movement is inbound to one node. All 0.64 TB enters the new machine through a single network card, so the critical path is 5,120 seconds either way.

What the ring actually buys

The ring’s advantage is real and decisive; it is just not elapsed time. Three things, all of which survive:

• 16x fewer bytes on the wire. 0.64 TB against 10.23 TB, and bandwidth inside a datacenter is shared, metered and contended.
• 16x less disk read. Every byte that moves is first read off a spindle that is also serving live traffic.
• One machine degraded instead of sixteen. During the mod-N migration every server in the fleet is spending its card on the copy for 1.42 hours. During the ring migration the joiner is busy for 1.42 hours and the fifteen incumbents contribute 5.3 minutes each — so the fleet is essentially unaffected, and the one machine that is saturated is the one with no live traffic on it yet.

Notice the ratio between the two movement percentages: 0.94 / 0.059 = 16, which is exactly N. The ring does not save you a constant factor; it saves you a factor of N, so the argument gets stronger as the fleet grows.

One caveat on the elapsed times above: nobody moves data at line rate. “Line rate” means saturating the network card, and a migration that does that starves the live traffic sharing it. So you throttle the copy — cap it at 20-30% of card capacity — which multiplies both elapsed figures by three or four.

This asymmetry is why real systems bootstrap a joining node from several sources at once, and add nodes in batches. The joiner’s own card is the bottleneck, and there are no fewer bytes to move, so both available fixes attack the receiver rather than the payload:

• Stream from many senders at once. The joiner’s V incoming arcs are owned by up to V different incumbents, so pull them concurrently. The limit then becomes the joiner’s card rather than any one sender’s.
• Add k nodes in one topology change instead of k changes. The inbound k/(N+k) is then split across k receiving cards instead of arriving serially at one. Bottlenecks and scaling shows that batching costs almost nothing in total bytes moved, and this receiver-side saving is the reason to do it.

API sketch

The whole partitioner is five methods, and two decisions inside them are load-bearing.

class Partitioner:
    def lookup(self, key: bytes) -> str: ...
    def preference_list(self, key: bytes, r: int) -> list[str]: ...
    def add(self, node: str, weight: float = 1.0) -> None: ...
    def remove(self, node: str) -> None: ...
    def load_shares(self) -> dict[str, float]: ...

Two things about this interface are load-bearing.

First: preference_list returns physical nodes, not ring positions. With many virtual nodes per server, the next few points clockwise very often belong to the same machine. Removing those duplicates is not a detail — it is the difference between three copies on three machines and three copies on one machine that can die all at once.

Second: there is no rebalance() method. In most systems, rebalancing means an explicit operation that redistributes data after a membership change. Here the ring is a pure function of the current server set — the same inputs always give the same output, with no stored state of its own — so there is nothing to trigger and nothing that can drift out of sync.

That is what “consistent” means in the name: consistent across clients and across time.

It is not the database sense of the word, and the two get conflated constantly. In a database, consistency is a claim about the data: that every reader sees the same value for a key at the same moment. That is the C of both ACID and CAP, and it is the entire subject of ch 06, where three replicas of one key are explicitly allowed to disagree.

Consistent hashing makes no such promise and cannot. It is a claim about the function: two clients asked “who owns user:8842” get the same name back. A ring can be perfectly consistent in this sense while the three machines it names hold three different values.

Data model: the ring is a sorted array

The ring is a picture, but the implementation is three plain arrays.

uint64 means an unsigned 64-bit integer and uint16 an unsigned 16-bit one, so each ring position costs 8 bytes and each owner index costs 2. M is the total number of ring points, N x V.

positions   uint64[M]   sorted, M = N x V
owners      uint16[M]   parallel array, index into a node table
node table  N entries   id, address, weight, state

The design decision here is two parallel arrays rather than one array of records, and the alternative it beat is worth naming. Packing a position and its owner into one 10-byte record would keep them together, which reads more naturally. But the binary search touches only positions — it never looks at an owner until the search finishes.

So you want as many of those 8-byte position words as possible in each cache line, the 64-byte block a CPU fetches from memory in one go. A packed record wastes 2 bytes of every 10 on data the search does not read.

Work out the size at this chapter’s ring. At M = 3,200, the positions array is 3,200 x 8 B = 25.6 KB, which is 25,600 / 64 = 400 cache lines. That is small enough to sit entirely in L2 cache — the second-level on-chip memory a core can read in a few nanoseconds, against the ~80 ns a main-memory access costs.

One lookup takes the path below: a key goes in on the left, an ordered list of replicas comes out on the right.

flowchart LR
    K(["key"]) --> H["1 hash<br/>xxhash64 · ~2 ns"]
    H --> B["2 binary search<br/>sorted uint64 array<br/>ceil log2 of N x V probes"]
    B --> V["3 ring position<br/>-> owning vnode"]
    V --> P["4 vnode -> physical node<br/>parallel owners array"]
    P --> R["5 walk clockwise<br/>skip repeats of the same box<br/>-> R distinct replicas"]
    R --> O(["preference list"])

    style H fill:#1d3557,color:#fff
    style B fill:#2d6a4f,color:#fff
    style P fill:#bc6c25,color:#fff
    style R fill:#40916c,color:#fff

Each fill marks the cost class of its step:

• Blue (box 1) — the hash. A fixed ~2 ns, with no dependence on N or V.
• Dark green (box 2) — the binary search. Costs a logarithm: ceil(log2(N x V)) probes, priced in What v costs memory lookup gossip and durability.
• Orange (box 4) — the array indirection. A single memory read.
• Mid green (box 5) — the clockwise walk. Costs a short linear scan, whose length depends on how many neighbouring ring points happen to belong to the same machine.

The two greens are the two search steps: dark for the logarithmic one, light for the linear one.

Follow one lookup through those five boxes:

1. Hash the key. xxhash64 turns any key string into a 64-bit number in about 2 ns. It is deliberately a non-cryptographic hash, meaning it is built for speed and even spreading rather than for resisting an attacker who wants to find collisions.
2. Binary search the sorted positions array for the first ring position at or above that number. A binary search halves the remaining range on each probe, so the probe count is the base-2 logarithm of the array length, rounded up: ceil(log2(N x V)).
3. That position is the owning virtual node — the first ring point clockwise from the key.
4. Index the parallel owners array at the same offset to turn that virtual node into the physical machine behind it. One memory read.
5. Walk clockwise from there, skipping any repeat of a machine already collected, until you have R distinct replicas.

That ordered list is the preference list the storage layer above will use.

2. Deep dive

The argument runs in five parts: what the obvious scheme costs, what the ring costs and why that cost is a proven floor, what virtual nodes do and do not buy, what they cost in return, and what none of this fixes.

1. The baseline: mod N, and the 94%

The obvious scheme is to number the servers and take the hash modulo the count. How much data that moves when the count changes can be derived exactly, and the answer is the opposite of most people’s intuition.

Server = hash(k) mod N, where mod is the remainder after division, so the hash is mapped into 0 .. N-1. It spreads keys evenly, costs one instruction and no memory, and it is the wrong answer for exactly one reason.

Go from N = 16 to N = 17. A key stays on the same server if and only if hash(k) mod 16 == hash(k) mod 17. Write h = hash(k) for short.

Three definitions first. Two numbers are coprime when they share no factor above 1 — 16 and 17 are, since 17 is prime. Their least common multiple, lcm, is the smallest number both divide into; for coprime numbers that is just their product, so lcm(16, 17) = 272. And the Chinese remainder theorem says that for coprime moduli, every possible pair of remainders occurs exactly once in each block of 272 consecutive integers.

Applied here: the pair (h mod 16, h mod 17) is spread uniformly over all 16 x 17 = 272 combinations.

That is worth showing rather than asserting, because it is four short steps and it is the whole derivation.

1. Suppose two integers h and h' give the same pair of remainders. Then h - h' is divisible by 16, and also divisible by 17.
2. A number divisible by both 16 and 17 is divisible by lcm(16, 17) = 272. So h - h' is a multiple of 272, meaning h and h' are at least 272 apart.
3. Therefore, within any run of 272 consecutive integers, no pair can repeat — all 272 integers give distinct pairs.
4. There are exactly 272 pairs available. A set of 272 distinct items drawn from 272 possibilities uses every one exactly once, which is the claim.

Coprimality is doing the work in step 2. For 16 and 18 the lcm is 144 rather than 288, so the run repeats itself twice and the counting argument collapses.

Now count the combinations in which the key stays put. The two remainders are equal only when their common value v is a valid remainder for both moduli, which means v < 16. That is 16 of the 272 combinations:

P(key stays)  =  16 / 272                =  0.0588
P(key moves)  =  1 - 0.0588              =  0.9412

The same argument works for any N -> N + 1, because consecutive integers are always coprime. The pair is uniform over N(N+1) combinations, and equal for the N values v < N:

P(stays)  =  N / (N x (N+1))   =  1/(N+1)
P(moves)  =  1 - 1/(N+1)

Substituting a few fleet sizes into 1 - 1/(N+1) gives the table below. Read the last column top to bottom.

Note the direction: mod N gets worse as the fleet grows. The intuition people carry — “one node in seventeen, so about one seventeenth of the data” — is the exact complement of the truth. mod N is not a bad heuristic that degrades; it is an anti-heuristic that converges to moving 100% of the corpus.

The reason is worth one sentence, because interviewers ask it: mod N does not assign keys to servers, it assigns keys to residues, and changing N renumbers every residue class simultaneously. Nothing about the mapping is stable under a change of modulus.

There is one case where mod N is fine, and it is worth naming because it is a real escape hatch.

Go from N = 16 to N = 32. Because 32 is exactly twice 16, h mod 32 is either h mod 16 or h mod 16 + 16 — nothing else is possible. So exactly half the keys move, and each old node’s keys split between itself and exactly one new node.

If your fleet only ever doubles, mod N with a power-of-two N moves 50% and needs no ring. That is precisely the “fixed logical shards, split by powers of two” advice in Hash vs range and why resharding hurts. Say this out loud; it shows you understand what the ring is actually for.

2. The ring, and why 1/(N+1) is not just small but optimal

The ring is the fix, and two things can be proved about it: a join moves 1/(N+1) of the data on average, and no scheme of any kind can move less.

Building the ring

Build it in four moves.

1. One number space for two kinds of thing. Map both keys and servers into the same 64-bit number space, using the same hash function. A key and a server name both become a number between 0 and 2^64 - 1.
2. Bend that space into a circle so the largest number sits next to zero. That circle is the ring.
3. Fix an ownership rule. A key is owned by the first ring position clockwise from hash(k), wrapping over the top if necessary.
4. Put each server at many points, not one. A server places V positions on the ring — its virtual nodes — by hashing the strings "server#0" through "server#V-1". One server name yields V positions that look unrelated to each other.

The ring now holds M = N x V positions in total. Those positions cut the circle into M arcs — an arc being the stretch of number space between one position and the next.

An arc is the unit of ownership. Every key falling inside an arc belongs to the server that owns the arc’s clockwise endpoint, so an arc’s length is the share of the key space it carries.

What one join does

Now add server s16 with its V positions, and watch what a single one of those positions does. Call that position p. Write pred(p) for the ring position immediately counter-clockwise of it, and succ(p) for the one immediately clockwise.

The new point p lands inside some existing arc and splits it in two.

• The keys in the counter-clockwise half, (pred(p), p], used to reach the arc’s old clockwise endpoint. Now they reach p first, so they belong to s16.
• The keys in the other half, (p, succ(p)], still reach the same endpoint as before and do not move at all.

Repeat that for all V of the new server’s points and you get the summary below. The third line is the one that matters, and it is the property mod N lacks.

one new vnode  ->  steals exactly one arc, from exactly one incumbent
V new vnodes   ->  steal V arcs, from at most V incumbents
no arc changes hands between two INCUMBENTS -- ever

Two words in that summary: vnode is the usual abbreviation for a virtual node, and an incumbent is a server that was already on the ring before the new one arrived.

Why the fraction is 1/(N+1)

Three steps get you there.

1. After the join the ring holds (N+1)V positions, all produced by the same hash function, and therefore statistically indistinguishable from one another. Statisticians call this exchangeability: relabelling the points changes nothing about their joint distribution.
2. So no arc is special, and every arc has the same expected length — namely 1/((N+1)V) of the circle, since (N+1)V equal expectations must sum to the whole circle.
3. The new server owns exactly V of those arcs, one per point it placed.

Multiply the count by the expected length:

E[fraction moved]  =  V / ((N+1) x V)   =  1/(N+1)
                   =  1/17              =  0.0588

V cancels. The expected movement is 5.9% whether you use 1 virtual node or 1,000. If you say nothing else in this interview, say that sentence.

Why 1/(N+1) is also the floor

1/(N+1) is not merely small. It is the best any scheme can do, and the argument is two sentences.

Any scheme that ends up with N+1 equally-loaded servers must give the new server 1/(N+1) of the keyspace. Every one of those keys is currently stored somewhere else, so every one of them has to move.

So at least 1/(N+1) must move, the ring moves exactly 1/(N+1), and there is no cleverer scheme waiting to be invented. The interesting question is not how to move less; it is what the ring costs to achieve the floor.

Removal, and an asymmetry to name

Removal is the mirror image of a join. Each of the departing node’s V arcs is absorbed by the arc on its clockwise side, so 1/N = 1/16 = 6.25% of keys move, and again nothing moves between the survivors.

The asymmetry is worth naming out loud, because it is what the back-of-envelope block turned on:

• On a join, movement is inbound to one node. One machine absorbs everything through one network card.
• On a departure, movement is outbound to up to V different nodes. The load is spread.

At V = 1 there is only one arc to hand over, so the entire departing node’s data lands on a single unlucky successor. That is a statement about spread rather than about averages, which is exactly what the next subsection is about.

The diagram below is a slice of the ring, unrolled into a straight line so you can see one arc split. Compare the two groups: before has three arcs owned by three servers, after has the middle one cut in two.

flowchart TD
    subgraph BEFORE["before · N = 16"]
        A1["arc owned by s7"] --> A2["arc owned by s3"] --> A3["arc owned by s11"]
    end
    subgraph AFTER["after · s16 joins with V points"]
        B1["arc owned by s7"] --> B2["SPLIT · left part now s16"] --> B3["right part still s3"] --> B4["arc owned by s11"]
    end
    BEFORE --> AFTER
    N1["Only the split parts move,<br/>and they all move ONTO s16.<br/>s7 and s11 are untouched."] -.-> AFTER

    style B2 fill:#9d0208,color:#fff
    style N1 fill:#1d3557,color:#fff

One colour needs disarming first. Ch 01 publishes a colour key for this track’s diagrams in which red means the one step you cannot undo — but here red marks the single arc that changes hands. That is the finding of this whole subsection: good news rather than a warning, since one split arc is exactly the bound the ring exists to give you. The navy box is an annotation, not a component.

Before the join there are three consecutive stretches of key space, each owned by one server. After s16 joins with its V points, one of those points lands inside the middle stretch and cuts it in two: the left part now belongs to s16, the right part still to s3.

Only the split parts move, and they all move onto s16. s7 and s11 are untouched, and no key is handed from one existing server to another. That last clause is the whole property, and it is what makes the migration bounded.

3. Virtual nodes buy variance, not mean

Now for the point the whole chapter exists for: what raising V changes, and — just as importantly — what it does not.

This is the single most-missed point in the interview. Candidates say “virtual nodes spread the load more evenly,” which is true and unquantified, and then say “and they reduce how much data moves,” which is false — The ring and why 1n1 is not just small but optimal just showed that V cancels out of the average.

What a server’s load actually is

A server’s load is the sum of the lengths of its V arcs. That sum is a random quantity, because the arcs come from hashing, so it has a distribution — and naming that distribution is what lets you put a number on the imbalance.

When M = N x V points are dropped uniformly at random around a circle, the resulting arc lengths are what statisticians call the spacings of a uniform sample: the gaps between sorted random points.

The sum of any V of those gaps follows a Beta distribution, written Beta(V, M - V). Beta is the standard distribution for a random fraction between 0 and 1, which is exactly what a server’s share of the ring is.

Where the Beta comes from, since it is the load-bearing step and is usually just asserted. Four steps:

1. The M spacings are non-negative and sum to 1, so together they are a random point on the simplex — the set of all ways of splitting 1 into M parts.
2. For uniformly dropped points, the distribution over that simplex is the flat one: Dirichlet(1, 1, ..., 1).
3. Pooling parts of a Dirichlet gives a Dirichlet on the pooled parts. Lump the server’s V arcs into one group and the other M - V into another, and the two-part result is Dirichlet(V, M - V) — which is by definition Beta(V, M - V).
4. Sanity-check it against something you already know. That distribution has mean V / (V + (M - V)) = V/M = 1/N, which just says a server owning V of M statistically identical arcs owns 1/N of the ring. Correct, and unsurprising.

The mean was never in doubt. The Beta form is what supplies the variance, and the variance is the quantity this subsection is about.

Putting a number on the spread

The Beta distribution’s mean and variance are known in closed form. The block below writes them down, then combines them into the one number to remember.

mean      =  V / M                       =  1/N
variance  =  V (M - V) / (M^2 (M + 1))

CV = sd/mean = sqrt( (M - V) / (V (M + 1)) )    exact
             = sqrt( (N - 1) / (N V + 1) )      substituting M = N V
            ~=  1 / sqrt(V)                     for N >> 1

In that block, sd is the standard deviation: the typical distance between one server’s share and the average share.

The coefficient of variation (CV) is that standard deviation divided by the mean. Dividing by the mean expresses the spread as a fraction of the average, which makes it comparable across fleet sizes. A CV of 0.94 means a typical server’s share differs from the average by about 94% of the average, which is enormous. A CV of 0.07 means 7%, which is fine.

Substitute this chapter’s N = 16 and V = 200 into the exact form to see it work: sqrt((16 - 1) / (16 x 200 + 1)) = sqrt(15 / 3201) = 0.068. The approximation 1 / sqrt(200) = 0.071 is close enough to quote from memory.

The coefficient of variation of per-server load falls as 1/sqrt(V), and V is the only term that matters.

The table below shows that at eight values of V, all at N = 16. Four columns to read together: the exact formula, the large-fleet approximation 1/sqrt(V), the CV measured over 400 simulated rings (by the cv_and_peak function further down), and the busiest node’s share as a multiple of the mean. The point of the table is the last column — that is the one you pay for.

One cell is not a measurement: the V = 1 peak is the exact closed form derived immediately after the table, and it is marked as such.

Read the first and last columns together, because that pair is the actual answer to “why virtual nodes”:

Without virtual nodes, a 16-server ring has a busiest server holding 3.38x the average keyspace, and in 5% of rings it holds over 5x. You provision for the peak, so a plain ring at V = 1 costs you 3.4 machines for every machine of useful capacity. At V = 200 the peak is 1.13x and the overprovisioning is 13%.

The V = 1 peak has an exact form

That 3.38 is not a simulation result. It has an exact closed form, and the form is the interesting part.

At V = 1 each server owns exactly one arc, so the busiest server is whichever one owns the largest of N uniform spacings.

Two known quantities give the ratio. The expected largest spacing is H_N / N of the circle, where H_N = 1 + 1/2 + 1/3 + ... + 1/N is the harmonic number — the sum of the reciprocals of the first N integers. The mean share is exactly 1/N, since N shares must sum to 1.

Divide the first by the second and the two 1/Ns cancel, leaving H_N:

E[peak / mean]  at V = 1   =  H_N          exactly
  H_16    =  1 + 1/2 + ... + 1/16          =  3.3807
  H_1000  =  1 + 1/2 + ... + 1/1000        =  7.4855

And H_N grows — slowly, like ln N, but without bound — so V = 1 does not merely fail at 16 nodes. It fails worse the bigger the fleet gets.

At a thousand nodes the busiest machine holds 7.5x the average, so you would be provisioning seven and a half machines for every one you actually use.

This is the mirror image of the 1/(N+1) movement result. The mean a server owns is 1/N at every N and never degrades; it is the spread around that mean that does. Quoting 3.33x from a 400-trial simulation is within sampling noise of the truth, but there is no reason to sample something you can write down.

Three consequences to volunteer

1. V = 1 is not “consistent hashing without an optimization.” It is unusable. The paper that introduced consistent hashing — Karger, Lehman, Leighton, Panigrahy, Levine and Lewin, Consistent Hashing and Random Trees, STOC 1997 — introduced virtual nodes in the same breath, for exactly this reason: its balance and spread bounds are proved for each machine replicated to O(log N) points on the circle, not one.
2. The returns shrink quadratically. Halving the imbalance costs four times the virtual nodes, because the CV falls as 1/sqrt(V). Reading the exact column of the table above at N = 16: going from 14% to 7% takes V: 50 -> 200, which is the 0.137 and 0.068 rows, and from 7% to 3.4% takes V: 200 -> 800, where sqrt(15/12801) = 0.0342 runs one row past the table. Past V ~= 200 you are buying single-digit percentages of capacity with a ring that grows linearly, which is why the answer to “how many virtual nodes” is 100-256 in every real system and never 10,000.
3. The randomness has an effective sample size, and it is V, not the number of keys. The effective sample size is how many independent random draws the result really depends on. A billion keys do not average anything out here, because the whole assignment is fixed by just N x V arc boundaries — the keys are along for the ride. This is exactly why rendezvous hashing behaves differently (Alternatives rejected): it randomizes per key, so its effective sample size is the key count.

The code, and the three assertions that carry the argument

Everything above is now checkable. The block below is the whole partitioner — the HashRing class — followed by two measurement functions. Nothing in it is longer than a dozen lines.

Read it in three passes rather than top to bottom:

1. add and get. add turns one server name into V ring points by hashing "node#0" through "node#V-1", and keeps self._pos sorted with bisect.insort. get is the lookup: bisect.bisect is the binary search from step 2 of the lookup diagram, and % len(self._pos) is the wrap over the top of the ring — index M means “past the last point”, which on a circle is index 0.
2. preference_list. This is the clockwise walk. The line doing the real work is if n not in out, which skips a ring point whose machine is already in the list. Without it, V = 200 would hand you three copies on one machine.
3. measure_join and the three asserts under it. These are the chapter’s claims, run against 200,000 real keys rather than argued.

The three asserts are the point of the block, so read those closely:

• Assert 1 checks the measured movement against 1/17. It comes out at 0.0593 against a predicted 0.0588; the comment explains the gap as sampling noise in the new node’s own share.
• Assert 2 checks the property mod N does not have: every key that moved landed on s16, and none was shuffled between two incumbents.
• Assert 3 is the control. It runs mod N over the same keys with the same hash function and measures 0.9406 against the predicted 0.9412.

cv_and_peak at the bottom is the function that produced the CV table above.

import bisect
import hashlib
import statistics


class HashRing:
    """Consistent hash ring with virtual nodes.

    Ownership convention: a key belongs to the first ring position clockwise
    from hash(key), wrapping at the top of the 64-bit space. That convention
    is what makes a join steal exactly one arc per virtual node.
    """

    def __init__(self, nodes=(), vnodes=200):
        self.vnodes = vnodes
        self._owner = {}          # ring position -> physical node
        self._pos = []            # sorted ring positions
        for n in nodes:
            self.add(n)

    @staticmethod
    def _h(s):
        """64 bits is enough, with room to spare.

        The largest ring this chapter builds is the 17-node post-join one at
        V = 200, so N x V = 3,400 points. Size the bound at 4,800 instead --
        a 24-node fleet at the same V, i.e. this chapter's 16 nodes grown by
        half -- so it still holds after the fleet has grown. Even there the
        birthday collision probability is 4,800^2 / 2^65 = 6.2e-13.
        """
        return int.from_bytes(
            hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

    def add(self, node):
        for i in range(self.vnodes):
            p = self._h(f"{node}#{i}")
            if p in self._owner:
                continue          # collision: drop the duplicate point
            self._owner[p] = node
            bisect.insort(self._pos, p)

    def remove(self, node):
        for i in range(self.vnodes):
            p = self._h(f"{node}#{i}")
            if self._owner.get(p) == node:
                del self._owner[p]
                self._pos.pop(bisect.bisect_left(self._pos, p))

    def get(self, key):
        if not self._pos:
            raise KeyError("empty ring")
        i = bisect.bisect(self._pos, self._h(key))
        return self._owner[self._pos[i % len(self._pos)]]

    def preference_list(self, key, r):
        """First r DISTINCT physical nodes clockwise -- the replica set.

        Skipping repeats of the same physical node is mandatory: with V=200
        the next point clockwise is very often another vnode of the same box.
        """
        if not self._pos:
            raise KeyError("empty ring")
        i = bisect.bisect(self._pos, self._h(key))
        out = []
        for j in range(len(self._pos)):
            n = self._owner[self._pos[(i + j) % len(self._pos)]]
            if n not in out:
                out.append(n)
                if len(out) == r:
                    break
        return out

    def load_shares(self):
        """Fraction of the 64-bit keyspace each physical node owns."""
        space = 2 ** 64
        share = {}
        for j, p in enumerate(self._pos):
            prev = self._pos[j - 1] if j else self._pos[-1] - space
            share[self._owner[p]] = share.get(self._owner[p], 0) + (p - prev)
        return {n: v / space for n, v in share.items()}


def measure_join(n_before=16, vnodes=200, n_keys=200_000):
    """Rebuild the ring with one more server and measure what actually moved."""
    keys = [f"key:{i}" for i in range(n_keys)]
    ring = HashRing([f"s{i}" for i in range(n_before)], vnodes=vnodes)
    before = {k: ring.get(k) for k in keys}
    ring.add(f"s{n_before}")
    after = {k: ring.get(k) for k in keys}
    movers = [k for k in keys if before[k] != after[k]]
    return movers, after, len(movers) / n_keys


movers, after, moved = measure_join(16, vnodes=200)

# 1. Mean is 1/(N+1) = 1/17 = 0.0588. Measured 0.0593. The residual is the
#    V=200 sampling noise of the new node's share: sd = 0.0588 x 0.069 = 0.004.
assert abs(moved - 1 / 17) < 0.01, moved

# 2. The property mod-N does not have: every key that moved, moved ONTO the
#    new server. No key was shuffled between two incumbents.
assert all(after[k] == "s16" for k in movers)

# 3. mod-N control, same keys and same hash: 0.9406 against a predicted 0.9412.
mod_moved = sum(HashRing._h(k) % 16 != HashRing._h(k) % 17
                for k in (f"key:{i}" for i in range(200_000))) / 200_000
assert abs(mod_moved - (1 - 1 / 17)) < 0.01, mod_moved


def cv_and_peak(n=16, vnodes=200, trials=200):
    """Coefficient of variation of per-node load, and the busiest node.

    This is the function that produced the table above. Run it at vnodes=1
    and vnodes=200 and the difference is the entire argument for vnodes.
    """
    cvs, peaks = [], []
    for t in range(trials):
        ring = HashRing([f"t{t}-s{i}" for i in range(n)], vnodes=vnodes)
        sh = list(ring.load_shares().values())
        mean = statistics.mean(sh)
        cvs.append(statistics.stdev(sh) / mean)
        peaks.append(max(sh) / mean)
    return statistics.mean(cvs), statistics.mean(peaks)

4. What V costs: memory, lookup, gossip, and durability

V is not free. There are four costs; two of them are negligible, one binds only at large fleet sizes, and the fourth is a durability problem that most explanations of consistent hashing never mention at all.

Memory. The ring holds N x V entries, at 16 bytes each — an 8-byte position plus an owner index padded out to 8 for alignment:

N = 16,     V = 200     3,200 entries x 16 B     =    51,200 B    ->  51 KB   L2-resident
N = 1,000,  V = 200   200,000 entries x 16 B     = 3,200,000 B    ->  3.2 MB  L3
N = 10,000, V = 200     2,000,000 entries x 16 B = 32,000,000 B   ->  32 MB   spills to DRAM

The right-hand annotation on each line says where that much data physically sits, and those three words matter for the lookup cost below.

L2 and L3 are the second- and third-level caches on the processor — small pools of fast memory holding recently used data, a few hundred KB and a few tens of MB respectively. DRAM is ordinary main memory: far larger, and roughly twenty times slower to reach than L2.

So the ring stays in cache until the fleet reaches thousands of nodes, and only then starts paying main-memory prices.

Lookup. A binary search over M sorted entries costs ceil(log2 M) probes, since each probe halves the range still in play:

M =     3,200    log2 = 11.6   ->  12 probes, all L2 at ~4 ns      =    48 ns
M = 2,000,000    log2 = 20.9   ->  21 probes; the top 11 levels fit
                                   in 32 KB of L1/L2, the bottom 10
                                   miss to DRAM at ~80 ns
                                   11 x 4 + 10 x 80               =   844 ns

Take the worst case, 844 ns, and compare it with the network round trip that follows every lookup: 844 / 500,000 = 0.0017, or 0.17% of one network hop.

So say it plainly: lookup cost is never the reason to limit V. Candidates who reach for “but the binary search gets slower” have found a real term and the wrong bottleneck.

Gossip and propagation. This one is real. Every client and every server holds its own copy of the ring, so the token list — the full set of N x V ring positions and their owners, “token” being the conventional name for one ring position — has to be shipped to everyone whenever the membership changes:

N = 1,000, V = 200:  ring is 3.2 MB
  broadcast to 1,000 peers    =  3,200 MB of egress
  at 125 MB/s per machine     =  25.6 s of a saturated 1 Gbps link
N = 1,000, V = 16:   ring is 256 KB
  broadcast to 1,000 peers    =    256 MB
  at 125 MB/s                 =   2.05 s

This is why Cassandra’s num_tokens default moved from 256 to 16 in 4.0 (CASSANDRA-13701, “Lower default num_tokens”). Cassandra is a widely deployed distributed database built on exactly this ring, and num_tokens is its name for V.

It is the correct trade, even though the balance gets worse. Both figures below are at N = 1,000, so they are comparable:

V = 200   CV = sqrt(999 / (1,000 x 200 + 1))  =  sqrt(999/200001)  =  0.071
V = 16    CV = sqrt(999 / (1,000 x  16 + 1))  =  sqrt(999/16001)   =  0.250

The reason that is acceptable: a 1,000-node cluster gets its balance from a deliberate token allocation algorithm — one that chooses ring positions to even out the arcs — rather than from raw randomness. Once an algorithm is placing the tokens, you no longer need a large V to average the randomness away.

Durability — the cost nobody names. With a replication factor of R, a key’s copies live on the next R distinct nodes clockwise from it. Call that group of machines the key’s replica set.

Data is lost only when every member of some replica set fails at once. So the question that decides durability is: how many distinct replica sets exist across the whole ring?

The two extremes are worth holding in mind. Few replica sets means most random multi-node failures hit machines that never shared any data, so nothing is lost. Many replica sets means almost any combination of failures destroys something.

The block below counts them at the two ends of the V range.

V = 1,   N = 16, R = 3:  each node has 1 arc -> N distinct replica sets  =  16
V = 200, N = 16, R = 3:  16 x 200 = 3,200 arcs, far more than
                         C(16,3) = 560 possible triples, so essentially
                         EVERY triple is a replica set for some key

C(16,3) is the number of ways to choose 3 machines out of 16 without regard to order — 16 x 15 x 14 / (3 x 2 x 1) = 560 possible triples in total.

At V = 1 there are only 16 replica sets, a tiny fraction of those 560. At V = 200 there are 3,200 arcs each handing out a replica set, comfortably more than 560, so essentially every triple is somebody’s replica set.

Turn that count into a probability. Pick 3 machines at random and fail them at the same instant. The chance you destroyed data is the chance that particular triple happens to be a replica set:

V = 1     P(the failed triple is a replica set)  =  16 / 560   =  0.0286
V = 200   P(the failed triple is a replica set)  ~=  1.0

Raising V from 1 to 200 takes an arbitrary 3-node failure from a 2.9% chance of data loss to a near-certain one.

Nothing was lost in expectation — the expected bytes lost is unchanged, since the same amount of data sits on the same machines either way. What changed is the probability of any loss at all, and it went to one. Outages are counted by incidents, not by expected bytes.

This is the real cost of virtual nodes, and it is the answer that separates a candidate who has read about the ring from one who has operated it.

The fix is not fewer virtual nodes. It is constraining which nodes may appear together in a replica set.

Two failure boundaries matter. A rack is a single cabinet of machines sharing power and a top-of-rack switch, so its machines tend to fail together. An availability zone (AZ) is the same idea one scale up: a datacenter or group of datacenters with independent power and network.

Rack- and AZ-aware placement skips any candidate replica whose rack already appears in the preference list. That collapses the replica-set count back to something structured, and guarantees the copies land on different failure boundaries.

Cassandra 4.0 pairs this with a deterministic token allocator — ring positions chosen by an algorithm aiming for even arcs, rather than drawn at random — instead of random placement. Say “virtual nodes plus rack awareness,” never virtual nodes alone.

The verdict, priced at one fleet size throughout. Every cell in the table below is at N = 1,000, because the ring-size column only makes sense at a stated fleet size. Where a figure differs materially at this chapter’s N = 16, the cell gives both — two of them do.

5. What consistent hashing does not fix

The technique has a boundary, and it is the thing an interviewer probes once you have shown you understand the ring itself.

Consistent hashing balances the keyspace. It does not balance bytes, and it does not balance requests. Three distinct balance problems get conflated into one, and only the first is solved by the ring:

Take the hot-key case and put numbers on it. A hot key is a single key receiving a wildly disproportionate share of requests — a celebrity’s profile, a viral post.

Set up the arithmetic: traffic is 100,000 QPS spread over N = 16 servers, and one hot key takes 30,000 of that by itself. The block below works out what the unlucky server that owns it actually sees, in three steps: the fair share, then the 70,000 non-hot requests spread evenly, then the one server that also carries the hot key.

uniform expectation per server   =  100,000 / 16      =  6,250 QPS
the other 70,000 spread over 16  =  70,000 / 16       =  4,375 QPS
the server owning the hot key    =  30,000 + 4,375    =  34,375 QPS
                                    34,375 / 6,250    =  5.5x the mean

A single key hashes to a single point, that point falls in a single arc, and that arc belongs to a single server. No value of V changes this — V = 10,000 still puts all 30,000 QPS on one box, because the key has exactly one hash. Candidates who answer “add more virtual nodes” have not understood what the variance argument was about.

The three real fixes, in the order you should offer them:

1. Cache in front, and coalesce. The hot key is hot precisely because it is read constantly, which also makes it the easiest thing in the system to cache. Give the front tier a copy with a 1-second TTL — a time to live, after which the cached copy is discarded and refetched. One fetch per second per front-end process turns 30,000 QPS into 1 QPS from each front-end; across 20 front-ends that is 20 QPS reaching the ring, which is 30,000 / 20 = 1,500x fewer. Then add single-flight: when the cached copy expires, only one request goes to the backend to refill it while the rest wait for that answer. Without it, the expiry moment sends 30,000 concurrent requests through at once — a cache stampede, whose mechanics are in sql 03 — Caching layers and invalidation. This is the answer, and it lives entirely outside the partitioner.
2. Split the key. Store the value under R derived names, k#0 through k#R-1, writing all of them and reading from a randomly chosen one. At R = 8 that is 30,000 / 8 = 3,750 QPS per copy — below the 6,250 uniform mean, so the hot key stops being the constraint. Two costs. Writes now fan out eight ways. And the R copies go stale independently of each other, so two readers can see different values. That is right for a hot counter, where an approximate answer is fine, and wrong for a hot document, where it is not.
3. Bounded-load consistent hashing. Cap each node at c x mean load and, when the natural owner is already full, probe clockwise until you find a node that is not. The expected number of probes is O(1/(c-1)) — order-of notation, meaning it grows proportionally to that expression — so c = 1.25 costs about 4 probes in the worst case. This bounds the imbalance caused by many warm keys, but it cannot help a single hot key, because one key is indivisible. It also makes the assignment depend on current load, so the lookup is no longer a pure function of the key and every client must somehow agree on load state. That is why the technique lives in load balancers and not in storage.

The sentence to say: “consistent hashing gives me a uniform keyspace; it gives me nothing against a Zipf request distribution, and those are different problems with different fixes.” A Zipf distribution is the heavily lopsided popularity pattern that real traffic follows — the most popular item gets roughly twice the requests of the second, three times the third, and so on — which is why one key holding 30% of all traffic is a normal Tuesday rather than an anomaly.

6. What each scheme assumes, and what breaks when it does not hold

Every partitioning scheme above is correct only in a world that behaves a certain way, and some of those assumptions are load-bearing.

Load-bearing means this: when the assumption fails, you must change algorithm, not tune a parameter.

A non-load-bearing assumption failing costs you a constant — more virtual nodes, a bigger cache, a different bounded-load c. A load-bearing one failing means the design is simply wrong for your situation.

Read the third column first. It is the one that tells you whether a failed assumption is a tuning job or a rewrite.

Three of the four assumption families that recur across this repo apply here, and one does not:

• Key distribution is the load-bearing one. Every number in this chapter — 5.9%, 1/sqrt(V), 1.13x — assumes keys and requests are spread uniformly. Keys usually are, because you hash them. Requests are not, because human attention follows a Zipf distribution (What consistent hashing does not fix), and no ring parameter repairs that.
• Node churn — machines joining and leaving — is what the whole scheme exists to survive, and the ring handles it at the theoretical minimum cost. It becomes a problem only when churn is fast: a node flapping every 40 seconds generates a continuous rebalance that competes with live traffic for the same network cards (Failure modes).
• Correlated failure is the assumption virtual nodes quietly break, and it is the finding of What v costs memory lookup gossip and durability. Independent failures are what the arithmetic assumes; a rack losing power is not independent.
• Clock skew — machines disagreeing about the time — does not apply, and saying so is worth a moment. The ring is a pure function of the key and the membership set, with no timestamps anywhere in it. That is a real advantage over any scheme whose correctness depends on time, and it is why membership changes need versioning rather than synchronized clocks.

3. Bottlenecks and scaling

Which constraint binds depends on the fleet size — and for small fleets nothing binds at all, which is itself a design finding.

Scaling by more than one node at a time is where the arithmetic gets useful. Adding k nodes to a fleet of N moves k/(N+k) of the corpus in one go, which is not the same as k separate joins of 1/(N+1) each.

Compare the two ways to get from 16 servers to 18. Sequentially you pay 1/17 and then 1/18; in one batch you pay 2/18:

16 -> 17 -> 18 (one at a time)   1/17 + 1/18   =  0.0588 + 0.0556   =  0.114
16 -> 18       (both at once)    2/18                              =  0.111

The two are nearly identical — 11.4% against 11.1% — so the argument for batching is not bytes moved. Two other reasons carry it:

• Each rebalance has a correctness window and a throttling budget, and you would rather have one of them than two.
• The bottleneck on a join is the receiver. From the back-of-envelope, a join is inbound to one network card. The same total bytes arriving at k joiners simultaneously finish in a kth of the wall-clock time that k sequential joins would take.

So scale in batches sized to the migration window, not to the capacity deficit.

4. Failure modes

A ring breaks in production in seven ways. The first is the one that loses data silently, and the last three are the ones that only appear under load.

5. Alternatives rejected

Six schemes are worth being able to name, along with what each genuinely does better than the ring and the specific condition under which it wins. Two of the six beat the ring outright in common situations, and saying so is what separates a memorized answer from a considered one.

The one to revisit, with a trigger: move from the ring to fixed logical shards if you find yourself writing a rebalancing tool anyway — at that point you already have the routing table and the ring’s only remaining advantage is that it needs no coordination.

6. Interviewer pushback

Spoken aloud, the derivations above sound like this. Each question names what it is testing, then gives an answer of the length that earns the point — every claim carrying the number behind it.

“Why not just hash(key) mod N?” Testing: whether you produce a number or an adjective. Because at N: 16 -> 17 it moves 94% of the corpus. A key stays only if h mod 16 == h mod 17, and since 16 and 17 are coprime the pair (h mod 16, h mod 17) is uniform over 272 combinations and equal for only 16 of them, so 1/17 stay and 16/17 move. The general form is 1 - 1/(N+1), which means it gets worse as the fleet grows — at 100 nodes it moves 99%. On 10.88 TB of logical data with 1 Gbps NICs that is 10.23 TB moved, 1.42 hours per node at line rate and several hours at a sane throttle — and the honest comparison is bytes, not clock: the ring moves 0.64 TB instead, a 16x saving on wire and disk, but since a join is inbound to one machine that 0.64 TB takes the same 1.42 hours to land. What the ring buys is that fifteen of the sixteen incumbents contribute 5.3 minutes each rather than 1.42 hours each. The one exception is doubling: 16 -> 32 moves exactly 50%, so if your fleet only ever doubles you do not need a ring.

“How much data moves when a node joins the ring?” Testing: whether you know V cancels. 1/(N+1), which is 5.9% at N = 16. The derivation: each new virtual node lands inside one existing arc and splits it, so V new points steal V arcs. After insertion there are (N+1)V arcs, each with expected length 1/((N+1)V) by symmetry, and the new server owns V of them, so V/((N+1)V) = 1/(N+1). The V cancels — the mean is the same at one virtual node or a thousand. And 1/(N+1) is optimal, not merely good: any balanced assignment must hand the new server 1/(N+1) of the keyspace, and all of that is currently elsewhere.

“Then what are virtual nodes for?” Testing: the point of the whole question. Variance. The coefficient of variation of per-server load is sqrt((N-1)/(NV+1)), which is about 1/sqrt(V). At V = 1 and N = 16 that is 0.94, and the busiest of 16 servers holds 3.38 times the average keyspace — that figure is exactly the harmonic number H_16, and since H_N grows it is 7.49x at a thousand nodes. In the worst 5% of rings at N = 16 it is over 5x. At V = 100 the CV is 10% and the peak is 1.18x; at V = 200 the CV is 7% and the peak is 1.13x. You provision for the peak, so V = 1 costs you 3.4 machines per useful machine at 16 nodes and 7.5 at a thousand. The returns are quadratic in the wrong direction — halving the imbalance costs 4x the vnodes — which is why every real system lands at 100-256 and not 10,000.

“So set V to 10,000 and forget about it.” Testing: whether you know what V costs. Three costs, and only one is the obvious one. Memory and lookup are nothing: at N = 16, V = 200 the ring is 51 KB and a lookup is 12 L2 probes, about 48 ns against a 500,000 ns network round trip. Gossip is real: at N = 1,000, V = 200 the token list is 3.2 MB and broadcasting it to 1,000 peers is 3.2 GB, or 25.6 seconds of a saturated 1 Gbps link per membership change — which is exactly why Cassandra dropped num_tokens from 256 to 16. And the one people miss is durability. With RF 3 and V = 1 there are only 16 distinct replica sets out of C(16,3) = 560 possible triples, so a random 3-node failure loses data 2.9% of the time. At V = 200 there are 3,200 arcs, essentially every triple is a replica set, and that same failure loses data with probability near 1. Virtual nodes trade load variance for a larger correlated-failure surface, and the fix is rack-aware placement, not fewer vnodes.

“One key is taking 30% of your traffic. How do virtual nodes help?” Testing: whether you know the boundary of the technique. They do not, at all. One key has one hash, that hash falls in one arc, and that arc belongs to one server — V = 10,000 changes nothing. At 100,000 QPS with 30,000 on the hot key, that server sees 34,375 QPS against a 6,250 mean, so 5.5x. Consistent hashing balances the keyspace; it says nothing about a Zipf request distribution. The fix is a front-tier cache with single-flight, which turns 30,000 QPS into about 1 per front-end process per TTL — 20 QPS reaching the ring across 20 front-ends. If it is a hot counter rather than a hot document, split it into k#0..k#7 and read a random suffix, which costs 8x write fan-out and gives you 8 independently-stale copies.

“Do I even need this? We have 12 servers.” Testing: whether you reach for the ring by reflex. Probably not. At N = 12, rendezvous hashing gives you the identical 1/(N+1) movement guarantee with no virtual nodes, near-perfect balance because it randomizes per key rather than per arc, and a free ordered replica list from the argsort. It costs O(N) hashes per lookup, about 24 ns at 12 nodes, which beats the ring’s binary search. The crossover is around 25 nodes. And if the fleet size is stable and you control the clients, fixed logical shards with a routing table balance better than the ring — 1,024 shards over 17 nodes is 60 or 61 each, a 1.3% peak — and move the same 5.9%. The ring earns its place when membership changes without coordination.

“Walk me through what the client does on a lookup.” Testing: whether the mechanism is concrete. Hash the key to 64 bits with a non-cryptographic hash — about 2 ns, and it must be pinned in the wire protocol so no client can disagree. Binary search the sorted position array for the first position greater than or equal to the hash, wrapping to index 0 — ceil(log2(N x V)) probes, 12 at N=16, V=200. That gives a virtual node; index the parallel owners array to get the physical node. Then walk clockwise collecting distinct physical nodes until you have R of them, skipping repeats — at V = 200 the next point is usually another vnode of the same box, so the deduplication is not optional — and skipping any node whose rack already appears. That ordered list is the preference list, and ch 06 is entirely about what to do with it.

“A node is flapping. What happens?” Testing: whether you connect the partitioner to operations. Each transition moves 1/16 of the corpus in and then back out, so a node failing a health check every 40 seconds generates a continuous rebalance that competes with live traffic for the same NICs. Two guards. First, membership must be hysteretic — the failure detector proposes, but removal from the ring needs a long timeout or a human, which is why real systems separate “down” from “removed.” Second, topology changes must be serialized under a lock, because a scale-down that starts while an anti-entropy repair is streaming has two migrations on one 125 MB/s link and neither finishes. And I would alert on migration bytes/s and on ownership transitions per node per hour, both of which move before anything user-visible does.

Cheat sheet

Every claim in this chapter, compressed to one line each, for the last five minutes before a round.

Next: 06 — Design a Key-Value Store — where the ordered list returned by preference_list(key, R) becomes a quorum, meaning a rule such as “a write is not done until 2 of the 3 replicas confirm it”, and every one of those R replicas is allowed to disagree in the meantime.