Tail latency

Orientation

Definition

Tail latency is the behavior of the slowest part of a latency distribution, usually p99, p99.9, and beyond. Tail amplification is what happens when a request depends on many components: a rare slow event in any of them becomes a common slow event for the whole request.

Why it matters

In a large system, the tail of one component becomes the median of the whole. If 1 leaf call in 100 is slow and a request waits for 100 leaves, then 63% of requests are slow. Those are not edge cases any more: they are what most of your users see. Tail latency also reveals conditions that averages hide, including garbage-collection pauses, lock contention, retries, background compaction, and noisy neighbors. Principal engineers need to know that tails often can't be engineered away component by component, so a system must be designed to tolerate them.

Prerequisites

P99 latency

Study time

About 2 hours, including the terminal lab and challenges. This is an estimate.

Related topics

Latency budgets and critical-path analysis, Benchmark design and coordinated omission (not yet written), Timeouts (not yet written), Latency, P99 latency, Garbage collection (not yet written), Packet loss, jitter, retransmission, and MTU problems (not yet written)

Learning objectives

• Calculate how fan-out and sequential depth amplify tail latency.
• Name the common causes of tail events, and how to tell them apart.
• Evaluate hedging, partial results, and tied requests, including their load and correctness costs.
• Explain why hedging fails when slowness is correlated.
• Set per-component tail targets from a whole-request goal.

Production scenario

A search service fans each query out to 100 index shards and waits for all of them. Every shard answers in about 10 ms, and it takes around 1,000 ms in 1% of calls, often during a background merge. The shard team reports, correctly, that shard p50 is 10 ms and that 99% of calls are fast. The search team reports, also correctly, that their median query takes 921 ms. Both are looking at the same 1%.

The team first tries to tune merges, which is slow and only partly works. They then send a hedge to another replica when a shard hasn't answered in 50 ms. Median query time falls from 921 ms to 59 ms, with only 1% extra leaf load. About 1.1% of queries are still slow, because sometimes both copies are unlucky. For those, the service stops at a deadline and returns results with a missing shard, marked as partial. Results are 99% complete on average and users rarely notice. These figures come from this lesson's simulation.

Mental model

Analogy

A dinner party of 100 guests can't start until everyone is seated. Each guest is on time 99% of the time. It sounds fine, but dinner starts late on 63% of evenings. You could not fix this by asking each guest to be slightly more punctual. What works is to not wait for all of them, or to invite a backup for anyone who's running late.

Where the analogy breaks

Guests are independent, but servers often aren't. A shared disk, an overloaded host, or a deployment makes many slow at once, and in that case a backup is just as late. Also, a backup guest costs little, whereas a hedge consumes real capacity, which is dangerous when the system is already overloaded. Finally, a dinner that starts without a guest is still a dinner, but a request that skips a shard might give a wrong answer, depending on what it does.

Entities, state, flow, and invariants

• Entities: the coordinator, leaf servers, replicas, in-flight copies, and deadlines.
• State: copies in flight, the remaining deadline, and the remaining hedge budget.
• Flow: fan out, wait, optionally hedge, take the first success, cancel losers, and merge.
• Invariant 1: a request waiting for all leaves is at least as slow as the slowest.
• Invariant 2: only idempotent, safe operations can be hedged. See Idempotency keys (not yet written).
• Invariant 3: extra copies are bounded by a budget, so that mitigation cannot create overload.

Foundations

Concepts and terminology

First-principles explanation

Waiting for all of k leaves takes the maximum of k values, and maxima are ruled by the tail. If each leaf is slow with probability p, a request avoids all slow leaves with probability (1 − p)^k. So as k grows, the chance of hitting at least one quickly approaches certainty. Depth has a similar effect, except sequential calls add rather than take the maximum.

Tails have many sources: resource sharing between tenants and between foreground and background work; queueing; garbage-collection pauses; TCP retransmission timeouts, which can add 200 ms or more; power and thermal throttling; lock contention; and cold caches after a deployment. Most are transient, and they happen at random to different machines, which is exactly why hedging works. Getting rid of every one of them is impractical, so systems tolerate them instead.

Hedging exploits independence. If 1% of calls are slow, and a second copy is independently slow 1% of the time, both are slow only 0.01% of the time. Crucially, hedges are only sent for calls still outstanding after the delay, so the extra load is about the probability of exceeding that delay.

Its limit is worth working through. With 100 leaves, each hedged leaf has a 0.01% chance of remaining slow, so 1 − 0.9999^100 ≈ 1% of requests still see a slow leaf. In this lesson's simulation, this leaves p95 at 62 ms and p99 at 850 ms. Hedging cut the slow fraction from 63% to 1.1%, but p99 sits right at that boundary, so it barely moved. Evaluate mitigations by the slow fraction as well as one percentile, or you may judge a big improvement as a failure.

Mathematics

Amplification: P(request slow) = 1 − (1 − p)^k.

Required leaf target: for request-level slow fraction r, p = 1 − (1 − r)^(1/k). For r = 1% and k = 100: 1 − 0.99^0.01 ≈ 0.01%. So each leaf must meet its target at p99.99 for the request to meet it at p99.

Hedged leaf: p′ = p² if independent. At p = 1%: p′ = 0.01%.

Hedge load: extra load ≈ P(call exceeds hedge delay). Hedging at the leaf's p95 adds about 5%.

Complexity

Fan-out to k leaves costs O(k) work per request and takes the maximum of k latencies. A hedge adds a constant factor of (1 + hedge rate). Tied requests add messages but little wasted work. The coordinator's merging is commonly O(k log k) or so. Reducing k, for example with index partitions that can be skipped, is often the highest-value change, as it improves both load and tail.

Mechanism

Normal path

1. The coordinator receives a request with a deadline.
2. It sends sub-requests to a replica of each needed shard.
3. It starts a hedge timer per sub-request, set near a high percentile of normal leaf latency.
4. If a leaf has not answered by the timer, and the budget allows it, it sends a copy to another replica.
5. The first success for each shard wins, and the other copy is cancelled.
6. At the deadline, the coordinator returns what it has, if partial results are acceptable, and marks the response.
7. Measurements feed back into which replicas to prefer and how to set the timer.

State transitions

stateDiagram-v2
    [*] --> Pending: first copy sent
    Pending --> Answered: reply received
    Pending --> Hedged: timer fires and budget available
    Pending --> WaitingNoBudget: timer fires and budget empty
    Hedged --> Answered: first reply wins, loser cancelled
    Pending --> Missing: deadline passes
    Hedged --> Missing: deadline passes
    WaitingNoBudget --> Answered: reply received
    WaitingNoBudget --> Missing: deadline passes
    Answered --> [*]
    Missing --> [*]

The WaitingNoBudget state is the safety valve. In an overload, slow calls become common, so an unbudgeted hedger would send copies for nearly every call and double the load at the worst moment. The budget turns this into an ordinary wait.

Concurrency behavior

Copies race, and the coordinator must handle a late answer after it has already moved on. Cancellation must propagate to actually save work, but many servers cannot stop an in-progress database query. Tied requests address this by queueing on two servers, with cross-cancellation when one begins. Concurrent hedges from many coordinators may converge on the same healthy replica, so choose replicas with care. See Deadlines and cancellation propagation (not yet written).

Ordering and consistency

Hedged reads may hit different replicas, which can return different versions. A later read can then see older data, violating monotonic reads. See Read-your-writes and monotonic-read guarantees (not yet written). Writes generally can't be hedged safely without idempotency, because both copies might succeed. Partial results change the semantics of a response, so a search may tolerate a missing shard while an account balance never may.

Ownership of data and control

The coordinator owns hedge policy, since it alone sees whole-request outcomes. Leaf teams own their leaf percentile targets, which should be derived from the whole-request goal. Product owns the decision about whether partial results are acceptable. Clients should know that a response was partial, for example through a response field.

Architecture

flowchart LR
    C["Client"] -->|"HTTPS, 500 ms deadline"| CO["Coordinator: owns hedge policy"]
    subgraph s1["Shard 1: owns index partition"]
      R1A["Replica A"]
      R1B["Replica B"]
    end
    subgraph s2["Shard 2: owns index partition"]
      R2A["Replica A: slow, merging"]
      R2B["Replica B"]
    end
    CO -->|"gRPC"| R1A
    CO -->|"gRPC"| R2A
    CO -.->|"hedge after 50 ms"| R2B
    CO -.->|"cancel"| R2A

Solid arrows are first attempts and dashed arrows are the hedge and its cancellation. Since a hedge requires a second copy of the data, replication already paid for for durability is what makes tail mitigation possible. Placing replicas in different zones also reduces correlation.

flowchart LR
    subgraph ts["TypeScript: hedged library"]
      F["hedged(call, options)"] --> T["Hedge timer"]
      T --> B["HedgeBudget: ratio and cap"]
      F --> AC["AbortController per copy"]
      AC --> W["First success resolves, losers aborted"]
    end
    subgraph py["Python: simulation"]
      L["Leaf model: fast or slow"] --> S1["fan_out"]
      L --> S2["hedged"]
      L --> S3["partial"]
      S1 --> O["Percentiles, slow fraction, load, completeness"]
      S2 --> O
      S3 --> O
    end

The TypeScript code is the mechanism and the Python code is the evaluation. The simulation's output includes extra load and completeness, as each mitigation has a price that a latency chart doesn't show.

sequenceDiagram
    participant C as Coordinator
    participant B as Hedge budget
    participant A1 as Replica A
    participant A2 as Replica B
    C->>A1: Search shard 2
    Note over A1: Stalled by a merge
    C->>B: Timer fired at 50 ms. Hedge allowed?
    B-->>C: Yes, one token used
    C->>A2: Same search
    A2-->>C: Result after 12 ms
    C->>A1: Cancel
    Note over C: Shard took 62 ms in place of 1,000 ms

The request's time is the hedge delay plus the second copy's time, so the delay sets the floor for rescued calls. Shorter delays rescue calls sooner but add load. Hence the common practice of setting the delay near the 95th percentile of normal latency.

flowchart TD
    A["Load rises, leaves slow down"] --> B["Most calls exceed the hedge delay"]
    B --> C{"Hedge budget in place?"}
    C -->|"no"| D["Traffic nearly doubles"]
    D --> E["Leaves slow further"]
    E --> B
    C -->|"yes"| F["Hedges capped at a small percentage"]
    F --> G["Load shedding handles the overload"]

Hedging assumes slowness is rare and independent, and overload breaks both of those assumptions. Without a budget, the tail mitigation becomes an amplifier, in much the same way as unbudgeted retries. See Retry budgets (not yet written).

Trade-offs

Advantages

• Tolerates causes that you don't control, such as hardware and neighbors.
• Very high return: in the simulation, 1% extra load cut slow requests from 63% to 1.1%.
• Partial results give a hard upper limit on latency.

Costs

• Hedging consumes capacity and needs idempotent operations and working cancellation.
• Different replicas can return different data versions.
• Partial results require product acceptance and client awareness.
• Added code paths are themselves a source of bugs, and they complicate debugging.

Alternatives

• Removing causes: isolate background work, tune garbage collection, and use dedicated resources. Worth doing, and limited by what you control.
• Reducing fan-out: skip shards that can't match, or use a two-tier index.
• Better load balancing: least-loaded or power-of-two-choices steers traffic away from slow servers.
• Ejecting slow instances: outlier detection removes persistently slow replicas.
• Overprovisioning: lowers queueing tail, at direct cost.

When to use it

When fan-out is high, reads are idempotent, replicas exist, slowness is transient and uncorrelated, and users value latency more than the small extra load.

When not to use it

Not for non-idempotent writes. Not for expensive requests where a hedge costs a lot. Not where cancellation doesn't work, as you'd pay for both copies. Not as a cover for a persistent problem, since a server that is always slow needs fixing or ejecting.

Reconsider when

• The hedge rate grows, since hedging may be hiding a real degradation.
• Slowness has become correlated, and hedges have stopped winning. Track the win rate.
• Fan-out changes, which changes the target percentile for each leaf.

