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