Tail Sampling and the Cost of the Decision Window

Head sampling decides before the outcome exists and is therefore blind to it. Tail sampling inverts the order: the spans of a trace are collected first, examined as a whole, and only then kept or discarded. The mechanism is simple to state, buffer by trace identifier, evaluate a policy, emit or drop, and every one of its costs follows from the word “buffer”. The buffer must be large enough to hold complete traces, long enough to let stragglers arrive, and co-located so that the traces are complete at all.

Grouping requires the whole trace in one place

A tail sampling processor maintains a map from trace identifier to the set of spans seen so far. Incoming spans are appended to the entry for their trace. When a decision is made, the entry is either exported whole or discarded whole. The map is the entire mechanism, and its size is the entire problem.

Trace completeness is not guaranteed by the map. A trace whose spans arrive at two different collectors produces two partial maps, each evaluated independently against a policy that may see only a fragment. A trace containing an error might be kept on the collector that saw the error span and discarded on the one that saw the four successful spans, producing a stored trace with a hole and no indication that it has one.

The standard remedy is a routing layer: a load-balancing exporter placed in front of the tail samplers, hashing the trace identifier so that all spans of a trace reach the same downstream instance. The hash must be computed over the identifier only, not over the whole span, and it must be stable across the lifetime of the trace. This is a consistent-hash problem, and it carries the usual consequence: when the set of tail samplers changes, the assignment changes, and traces in flight at the moment of the change are split across the old and new assignment.

Two-level topology is the usual arrangement: an agent tier batches and forwards, a gateway tier hashes by trace identifier and forwards to a stateful sampling tier, and the sampling tier exports to storage. Each tier adds a network hop, and each hop adds the latency of its own batching interval, which is why the batching interval must be counted against the decision window rather than treated separately.

The decision window as a latency budget

Every trace in the buffer must be resolved eventually. Three conditions can close an entry:

A time bound. The entry is resolved when it has been open longer than a configured window, measured from the first span’s arrival. This is the backstop and the only condition that guarantees the buffer drains.

A span count bound. The entry is resolved when it accumulates more spans than a threshold, which caps the memory of any single trace and prevents one pathological fan-out from monopolizing the buffer.

An explicit signal. Some policy conditions can be decided as soon as the relevant span arrives, an error status, a specific attribute, but resolving early is only safe if the policy’s outcome cannot be changed by a later span. A policy that keeps traces containing an error can resolve as soon as it sees one; a policy that keeps traces exceeding a duration threshold cannot resolve until the root span arrives, since the root carries the total duration.

The time bound is the one that costs. Every span in the buffer is delayed by up to the full window before it reaches storage, so the visible lag of trace data grows by that amount. A window of thirty seconds means an operator investigating an error sees the trace thirty seconds after it completes, at best. The window is therefore set by the slowest trace the deployment expects, and the expectation is frequently wrong: a retry with a long timeout, a queued job, or a batch process can stretch a trace well past the window, and its spans then arrive after resolution and are treated as a new trace with the same identifier.

Memory is the real constraint

The buffer’s size is the product of arrival rate, window length, and mean trace size in bytes. At a hundred thousand spans per second with an average span of 500 bytes and a thirty-second window, the buffer holds roughly 1.5 gigabytes of span data before any overhead for the map itself. The map adds an entry per open trace, with a hash table slot and a slice header per entry, so a workload of many small traces costs proportionally more in bookkeeping than one of few large traces.

That arithmetic drives the most common misconfiguration: a window long enough to capture complete traces combined with a span rate high enough that the buffer does not fit. The resolution is not a longer window but a policy that resolves most entries early. A policy with several conditions should evaluate them incrementally as spans arrive, resolving entries that already satisfy a decisive condition and leaving only the undecided ones to age out. The undecided set is usually a small fraction of the total, and the buffer’s steady-state size is proportional to it rather than to the arrival rate.

