Head-Based Sampling: Where the Decision Belongs and What It Costs

A service that handles a thousand requests per second and writes fifty spans per request produces fifty thousand span records per second. At a few hundred bytes each, before compression, that is tens of megabytes per second from one service, and a system of fifty such services produces more data than the storage layer can index and more network capacity than the collector fleet can absorb. Something has to be discarded, and the only question is where the decision is made. Head-based sampling makes it at the start, before any of the work has happened, and the entire design follows from that one timing choice.

The decision precedes the information

The phrase head-based refers to the head of the trace, the root span. At the moment the root span is created, the system knows almost nothing: the operation name, the service, the start time, and whatever attributes the entry point could attach before dispatching. It does not know the duration, the status, whether an error will occur, which downstream services will be called, or how many spans the trace will contain. The sampler must decide on that thin information, and the decision is irrevocable.

This is the trade in one sentence: head-based sampling is cheap and consistent, and it is blind. Tail-based sampling inverts the trade, buffering spans so that the decision can use the outcome, at the cost of memory, latency, and a much more complex pipeline; tail-based sampling covers that side. The two are not alternatives to choose between globally. A system typically runs head-based sampling at the edge to cut volume, and tail-based sampling on a smaller fraction for the traces that matter.

Consistency is the requirement, not the probability

The naive implementation samples independently at each service. The result is a trace that exists in fragments: the entry service records its spans, the next service drops all of its own, the third records a few. A reader sees a tree with holes and cannot distinguish a missing span from a span that was never called. A fragmented trace is worse than a dropped one because it invites conclusions about latency and errors that the absent data would contradict.

The fix is to make the decision once, at the root, and propagate it. The mechanism is already in the header: the sampled flag in the trace flags byte. A service that receives a valid context with the sampled flag set records unconditionally; a service that receives it clear does not record, even if its own local sampling rate would have kept the trace. The local sampler is consulted only when there is no valid incoming context, which means the service is the root.

This is why the flag is described as authoritative rather than advisory. Downstream services are not permitted to re-sample. A service that wants to reduce its own volume independently has to do so by a different mechanism, such as dropping spans within a trace, which produces the fragmentation problem again, or by applying a per-service sampling rate only to the spans it originates in traces where it is the root.

The consistency rule has a cost that is easy to overlook: the effective sampling rate of the whole system is the rate at the entry points, and no downstream service can adjust it. If the entry point samples at one percent and a rare backend service handles one request per hour, the chance that any given hour’s request is recorded is one percent, so the backend’s traces appear roughly once every hundred hours. A low-volume service behind a high-volume entry point becomes nearly invisible, and the resulting absence of traces for that service is often mistaken for a propagation bug.

Probabilistic sampling and its arithmetic

The simplest sampler keeps each trace with a fixed probability p, decided by a random draw. The implementation detail that matters is where the randomness comes from. Using a random number generator per decision is fine. Using the trace identifier itself is better, because the decision then becomes deterministic and reproducible: hash or truncate the identifier to a uniform value in the unit interval and keep the trace if that value is below p. The advantage appears when a trace is re-evaluated, when a collector needs to check whether it would have been sampled, or when the same identifier arrives twice.

The statistical properties are those of a Bernoulli trial. With n traces and probability p, the number kept has mean n·p and standard deviation sqrt(n·p·(1-p)). At p = 0.01 and n = 100,000 traces per hour, the expected kept count is 1,000 with a standard deviation of about 31, so hour-to-hour variation of a few percent is normal and not a signal. At low volume the variance dominates: with 100 traces per hour at one percent, the expected count is one and the observed count is frequently zero. Any alert or capacity plan based on sampled counts must account for that variance, which is the reason sample rates are usually stated alongside counts and the reason raw sampled counts should not be compared across services with different rates without weighting.

Rate-limiting samplers take a different approach: keep the first k traces per unit time and drop the rest. This bounds the storage cost directly and adapts automatically to traffic, which is attractive operationally. The distribution it produces is biased in a specific way: during a traffic spike, the sampler keeps the earliest traces in each interval and drops the later ones, so the sample over-represents whatever happens at the start of a window. If traffic is bursty and the bursts are correlated with a particular kind of request, the sample is biased toward that kind. Probabilistic sampling has no such bias, which is why it is the better default when the goal is representative latency statistics rather than a hard cost cap.

Composing samplers

Production configurations rarely use a single sampler. A typical chain is a parent-based sampler that honours an incoming decision, falling back to a probabilistic sampler with a configurable rate, sometimes wrapped in a rule that always keeps traces matching a predicate such as a specific header or a specific operation.

The composition order matters and is a frequent source of confusion. A rule-based sampler that keeps all traces with a debug header must run before the probabilistic sampler, or the debug traces are subject to the random draw and are kept only p of the time. A parent-based sampler must run before both when a decision arrives from upstream, because the upstream decision is authoritative and must not be overridden by a local rule. The standard composition is therefore: if a valid parent decision exists, honour it; otherwise apply local rules in priority order; otherwise apply the probabilistic default.

A per-service rate that differs from the upstream rate is legitimate only for services that can be roots. A queue consumer processing messages produced by a sampled trace is not a root, so its local rate never applies to those messages; it applies to messages whose producer did not inject context. This asymmetry is worth making explicit in configuration, because an operator who sets a rate on a consumer expecting it to reduce that consumer’s volume will find it has no effect on the traffic that matters.

What head-based sampling cannot answer

Because the decision precedes the outcome, head-based sampling cannot guarantee that errors are retained. At a one percent rate, an error that occurs in one request in a thousand is recorded roughly once in a hundred thousand requests. The error rate estimated from the sample is unbiased, but the absolute count of error traces is small, and the individual traces needed to diagnose a rare failure are usually absent precisely when they are wanted.

This is the strongest argument for the hybrid arrangement. Head-based sampling at the edge controls volume; a tail-based stage downstream retains all error traces and a sample of the rest, subject to its own buffering limits. The head stage’s rate should be set with the tail stage’s input capacity in mind, since the tail stage sees only what the head stage forwarded and cannot recover a dropped trace.

There is one more consequence of deciding early that is rarely stated: the sampling rate is part of the meaning of the data. A count of spans is a count of sampled spans, and multiplying by the inverse rate is valid only if the rate is known and constant over the interval. When rates change, the multiplication must use the rate in effect for each trace, which means the rate itself must be recorded, usually as an attribute on the root span or as an entry in the trace state. Without that record, historical counts cannot be rescaled and comparisons across time are invalid. The mechanism for carrying per-trace metadata alongside the context is the baggage header, and sampling rate is one of its legitimate uses.