Tail Latency

Overview

• This article covers Tail at Scale by Jeffrey Dean and Luiz André Barroso, both contributed to building what we call today modern data centers and framed an important topic and its effects in systems at large scale called Tail Latency (coining the term "tail-tolerant").
• Tail Latency is a topic that Google Search and other services take advantage of to avoid latency issues and reach that performance that we observe in our daily life.
• We will discuss more than just "What is Tail Latency?", but also:
  • What are p50, p99, p99.9, and other percentiles?
  • Why both average and median lie?
  • What causes tail latency?
  • Parallelizing requests across multiple distributed systems using Fan-Out and Fan-In techniques.
  • The effects of variability at small and large scale.
  • Can we kill variability or do we need to understand how to engineer on top of that fact?
  • What is the naive "latency fix" and why it spends unnecessary money, computing power and energy resources?
  • How to apply that knowledge in the systems you are building? How to collect metrics, analyze them and take action? (prometheus, grafana, and k6)
  • The risks of gathering incorrect data in load tests: Coordinated omission.

What is p50, p99, p99.9, and other percentiles?

• Imagine you have a line cut into 100 equal pieces from left to right. The 50th piece represents the p50, also called the median.
• The 99th piece is almost the last one closer to the right side.

• Now imagine that this line represents requests sorted by their latency, where the leftmost one has the smallest latency and the further right we go, the higher the latency is.
• When someone says "The p99 is 1s", it means: "1 of 100 users is facing a response time of 1 second or more."
• When someone says "p50 is 100ms", it means: "50 of 100 users are facing a response time under 100ms"

• To understand p99.9 we need to cut this line not in 100 pieces, but in 1000 smaller parts. It is the rightmost part, the 999th.
• "p99.9 is 10s" = "1 of 1000 users is facing a response time of 10 seconds or more."

Why both Average and Median (p50) lie?

• Average gets pulled by higher values, but at scale one slow request barely changes it, since that single value gets diluted across all the fast ones. It seems good for showing us problems, but it actually hides the tail.
• Median is completely blind to the tail, we could make the 49% slowest requests take hours and the median would not move.
  • p50(1,2,3,500) = (2+3)/2 = 2.5

What is Tail Latency and What Causes it?

• What causes Tail Latency? Variability, response times are not constant, they spread out.
• What is Tail Latency? The slow end of that spread of response times far above the median. It is a region of the distribution, not a single latency value.
  • p99 and p99.9 are the metrics we use to measure the tail, and identify how bad the tail is.

And Why Latency Variability Exists?

• Multiple factors, such as:
  • Cache miss: forcing a slower path through the disk or doing network calls.
  • Shared resources: CPU cores, processor caches, memory bandwidth, network bandwidth...
  • Queueing: Requests do not arrive evenly, they come in bursts. If more arrive than the server can process, requests pile up in the queue and wait, which increases the total request time a lot.
  • Background maintenance activities: such as cronjobs, log compaction, data reconstruction in distributed file systems, etc...
  • Garbage Collector: The runtime of garbage-collected languages (e.g. Java) periodically pauses normal work to reclaim unused memory. Unlucky requests will get frozen for the duration of it.
  • Even power limits used in hardware to control temperature of modern CPUs and other components.
  • These and much more...

What is Fan-Out and Fan-In?

• A technique used to turn a unit of work into multiple parallel units of work (1:M).
• It can happen in the same server using different threads.
• But in distributed systems it can also mean parallelizing requests across multiple different services and then merging their results into a single response. In this way you are not only limited to a single machine's cores to parallelize tasks, but to multiple nodes.
  • The distributed systems concepts are very similar to the fork/join concepts when working with threads in a single machine.
• Fan-Out = split a larger task into smaller sub tasks; root server distributes sub tasks to other services
• Fan-In = used if you need to wait for all sub tasks to complete before moving to the next processing step; root receives the responses and merges them into a single response.
• NO, Fan-In isn't required after Fan-Out!

How Scale Amplifies Variability Effects

• If you don't understand the probabilities, I suggest you watch Independent & dependent probability - Khan Academy.

• As you can see the effect of variability at scale can be a killer for your services. Imagine if Google hadn't cared about that, would they be that huge, or would customers use other, faster services?

Can we kill variability?

• No, eliminating all variability is infeasible, so you build tail-tolerant systems instead. So how to do that?

1. Fix the node first

