TraceState: Probability Sampling

Overview

Probability sampling allows OpenTelemetry tracing users to lower span collection costs by the use of randomized sampling techniques. The objectives are:

Compatible with the existing W3C trace context sampled flag
Spans can be accurately counted using a Span-to-metrics pipeline
Traces tend to be complete, even though spans may make independent sampling decisions.

This document specifies an approach based on an “r-value” and a “p-value”. At a very high level, r-value is a source of randomness and p-value encodes the sampling probability. A context is sampled when p <= r.

Significantly, by including the r-value and p-value in the OpenTelemetry tracestate, these two values automatically propagate through the context and are recorded on every Span. This allows Trace consumers to correctly count spans simply by interpreting the p-value on a given span.

For efficiency, the supported sampling probabilities are limited to powers of two. P-value is derived from sampling probability, which equals 2**-p, thus p-value is encoded using an unsigned integer.

For example, a p-value of 3 indicates a sampling probability of 1/8.

Since the W3C trace context does not specify that any of the 128 bits in a TraceID are true uniform-distributed random bits, the r-value is introduced as an additional source of randomness.

The recommended method of generating an “r-value” is to count the number of leading 0s in a string of 62 random bits, however, it is not required to use this approach.

Definitions

Sampling

Sampling is a family of techniques for collecting and analyzing only a fraction of a complete data set. Individual items that are “sampled” are taken to represent one or more spans when collected and counted. The representivity of each span is used in a Span-to-Metrics pipeline to accurately count spans.

Sampling terminology uses “population” to refer to the complete set of data being sampled from. In OpenTelemetry tracing, “population” refers to all spans.

In probability sampling, the representivity of individual sample items is generally known, whereas OpenTelemetry also recognizes “non-probability” sampling approaches, in which representivity is not explicitly quantified.

Adjusted count

Adjusted count is a measure of representivity, the number of spans in the population that are represented by the individually sampled span. Span-to-metrics pipelines can be built by adding the adjusted count of each sample span to a counter of matching spans.

For probability sampling, adjusted count is defined as the reciprocal (i.e., mathematical inverse) of sampling probability.

For non-probability sampling, adjusted count is unknown.

Zero adjusted count is defined in a way that supports composition of probability and non-probability sampling. Zero is assigned as the adjusted count when a probability sampler does not select a span.

Thus, there are three meaningfully distinct categories of adjusted count:

Adjusted count is	Interpretation
Unknown	The adjusted count is not known, possibly as a result of a non-probability sampler. Items in this category should not be counted.
Zero	The adjusted count is known; the effective count of the item is zero.
Non-zero	The adjusted count is known; the effective count of the item is greater than zero.

Sampler

A Sampler provides configurable logic, used by the SDK, for selecting which Spans are “recorded” and/or “sampled” in a tracing client library. To “record” a span means to build a representation of it in the client’s memory, which makes it eligible for being exported. To “sample” a span implies setting the W3C sampled flag, recording the span, and exporting the span when it is finished.

OpenTelemetry supports spans that are “recorded” and not “sampled” for in-process observability of live spans (e.g., z-pages).

The Sampler interface and the built-in Samplers defined by OpenTelemetry decide immediately whether to sample a span, and the child context immediately propagates the decision.

Parent-based sampler

A Sampler that makes its decision to sample based on the W3C sampled flag from the context is said to use parent-based sampling.

Probability sampler

A probability Sampler is a Sampler that knows immediately, for each of its decisions, the probability that the span had of being selected.

Sampling probability is defined as a number less than or equal to 1 and greater than 0 (i.e., 0 < probability <= 1). The case of 0 probability is treated as a special, non-probabilistic case.

Consistent probability sampler

A consistent probability sampler is a Sampler that supports independent sampling decisions at each span in a trace while maintaining that traces will be complete with a certain minimum probability across the trace.

Consistent probability sampling requires that for any span in a given trace, if a Sampler with lesser sampling probability selects the span for sampling, then the span would also be selected by a Sampler configured with greater sampling probability.

Trace completeness

A trace is said to be complete when all of the spans belonging to the trace are collected. When at least one span is collected but not all spans are collected, the trace is considered incomplete.