Capacity planning

Inputs and assumptions

Fan-out to 100 shards at 500 queries per second. Each replica safely serves 300 requests per second. Hedge delay is set at about p95, so extra load is 5%. Three zones with one replica per zone at most.

Formula and units

• Per-shard load (requests per second) = queries per second × (1 + hedge rate), when each query touches each shard.
• Replicas per shard = per-shard load ÷ safe rate per replica ÷ (1 − headroom).
• Total leaf calls per second = queries per second × fan-out × (1 + hedge rate).

Intermediate calculations

• Per-shard load: 500 × 1.05 = 525 requests per second.
• Replicas at exact capacity: 525 ÷ 300 = 1.75.
• Total leaf calls: 500 × 100 × 1.05 = 52,500 per second.
• Hedges sent: 2,500 per second, charged to shared network and CPU.

Headroom

With 30% headroom: 525 ÷ 0.7 = 750 requests per second of capacity per shard, or 2.5 replicas, so 3. Tail latency is very sensitive to utilization, so tail-critical systems usually run with more headroom than the mean alone suggests. See Latency.

Failure capacity

With 3 replicas in 3 zones, losing a zone leaves 600 requests per second against 525 of load: 87.5% utilization, where tails grow quickly. To keep 750 after losing a zone needs 750 × 3 ÷ 2 = 1,125, or 4 replicas. In the failure state, also reduce the hedge budget, because extra load is costliest then.

Failure modes

Security and privacy

Threats

Attackers may cause tail events on purpose, such as sending costly queries that hit every shard, or crafting inputs that trigger worst-case behavior. Hedging then gives them amplification. Timing differences in tails can also reveal which shard holds data, or whether a record exists.

Trust boundaries

Decide hedging and fan-out inside your trust boundary. Never let a client request options that control the hedge count or width. Treat client-supplied deadlines as capped hints.

Authentication and authorization

Each copy of a request must carry the same authorization context. A hedge sent to another replica must not skip checks. Fan-out services should not hold broad credentials on behalf of every user if they can propagate an identity instead. See Workload identity (not yet written).

Tenant isolation

Tail events often come from noisy neighbors. Per-tenant concurrency limits and fair queueing shield others. Partial results must never mix one tenant's records into another's. Apply budgets per tenant, so one client's slow queries can't exhaust the hedge budget of everyone else.

Sensitive data

Hedging sends sensitive payloads to more servers, and cancelled copies may still be logged. Treat every replica the same way as far as logging and retention go. Partial results in authorization-related queries are dangerous: a missing shard in a "deny list" lookup must fail closed, not return "not found".

Abuse resistance

Limit fan-out for expensive query types, cap per-client concurrency, and reject requests whose estimated cost exceeds a threshold. Monitor for clients with unusually high hedge rates or partial-result rates.

Observability

Metrics

Track p50, p99, and p99.9 at the coordinator and per shard, slow-request fraction, hedge rate, hedge win rate, cancellation rate, budget exhaustion, partial-result rate, and average completeness. Export per-replica deviation from its group's median. See Metric cardinality and histogram design (not yet written).

Logs

For slow requests, log which shard was slowest and whether a hedge was sent. For partial results, log missing shards. Sample successful logs to control volume.

Traces

Tail-sampled traces are key here: capture traces for the slowest requests, because head sampling mostly misses them. Show hedges as sibling spans with a link and an attribute saying which won. See Trace sampling and context propagation (not yet written).

Dashboards

Show a heat map of leaf latency, a shard-by-time slowness grid, and hedge rate on one axis with win rate on another. A vertical line in a grid means correlated slowness in one shard, and a horizontal line means a time-based, fleet-wide event.

Alerts

Page on whole-request SLO burn. Send a ticket when the hedge rate is more than twice normal, when win rate falls below an agreed level, or when one replica deviates persistently. Rising hedge rates are an early warning that fast user latency is hiding degradation.

SLO examples

• 99% of search requests finish within 200 ms over 28 days.
• 99.9% of responses are at least 95% complete.
• Hedges stay under 5% of leaf calls for 99% of minutes.

