Give each tenant k of your n nodes, drawn at random. Two tenants share no node at all with probability C(n−k, k)/C(n, k) and hold the identical set with probability 1/C(n, k) — and only the identical set means one tenant's bad request can take the other down. At n = 16 and k = 2 those are 91/120 and 1/120, and one failed node degrades 1/8 of tenants while taking down none of them.
Core ideas
The whole lesson is a hypergeometric distribution over how many nodes two tenants have in common, and the two ends of it are the ones that matter.
A tenant holds k of n nodes. A second tenant, drawn independently and uniformly, shares exactly j of them with probability C(k,j)·C(n−k, k−j)/C(n,k). Summing over j gives one, which is the cheapest check on the arithmetic. At n = 16, k = 2 the three outcomes are 91/120, 7/30 and 1/120 for zero, one and two shared nodes.
A tenant that shares one of your two nodes has lost half its capacity and still has the other half; it is degraded, not down. A tenant holding exactly your set has nowhere to go. So the number that matters is 1/C(n,k) = 1/120, not the 23.3% chance of some overlap — and those two differ by a factor of twenty-eight at this setting.
A single bad node is used by the k/n of tenants whose shard includes it — 1/8 at n = 16, k = 2. Every one of them loses one node out of k and keeps the rest. Without shuffle sharding, a fleet split into n/k fixed shards would give the same node k/n of the tenants as a full outage, which is the same fraction with an entirely different consequence.
The material
Where the two probabilities come from, why overlap is not collision, and how the numbers move when the shard size does.
Under shuffle sharding each tenant is assigned a random k-subset of the n nodes, drawn independently per tenant, rather than being placed in one of n/k fixed shards. There are C(n,k) distinct assignments. Two tenants overlap in j nodes with probability C(k,j)·C(n−k, k−j)/C(n,k); they are disjoint when j = 0 and identical when j = k.
The counting is direct. Fix the first tenant's k nodes. The second tenant's set is one of the C(n,k) equally likely subsets, and the ones sharing exactly j nodes are formed by choosing j from the first tenant's k and the remaining k − j from the n − k nodes it does not hold. That is the hypergeometric distribution, and nothing about it is approximate.
Read the third row against the second. Nearly a quarter of tenants share a node with you, and one in a hundred and twenty shares both. Sharing nothing is 91 times likelier than sharing everything, and that ratio is the entire argument for drawing shards at random rather than assigning them in blocks.
Suppose a tenant sends a request that makes a node unusable — a poison pill, a query that exhausts memory, a pattern that triggers a bug. Every tenant sharing that node is affected. But a tenant that shares one of your two nodes still has one working node and, if the client retries elsewhere, still has a service. Only a tenant whose entire set is inside the damage has nothing left.
The node fails or is poisoned. k/n = 1/8 of tenants use it, so one in eight is degraded to a single remaining node. None is down, because no tenant's shard is a subset of a single-node failure when k = 2. Compare a fixed-shard layout of eight shards of two: the same node takes out one shard entirely, and every tenant in it — 1/8 of the fleet — is fully down.
Raising k cuts the collision probability hard, because C(n,k) grows quickly, while raising the blast radius k/n of each individual node. At n = 24 and k = 4 there are 10 626 distinct shards, so two tenants collide with probability 1/10 626 — 0.0094% — and 45.596% share nothing. The cost is that one bad node now touches 1/6 of tenants rather than 1/8, each of them losing one node of four.
Two levers and they pull in opposite directions, which is the design question this lesson leaves you with. More nodes per tenant means fewer tenants can take you down with them and more tenants feel each individual failure, at a lower severity each. The lab computes both columns for whatever n and k you set.
The lab draws a sample assignment from a seed and marks each tenant with the number of your nodes it shares. At n = 16, k = 2 and twelve tenants, the expected number holding your exact set is 11/120 ≈ 0.0917, so a draw in which none does is the ordinary outcome. Raise the tenant count and the seed and watch how rarely a red row appears — that rarity is the 1/120, made visible.
One boundary. At k = 1 the distinction this lesson turns on disappears: a tenant on one node is degraded and down by the same event, and the collision probability is 1/n, which is simply the chance of landing on the same node. Shuffle sharding needs k ≥ 2 to mean anything, and the client has to be able to use the surviving nodes — if a request is pinned to one node of the k, the arithmetic on this page is describing a system you do not have.
Interactive
Two tenants, k nodes each, and the probability that one of them takes the other down
Method
Two coefficients answer the question, and the third and fourth steps are where the answer either applies to your system or does not.
That integer is the headline: C(16,2) = 120, C(24,4) = 10 626. The probability that two tenants hold the identical set is its reciprocal, so the whole design is an argument about how large you can make a binomial coefficient at acceptable cost.
C(n−k,k)/C(n,k) for sharing nothing, 1/C(n,k) for sharing everything, and the hypergeometric terms in between. Summing all k + 1 of them must give exactly one; if it does not, a coefficient is wrong.
The arithmetic says a tenant sharing j < k nodes keeps k − j of them. Whether that is a working service depends on whether your client retries on another node and whether one node can carry the tenant's load. If either answer is no, partial overlap is an outage and the 1/C(n,k) figure is not the one to quote.
Raising k shrinks 1/C(n,k) fast and raises k/n, so more tenants feel each failure at lower severity. Pick the point on that trade rather than inheriting it, and state both numbers when you do — a collision probability quoted without the blast radius has reported one half of the design.
A realistic sizing question. One tenant is capable of making a node unusable, and the operator wants to know how many other tenants go down with it and how many merely notice.
Both numbers are needed and they say opposite-sounding things. Nearly half the fleet is touched, which sounds alarming until the severity is attached: each of those tenants has lost one node of four and keeps three. The number of tenants that lose everything is 0.0278 in expectation — about one occurrence in thirty-six such events.
Compare the fixed-shard alternative at the same k: eight shards of four, each holding 125 tenants. The poisoned tenant takes its entire shard down, so 125 tenants are fully out and 875 are untouched. Shuffle sharding converts one hundred and twenty-five outages into four hundred and thirty degradations and a rounding error, which is the trade in one sentence.
For a faded rehearsal, the operator proposes n = 32, k = 2 instead, to halve the per-tenant footprint. The supplied first move is that C(32,2) = 496, so the collision probability rises by a factor of 35 960/496. Compute the expected fully-down tenants and the expected degraded tenants under that setting, check both in the lab, and say which of the two columns you would be willing to trade.
You should be able to compute C(n,k), the disjoint and identical probabilities and the hypergeometric terms between them, check that they sum to one, separate degradation from outage, and state the collision probability and the blast radius together as the two halves of one design choice.
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.