Trace incompleteness may happen on purpose (e.g., through sampling configuration), or by accident (e.g., through collection errors). The OpenTelemetry trace data model supports a one-way test for incompleteness: for any non-root span, the trace is definitely incomplete if the span’s parent span was not collected.

Incomplete traces that result from sampling configuration (i.e., on purpose) are known as partial traces. An important subset of the partial traces are those which are also complete subtraces. A complete subtrace is defined at span S when every descendent span is collected.

Since the test for an incompleteness is one-way, it is important to know which sampling configurations may lead to incomplete traces. Sampling configurations that lead naturally to complete traces and complete subtraces are discussed below.

Non-probability sampler

A non-probability sampler is a Sampler that makes its decisions not based on chance, but instead uses arbitrary logic and internal state. The adjusted count of spans sampled by a non-probability sampler is unknown.

Always-on consistent probability sampler

An always-on sampler is another name for a consistent probability sampler with probability equal to one.

Always-off sampler

An always-off Sampler has the effect of disabling a span completely, effectively excluding it from the population. This is defined as a non-probability sampler, not a zero-percent probability sampler, because the spans are effectively unrepresented.

Consistent Probability sampling

The consistent sampling scheme adopted by OpenTelemetry propagates two values via the context, termed “p-value” and “r-value”.

Both fields are propagated via the OpenTelemetry tracestate under the ot vendor tag using the rules for tracestate handling. Both fields are represented as unsigned decimal integers requiring at most 6 bits of information.

This sampling scheme selects items from among a fixed set of 63 distinct probability values. The set of supported probabilities includes the integer powers of two between 1 and 2**-62. Zero probability and probabilities smaller than 2**-62 are treated as a special case of “ConsistentAlwaysOff” sampler, just as unit probability (i.e., 100%) describes a special case of “ConsistentAlwaysOn” sampler.

R-value encodes which among the 63 possibilities will consistently decide to sample for a given trace. Specifically, r-value specifies the smallest probability that will decide to sample a given trace in terms of the corresponding p-value. For example, a trace with r-value 0 will sample spans configured for 100% sampling, while r-value 1 will sample spans configured for 50% or 100% sampling, and so on through r-value 62, for which a consistent probability sampler will decide “yes” at every supported probability (i.e., greater than or equal to 2**-62).

P-value encodes the adjusted count for child contexts (i.e., consumers of tracestate) and consumers of sampled spans to record for use in Span-to-metrics pipelines. A special p-value of 63 is defined to mean zero adjusted count, which helps define composition rules for non-probability samplers.

An invariant will be stated that connects the sampled trace flag found in traceparent context to the r-value and p-value found in tracestate context.

Conformance

Consumers of OpenTelemetry tracestate data are expected to validate the probability sampling fields before interpreting the data. This applies to the two samplers specified here as well as consumers of span data, who are expected to validate tracestate before interpreting span adjusted counts.

Producers of OpenTelemetry tracestate containing p-value and r-value fields are required to meet the behavioral requirements stated for the ConsistentProbabilityBased sampler and to ensure statistically valid outcomes. A test suite is included in this specification so that users and consumers of OpenTelemetry tracestate can be assured of accuracy in Span-to-metrics pipelines.

Completeness guarantee

This specification defines consistent sampling for power-of-two sampling probabilities. When a sampler is configured with a non-power-of-two sampling probability, the sampler will probabilistically choose between the nearest powers of two.

When a single consistent probability sampler is used at the root of a trace and all other spans use a parent-based sampler, the resulting traces are always complete (ignoring collection errors). This property holds even for non-power-of-two sampling probabilities.

When multiple consistent probability samplers are used in the same trace, in general, trace completeness is ensured at the smallest power of two greater than or equal to the minimum sampling probability across the trace.

Context invariants

The W3C traceparent (version 0) contains three fields of information: the TraceId, the SpanId, and the trace flags. The sampled trace flag has been defined by W3C to signal an intent to sample the context.

The Sampler API is responsible for setting the sampled flag and the tracestate.

P-value and r-value are set in the OpenTelemetry tracestate, under the vendor tag ot, using the identifiers p and r. P-value is an unsigned integer valid in the inclusive range [0, 63] (i.e., there are 64 valid values). R-value is an unsigned integer valid in the inclusive range [0, 62] (i.e., there are 63 valid values). P-value and r-value are independent settings, each can be meaningfully set without the other present.

