Fan-out tail latency swimlanes (2D)

One lane per server: the request is only done when the slowest lane finishes. Watch stragglers set the finish line, and a delayed hedge cut them short.

Switch to 3D

Presets

Parameters

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 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.

What the 2D view adds

  • Each lane is one leaf server; the request ends at the right-most lane end (the maximum). Red lanes are stragglers, cyan bars are hedged duplicates sent after delay d.
  • The dashed vertical lines mark the exact p50 and p99 of the request time, so you can compare a single lucky or unlucky request with the distribution.

The rack, aggregator and packet sprites and the floor background are Blender 5.2 renders of the same models used in the 3D version; the random service times and requests are generated live in your browser on one shared maths module (tl_core.js).

Loading sprites...
CDF of the request time (max of N leaves)
p99 against fan-out N
Histogram of recent request times
Made with 🟠 Blender