• Before any sophisticated technique we start simple.
• Run the server at realtime priority so background daemons cannot preempt it. (OS scheduling)
• Dedicate a core to interrupts so network packet interrupts do not keep stealing the application's cores.

2. Within-request techniques

• These act inside a single request, in tens of milliseconds, and reuse replicas you already keep for availability.

• Hedged requests: if the request to the first replica (that seemed to be the most appropriate) lasts for more than p95, we send a copy to another replica and take whichever replies first cancelling the rest.

  • It's especially good because if the first server hit a bad moment (GC pause, etc) the second rescues the application.
  • Waiting too short (hedge at p50) = 50% of requests duplicated.
  • Waiting too long (hedge at p99.9) = Almost no duplicates, but the response is very slow before help arrives.
  • Because of that, the authors of the article "The Tail at Scale" suggest hedging at p95.

• Tied requests: Send the request to two servers at once, each tagged with the other's identity. Whichever begins execution first sends a cancel to its twin, so our app rarely pays for double work.

3. Cross-request techniques

• These handle coarser problems (load imbalance, or a particularly slow machine) over seconds to minutes.

• Micro-partitions: Create many more partitions (data chunks) than machines, so you can move load between machines in small steps instead of moving a whole machine's worth at once. With 20 partitions per machine you shed load in 5% increments and rebalance much faster, since each move copies only a small chunk.

• Selective replication: Detect (or predict) the items likely to get hot and make extra copies of just those, so the load balancer can spread that heat without moving whole partitions around.

• Latency-induced probation: Watch each machine's latency and temporarily remove one that has turned slow, while still sending test requests to it in the background so you know when it recovers and can bring it back.

  • It sounds counterintuitive, why would removing one slow machine help reduce latency and build a tail-tolerant system? Because we fan out and wait for all of them, so the slowest one sets the latency of the whole request. Removing it leaves only the fast ones, and we keep probing the slow one to bring it back once it recovers.

4. Information-retrieval techniques

• For search-like systems where a good answer now beats a perfect answer later.

• Good-enough responses: Once enough leaf servers have replied, return slightly incomplete results instead of waiting for slower ones.

• Canary requests: Send the request to one or two leaves first, and only fan out to the rest if the canary comes back cleanly in a reasonable period of time, protecting against a bad request that could stall thousands of servers.

  • "Canary" comes from the idea that miners used a bird to see if the mine had poison gas so if the bird died they could leave safely.
  • Same as we do with canary deployment, slowly routing traffic to the server and if it dies we roll back to the stable one.

The naive fix and unnecessary waste of money

• High utilization makes tail latency much worse.
  • Imagine a supermarket cashier idle, then 3 customers arrive at once and they are served right away, no line forms.
  • Now what if the cashier was busy most of the time? Then the same 3 customers at once will wait a long time.
• The obvious move is to keep servers 30-40% busy, so there is always slack to handle incoming requests. It works and is pretty expensive as you can imagine.
  • Naive approach: Paying for 100 servers to do the work of 40 just to reduce tail latency having 60 servers for latency insurance.
• The right approach mentioned in the previous section: techniques to build tail-tolerant systems.
  • Hedged requests and tied requests lean on already existent replicas for fault tolerance, not new servers to avoid tail latency.
  • Tail-tolerant techniques let us keep the tail low while running servers hot, buying fewer machines.

Measuring the Tail in Real Systems

• We could gather latency data using monitoring systems such as Prometheus and an observability system such as Grafana to build charts and dashboards to analyze these data.
• We could also implement a load test on our service and analyze the results in charts and dashboards using k6

• Now take a look at these K6 load test results: Github - K6 load test POC
• Below I'll show only the latency and some percentiles, but k6 provides us much more information.

• The overall p99 is 220ms which is good. The warmup pushed p99 above 1s which looks bad, but since it was just the warmup that spike is expected and not a real concern.

• One problem of load test tools if misconfigured is Coordinated omission.

• Coordinated omission happens when your load tester keeps waiting on a slow request instead of sending the next ones on schedule, so it silently skips the requests that would have been slow too, making your measured p99 look far better than reality.

  • Named by Gil Tene on How NOT to Measure Latency (coordinated omission starts around 33:50).

References

• The Tail at Scale by Jeffrey Dean and Luiz André Barroso (CACM)
• Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency (SOCC 2014)
• Exploring the Fan out and Fan in pattern with OpenFaaS
• Analyze service graph data - Grafana
• How NOT to Measure Latency by Gil Tene