Runbook actions

When tail latency rises: check whether it's one replica, one shard, or all. For one replica, eject it. For all, check utilization and hedge rate, set the budget to a low value if the system is overloaded, and shed load. Check recent deployments and background jobs such as merges and compaction.

Implementation

Architecture of the examples

TypeScript is a small hedged library with a demo: it manages copies, timers, cancellation, and a budget. Python is a seeded simulation comparing strategies across 20,000 requests, since a real cluster would be needed to do this with live traffic.

Data structures

hedged keeps a list of AbortControllers, one per copy. HedgeBudget is a token bucket that earns tokens per request rather than per second, so hedges are limited to a ratio of traffic. The Python Outcome reports percentiles plus over_100ms_pct, extra_load_pct, and mean_completeness_pct.

Interfaces

hedged(call, { hedgeAfterMs, maxCopies, budget }) returns { value, winner, copiesSent }. call receives an AbortSignal and a replica number, so any client can adopt it. Python exposes fan_out, hedged, partial, and the two prediction functions.

Error handling

A failed copy immediately triggers the next one, if allowed, since waiting would be pointless. If all copies fail, AllCopiesFailed carries every cause for diagnosis. Late results are ignored by a settled flag, so nothing can resolve twice.

Concurrency considerations

JavaScript's single thread means that no locking protects settled, though callbacks interleave at await points, which the flag handles. clearTimeout stops stale hedge timers. The test confirms that aborting fires on the loser. A multi-threaded language would need an atomic first-wins step and explicit goroutine or task cleanup.

Educational limitations

The simulation treats leaves as independent, which is the best case for hedging. There are no queues, so hedges don't slow anything down. Aborting in the demo only stops a local timer. Replica selection is simply by number.

Production hardening

Use proxy or client-library hedging where available, make it opt-in per method, track win rate, adapt the delay from recent latency, propagate deadlines and cancellation, avoid same-domain replicas, and test under overload.

Example source

// Hedged requests with cancellation. A second copy goes out if the first has not answered in time,
// the first success wins, and the loser is aborted so that it stops consuming server resources.
import { fileURLToPath } from 'node:url';

export type Call<T> = (signal: AbortSignal, replica: number) => Promise<T>;
export interface HedgeOptions { hedgeAfterMs: number; maxCopies: number; budget?: HedgeBudget }
export interface HedgeResult<T> { value: T; winner: number; copiesSent: number }

// Caps hedges at a fraction of requests, so hedging cannot multiply load during an overload.
export class HedgeBudget {
  private tokens = 0;
  private readonly ratio: number;
  private readonly capacity: number;
  constructor(ratio: number, capacity: number) { this.ratio = ratio; this.capacity = capacity; }
  onRequest(): void { this.tokens = Math.min(this.capacity, this.tokens + this.ratio); }
  tryHedge(): boolean {
    if (this.tokens < 1) return false;
    this.tokens -= 1;
    return true;
  }
}

export class AllCopiesFailed extends Error {
  readonly causes: unknown[];
  constructor(causes: unknown[]) { super(`All ${causes.length} copies failed.`); this.causes = causes; }
}

export function hedged<T>(call: Call<T>, opts: HedgeOptions): Promise<HedgeResult<T>> {
  if (opts.maxCopies < 1) throw new RangeError('maxCopies must be at least 1.');
  opts.budget?.onRequest();
  return new Promise<HedgeResult<T>>((resolve, reject) => {
    const controllers: AbortController[] = [];
    const failures: unknown[] = [];
    let settled = false;
    let inFlight = 0;
    let timer: ReturnType<typeof setTimeout> | undefined;

    const canSendMore = (): boolean => controllers.length < opts.maxCopies;
    const send = (): void => {
      const replica = controllers.length;
      const ctrl = new AbortController();
      controllers.push(ctrl);
      inFlight++;
      call(ctrl.signal, replica).then(
        (value) => {
          inFlight--;
          if (settled) return;
          settled = true;
          clearTimeout(timer);
          controllers.forEach((c, i) => { if (i !== replica) c.abort(); });
          resolve({ value, winner: replica, copiesSent: controllers.length });
        },
        (err: unknown) => {
          inFlight--;
          if (settled) return;
          failures.push(err);
          if (canSendMore()) { clearTimeout(timer); send(); schedule(); return; }
          if (inFlight === 0) { settled = true; clearTimeout(timer); reject(new AllCopiesFailed(failures)); }
        },
      );
    };
    const schedule = (): void => {
      if (!canSendMore()) return;
      timer = setTimeout(() => {
        if (settled || !canSendMore()) return;
        if (opts.budget && !opts.budget.tryHedge()) return;
        send();
        schedule();
      }, opts.hedgeAfterMs);
    };
    send();
    schedule();
  });
}

