Fan-out tails

# Things to try

• Under Wait for all, slide the workers from 1 to 16. No task gets any slower, yet the job’s exact p50 goes from 1.00 s to 2.81 s, and the last readout climbs to 14.9%: about one job in seven waits on a task from the slowest 1%.
• Switch to First k of N, which needs 5 of 8 answers. The three stragglers are cancelled before they finish, and the job’s exact p99 falls from 6.13 s to 2.02 s.
• Choose Hedge after p95 and press Run ×1,000 a few times. About 5% of tasks get a copy. The median stays put, because it sits below the 2.68 s hedge point, while the exact p99 drops from 6.13 s to 4.40 s. The simulated p99 wobbles from batch to batch, because only ten runs in a thousand decide it.

# How it works

A job sends one task to each of N workers and waits for the answers. Each task’s time is drawn from a log-normal distribution with a median of 1 second; sigma sets how long the tail is. Waiting for all of them means the job takes as long as its slowest task, and the slowest of many draws usually comes from the tail.

One number explains most of it. If each task is slower than its own p99 one time in a hundred, the chance that at least one of N is that slow is 1 - 0.99^N: 7.7% for 8 workers, 14.9% for 16. Jeffrey Dean and Luiz André Barroso use 100 servers in The Tail at Scale (Communications of the ACM 56(2), 2013); there the same formula gives 63.4%. Rare slowness on one machine becomes common slowness for the request.

The other two strategies are among the paper’s remedies. Taking the first k answers only works when partial results are good enough; then the job stops waiting for stragglers. A hedged request sends a second copy of any task still outstanding at the 95th-percentile latency and keeps whichever answer arrives first, for about 5% more work.

Every run draws the same sixteen task times for a given seed, so switching strategy replays the same tasks. The exact readouts solve each strategy’s distribution directly; the others come from 1,000 simulated runs, computed in small pieces while the page is idle.

# Keyboard