Sampled flag

Probability sampling uses additional information to enable consistent decision making and to record the adjusted count of sampled spans. When both values are defined and in the specified range, the invariant between r-value and p-value and the sampled trace flag states that ((p <= r) == sampled) OR (sampled AND (p == 63)) == TRUE.

The invariant between sampled, p, and r only applies when both p and r are present. When the invariant is violated, the sampled flag takes precedence and p is unset from tracestate in order to signal unknown adjusted count.

Requirement: Inconsistent p-values are unset

Samplers SHOULD unset p when the invariant between the sampled, p, and r values is violated before using the tracestate to make a sampling decision or interpret adjusted count.

P-value

Zero adjusted count is represented by the special p-value 63, otherwise the p-value is set to the negative base-2 logarithm of sampling probability:

p-value	Parent Probability	Adjusted count
0	1	1
1	1/2	2
2	1/4	4
…	…	…
N	2**-N	2**N
…	…	…
61	2**-61	2**61
62	2**-62	2**62
63	0	0

Requirement: Out-of-range p-values are unset

Consumers SHOULD unset p from the tracestate if the unsigned decimal value is greater than 63 before using the tracestate to make a sampling decision or interpret adjusted count.

R-value

R-value is set in the tracestate by the Sampler at the root of the trace, in order to support consistent probability sampling. When the value is omitted or not present, child spans in the trace are not able to participate in consistent probability sampling.

R-value determines which sampling probabilities will decide to sample or not decide to sample for spans of a given trace, as follows:

r-value	Implied sampling probabilities
0	1
1	1/2 and above
2	1/4 and above
3	1/8 and above
…	…
0 <= r <= 61	2**-r and above
…	…
59	2**-59 and above
60	2**-60 and above
61	2**-61 and above
62	2**-62 and above

These probabilities are specified to ensure that conforming Sampler implementations record spans with correct adjusted counts. The recommended method of generating r-values is to count the number of leading 0s in a string of 62 random bits, however it is not required to use this approach.

Requirement: Out-of-range r-values unset both p and r

Samplers SHOULD unset both r and p from the tracestate if the unsigned decimal value of r is greater than 62 before using the tracestate to make a sampling decision.

Requirement: R-value is generated with the correct probabilities

Samplers MUST generate r-values using a randomized scheme that produces each value with the probabilities equivalent to those produced by counting the number of leading 0s in a string of 62 random bits.

Examples: Context invariants

Example: Probability sampled context

Consider a trace context with the following headers:

traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-01
tracestate: ot=r:3;p:2

The traceparent contents in this example example are repeated from the W3C specification) and have the following base64-encoded field values:

base16(version) = 00
base16(trace-id) = 4bf92f3577b34da6a3ce929d0e0e4736
base16(parent-id) = 00f067aa0ba902b7
base16(trace-flags) = 01  // (i.e., sampled)

The tracestate header contains OpenTelemetry string r:3;p:2, containing decimal-encoded p-value and r-value:

base10(r) = 3
base10(p) = 2

Here, r-value 3 indicates that a consistent probability sampler configured with probability 12.5% (i.e., 1-in-8) or greater will sample the trace. The p-value 2 indicates that the parent that set the sampled flag was configured to sample at 25% (i.e., 1-in-4). This trace context is consistent because p <= r is true and the sampled flag is set.

Example: Probability unsampled

This example has an unsampled context where only the r-value is set.

traceparent: 00-4bf92f3577b34da6a3ce929d0e0e4736-00f067aa0ba902b7-00
tracestate: ot=r:3

This supports consistent probability sampling in child contexts by virtue of having an r-value. P-value is not set, consistent with an unsampled context.

Samplers

ParentConsistentProbabilityBased sampler

The ParentConsistentProbabilityBased sampler is meant as an optional replacement for the ParentBased Sampler. It is required to first validate the tracestate and then respect the sampled flag in the W3C traceparent.

Requirement: ParentConsistentProbabilityBased API

The ParentConsistentProbabilityBased Sampler constructor SHOULD take a single Sampler argument, which is the Sampler to use in case the ParentConsistentProbabilityBased Sampler is called for a root span.

Requirement: ParentConsistentProbabilityBased does not modify valid tracestate

