Shuffle Sharding

#sharding | #reliability | #distributed
Sep. 6, 2026 · 5 min read

Why does Route 53 give your hosted zone four seemingly random name servers instead of the same ones everyone else gets? There are 2,048 of them, arranged into 730 billion possible combinations. That’s what keeps another customer’s failure domain separate from yours.

Shuffle sharding

A volumetric DDoS attack floods one customer’s DNS name servers with random labels, causing elevated latency. On a normal shared fleet of machines, that attack would cause delays for other customers too. At Route 53, only that single customer’s name servers are impacted.

What is shuffle sharding?

Shuffle sharding assigns each tenant a random K-resource subset of a shared pool of N, instead of splitting N into fixed, non-overlapping N/K groups. Colm MacCárthaigh found it in Knuth’s TAOCP 4F3[1], while his six-person team was working out how Route 53 would withstand DDoS attacks. Assign each customer a unique combination of four virtual name servers from a pool of about 2,000, and the maths bound how much overlap any two customers could share[2].

First up, regular sharding. Picture eight workers handling requests for many customers. Split them into four regular shards of two workers each. Any single failure takes down that shard, with a blast radius of one in four customers.

Now shuffle-shard it. The same eight workers produce (8 * 7) / 2! = 28 distinct pairs[3]. Spread customers across all 28, and a single failure now hits one in 28 customers, down from one in four.

The maths scales combinatorially

Route 53 runs this at a scale where the effect gets absurd. It uses 2,048 virtual name servers and assigns each hosted zone to a shard of four name servers[3]. The count of distinct four-server combinations is (2048 choose 4) = (2048 * 2047 * 2046 * 2045) / 4! = 730,862,190,080.

Regular sharding gives 512 (2048/4) groups. Shuffle sharding gives 730 billion, using the same hardware. Route 53 can assign a unique shard to each hosted zone with plenty of room to spare.

730 billion possible shards is massive, but it doesn’t rule out two customers colliding. Draw enough four-server combinations at random from the same pool of 2,048, and some pair will collide. Route 53 assigns each new zone only after searching for and rejecting any candidate that would share more than two of four virtual name servers with an existing hosted zone[3]. That number is two because testing showed domain resolution is reliable even while two of its four name servers are unreachable[2].

Run the numbers (2,048 servers, four per customer) through MacCárthaigh’s blast-radius calculator[4]: 99.22% of customer pairs share zero servers, 0.78% share one, and sharing two or more drops below two hundredths of a percent. The same cap that limits two-way overlap to two shared servers rules out three- and four-way overlap entirely. When one domain gets attacked, the overwhelming majority of other zones notice nothing at all.

Beyond AWS

Grafana Cloud is built on Mimir (a fork of Weaveworks/CNCF Cortex), which shuffle-shards tenants across ingesters, queriers, store-gateways, and compactors[5]. Shard size ranges from one instance to the full fleet, letting each tenant’s blast radius be sized independently rather than fixed for everyone.

Kubernetes API Priority and Fairness (APF) shuffle-shards each request across a subset of queues. The subset size, called handSize, keeps one noisy client from starving the rest[6]. At a handSize of 10 across 64 queues, the odds of a noisy flow colliding with a quiet one are about 1 in 150 billion.

HashiCorp Terraform Cloud uses a cellular architecture to schedule customer workloads across a pool of Nomad clusters. Each customer is assigned a random but deterministic subset, “the odds that any two customers share the exact same virtual shard assignment is exceedingly small"[7].

Common mistakes

You draw random shards without bounding overlap. Two customers can still end up with overlapping shards. The fix is an assignment scheme that searches for and rejects any draw crossing the bound.

You miss the shared dependency behind the shard. Shuffle sharding only isolates independent failures, like one crashing worker. Any SPoF (e.g., shared config, shared datastore) impacts everyone at once.

You retry a crashing query against a fresh querier. Mimir documents a failure mode where a query-frontend retries a crashing query (e.g., oomkiller trigger, panic, segv) against a fresh querier, so the crash works its way through the whole fleet. Mimir mitigates it with a forget-delay setting that pins retries to the same querier[5].

You shrink a stateful shard without a rollout plan. Route 53’s name servers are stateless, so resizing a customer’s shard costs nothing. Ingesters in Mimir hold tenant data, so shrinking a shard too soon can silently return incomplete results. Mimir documents a specific rollout order for changing shard size[5].

Put it into practice

Examine your system the way Route 53 examined its fleet of name servers. If one bad request or one bad customer can take down a shard that serves a large share of your customers, shuffle sharding is worth considering. It shrinks your blast radius combinatorially instead of linearly.

Measure the maximum overlap between any two tenants’ assignments. Route 53’s open source Infima library enforces that bound and rejects any draw that violates it[3].

You’ll reduce your blast radius for basically nothing. Route 53’s original team proved it on a total infrastructure budget in the tens of thousands of dollars, versus the tens of millions for proper packet-scrubbing hardware[2].

References

  1. Knuth, Donald E. (2005). The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions. Addison-Wesley. https://www.informit.com/store/art-of-computer-programming-volume-4-fascicle-3-generating-9780201853940
  2. MacCárthaigh, Colm (2025). Comment on "Donald Knuth's 2024 Christmas Lecture: Strong and Weak Components." Hacker News. https://news.ycombinator.com/item?id=42975315
  3. MacCárthaigh, Colm (2019). "Workload Isolation Using Shuffle-Sharding." Amazon Builders' Library. https://d1.awsstatic.com/builderslibrary/pdfs/workload-isolation-using-shuffle-sharding.pdf
  4. MacCárthaigh, Colm. "shardcalc.py." GitHub Gist. https://gist.github.com/colmmacc/4a39a6416d2a58b6c70bc73027bea4dc/0cbe948c3b2e60289aed25f40e1a6a72dca2cec9
  5. Grafana Labs (2024). "Configure Shuffle Sharding." Grafana Mimir Documentation. https://grafana.com/docs/mimir/latest/configure/configure-shuffle-sharding/
  6. Kubernetes. "API Priority and Fairness." Kubernetes Documentation. https://kubernetes.io/docs/concepts/cluster-administration/flow-control/
  7. Ludden, Chris, and Anthony Davis (2023). "Using Temporal at HashiCorp." Replay 2023. https://temporal.io/resources/on-demand/temporal-hashicorp

Outtakes

MacCárthaigh described “recursively” shuffle sharding the caller’s caller too, so a misbehaving downstream client burns through only its own slice of the assigned shard (MacCárthaigh, 2021).

MacCárthaigh noted that shuffle sharding applied to rate limits resembles Stochastic Fair Blue, a fairness algorithm for stopping one flow from hogging a shared link (Feng et al., 2001).

Infrastructure wasn’t the only cost. Route 53 needed 2,048 anycast IP addresses for its virtual name servers, and had to register 512 domains to satisfy TLD glue-record requirements (MacCárthaigh, 2025).

Route 53 allocates each customer’s four name servers from four independent stripes, one per TLD (co.uk (2LD actually), com, net, org). If one of those TLDs has a problem (e.g., TLD key-rollover mistake, DS/DNSKEY mismatch), only one of the four name servers is affected (MacCárthaigh, 2025).

Changelog

2026-09-07 Dropped references to Cortex (CNCF).
2026-09-06 Initial release.

Similar articles: