Step 2 of 13 · 1 min

Where the tail comes from

The tail is the slow end of the latency distribution: the p99, p99.9, and beyond. When the team traced a sample of slow home feed requests (lesson 6.4 covers tracing), they found no single cause. They found many small ones, each rare:

• Garbage-collection pauses. Services written in languages with automatic memory management occasionally pause for tens or hundreds of milliseconds to clean up memory.
• Queueing. A brief burst of requests lands on one server at once, and the last ones wait (lesson 2.1's queueing table).
• Background work. A database's vacuum or compaction (lesson 3.2), a log rotation, a backup, a cache refreshing a big entry, all briefly competing for the same disk and CPU.
• Noisy neighbours. Other workloads on the same physical machine, in a cloud or a shared cluster, using the CPU, cache or network at the same moment.
• Cache misses. Most reads hit the cache (lesson 2.4); a few go to the database and take ten times longer.
• Network hiccups. A lost packet makes TCP wait before resending. On Linux, that wait is at least 200 ms by default, so a single dropped packet turns a 1 ms call into a 200 ms one.

Each of these affects any single call only rarely. The problem is how many calls one request makes.

Step 3 of 13 · 1 min

Fan-out turns rare into common

A Chirp home feed request wasn't one call. Building it touched the feed cache, then fetched post details from several shards (lesson 5.1), author profiles, like counts, and a couple of smaller services. Around 40 internal calls, many in parallel, and the page waited for all of them.

Lesson 1.2 introduced the arithmetic, and lesson 5.1 used it for scatter-gather. If each call is slow (say, over 100 ms) just 1% of the time:

chance at least one of 40 calls is slow = 1 − 0.99⁴⁰ ≈ 33%

So a third of home feed loads include at least one slow call. Since the page waits for the slowest, the page's p99 ends up driven by its components' p99.9 and beyond. Every service can look healthy on its own dashboard ("our p99 is 20 ms!") while the page they serve together is slow.

This is the central insight of a well-known 2013 paper by Jeffrey Dean and Luiz André Barroso, The Tail at Scale: in large systems that fan out, you can't make the tail go away by making each part reliable enough. Rare slowness is unavoidable at scale. You have to design the system to tolerate it.

Step 4 of 13 · 1 min

Measure it properly first

Before fixing a tail, you need to see it accurately, and several common measuring habits hide it.

Averages hide it. Lesson 1.2's point: Chirp's 110 ms average blended a million fast requests with a few slow ones, and looked fine.

Percentiles can't be averaged. Chirp's first p99 dashboard averaged each server's p99 together. That number is meaningless. Suppose nine servers have a p99 of 50 ms and one has a p99 of 2 seconds. The average of the p99s is about 250 ms, but the fleet's real p99 depends on how many slow requests there are in total, which this calculation can't know. To get a correct fleet-wide percentile, you need the underlying distribution: each server records a histogram (counts of requests in latency buckets, such as 0–1 ms, 1–2 ms, 2–4 ms…), the histograms are added together, and the percentile is read from the combined histogram. Most monitoring systems support this, as long as you record histograms rather than pre-computed percentiles.

Load tests can hide it too. A common mistake in benchmarking tools: send a request, wait for the response, then send the next. When the system stalls for a second, the tool stops sending during the stall, so it records one slow request instead of the hundreds that real users would have sent and waited on during that second. This is called coordinated omission, and it can make a system's tail look many times better than it really is. Good load-testing tools send requests on a fixed schedule regardless of how long responses take.

Step 5 of 13 · 1 min

Hedged requests

The most effective tail-taming trick in the Tail at Scale paper is surprisingly simple.

If a request to one replica is taking unusually long, send the same request to a second replica, and use whichever answer comes back first. The slow replica was probably in a garbage-collection pause or a burst of queueing. The second one probably isn't. This is a hedged request.

The trick is in when to send the second request:

• Send it immediately, to every request, and you double the load, which makes everything slower.
• Send it only after the first request has been waiting longer than the 95th percentile of normal latency. Then only about 5% of requests get a second copy, adding about 5% load, but those are exactly the requests that were heading for the tail.

The paper's example, from Google's Bigtable: hedging after the 95th-percentile wait cut the 99.9th-percentile latency of a 1,000-key read from about 1,800 ms to 74 ms, while sending only about 2% more requests.

A refinement, also from the paper, is the tied request: send to two replicas at once, but tell each about the other, so that whichever starts working on it first tells the other to cancel. That gets most of the benefit with even less duplicated work, at the cost of more complexity.

Hedging only works for requests that are safe to send twice: reads, or writes with idempotency keys (lesson 1.5). And it needs a budget, like retries in lesson 6.1, so that when everything is slow, hedging doesn't double the load on a system that's already overloaded.

Chirp added hedging to post-detail and profile lookups from the cache and the database replicas. The home feed's p99 dropped from 1.8 seconds to 400 ms the week it shipped, for about 4% more read traffic.

Step 6 of 13 · 1 min

Other ways to shrink the tail

Hedging attacks slowness after it happens. Several design choices reduce how much there is to begin with.

Make fewer calls. Every call added to a request adds another chance of hitting a slow one. Chirp combined several small lookups (like counts, "have I liked this," author profile) into fewer, batched calls (lesson 1.2's lesson, again). Going from 40 calls to 15 cut the chance of any slow call by more than half before any other change.

Split work into smaller pieces. If each shard holds a smaller piece of data, a slow shard affects fewer requests, and its work can be moved elsewhere faster. Many systems deliberately use far more partitions than machines (lesson 5.2's logical shards) partly for this reason.

Keep slow machines out of rotation. If one server is consistently slower than its peers, stop sending it traffic for a while, even though it isn't failing. That's lesson 2.2's outlier detection, applied to latency rather than errors. The paper calls it latency-induced probation.

Move background work away from busy times, or off the request path. Run compaction, vacuum and backups at quiet hours, or throttle them. Use memory and garbage-collection settings that favour short pauses for latency-sensitive services.

Return a good-enough answer. For some requests, a slightly incomplete answer, delivered on time, is better than a complete one delivered late. A search that has heard from 47 of 48 shards after its deadline can return results from the 47, which are very likely nearly the same. Chirp's home feed did this for optional pieces: if like counts weren't back by the deadline, posts were shown without them, and the counts filled in a moment later. (That's lesson 6.1's graceful degradation, applied to slowness rather than failure.)

Step 7 of 13 · 1 min

From the real world: a spike every two minutes

Discord's post "Why Discord is switching from Go to Rust" (2020) is a neat, measurable example of a tail-latency source that has nothing to do with load.

Discord's Read States service tracks, for every user and every channel, which messages that user has read. It's called on every connection, every message sent and every message read, so it's on the hot path for almost everything. Each instance kept a large in-memory cache of recent read states, tens of millions of entries, in front of Cassandra.

The service was written in Go, and its latency graph had a spike every two minutes, like clockwork, along with a burst of CPU. The cause was Go's garbage collector. Go forces a collection at least every two minutes, even if little garbage has been produced, and each collection had to scan the entire live cache to find out what was still in use. The cache was the problem precisely because it was large and long-lived. Tuning the collector didn't help, because the issue was the size of live memory, not the amount of garbage.

Discord rewrote the service in Rust, which manages memory without a garbage collector. The spikes disappeared, and because memory was no longer a latency risk, they could make the cache bigger (8 million read states per instance), which also reduced database reads. Average latency moved to microseconds.

You don't need to rewrite services to take the lesson:

• Look for periodic spikes, and correlate them with GC logs, cron jobs, compactions, cache expiry times and log rotation. Regular patterns have mechanical causes.
• Large, long-lived heaps in garbage-collected runtimes are tail-latency risks. Options: keep the cache smaller, move it off the heap or out of the process (a local Redis), use a collector designed for big heaps (Java's ZGC or Shenandoah), or, for a few critical services, use a runtime without a collector.

Step 8 of 13 · 1 min

Going deeper: tied requests

Hedged requests, earlier in this lesson, wait for the 95th-percentile time before sending a second copy. That caps the extra load at about 5%, but it means the slowest requests always wait at least that long before help arrives. "The Tail at Scale" describes a refinement used inside Google: tied requests.

The client sends the request to two replicas immediately, and each copy carries the identity of the other replica. Requests wait in each server's queue. Whichever server starts working on it first sends a cancellation to the other. Since most requests spend most of their slow time waiting in a queue rather than being processed, the losing copy is almost always cancelled before it uses any real resources.

The result is close to "always use the replica with the shorter queue," without knowing queue lengths in advance, and without waiting for a p95 timer. Two details make it work:

• A small delay between the two sends (about the network round-trip time) makes it unlikely both servers are idle and start the request at the same moment, which would do the work twice.
• Servers must support cancellation of queued work, and must check for it cheaply. That's a server feature, not just a client trick, which is why tied requests are more common inside storage systems (Google described their use in BigTable and its file system) than between ordinary microservices.

For Chirp, hedging remains the practical tool between services. Tied requests are worth knowing for interviews, and for when you're building the storage layer itself.

Step 9 of 13 · 1 min

What Chirp changed

• Dashboards show p50, p99 and p99.9 for every user-facing endpoint, built from combined histograms, never averaged percentiles.
• Latency targets were set for whole pages, not just individual services, so a service's tail is judged by its effect on the pages that use it.
• Hedged requests for reads from caches and database replicas, triggered after the 95th-percentile wait, within a 5% budget.
• Home feed calls cut from about 40 to 15 by batching.
• Latency outlier detection: servers whose p99 stays well above their peers' are taken out of rotation for a few minutes.
• Optional parts of pages are dropped if they miss the deadline, and filled in later.
• Load tests send requests on a fixed schedule, to avoid coordinated omission.

The heaviest users' complaints about "hanging" mostly stopped. The next round of interviews found new things to complain about, which the product team took as a good sign.

Step 10 of 13 · 1 min

In the simulation

Stage 5's dashboard reports page-level p50 and p99, and lets you add hedging, batch calls, and degrade optional components. Watch how changing a single service's tail shows up in the page's tail, and how much extra load hedging costs when it's set too eagerly.

Open the simulation →

Step 11 of 13 · 1 min

If you're here for an interview

Tail latency comes up whenever a design fans out to many services or shards. Strong answers:

• Talk in percentiles, and explain why fan-out makes the page's tail worse than any component's.
• Know the arithmetic: 1 − (1 − p)ⁿ for the chance that at least one of n calls is slow.
• Propose hedged requests with a sensible trigger (after the p95 wait) and a budget, and note they need idempotent operations.
• Mention design-level fixes: fewer calls, smaller partitions, partial results within a deadline.
• Bonus: percentiles can't be averaged; measure with histograms.

Step 12 of 13 · 1 min

Try these yourself

Step 13 of 13 · 1 min

Further reading

• Jeffrey Dean and Luiz André Barroso, "The Tail at Scale," Communications of the ACM, 2013. Short, and one of the most useful papers in the field.
• Gil Tene, "How NOT to Measure Latency" (talk), on coordinated omission and histograms.
• HdrHistogram's documentation, for how latency histograms are recorded and combined.
• Brendan Gregg, Systems Performance, for tracking down the sources of tail latency on a single machine.
• Jesse Howarth, "Why Discord is switching from Go to Rust," Discord blog, 2020.
• Jeffrey Dean and Luiz André Barroso, "The Tail at Scale," Communications of the ACM, 2013, the section on tied requests.