Tail-based consistent sampling
Clearly, head-based sampling has its benefits and its challenges. It is fairly simple to implement, yet far from simple to manage at scale. There is one other drawback of head-based sampling that we have not discussed yet: its inability to tune the sampling decision to the behavior of the system captured in the traces. Let's assume our metrics system tells us that the 99.9th percentile of the request latency in a service is very high. It means that only one in a thousand requests on average exhibits the anomalous behavior. If we are tracing with head-based sampling and 0.001 probability, we have one in a million chance that we will sample one of these anomalous requests and capture the trace that might explain the anomaly.
Although we could say that one in a million is not that low, given how much traffic goes through modern cloud-native applications, and we probably will capture some of those interesting traces, it also means that the remaining 999 traces out...