Scatter-gather

How does fanning out multiply the tail and the failure probability, and which escapes exist?

Scatter-gather: the cost of asking everyone

Scatter-gather means fanning a request out to N shards and waiting for all the answers. It brings two independent penalties, both multiplicative in N.

Latency is the expected maximum of N draws, E[max of N]. The whole request inherits the tail of the worst shard: at N = 100, 63% of requests meet at least one shard above its own p99 (tail at scale). The median fan-out request contains a p99 event. The tail is not an edge case at width. It is the common case.

Ingrid's page. With N = 40: 1 − 0.99⁴⁰ = 1 − 0.669 ≈ 33% of page loads contain at least one shard slower than its p99. The page's own median sits at about the shard's 98th percentile. That is why the page p99 is so much worse than 50 ms.

Availability is p^N if shard failures are independent. At three nines (0.999) per shard and N = 100, the query succeeds with probability 0.999¹⁰⁰ ≈ 90%. This is why every fan-out system is also a replicated system (a retry needs somewhere else to go), and why fan-out width and replication factor are not independent decisions.

Four escapes, four currencies

1. Narrow the fan-out by making partitions larger. This conflicts directly with the arithmetic of distribution, where small partitions bought quadratic recovery speed and fine-grained balance. The conflict is real and cannot be resolved in general: the partition size that is best for recovery and balance is not the size that is best for fan-out tail. Which objective wins depends on whether your queries touch all shards or one. Point-lookup workloads should partition finely. Scatter-gather workloads should not. This is the one place where two parts of this mechanism give opposite advice.

2. Hedge the slow shards (Hedging, next). It costs duplicate work and works only if the slowness is attempt-local.

3. Return partial results. Answer after 95% of shards have reported, and mark the response as degraded. This is the only escape that costs no extra work, and it costs exactness instead. Its precondition is algebraic: you can drop a shard if and only if the aggregation tolerates a missing input.

   • Tolerant: top-k, sums with an error estimate, sampled counts, search relevance.
   • Not tolerant: exact counts, joins, existence queries ("does any row match?" cannot be answered if a shard is missing).

   This is "the right algebra removes the coordinator" in a new form. Earlier, algebra decided whether operations could be reordered or merged. Here it decides whether an input can be absent. It is the same property with a stronger consequence, and it is why search engines degrade gracefully at width while analytical engines cannot.

4. Tree-structured gather. This needs a correction. A tree reduces the fan-in at each node, the incast pressure (many senders hitting one receiver at once) and the merge CPU at the root. It does not improve the tail, because completion is still bounded by the slowest leaf and the tree adds extra hops. Trees are a bandwidth and CPU mechanism that is often sold as a latency mechanism.

Lay these side by side and the three-currency structure is clear:

There is no fourth.

In short: fan-out multiplies both the tail and the failure probability by N, and the only escape that costs no extra work is the one your aggregation's algebra either permits or forbids.