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
Nindependent times, soP(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 is1 - (1-p)N, which is why the tail grows fast withN. - Without stragglers the mean is exactly
E[max] = μ HNwith the harmonic numberHN, andp99 = -μ 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. ThenSh(t) = S(t)fort < dandS(t) S(t-d)fort ≥ d. The extra load is the fraction of leaf calls that outlived, i.e.S(d).
Checks run in this page
- Monte Carlo: 40,000 simulated requests of
Nleaves 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/μ)Nreproducesμ 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
Nthe 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...