The ParentConsistentProbabilityBased Sampler MUST NOT modify a valid tracestate.

Requirement: ParentConsistentProbabilityBased calls the configured root sampler for root spans

The ParentConsistentProbabilityBased Sampler MUST delegate to the configured root Sampler when there is not a valid parent trace context.

Requirement: ParentConsistentProbabilityBased respects the sampled flag for non-root spans

The ParentConsistentProbabilityBased Sampler MUST decide to sample the span according to the value of the sampled flag in the W3C traceparent header.

ConsistentProbabilityBased sampler

The ConsistentProbabilityBased sampler is meant as an optional replacement for the TraceIdRatioBased Sampler. In the case where it is used as a root sampler, the ConsistentProbabilityBased sampler is required to produce a valid tracestate. In the case where it is used in a non-root context, it is required to validate the incoming tracestate and to produce a valid tracestate for the outgoing context.

The ConsistentProbabilityBased sampler is required to support probabilities that are not exact powers of two. To do so, implementations are required to select between the nearest powers of two probabilistically. For example, 5% sampling can be achieved by selecting 1/16 sampling 60% of the time and 1/32 sampling 40% of the time.

Requirement: TraceIdRatioBased API compatibility

The ConsistentProbabilityBased Sampler MUST have the same constructor signature as the built-in TraceIdRatioBased sampler in each OpenTelemetry SDK.

Requirement: ConsistentProbabilityBased sampler sets r for root span

The ConsistentProbabilityBased Sampler MUST set r when it makes a root sampling decision.

Requirement: ConsistentProbabilityBased sampler unsets p when not sampled

The ConsistentProbabilityBased Sampler MUST unset p from the tracestate when it decides not to sample.

Requirement: ConsistentProbabilityBased sampler sets p when sampled

The ConsistentProbabilityBased Sampler MUST set p when it decides to sample according to its configured sampling probability.

Requirement: ConsistentProbabilityBased sampler records unbiased adjusted counts

The ConsistentProbabilityBased Sampler with non-zero probability MUST set p so that the adjusted count interpreted from the tracestate is an unbiased estimate of the number of representative spans in the population.

Requirement: ConsistentProbabilityBased sampler sets r for non-root span

If r is not set on the input tracecontext and the Span is not a root span, ConsistentProbabilityBased SHOULD set r as if it were a root span and warn the user that a potentially inconsistent trace is being produced.

Requirement: ConsistentProbabilityBased sampler decides not to sample for probabilities less than 2**-62

If the configured sampling probability is in the interval [0, 2**-62), the Sampler MUST decide not to sample.

Examples: Consistent probability samplers

Example: Setting R-value for a root span

A new root span is sampled by a consistent probability sampler at 25%. A new r-value should be generated (see the appendix for suitable methods), in this example r-value 5 is used which happens 1.5625% of the time and indicates to sample:

tracestate: ot=r:5;p:2

The span would be sampled because p-value 2 is less than or equal to r-value 5. An example tracestate where r-value 1 indicates not to sample at 25%:

tracestate: ot=r:1

This span would not be sampled because p-value 2 (corresponding with 25% sampling) is greater than r-value 1.

Example: Handling inconsistent P-value

When either the consistent probability sampler or the parent-based consistent probability sampler receives a sampled context but invalid p-value, for example,

tracestate: ot=r:4;p:73

the tracestate will have its p-value stripped. The r-value is kept, and the sampler should act as if the following had been received:

tracestate: ot=r:4

The consistent probability sampler will make its own (consistent) decision using the r-value that was received.

The parent-based consistent probability sampler will in this case follow the sampled flag. If the context is sampled, the resulting span will have an r-value without a p-value, which indicates unknown adjusted count.

Example: Handling corrupt R-value

A non-root span receives:

tracestate: ot=r:100;p:10

where the r-value is out of its valid range. The r-value and p-value are stripped during validation, according to the invariants. In this case, the sampler will act as though no tracestate were received.

The parent-based consistent probability sampler will sample or not sample based on the sampled flag, in this case. If the context is sampled, the recorded span will have an r-value without a p-value, which indicates unknown adjusted count.

The consistent probability sampler will generate a new r-value and make a new sampling decision while warning the user of a corrupt and potentially inconsistent r-value.