const sleep = (ms: number, signal: AbortSignal): Promise<void> => new Promise((resolve, reject) => {
  const t = setTimeout(resolve, ms);
  signal.addEventListener('abort', () => { clearTimeout(t); reject(new Error('aborted')); }, { once: true });
});

async function demo(): Promise<void> {
  const delays = [500, 20]; // the first replica is stuck, and the second is healthy
  let cancelled = 0;
  const call: Call<string> = async (signal, replica) => {
    try {
      await sleep(delays[replica] ?? 20, signal);
      return `answer from replica ${replica}`;
    } catch (err) { cancelled++; throw err; }
  };
  const start = performance.now();
  const r = await hedged(call, { hedgeAfterMs: 50, maxCopies: 2 });
  await new Promise((resolve) => { setImmediate(resolve); });
  console.log(JSON.stringify({ level: 'info', msg: 'hedge.done', ...r, cancelled, elapsedMs: Math.round(performance.now() - start) }));
}

if (process.argv[1] === fileURLToPath(import.meta.url)) {
  demo().catch((err: unknown) => {
    console.error(JSON.stringify({ level: 'error', msg: 'hedge.failed', error: String(err) }));
    process.exitCode = 1;
  });
}

"""Seeded simulation of tail amplification and three mitigations.

Each leaf server is usually fast and occasionally very slow. A request fans out to many leaves and
waits for all of them, so one slow leaf delays the whole request. Hedging sends a second copy after
a short delay, and partial results return at a deadline with some answers missing.
"""

from __future__ import annotations

import json
import math
import random

from pydantic import BaseModel, Field


class Leaf(BaseModel):
    fast_ms: float = Field(default=10, gt=0)
    slow_ms: float = Field(default=1_000, gt=0)
    slow_probability: float = Field(default=0.01, ge=0, le=1)


class Outcome(BaseModel):
    name: str
    p50_ms: float
    p95_ms: float
    p99_ms: float
    p999_ms: float
    over_100ms_pct: float
    extra_load_pct: float = 0.0
    mean_completeness_pct: float = 100.0


def leaf_time(rng: random.Random, leaf: Leaf) -> float:
    base = leaf.slow_ms if rng.random() < leaf.slow_probability else leaf.fast_ms
    return base * rng.uniform(0.8, 1.2)


def pct(values: list[float], q: float) -> float:
    ordered = sorted(values)
    return round(ordered[math.ceil(q * len(ordered)) - 1], 1)


def summarize(name: str, totals: list[float], extra: float = 0.0, complete: float = 100.0) -> Outcome:
    over = 100 * sum(1 for t in totals if t > 100) / len(totals)
    return Outcome(name=name, p50_ms=pct(totals, 0.5), p95_ms=pct(totals, 0.95), p99_ms=pct(totals, 0.99),
                   p999_ms=pct(totals, 0.999), over_100ms_pct=round(over, 2),
                   extra_load_pct=round(extra, 1), mean_completeness_pct=round(complete, 2))


def fan_out(requests: int, width: int, leaf: Leaf, seed: int = 1) -> Outcome:
    rng = random.Random(seed)
    totals = [max(leaf_time(rng, leaf) for _ in range(width)) for _ in range(requests)]
    return summarize(f"fan-out {width}", totals)


