Tail-Based Sampling: Buffering Traces Until the Outcome Is Known

Head-based sampling decides before the outcome exists, so it cannot promise that failures are retained. Tail-based sampling makes the opposite bet: hold every span until the trace is complete, then decide with full knowledge. The bet is expensive, because holding spans means storing them, and storing them means the pipeline must solve two problems that head-based sampling never faces, namely keeping the spans of one trace together and knowing when a trace is finished.

The decision is only as good as the window

A tail sampler receives spans one at a time, from many services, in no particular order. It groups them by trace identifier. When a decision point is reached, it evaluates the complete group and either keeps all of it or drops all of it. The decision criteria can reference anything the spans contain: whether any span has an error status, whether the root duration exceeded a threshold, whether a particular service appears in the trace, whether an attribute matched.

The first hard question is when to evaluate. A trace is complete when all its spans have arrived, and there is no signal that says so. Spans are written when operations finish, so they arrive in end-time order, which is roughly reverse order of nesting: the deepest child finishes first and the root last. But the root’s arrival does not guarantee that everything has arrived, because a span written on a host with a slow exporter may still be in flight.

Practical implementations therefore use a timeout. Spans are accumulated in a window, and a trace is evaluated when either the root span arrives and a short grace period passes, or when the oldest span in the group has been held longer than the window. The window is the design parameter that trades completeness against memory. A window of thirty seconds captures nearly all traces in a system whose spans arrive promptly and drops the tail of traces delayed by a backed-up exporter. A window of five minutes captures more but multiplies the buffer size, since the buffer holds every span produced in the window, not just the kept ones.

The arithmetic is unforgiving. If the system produces 50,000 spans per second at 500 bytes each, that is 25 MB per second of raw spans. A thirty-second window holds about 750 MB. Head-based pre-sampling reduces this proportionally: at a ten percent head rate the window holds 75 MB. This is why tail sampling is almost always deployed behind a head sampler rather than in front of one.

Keeping a trace’s spans in one place

The second hard question is routing. A tail sampler cannot decide correctly unless all the spans of a trace reach the same instance of the sampler. If spans are load-balanced across four collector instances by connection, the four instances each see a quarter of every trace, and each decides on a fragment.

The solution is consistent routing by trace identifier. The receiving layer hashes the trace identifier and selects a destination from the set of sampler instances, so every span of a given trace goes to the same one. The hash must be stable across the set membership, or a change in instance count reshuffles traces mid-flight and splits the ones currently buffered. Consistent hashing, or a static assignment of identifier ranges to instances, provides that stability; naive modulo arithmetic on the instance count does not.

This routing requirement is the reason tail sampling changes the shape of the pipeline rather than just adding a filter. The collector layer that receives spans must be aware of the sampler’s topology, which means the two are usually co-located in the same deployment and scaled together. Routing traces through a collector pipeline covers the routing mechanism in its own terms, including the failure behaviour when the instance set changes.

Policies and their interaction

A tail sampler is configured with an ordered list of policies, each a predicate plus a rate. The common set is: keep everything with an error status, keep everything slower than a latency threshold, keep a small percentage of everything else. The policies are evaluated in order and the first match decides.

Two properties of this arrangement cause trouble.

The first is that “error” is a property of the trace, not of the policy. A span status of error on any span is the usual test, but many systems do not set status reliably: an HTTP client that receives a 500 may record a successful span if the instrumentation only checks for transport errors. The policy then never fires for the failures that matter. Recording the HTTP status code as an attribute and testing that, rather than relying on the status field, is the more reliable predicate, and it is a case where the attribute conventions pay for themselves.

The second is that the fallback rate applies to the complement of all the earlier policies, and computing that complement correctly requires the policies to be mutually exclusive. If the latency policy and the error policy can both match the same trace, the effective sampling of error traces is not the configured rate but something larger, and the weights needed to rescale counts become ambiguous. Making the policy list a partition, with an explicit catch-all last, keeps the arithmetic clean.

Where the pipeline loses traces it meant to keep

The failures specific to tail sampling are mostly about the buffer.

Memory exhaustion is the first. The buffer holds spans from a window, and a traffic spike increases the arrival rate without changing the window length, so the buffer grows. When it hits its limit, the sampler must either drop spans, which breaks the traces being assembled, or evict the oldest groups, which discards traces before their decision. Evicting the oldest is the safer choice because it loses whole traces rather than fragments, but it means that during a spike the sampler systematically loses the traces that were waiting longest, which are the slow ones, which are exactly the ones a latency policy wants to keep.

Late spans are the second. A trace that was already decided and dropped cannot be reconsidered when a straggler arrives, so the straggler is dropped too. If the straggler is the root span carrying the error status, the sampler has dropped an error trace because the error arrived after the deadline. Widening the window reduces this, and so does ordering the decision to wait for the root specifically rather than for a fixed time from the first span.

Third is the interaction with the sampled flag. A tail sampler downstream of a head sampler only sees traces the head sampler kept, so its error-retention guarantee applies to that subset. If the head rate is one percent and the tail sampler is configured to keep all error traces, it keeps all error traces among the one percent it received. Whether that is acceptable depends on the error rate: at a one percent error rate, a one percent head rate yields one error trace per ten thousand requests, which may be enough to characterise the failure and is definitely not enough to count it. This is why head and tail rates are chosen together and why the head rate is sometimes raised specifically to feed the tail stage.

The storage and consistency cost

The kept traces are written to a store that must be able to answer queries by trace identifier and by service-and-time. Tail sampling does not change the query shape, but it changes the write pattern: writes arrive in bursts when decisions are made rather than steadily as spans arrive, and a burst is one whole trace, which is a few dozen to a few thousand records that must be written together to be useful. A store that batches by time rather than by trace identifier produces writes that are scattered across the trace’s duration, which slows the read-back.

There is also a consistency issue across the pipeline. A span that was sampled at the head and forwarded, then dropped at the tail, has been counted as sampled by the head sampler’s statistics. The two rates multiply, and any count rescaling must use the product, not either rate alone. Recording the effective decision as an attribute on the retained spans, rather than relying on configuration knowledge, is the only way to keep historical data interpretable after a rate change; the metadata channel for that kind of per-trace annotation is the baggage header, though it is carried forward only for traces that survive.

When the complexity is not worth it

Tail sampling buys outcome-aware retention and costs a stateful, hash-routed, memory-bounded layer that must be operated as a cluster. For a system where failures are common enough that head sampling retains plenty of them, or where the diagnostic workflow is based on aggregate latency rather than individual traces, the tail stage adds operational surface without changing what can be answered. It earns its place when the question is “show me a trace of the slowest request in the last hour” or “keep every trace that returned a 500”, because those questions cannot be answered from a sample chosen before the answer existed.