Shuffle sharding

How does combinatorial assignment isolate tenants without reserving capacity?

This is the sharpest idea in the article, and it is pure combinatorics. With n nodes, assign each tenant (a customer or client of the service) a random subset of k nodes. The number of distinct assignments is the binomial coefficient C(n, k) (the number of ways to choose k items out of n).

Worked example

n = 100, k = 2: C(100, 2) = 100 × 99 / 2 = 4,950 distinct pairs. A single abusive or poisoned tenant that destroys both of its nodes fully impacts only the tenants that share that exact pair: about 1/4,950 of tenants. Tenants that share just one node degrade but survive, because they can retry on their other node.

RelationshipShuffle sharding →

(2 100) = 4, 950

$n$: nodes in the pool
$k$: nodes assigned to each tenant

Data table

Share of tenants fully exposed to one bad tenant, by nodes (k = 2)
Nodes n	Tenants fully impacted
4	16.7%
4.29	14.2%
4.59	12.1%
4.92	10.4%
5.27	8.88%
5.65	7.62%
6.05	6.54%
6.48	5.62%
6.95	4.84%
7.44	4.17%
7.98	3.59%
8.55	3.1%
9.16	2.68%
9.81	2.31%
10.5	2%
11.3	1.73%
12.1	1.5%
12.9	1.3%
13.9	1.12%
14.8	0.973%
15.9	0.844%
17	0.732%
18.3	0.635%
19.6	0.551%
21	0.478%
22.5	0.415%
24.1	0.36%
25.8	0.313%
27.6	0.272%
29.6	0.236%
31.7	0.205%
34	0.178%
36.4	0.155%
39	0.135%
41.8	0.117%
44.8	0.102%
48	0.089%
51.4	0.077%
55.1	0.067%
59	0.058%
63.2	0.051%
67.8	0.044%
72.6	0.039%
77.8	0.034%
83.4	0.029%
89.3	0.025%
95.7	0.022%
103	0.019%
110	0.017%
118	0.015%
126	0.013%
135	0.011%
145	0.01%
155	0.008%
166	0.007%
178	0.006%
191	0.006%
204	0.005%
219	0.004%
235	0.004%
251	0.003%
269	0.003%
289	0.002%
309	0.002%
331	0.002%
355	0.002%
381	0.001%
408	0.001%
437	0.001%
468	0.001%
501	0.001%
537	0.001%
576	0.001%
617	0.001%
661	0%
708	0%
759	0%
813	0%
871	0%
933	0%
1K	0%

Principle: Randomization replaces coordination →

Two conditions make it work, and both are essential.

The workload must be retryable and effectively stateless across the members of a shard, or the surviving node is no help.
The failure must be tenant-induced, not resource-induced. Shuffle sharding isolates poison pills and hot tenants. It does not isolate a capacity shortfall, because every node still serves many tenants and there is no resource partition at all.

That is also its advantage over bulkheads: no multiplexing loss. Isolation comes from combinatorics instead of from reservation.

This is randomization replacing coordination once more, and here the randomness does something specific: it manufactures independence between tenants where the physical system offers none. It does the same job as jitter on a different axis. Jitter decorrelates in time; shuffle sharding decorrelates in assignment.

import random
def shard_for(tenant_id, nodes, k=2):
    rng = random.Random(tenant_id)          # stable per tenant
    return rng.sample(nodes, k)             # each tenant gets its own random pair