Scatter Gather

Scatter Gather

Purpose

For all-of-N, root latency includes the maximum of the required leaf completion times plus scatter/gather overhead. First-success and k-of-N use order statistics and can return earlier; quorum/partial semantics decide whether that answer is correct. At N = 100 with independent, identically distributed leaves, roughly 63% of root requests contain at least one leaf beyond its own p99. The arithmetic is tail-latency-analysis; the consequence is this skill's whole subject.

The failure this prevents is the optimisation that reverses: work is split across more leaves so each leaf does less, every leaf's p99 improves, and the user-facing p99 gets worse. No leaf dashboard shows it, because no leaf is at fault. The second failure is the fan-out that costs N units of work for one answer — the gather is satisfied, the root replies, and the losing leaves keep running with their connections held.

Compatibility and evidence

Inspect deployed Java/client versions, existing execution model and the caller's consistency contract before changing fan-out. The Java sketch targets Java 21+ without preview; preserve older supported executors/frameworks when appropriate rather than upgrading implicitly. Missing joint traces, ownership epochs or cancellation evidence leave the corresponding latency/correctness claim unverified. Report the completion rule, bounded work/bytes, deadline allocation, actual evidence and the validation still needed.

Workflow

1. State the completion rule before writing any code. All-of-N (the answer needs every leaf), first-success (first acceptable equivalent answer), or k acceptable distinct owners by deadline. Define insufficient-k behavior separately; an error completing first is not a successful winner. Every other decision below follows from this one.
2. Choose N, and record why. N is a trade between per-leaf work and tail exposure, not a free parameter. "One leaf per shard" is a default inherited from the data layout, not a decision — see references/tail-amplification-and-hedging.md.
3. Derive every leaf cutoff from one root deadline, reserving time for cancellation bookkeeping, merge/serialization/return. Start a leaf only when its probability/value of completing within remaining budget justifies the work; p50 is not a universal cutoff (timeouts-and-deadlines).
4. Bound fan-out across concurrent roots as well as within each request. Limit admission, waiting tasks, response bytes and active leaf work. Virtual threads still retain memory; a semaphore caps holders, not its waiter population (concurrency-limiting-and-bulkheads).
5. Signal cancellation to losers when the gather is satisfied, and verify root tasks plus remote work release resources. Cancellation may be advisory and cannot undo a committed effect; budget residual work even after reply.
6. Decide the partial/quorum-result contract with the caller. Include expected/responded/ missing owners, errors, data/version watermark and whether aggregation is exact, lower/ upper-bounded or stale (rpc-and-api-contracts).
7. Only then consider hedging, with operation safety, replica independence/consistency, rate/capacity budget and cancellability measured.

Decision block

Use scatter/gather when:
- the answer genuinely requires data from several owners, each holding a disjoint slice
  (sharding-and-partitioning), and it must be current as of this request
- N and total work are bounded by an admission budget; hierarchical/dynamic fan-out has a
  global descendant cap rather than recursively multiplying unchecked
- root latency is derived from measured joint/order-statistic behavior, not one leaf percentile
- the caller's contract can express a partial answer, or all-of-N genuinely fits the budget
Avoid scatter/gather when:
- the leaves share a saturated resource — one database, one pool, one node — so the fan-out
  is concurrency against itself rather than parallelism
- N grows with data volume: latency then degrades as the workload succeeds
- the request writes and requires atomic all-or-nothing visibility without a commit protocol.
  Fan-out writes can be valid for replicated/quorum or idempotent broadcast semantics, but
  scatter/gather alone is not a transaction (`distributed-transactions-and-sagas`)
- the measured all-of-N tail plus dispatch/merge cost does not fit the root target;
  a leaf p99 alone cannot prove a breach for every request or for first-success
Prefer instead:
- an index or denormalised view keyed by the query, so one owner answers it
  (sharding-and-partitioning) — this is the fix for a query that always fans out
- caching the gathered result when the inputs change more slowly than they are read
  (caching-strategies)
- a precomputed aggregate maintained out of band when the answer need not be per-request
  (distributed-aggregation-and-barriers)

Rules

• Never quote a leaf's p99 as the root's SLO. Derive each leaf's budget backwards from the root's, using the fan-out amplification in tail-latency-analysis.
• Raising N may reduce divisible data work, but fixed setup, skew, duplicate work and shared bottlenecks prevent linear scaling. For all-of-N it increases exposure to any slow leaf; correlation determines how much. Find the crossover at the root with realistic placement.
• The coordinator/root is a failure and capacity domain unless replicated/stateless. Under all-of-N, independent required leaves with aligned success definitions multiply to about 98% at N=20 and 99.9% each; real correlation requires joint measurement. k-of-N availability follows a binomial model only for independent identical leaves, while quorum correctness has separate consistency assumptions.
• A partial result must carry an explicit completeness field naming the missing owners. A list of 8 elements is indistinguishable from 8 shards that had no data, and a caller that cannot tell will cache the wrong answer or show it as authoritative.
• Each leaf timeout is bounded by the remaining leaf cutoff; a smaller dependency-specific timeout may also apply. Include queue/admission time. An early dependency timeout is valid, but a fresh timeout must not extend the root deadline.
• Java Future.cancel(true) attempts interruption; CompletableFuture.cancel does not guarantee interrupting supplier execution, and remote cancellation depends on protocol/ client. A cancelled handle proves only local state. Assert remote in-flight/resource release.
• Hedging requires all of these: equivalent/read-only or downstream-idempotent operation; an independent eligible replica with acceptable consistency; remaining deadline; global hedge/concurrency budget; and cheap cancellation/residual-work accounting. An uncapped hedge fires most often exactly when the dependency is already slow, which makes it a load multiplier at the worst moment.
• Prefer a different failure domain than the original after a conditional latency trigger. A different replica sharing the same shard/database may add only load, and a stale replica may not be semantically equivalent. Trigger placement is tail-latency-analysis.
• A retry inside a leaf multiplies the whole fan-out: N leaves at 3 attempts is 3N calls inside one root budget, and the budget arithmetic must include it (retries-and-backoff).
• Scatter/gather scales worse than it looks. Adding leaves adds tail exposure and root fan-out cost; it converts a capacity problem into a latency-variance problem. Say that in the design review rather than discovering it at N = 50.
• Java: the production shape is Executors.newVirtualThreadPerTaskExecutor() in a lifecycle-managed virtual-thread executor (Java 21+) plus completion/cancellation tracking, or a framework client with equivalent lifecycle. A per-call try-with-resources executor can block in close() until uncooperative tasks terminate, defeating the response deadline. StructuredTaskScope expresses ownership better but remains preview through JDK 26 (JEP 525), requiring preview flags/recompilation; structured-concurrency owns the version matrix.

References

• Tail amplification and hedging — the max-of-N consequence with the N table, how to choose N and where the crossover sits, the hedging eligibility conditions and admission caps, backup-request placement, and the series that show whether hedging is helping or adding load. Read before changing N, and before enabling any hedge or backup request.
• Fan-out in Java — a virtual-thread executor fan-out under a propagated deadline, per-leaf timeouts derived from the remaining budget, cancellation of outstanding leaves and the close() trap behind it, partial-result assembly with completeness/watermark fields, and tests distinguishing local cancellation from residual remote work. Read when implementing or reviewing a fan-out.