def hedged_leaf(rng: random.Random, leaf: Leaf, hedge_after_ms: float) -> tuple[float, bool]:
    """Returns finish time and whether a second copy was sent."""
    first = leaf_time(rng, leaf)
    if first <= hedge_after_ms:
        return first, False
    return min(first, hedge_after_ms + leaf_time(rng, leaf)), True


def hedged(requests: int, width: int, leaf: Leaf, hedge_after_ms: float, seed: int = 1) -> Outcome:
    rng = random.Random(seed)
    totals: list[float] = []
    sent = 0
    for _ in range(requests):
        results = [hedged_leaf(rng, leaf, hedge_after_ms) for _ in range(width)]
        sent += sum(1 for _, h in results if h)
        totals.append(max(t for t, _ in results))
    return summarize(f"fan-out {width}, hedge at {hedge_after_ms:g} ms", totals, 100 * sent / (requests * width))


def partial(requests: int, width: int, leaf: Leaf, deadline_ms: float, seed: int = 1) -> Outcome:
    rng = random.Random(seed)
    totals: list[float] = []
    answered = 0
    for _ in range(requests):
        times = [leaf_time(rng, leaf) for _ in range(width)]
        answered += sum(1 for t in times if t <= deadline_ms)
        totals.append(min(max(times), deadline_ms))
    return summarize(f"fan-out {width}, partial at {deadline_ms:g} ms", totals, 0.0, 100 * answered / (requests * width))


def predicted_slow_fraction(width: int, slow_probability: float) -> float:
    return 1 - (1 - slow_probability) ** width


def predicted_hedged_slow_fraction(width: int, slow_probability: float) -> float:
    # A hedged leaf is slow only if both copies are, assuming independent copies.
    return predicted_slow_fraction(width, slow_probability**2)


def main() -> int:
    leaf = Leaf()
    n = 20_000
    rows = [fan_out(n, w, leaf) for w in (1, 10, 100)]
    rows += [hedged(n, 100, leaf, 15), hedged(n, 100, leaf, 50), partial(n, 100, leaf, 50)]
    print(json.dumps({
        "predicted_slow_fraction": {str(w): round(predicted_slow_fraction(w, 0.01), 3) for w in (1, 10, 100)},
        "predicted_hedged_slow_fraction_100": round(predicted_hedged_slow_fraction(100, 0.01), 4),
        "results": [r.model_dump() for r in rows],
    }, indent=2))
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

Terminal lab

Setup

cd topics/tail-latency/examples/python
uv sync --quiet

Run

uv run python -m app.main | jq -c '.predicted_slow_fraction, (.results[] | {name,p50_ms,p95_ms,p99_ms,over_100ms_pct,extra_load_pct,mean_completeness_pct})'

Then see a hedge in action:

cd ../typescript && pnpm install --ignore-workspace --silent && pnpm --silent start

Test

cd ../python && uv run pytest -q

cd ../typescript && pnpm test

Expected output

Seeded results, measured on the review date:

{"1":0.01,"10":0.096,"100":0.634}
{"name":"fan-out 1","p50_ms":10.0,"p95_ms":11.8,"p99_ms":817.1,"over_100ms_pct":1.07,"extra_load_pct":0.0,"mean_completeness_pct":100.0}
{"name":"fan-out 10","p50_ms":11.8,"p95_ms":989.7,"p99_ms":1155.6,"over_100ms_pct":9.51,"extra_load_pct":0.0,"mean_completeness_pct":100.0}
{"name":"fan-out 100","p50_ms":921.3,"p95_ms":1179.2,"p99_ms":1195.8,"over_100ms_pct":63.13,"extra_load_pct":0.0,"mean_completeness_pct":100.0}
{"name":"fan-out 100, hedge at 15 ms","p50_ms":24.2,"p95_ms":26.8,"p99_ms":826.5,"over_100ms_pct":1.12,"extra_load_pct":1.0,"mean_completeness_pct":100.0}
{"name":"fan-out 100, hedge at 50 ms","p50_ms":59.2,"p95_ms":61.8,"p99_ms":849.7,"over_100ms_pct":1.12,"extra_load_pct":1.0,"mean_completeness_pct":100.0}
{"name":"fan-out 100, partial at 50 ms","p50_ms":50.0,"p95_ms":50.0,"p99_ms":50.0,"over_100ms_pct":0.0,"extra_load_pct":0.0,"mean_completeness_pct":99.0}