An eviction policy is still required for the case where the buffer is full and nothing is decidable. Dropping the oldest entry is the usual choice, and it biases the retained set toward short traces, since long traces are the ones most likely to still be open when pressure arrives. That bias is not visible in any counter unless the drops are counted separately from policy rejections.

Policy composition and its arithmetic

Tail sampling policies are boolean predicates over the assembled trace. The common forms are status-based, latency-based, attribute-based, and probabilistic. A trace is kept if any policy matches, which makes the composite a disjunction, and the disjunction has a property that is easy to get wrong: the retained fraction is not the sum of the individual fractions, because the sets overlap. A latency policy that keeps 5% and an error policy that keeps 0.5% can compose to anything between 5% and 5.5%, depending on how much the two populations overlap. Measuring the composite rate requires measuring the union, not adding the parts.

A probabilistic policy applied after the others is the standard way to bound the total. Ordering matters: an error policy that fires first retains every error, and the probabilistic policy only sees what survives. If the probabilistic policy is evaluated over all traces regardless of the others, the error set is thinned along with everything else, and the guarantee that errors are always kept is lost.

The distinction between “keep if error” and “sample at 10% but always keep errors” is the difference between a policy set and a policy set with a bypass, and the bypass must be expressed explicitly in the composition rather than assumed.

Why the decision must be recorded

A trace that was discarded leaves no record of having existed. The count of traces is therefore the count of kept traces, and every rate computed from it is scaled by an unknown factor. Head sampling has the same issue, but there the factor is a configured constant; with tail sampling the factor is the output of a predicate over a population that is itself unknown, so the factor cannot be recovered from configuration alone.

Two mitigations are available. The sampler can emit a counter of decisions by policy and outcome, which gives the aggregate factor for a window even though it gives nothing per trace. Or the sampler can attach a sampling weight to each retained span, derived from the inverse of the retention probability estimated for that trace’s stratum. The first is cheap and sufficient for aggregate volume accounting; the second is necessary for any per-trace weighting and requires the sampler to know the stratum probabilities, which are a property of the workload rather than of the configuration.

Neither mitigation reconstructs the discarded traces, and neither makes a count of errors in the retained set an estimate of the error count in the population, a policy that keeps every error means the retained error count is the true error count, while a policy that keeps a fraction of errors makes it a sample. The two cases must be distinguished when the numbers are used.

When tail sampling is worth its topology

The mechanism’s benefit is precision: it retains the traces that matter and discards the rest, and the definition of “matter” is a policy that can reference the outcome. That benefit is real for workloads with rare, high-value events and abundant, low-value traffic, a service where errors are rare and routine requests are numerous is the canonical case.

The cost is a stateful tier, a routing layer to make it correct, a latency floor equal to the decision window, and a memory footprint proportional to arrival rate times window. A deployment with modest trace volume can afford to keep everything and skip the tier entirely; the crossover is when storage or export cost for the full stream exceeds the cost of running the stateful tier.

A hybrid is common and worth naming: head sampling at a generous rate at the source, tail sampling at a strict rate at the gateway. The head decision reduces the volume reaching the tail tier, so its buffer arithmetic becomes tractable, and the tail decision applies the outcome-aware policy to what remains. The head rate then acts as a pre-filter whose bias must be accounted for, since the tail tier can only keep what the head tier forwarded, the interaction between the two stages is the same estimation problem described in Head-Based Sampling by Trace-ID Threshold, compounded.

Stragglers and the second decision

Spans that arrive after their trace has been resolved are the mechanism’s characteristic failure. The collector sees a span with a known trace identifier and no open entry, creates a new entry, and evaluates the policy again, usually against a single span that satisfies nothing, so the straggler is discarded. The result is a retained trace missing its tail, and the missing part is often the slowest operation, which is the part most worth seeing.

Lengthening the window reduces the rate of stragglers at a linear cost in memory. A better remedy is to make late arrival cheap to detect: a span whose start time precedes the resolution time of its trace is a straggler by definition, and the sampler can count it. Without that count the phenomenon is invisible, because a discarded straggler and a span that was never produced are indistinguishable in the stored data.