# TraceState: Probability Sampling

**Status**: Experimental

## 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.