Lorenz and Little: How Much Does Your Tail Cost? - Marc's Blog

Marc's Blog

About Me

My name is Marc Brooker. I like to build things that work, and do cool stuff. I like building big things. I also dabble in machining, welding, cooking, and skiing.

I am an engineer at Amazon Web Services (AWS) in Seattle, where I work on agentic AI, especially safety and policy for agentic AI. Before that, I worked on EC2, EBS, databases, serverless, and serverless databases.

All opinions are my own.<br>Links

My Publications and Videos

@marcbrooker on Mastodon<br>@MarcJBrooker on Twitter

Is this blog written by AI?

Lorenz and Little: How Much Does Your Tail Cost?

Lorenz and Little sounds like hipster burger bar from 2015.

It’s time for Marc’s Amateur Statistics Corner! Today: why I pay a lot of attention to tail latency when optimizing cost.

I’ve written before on the importance of tail latency for customer experience (e.g. in 2026, 2021, and 2021, and 2017). Today, I want to talk about tail latency from the perspective of cost and capacity.

Like many system operators, I think about tail latency using percentiles.

Here’s a question: how much does each of my latency percentiles contributed to the mean latency? Intuitively, the answer is “quite a lot”, but can we quantify that? We can! The thing we’re looking for is the empirical Lorenz Curve. It directly calculates the answer to the question: given a latency percentile $P$ (e.g. p99=100ms), how much do requests taking shorter than $P$ contribute to the mean latency? (Let’s call it $L(P)$ , so the real answer to our question is $1 - L(P)$).

Starting from latency samples, the calculation is pretty simple: L = sum(sorted(x)[:k]) / sum(x) (for a set of n latency samples x, and k=p*n). From a vector of quantiles, things get a little more complicated, because we have to choose how to interpolate between the samples and extrapolate out to the maximum. Here I’m interpolating using a power law, which is a little bit of a sin1, but good enough for our purposes.

# Calculate 1 - L(p) for a vector of measured quantiles<br># q - an array of quantiles (e.g. [1, 10, 200, 10000, 20000])<br># p - an array of percentiles they're measured at (e.g. [0, 0.5, 0.9, 0.99, 0.999])<br># OneMinusL - One minus the empirical Lorenz curve for each of the percentiles<br>def OneMinusL(q, p):<br>...Show full implementationHide implementation

# Calculate 1 - L(p) for a vector of measured quantiles<br># q - an array of quantiles (e.g. [1, 10, 200, 10000, 20000])<br># p - an array of percentiles they're measured at (e.g. [0, 0.5, 0.9, 0.99, 0.999])<br># OneMinusL - One minus the empirical Lorenz curve for each of the percentiles<br>def OneMinusL(q, p):<br>q, p = np.asarray(q, float), np.asarray(p, float)<br>assert q.shape == p.shape and q.size >= 2, "q, p must be same-length, size >= 2"<br>assert p[0] == 0 and p[-1] 0), "p must be strictly increasing"<br>assert q[0] > 0 and np.all(np.diff(q) > 0), "q must be positive and strictly increasing"<br>w = q*(1-p)<br>a = np.log((1-p[1:])/(1-p[:-1]))/np.log(q[:-1]/q[1:])<br>assert np.all(np.abs(a-1) > 1e-9), "alpha == 1 in some cell: divide by zero"<br>assert a[-1] > 1, f"tail alpha={a[-1]:.3f}

For example:

print(OneMinusL([1, 10, 200, 10000, 20000], [0, 0.5, 0.9, 0.99, 0.999]))<br>[1. 0.99377318 0.93082759 0.51712644 0.10342529]

That tells us that, for this distribution, requests at or longer than the median (p50) contribute about 99% of the mean latency, at requests at or longer than the p99 contribute about 52% of the mean latency2.

That’s fun, but why do I care? Because Little’s law tells us that this same value (contribution to the mean) is also the contribution to the concurrency in the system. In a simple threaded system, if $1 - L(p) = k$ , then $100k$% of the busy threads in our service are busy with requests with a latency3 above the $p$th percentile. Queues, event-based implementations, etc complicate the mapping of concurrency to cost, so you’ll need to think about those in context of your own system.

In my experience, it’s not unusual in services for $1 - L(0.99)$ to be greater than $0.5$ or even $0.75$. That tells us that optimizing the tail could be a much bigger than expected contributor to reducing concurrency, and along with that reducing capacity demand, lock contention, and other things that come with higher concurrency. Tails tend to be disproportionately expensive to serve, and so disproportionately important to focus on as we think about optimization. We shouldn’t make the mistake of trimming them off, because they’re often the thing that’s driving costs! (And, of course, bad customer experiences).

If you want to play with some values, type your percentiles in here, and see your curve:

p0: ms

p50: ms

p90: ms

p99: ms

p99.9: ms

Share of mean latency from requests at or above each percentile:<br>p50 – ,<br>p90 – ,<br>p99 – , and<br>p99.9 – .<br>By Little's law, these are also their shares of system concurrency.

Footnotes

There are two sins here: one of them is that I’m arbitrarily choosing a...