Sampling

01The intuition

The problem it solves

A factory makes a million biscuits a day. To check quality you do not eat a million biscuits; you eat fifty, chosen from different batches and times, and if two are burnt you know roughly 4 percent of the day's biscuits are burnt. The fifty cost almost nothing and the estimate is good enough to act on.

A service handling a billion requests a day produces, for each one, a trace of every internal call: 50 spans of 300 bytes, 15 KB per request, 15 TB a day. Storing and indexing that is more expensive than the service itself. Yet almost all traces say the same thing: everything was fine. The questions people ask, "what is the p99 latency", "which service is slow", "why did this error happen", can be answered from a fraction, as long as the fraction is chosen well.

Build it one piece at a time

Step 1: keep one in a hundred. At the entry point, roll a die once per request: with probability 1 percent, mark the request as sampled. Every downstream service reads the mark from the request headers and keeps or drops its spans accordingly, so a sampled request is kept whole across all 50 services, not in pieces. Storage falls to 150 GB a day.

Step 2: keep the interesting ones on purpose. Row three is the problem: the rare failure is exactly what a uniform sample throws away. So decide at the end of the request instead, when you know its outcome: keep 100 percent of errors and of requests slower than 1 second, 1 percent of the rest. This is tail-based sampling. It needs the spans buffered briefly until the request finishes, which a collector does in memory.

Step 3: keep the rare paths too. A route that gets 10 requests a day will almost never be sampled at 1 percent. Give each route a floor: at least 1 request a minute is kept, whatever the rate. Rate-based sampling like this keeps the picture complete for small services and cheap for large ones.

Step 4: weight the estimates. If a span was kept at probability p, it stands for 1/p requests. When computing counts or averages from the sample, multiply by that weight. A trace kept at 1 percent counts as 100; an error kept at 100 percent counts as 1. Without weights, errors look a hundred times more common than they are.

Step 5: sample consistently across systems. Decide using a hash of the trace ID rather than a random number, so logs, metrics and traces all keep the same requests, and a debugging session can follow one request through all three.

Why it works, with the numbers

The error of an estimate from a sample shrinks with the square root of the sample size, not with the population. To know an error rate of about 1 percent to within 0.1 percent you need roughly

n ≈ p(1 − p) / e² = 0.01 × 0.99 / 0.001² ≈ 9,900 samples

which is nothing against a billion requests. Storage for a day at 1 percent plus all errors and slow requests (say 0.5 percent) is about 225 GB instead of 15 TB. The guarantee is that aggregate answers are accurate to a known error bar and that every error and every slow request is kept. The failure modes are forgetting the weights, sampling at each hop independently so traces arrive in fragments, and a tail-based collector that runs out of memory during an incident, when every request is slow and all are kept.

The trade-off you must say out loud

You give up the ability to look up any particular normal request in exchange for a system you can afford. Say your base rate, your always-keep rules, your per-route floor and how you weight. Say what happens during an incident when the tail-based rule keeps everything. The follow-up is "how do you debug one user's complaint", and the answer is a debug flag on that user that forces sampling for an hour.

Where it shows up in the 100 Google problems

• Distributed tracing: head-based versus tail-based sampling is the first deep dive, with the collector's buffer as the cost.
• ML model monitoring: a sample of predictions is stored with features so drift can be measured without logging every inference.
• Log pipeline: debug logs are sampled at the agent when the collector is behind.
• Metrics and monitoring: high-cardinality labels are sampled or dropped so the time-series count stays bounded.

02Used in these problems

• Design distributed tracing for a microservice fleet
• Monitor an ML model's performance in real time