Observed slow fractions match the formula: 1.07%, 9.51%, and 63.13% against predictions of 1%, 9.6%, and 63.4%. Hedging leaves p99 high since about 1.1% of requests still see both copies slow, which is exactly the 1% predicted. Check p95 and the slow fraction to see its real benefit. The hedging demo prints "winner":1, "copiesSent":2, "cancelled":1, and takes about 70 ms, not 500 ms.

Cleanup

rm -rf .venv ../typescript/node_modules

Troubleshooting

• The demo's elapsedMs varies by a few milliseconds due to timer resolution.
• The results match exactly only with the same seed and a compatible Python random generator.

Practical challenges

Industry standards and trends

Standards and specifications

There's no formal standard for tail mitigation. The gRPC retry and hedging design, a project proposal, defines hedging policy and throttling, including the idempotency caveat. RFC 9293, August 2022, defines TCP, whose retransmission timeouts are a common cause of tail events.

Established practice

The Tail at Scale, Dean and Barroso, Communications of the ACM, 2013, introduced much of the vocabulary here, including hedged and tied requests. Findings there are specific to the systems studied, so measure your own. Envoy's HTTP routing documentation describes proxy-level hedging. Outlier ejection and least-request load balancing are also established proxy features.

Managed-service options

Service meshes and some cloud load balancers support outlier detection, and some support hedging. Managed databases offer read replicas, which may or may not allow hedged reads. Check how each charges, since duplicate requests can double the bill.

Emerging approaches

Low-pause garbage collectors, such as ZGC, reduce one common cause. LLM inference has a distinct tail problem, where a single long request can occupy a GPU batch slot, so hedging is costly and admission control matters more. This last point is an inference from public systems, without a settled practice.

Recent changes

No significant standards change was identified at the review date. gRPC hedging support differs across language implementations, so check yours.

Adoption constraints

Hedging needs idempotent operations, replicas, and working cancellation. Metered or per-request-priced dependencies make duplicates directly costly. Measure the win rate before rolling out widely.

Links in this section were checked on 2026-11-03 (access date). Items labelled as emerging or inferred are not settled facts and should be re-checked before you rely on them.

Interview preparation

Review

Key takeaways

• P(request slow) = 1 − (1 − p)^k, so fan-out turns rare into common.
• Tails come from sharing, pauses, retransmits, and background work, and can't be removed entirely.
• Hedging exploits independence, at a small load cost.
• Budget hedges, since overload breaks their assumptions.
• Judge mitigations using slow fraction and multiple percentiles, not just p99.
• Partial results bound latency, where a missing piece doesn't break correctness.

Decision checklist

• What is the fan-out, and what does it require from each leaf?
• Are slow events independent across replicas?
• Is the operation idempotent?
• Does cancellation reach the server?
• Is a partial result acceptable to the product?

Production-readiness checklist

• Hedges are opt-in per method, and budgeted.
• Hedge rate and win rate are monitored.
• Per-replica outliers are detected and ejected.
• Background work is isolated and staggered.
• Slow requests get tail-sampled traces.

Glossary

• Tail amplification: rare slowness turning common through fan-out.
• Hedged request: a delayed duplicate, where the first answer wins.
• Tied request: duplicates that cancel each other when one starts work.
• Win rate: the share of hedges finishing before the original.
• Tail sampling: deciding to keep a trace after seeing its outcome.
• Outlier ejection: removing an unusually slow or failing instance from rotation.

Quiz

Further study

Continue with Latency budgets and critical-path analysis to allocate time across a request, Deadlines and cancellation propagation (not yet written) to propagate deadlines, and Retry budgets (not yet written) for budgeting extra load. Graceful degradation and brownouts (not yet written) extends partial results into a general approach to degradation.

Progress

Progress is stored only in this browser. Export it from the curriculum page.