Search tools and guides ⌘K
IV · Queueing theory

Tail latency

What it is

For fan-out queries, system latency is dominated by the slowest of N parallel requests. p99 of one becomes p50 of 100.

Where it lives

Microservice composition, every search index, MapReduce stragglers.

The key insight

Hedged requests (fire two, take the first) cut tail latency at modest extra cost — Dean & Barroso 2013.

More in Queueing theory
Little's law L = λW. Average number in system = arrival rate × average time in syst… M/M/1 queue Single server, Poisson arrivals (rate λ), exponential service (rate μ)… Universal scalability law C(N) = N / (1 + α(N−1) + βN(N−1)). Throughput as a function of concurr…
Across the foundations
V Amdahl's law Physics & hardware limits VI One-way functions Cryptographic foundations VI Discrete log Cryptographic foundations VI Birthday attack Cryptographic foundations VI AEAD Cryptographic foundations VII P vs NP Computational complexity VII NP-completeness Computational complexity VII Approximation algorithms Computational complexity
← All foundations