Fan-out tail latency and hedged requests (3D)

A request that waits for N servers is as slow as the slowest one. See how rare stragglers dominate p99 and how a delayed duplicate request cuts the tail.

Parameters

Camera

Quality

Model checks

The science

What is modelled

An aggregator sends one request to N leaf servers and waits for all answers (scatter-gather, as in search or a model-serving fan-out). Each leaf takes an independent random service time: exponential with mean μ, but with probability p it is a straggler whose mean is kμ (garbage collection, a busy disk, a noisy neighbour).

Equations

  • Leaf survival function: S(t) = (1-p) e-t/μ + p e-t/(kμ).
  • The request finishes at the maximum of N independent times, so P(T ≤ t) = (1 - S(t))N. The p99 solves (1 - S(t))N = 0.99; the chance that at least one leaf is a straggler is 1 - (1-p)N, which is why the tail grows fast with N.
  • Without stragglers the mean is exactly E[max] = μ HN with the harmonic number HN, and p99 = -μ ln(1 - 0.991/N).
  • Hedging: if a leaf has not answered after delay d, the same request is sent to a second replica and the first answer wins. Then Sh(t) = S(t) for t < d and S(t) S(t-d) for t ≥ d. The extra load is the fraction of leaf calls that outlive d, i.e. S(d).

Checks run in this page

  • Monte Carlo: 40,000 simulated requests of N leaves each give the empirical p50 and p99, compared with the exact quantiles of (1 - Sh)N (p50 within 2 %, p99 within 4 %).
  • Harmonic number: numerical integration of 1 - (1 - e-t/μ)N reproduces μ HN (within 0.2 %).
  • Hedge load or closed-form p99: with hedging on, the measured fraction of hedged leaf calls equals S(d); with hedging off, the numerical p99 of the straggler-free model equals -μ ln(1 - 0.991/N).

Honest simplifications

  • Service times are independent and memoryless. Real latency distributions are heavier-tailed, correlated between leaves, and depend on load: hedging adds load, which can itself increase latency (not modelled here).
  • Network transit and queueing delays are zero; the packets in the 3D view take a fixed animation time that is not counted in the latency.
  • The backup replica is assumed idle and statistically identical. Cancelling the losing request is free.
  • At most 24 racks are drawn; for larger N the extra leaves are still sampled (they decide the request time) but have no picture.

The racks, aggregator, packets and baked floor texture are Blender-built; the random service times and queue of requests are generated live in your browser.

Loading model...
Loading Blender model...
CDF of request latency (ms): exact vs Monte Carlo
p99 against fan-out N: no hedge vs hedge
Live latencies of recent requests (ms)
Made with 🟠 Blender · Three.js