You can't keep it all#
TL;DRthe 30-second version
- Observability data volume scales with traffic, and cost scales with volume. Keeping every trace, span, and log at scale is unaffordable, so you sample: keep a chosen fraction, drop the rest.
- There are two ways to decide. Head-based sampling rolls the dice at the start of a request — cheap, but it can't know the request was the slow one you wanted. Tail-based sampling waits until the request finishes, then keeps the errors and slow ones — smarter, but it has to buffer every span first.
- Reservoir sampling is the classic algorithm for keeping a uniform random sample of a fixed size k from a stream of unknown length, in one pass. The i-th item is kept with probability k/i, evicting a random slot.
- A sampled number must be scaled back up: if you kept 1 in 100, multiply your counts by 100 to estimate the real total. That works for common things and gets jumpy for rare ones — a single sampled error becomes 100 estimated errors.
- Cardinality control is the same cost problem on the metrics side: instead of dropping events, you drop or aggregate high-cardinality labels to bound the number of time series.
Start with why the bill grows. Every request your system serves can produce a trace — the record of where that one request spent its time as it fanned out across services (that's the /tracing topic). One request might be twenty spans, and each span is a few hundred bytes of timing and metadata. A service handling 10,000 requests a second is emitting on the order of 200,000 spans a second, which works out to terabytes a day for that one service alone. Multiply by every service in the fleet and you're looking at petabytes a month, plus the network cost of shipping it all and the compute cost of indexing it so you can search it.
None of that cost buys you much, because you will never look at almost any of it. The overwhelming majority of requests are boring: they succeeded, they were fast, they look exactly like the millions of requests around them. You keep them only in case something is wrong — and when something is wrong, you need a handful of examples, not all ten million. So the honest move is to keep a fraction and drop the rest. Deciding which fraction, and making sure the numbers you compute from it still mean something, is the whole subject.
Two decisions, and one algorithm#
The first choice is when you decide. You can decide at the start of a request, before you know anything about it, or you can wait until the request has finished and decide based on how it went. Those are the two families, and each is covered in depth on the /tracing page — here's the shape of each so the rest of this page has the vocabulary.
Head-based sampling decides at the head of the request: when the request first arrives, roll the dice, and if it loses, don't record any spans for it at all. It's cheap because a dropped request costs almost nothing, and it's consistent because the decision is made once and carried downstream, so either the whole request is traced end-to-end or none of it is. The flaw is that the dice are rolled before you know whether the request was interesting — the one that took two seconds or returned an error looks like every other request at the moment you decide, so it's usually dropped along with the boring ones.
Tail-based sampling fixes that by deciding at the tail — after the request finishes. Now you can look at the outcome: keep it if it errored, keep it if it was slow, otherwise keep a small random fraction of the healthy baseline. That's the ideal set of traces. The cost is that something has to hold all of a request's spans until the request is done before it can judge it, and because those spans come from different services on different machines, a central buffer has to collect them and wait. That's memory, and the risk that a late or lost span makes the decision on an incomplete trace. The /tracing page has the full head-vs-tail comparison and when to pick which.
The second choice is how you pull a fair sample when you don't get to see the whole stream first. Say you want to keep exactly 1,000 example traces from today, chosen uniformly at random — every trace equally likely to be one of the thousand you keep. The trouble is you don't know how many traces today will bring. You can't wait for the day to end and pick 1,000 from the full list, because you can't hold the full list; you have to decide on each trace as it streams past, keeping only 1,000 at any moment. The algorithm that does this in a single pass is reservoir sampling.
The reservoir is an array of k slots — here k is 1,000. The rule:
- Fill the reservoir with the first k items as they arrive. The first 1,000 traces just go straight in.
- For every item after that — the i-th item overall — keep it with probability k/i. Generate a random number; if it says keep, pick one of the k slots at random and overwrite it with the new item. Otherwise drop the new item.
- When the stream ends, the k items left in the reservoir are a uniform random sample of everything that went by.
Walk one step to feel it. The 5,000th trace arrives. It's kept with probability k/i = 1,000/5,000 = 1/5, so one time in five it displaces a random one of the thousand already held. Early items go in for free; later items face longer and longer odds (the 100,000th trace is kept with probability 1,000/100,000 = 1/100). That declining probability is exactly what's needed to keep every item — early or late — equally likely to survive to the end. Why k/i produces a perfectly uniform sample is a short proof, in the under-the-hood beat below; the rule itself is all you need to use it.
Scaling a sample back up — and where it breaks#
Once you're keeping 1 in 100 requests, your stored data no longer counts the real world directly. You stored 100 traces for the /checkout endpoint today, but that's not 100 checkouts — it's 100 out of roughly 10,000, because you kept one in a hundred. To recover the real number you multiply by the inverse of the sampling rate. Keep 1 in 100 and every kept item stands for 100 real ones, so you scale your counts by 100. This multiplier has a name: the adjusted count, the number of real events each sampled event represents. Sample at 1%, the adjusted count is 100; sample at 5%, it's 20.
For that to work, the sampling rate has to travel with the data. If a service samples at 1% but forgets to record that it did, a dashboard downstream has no way to know each trace stands for 100, and it will report throughput a hundred times too low. So the rate is stamped onto every kept trace, and every count computed from sampled data is really an estimate: kept count × adjusted count. For common things this estimate is excellent. You kept 100 checkout traces, you estimate 10,000 checkouts, and the true number is close — a big sample of a common event is stable.
So the accuracy rule of thumb: uniform random sampling is great for measuring the busy, common path and unreliable for counting rare events. If you sample uniformly and then compute an error rate from the sample, that error rate is one of your least trustworthy numbers. The fix isn't a bigger uniform sample (errors are rare no matter how much you keep); it's to stop sampling the errors at all — keep 100% of errors and sample only the successes, which is exactly what tail-based and priority sampling do. You trade a little more storage for error counts you can believe.
PredictYou sample traces uniformly at 2% (keep 1 in 50). Over an hour you kept 4,000 traces for one endpoint, of which 3 were errors. What do you report for total requests and for errors — and which number should you distrust?
Hint: Multiply by the inverse rate for both. Then ask which estimate stands on enough kept examples to be stable.
The adjusted count is 1 / 0.02 = 50, so each kept trace stands for 50 real ones. Total requests: 4,000 × 50 = 200,000 — a solid estimate, because it stands on 4,000 kept samples of a common event. Errors: 3 × 50 = 150 — and this is the number to distrust. It stands on just 3 kept examples, so the estimate is coarse and jumpy: catch one fewer error next hour and you'd report 100; catch one more and you'd report 200; catch zero and you'd report no errors at all while real errors were happening. The busy total is stable under uniform sampling; the rare error count is not. If you need a trustworthy error rate, don't sample the errors — keep all of them (tail-based / priority sampling) and sample only the successes.
Uniform, or keep-the-interesting?#
Every sampling design is choosing between two goals that pull apart: a representative sample of everything, and a guaranteed sample of the rare things you care about. You usually can't maximize both at a fixed budget, so the design is about how you split that budget.
- Uniform sampling keeps the same fraction of everything — 1 in 100, no matter what. It gives you a faithful miniature of the whole, so scaled-up totals and the common-path distribution are accurate. Its weakness is the one above: rare events get sampled into noise.
- Dynamic (priority) sampling keeps different fractions for different things: 100% of errors, 100% of slow requests, and maybe 1 in 1,000 of the flood of fast successes. Now you're guaranteed to see every problem, and you spend almost nothing on the boring baseline. The cost is that your sample is no longer a plain miniature — you must weight each class by its own adjusted count to reconstruct real totals, and if you get those weights wrong your numbers are wrong.
- The rate itself is a dial. A lower rate saves more money and gives you fewer examples and jumpier rare-event estimates; a higher rate costs more and steadies the numbers. There's no universally right value — Google's Dapper famously ran as aggressive as 1 in 1,024 and still caught the problems that mattered, because at Google's volume even 1/1024 of the traffic is a huge absolute number of traces.
The practical path most teams walk: start with uniform head-based sampling because it's simple and cheap and fine when you mostly want a representative sample. Add priority or tail-based rules once the system is big enough that the interesting requests are rare and keep getting dropped — keep every error and slow trace, sample the rest hard. The honest summary is that sampling is a budget, and the design question is always the same: given that you can only keep a fraction, spend it where a dropped example would hurt most.
Two ways to bound the bill: drop events, or drop labels#
Sampling is the answer when your cost grows with the number of events — traces and logs, where each request is its own record. But metrics have a different cost shape, and they need a different lever. It's worth putting the two side by side, because interviewers like the seam between them.
A metric doesn't store one row per request; it stores one running time series per unique combination of label values (the /metrics-observability page covers this in full). The cost driver for metrics isn't how many requests flow through — it's how many distinct label combinations exist. Put a bounded label like HTTP method on a counter and you get a handful of series. Put an unbounded label like user_id on it and a million users become a million series, each held in memory. That blow-up is called a cardinality explosion, and the way you control it is not sampling — it's cardinality control: dropping or aggregating the high-cardinality labels so the number of series stays bounded.
So the two levers pair up by data type. Here's the split:
| Sampling | Cardinality control | |
|---|---|---|
| Applies to | Traces and logs (one record per event) | Metrics (one series per label combination) |
| Cost grows with | Number of events | Number of distinct label combinations |
| What you drop | Whole events, at random (keep a fraction) | Labels — the high-cardinality ones (user_id, request_id) |
| You still get | Scaled-up totals + example traces | Bounded, aggregate time series |
| You lose | Most individual events (rare ones especially) | The ability to slice by the dropped label |
They even hand off to each other. When you drop a high-cardinality label from a metric, the per-value detail doesn't vanish from the world — it lives in the traces and logs, where each event stands alone and sampling (not cardinality) is the cost lever. 'How many distinct users hit this today?' isn't a metric label at all; it's better answered by a distinct-count estimate, which the /hll/sim (HyperLogLog) covers, or a frequency estimate over a small footprint, which the /count-min/sim shows. And when you compute a p99 from sampled trace data, you want a summary that merges correctly across a fleet — the /tdigest/sim demonstrates estimating a quantile over a huge stream from a small, mergeable structure. The through-line: at scale you never keep everything, so every observability tool is a way to answer a question from a fraction of the data.
Under the hood: why k/i is uniform, and keeping a trace whole
Why does keeping the i-th item with probability k/i produce a perfectly uniform sample — every item equally likely to survive, no matter when it arrived? It's a short proof by induction on the stream length. Claim: after n items have streamed past, every one of them is in the reservoir with probability k/n.
- Base case: after the first k items, all of them are in the reservoir, each with probability k/k = 1. The claim holds.
- Inductive step: assume after i−1 items every item is in with probability k/(i−1). Now the i-th item arrives. It's kept with probability k/i — that settles the new item directly. For an item already in the reservoir to stay, two things must go right: either the new item is dropped (probability 1 − k/i), or it's kept but evicts one of the other slots. The chance an already-held item survives this round works out to (i−1)/i.
- So an old item's probability of being in the reservoir becomes its old probability times its survival chance: k/(i−1) × (i−1)/i = k/i. Both the new item and every old item now sit at k/i — the claim holds for i, and by induction for the whole stream.
That uniform guarantee is the base version. Two refinements matter in practice. Weighted (priority) reservoir sampling gives each item a weight and samples in proportion to it, so you can keep important traces (errors, slow requests) with higher probability than boring ones while still holding a fixed k — the dynamic-sampling idea from above, made into a single-pass algorithm. And there's a subtler problem sampling creates for tracing specifically: a trace's spans are produced independently by many services, so if each service sampled on its own coin flip, you'd keep the frontend's span of a request but drop the database's span of the same request, and end up with shredded half-traces.
In the wild
- Google's Dapper (2010), the paper that started distributed tracing, sampled as aggressively as 1 trace in 1,024 requests and still caught the problems that mattered — the original proof that a tiny fraction is enough at scale.
- OpenTelemetry ships both a head-based sampler in its SDKs and a tail-sampling processor in its Collector, and it standardizes consistent probability sampling (the randomness + threshold in tracestate) so adjusted counts stay correct across services and vendors.
- Honeycomb built its product around dynamic sampling — keep every error and slow trace, sample the common successes hard — and popularized tail-based sampling to keep the outlier traces that uniform head-based sampling drops.
- Datadog and other commercial platforms apply ingestion sampling and let you compute metrics from sampled traces by scaling with the adjusted count; they also bill metrics by cardinality, which is why controlling label cardinality is a line item on the invoice, not just a tidiness concern.
- Elastic APM and other systems weight sampled data by the inverse sampling rate to estimate real throughput, and document the accuracy caveat directly: the scale-up is fine for volume and worse for errors, because a single sampled error blows up into a whole adjusted count.
Pitfalls & gotchas
If I sample, am I lying about my traffic numbers?
No — as long as you scale back up. A random sample plus its sampling rate lets you estimate the real totals: kept count × the adjusted count (the inverse rate). The lie only happens if you forget to record the rate and read the sampled counts as if they were the whole, which reports throughput far too low. Stamp the rate on the data and the totals come back honest.
Why can't I just sample harder to save more money?
You can, but you pay in rare-event accuracy. A lower rate means fewer kept examples, and the fewer examples a rare event stands on, the jumpier its scaled-up estimate. Errors are the usual victim: at a low uniform rate you catch zero or one, so your error count swings between nothing and a full adjusted count. If errors matter, don't sample them uniformly — keep them all and sample only the successes.
Doesn't reservoir sampling favor the items that arrived first?
It's the opposite worry, and the answer is no — it's uniform. Early items go in for free but face many later chances to be evicted; late items face long odds of being kept but almost no chance of later eviction. The k/i rule balances these two effects exactly, so after the stream ends every item, first or last, sits at the same probability k/n of being in the reservoir. The proof is the induction in the under-the-hood beat.
Each of my services samples on its own — why are my traces coming back in fragments?
Because independent coin flips disagree. If the frontend keeps a request but the database drops the same request, you get half a trace. The fix is consistent sampling: every service derives the same random value from the shared trace id and applies the same threshold, so all of them reach the same keep-or-drop decision and the trace stays whole end-to-end. OpenTelemetry carries that value and threshold in the trace's tracestate for exactly this reason.
Is cardinality control just sampling for metrics?
No — they attack different cost shapes. Sampling drops whole events because trace and log cost grows with the number of events. Cardinality control drops labels because metric cost grows with the number of distinct label combinations, not the number of requests. Sampling a metric wouldn't help: the series count is set by your labels, and a million user_id values is a million series whether you scrape them often or rarely. You bound metric cost by removing the unbounded label, not by sampling.
QuizA team samples all traces uniformly at 0.5% to cut costs, then builds their error-rate alert on the error count from that sampled data. Errors are rare. What's the flaw, and the fix?
- No flaw — a random sample is representative, so the error rate is accurate.
- Uniform sampling measures rare errors poorly: at 0.5% you catch zero or one, so the scaled-up error count swings between 0 and a full adjusted count (200). Keep 100% of errors (tail-based / priority sampling) and sample only the successes.
- The flaw is the rate is too high; drop to 0.05% so the alert stabilizes.
- Switch the alert to average latency instead — it's always accurate under sampling.
Show answer
Uniform sampling measures rare errors poorly: at 0.5% you catch zero or one, so the scaled-up error count swings between 0 and a full adjusted count (200). Keep 100% of errors (tail-based / priority sampling) and sample only the successes. — Uniform sampling is faithful for common things and unreliable for rare ones, and errors are rare. At a 0.5% rate the adjusted count is 200, so a single caught error is reported as 200 and catching none is reported as zero — the estimate has no stable middle, which makes it a terrible foundation for an alert. Sampling harder (a lower rate) makes it worse, not better, because the errors stand on even fewer examples. The correct design is priority or tail-based sampling: keep 100% of the errors and slow requests, sample the common successes hard, and weight each class by its own adjusted count. You get trustworthy error counts and still keep the storage bill down, because the successes — not the errors — are the volume.
In an interview
Sampling comes up whenever a design has to survive its own observability volume — a tracing system, a logging pipeline, any 'how would you keep this affordable at scale' follow-up. The strong answers all connect the strategy to its cost in accuracy, not just name the strategies.
- Lead with why: cost grows with traffic, keeping 100% is unaffordable, so you keep a representative fraction and scale the numbers back up. Framing it as a budget, not a switch, is the senior signal.
- Name both decisions: head-based (decide at the start, cheap, but drops the rare slow/error trace) vs tail-based (decide after the outcome, keeps every error, but must buffer spans centrally). Say which you'd start with (head) and when you'd add the other (once interesting requests are rare and getting dropped).
- Know the scale-up: a sampled count times the inverse rate (the adjusted count) estimates the real total, and it only works if the rate travels with the data. Then name the trap unprompted — the estimate is stable for common events and jumpy for rare ones, so don't compute error rates from a uniform sample.
- Have reservoir sampling ready as the algorithm for a fixed-size uniform sample from an unbounded stream: keep the i-th item with probability k/i. It's a common standalone coding-round question too.
- Close the loop to metrics: sampling drops events (traces/logs); cardinality control drops labels (metrics). Different cost shape, different lever — and high-cardinality identity that you strip from a metric belongs in the sampled traces instead.
PredictAn interviewer says: 'Our tracing bill is out of control, but last week we missed a rare 500-error spike because the traces for it had been sampled away. What would you change?' What's the strong answer?
Hint: A lower uniform rate drops errors even more. What has to be true about how you sample errors versus successes?
Recognize that a single uniform head-based rate is being asked to do two jobs it can't do at once: cut cost and guarantee you keep the rare errors. Uniform sampling at a low rate saves money precisely by dropping most requests at random — including the rare error traces you needed, which is exactly what happened. The move is to split the budget by outcome instead of sampling everything the same: switch to tail-based (or priority) sampling so you keep 100% of errors and slow traces and sample the common fast successes hard — maybe 1 in 1,000. Now the errors can never be sampled away, and the bill actually drops further because the boring successes are the volume, not the errors. Note the cost you're taking on: tail-based needs a central collector to buffer a request's spans until it finishes before it can judge the outcome, which is memory and a moving part. And keep the adjusted counts correct per class so your scaled-up totals still hold. Naming that the fix is differential sampling by outcome — not a different uniform rate — is what makes the answer strong.
References
- Vitter — Random Sampling with a Reservoir (1985) — The original paper: Algorithm R and the k/i replacement rule for a fixed-size uniform sample over a stream.
- Reservoir sampling — Wikipedia — Algorithm R with the k/n correctness proof by induction, plus weighted and optimized variants.
- OpenTelemetry — Sampling — Head-based vs tail-based sampling and how the sampled decision propagates across services.
- OpenTelemetry — TraceState: Probability Sampling — Consistent probability sampling: the randomness value and threshold in tracestate, and adjusted counts.
- Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (Google, 2010) — The origin of low-rate trace sampling — 1 in 1,024 and still catching what mattered.
- Honeycomb — Sampling and Dynamic Sampling — Keeping every error and slow trace while sampling the common successes hard — dynamic/priority sampling in production.