OTEP-0170: テレメトリイベントの確率的サンプリング

目的: OpenTelemetryにおけるサンプリング手法の基盤を規定します。

Motivation

確率的サンプリングにより、サンプリングされたテレメトリデータの利用者は、テレメトリイベントの一部を収集し、それを使ってイベント母集団に関する合計量（たとえば特定の属性を持つイベントの合計発生率など）を推定できます。

これらの手法により、テレメトリ収集のコストを、プロデューサー（つまりSDK）とプロセッサー（つまりCollector）の両方について削減しつつ、（少なくとも大まかには）システム全体を監視する能力を失わずに済みます。

サンプリングは確率論の成果の上に成り立っています。 確率的サンプルから導かれる推定値は、真の値に等しくなることが期待される 確率変数 です。 サンプリングロジックのサンプルを計算するために使われる項目のすべての潜在的な組み合わせが等しく起こりうる場合、つまりすべての結果が等しく起こりうる場合、そのサンプルは 不偏 であるといいます。

不偏サンプルは事後分析に利用できます。 「プロパティXを持つイベントの割合は？」といった問いに、サンプル中でプロパティXを持つイベントの割合を使って答えることができます。

本書では、サンプルテレメトリデータのプロデューサーとコンシューマーが、サンプルがどのように計算されたかという情報を伝えることなく、テレメトリイベントの合計数に関する推定値を伝える方法について、調整カウント (adjusted count) と呼ばれる量を使って概説します。 一般的な言葉で言えば、「N回に1回」のサンプリング方式は、調整カウントがNに等しいイベントを発生させます。 調整カウントとは、個々のサンプルイベントが表す母集団におけるイベント数の期待値です。

Examples

これらの例では、サンプリング確率を伝えるために sampler.adjusted_count という属性を使用します。 調整カウントが付与されたスパン、メトリクス、ログの利用者は、サンプリング設定の詳細を知らなくても、イベント母集団全体について正確な統計を計算できます。

仮想の sampler.adjusted_count 属性は、この概念を示すためにこれらの例全体で使用されていますが、以下で述べるOpenTelemetryの Span メッセージに対する提案では、親サンプリング確率を伝えるための特定の解釈を持つ専用フィールドが導入されます。

Span sampling

スパンの確率的サンプリングの例としてのユースケースは、一般にスパンからメトリクスを生成することに関わります。

Sample spans to Counter Metric

この例では、トレーシング用のOpenTelemetry SDKに、処理されるサンプルスパンをその調整カウントに基づいてカウントする SpanProcessor が設定されています。 このSDKは、たとえばPrometheusを使ってリクエストレートを監視するために使用できます。

受信した完了済みのサンプルスパンごとに、この例の SpanProcessor は、スパン名 S に対応する S_count という名前のCounterが元のスパンごとに1回インクリメントされたかのようにメトリクスデータを合成します。 代わりにサンプリングされたスパンの調整カウントを使うことで、S_count の値はスパンの真の数に等しくなることが期待されます。

この SpanProcessor は、受信したスパンごとに、そのスパンの調整カウントを対応するメトリクスCounterインストゥルメントに加算します。 たとえばOpenTelemetry Metrics APIを直接使用すると、次のようになります。

func (p *spanToMetricsProcessor) OnEnd(span trace.ReadOnlySpan) {
    ctx := context.Background()
    counter := p.meter.NewInt64Counter(span.Name() + "_count")
    counter.Add(
        ctx,
        span.AdjustedCount(),
        span.Attributes()...,
            )
}

Sample spans to Histogram Metric

受信したスパンごとに、この例のプロセッサーは、スパン名 S に対する S_duration という名前のHistogramインストゥルメントが元のスパンごとに1回観測されたかのようにメトリクスデータを合成します。

OpenTelemetryのメトリクスデータモデルは、非整数カウントのヒストグラムバケットをサポートしていないため、ここでは整数の調整カウント（つまりNが整数の「N回に1回」のサンプリング率）を使用せざるを得ません。

論理的に言えば、このプロセッサーは、受信したサンプルスパンごとに、そのスパンの継続時間を 調整カウント の回数だけ観測します。 そのため、この例では、Histogramの測定値の複数の観測結果を一度に取り込むために、仮想の RecordMany() メソッドを使用します。

    histogram := p.meter.NewFloat64Histogram(
        span.Name() + "_duration",
        metric.WithUnits("ms"),
    )
    histogram.RecordMany(
        ctx,
        span.Duration().Milliseconds(),
        span.AdjustedCount(),
        span.Attributes()...,
    )

Sample span rate limiting

あるCollectorプロセッサーは、完全なデータフレームを受信したことを保証するためにわずかな遅延を導入し、その間、完了済みの入力スパンの固定サイズバッファーを維持します。 受信したスパンの数が間隔の終了前にバッファーのサイズを超えた場合、各スパンの調整カウントを入力重みとして使う重み付きサンプリングを開始します。

このプロセッサーは、設定されたレートの閾値を超えるとスパンをドロップし、そうでなければ調整カウントを変更せずにスパンを通過させます。

間隔が終了し、サンプルフレームが完了したとみなされると、選択されたサンプルスパンは、更新されている可能性のある調整カウントとともに出力されます。

Explanation

1つ以上の関連する数値を含むデータ項目のストリームが生成される、仮想のテレメトリシグナルを考えてみます。 OpenTelemetryのメトリクスデータモデルの用語を使うと、サンプリングが一般的な2つのシナリオがあります。

1. Counterイベント: 各イベントはカウントを表し、合計の変化を意味します。
2. Histogramイベント: 各イベントは個々の変数を表し、分布へのメンバーシップを意味します。

トレーシングのスパンイベントは、これら両方のケースに同時に該当します。 1つのスパンは、少なくとも1つのCounterイベント（たとえば1つのリクエスト、読み取られたバイト数）と、少なくとも1つのHistogramイベント（たとえばリクエストのレイテンシ、リクエストのサイズ）の両方として解釈できます。

メトリクスにおいては、StatsdのCounterイベントとHistogramイベントがこの定義を満たします。

どちらの場合も、サンプリングの目標は、サンプルで選択されたイベントのみを使って、母集団全体（つまりすべてのイベント）におけるイベント数を推定することです。

Model and terminology

このモデルは、APIの境界における個々のイベントが収集のためにサンプリングされるようなテレメトリ収集の状況に適用されることを意図しています。 個々のAPIレベルのイベントをサンプリングするプロセスを理解した後、これらの手法を集計データのサンプリングに適用する方法を学んでいきます。

サンプリングにおいて、サンプリング設計 (sampling design) という用語はサンプリング確率がどのように決定されるかを指し、サンプルフレーム (sample frame) という用語はイベントが離散的な母集団にどのように編成されるかを指します。 サンプリング戦略の設計は、母集団がどのようにフレーミングされるかを決定します。

たとえば、単純な設計は均一な確率を使用し、単純なフレーミング手法は、1時間ごとに個別のスパン名ごとに1つのサンプルを収集することです。 別のサンプルフレーミングでは、10分ごとにすべてのスパン名にわたって1つのサンプルを収集することもできます。

あるフレームに対してサンプリング設計を実行すると、サンプルで選択された各項目は、その項目が選択される可能性を決定する既知の 包含確率 (inclusion probability) を持つことになります。 暗黙的に、サンプルに選択されなかったすべての項目は包含確率がゼロになります。

サンプリング設計を説明するためによく使われる記述語を以下に示します。

• Fixed（固定）: サンプリング設計がフレームごとに同じである
• Adaptive（適応的）: サンプリング設計が観測されたデータに基づいてフレームごとに変化する
• Equal-Probability（等確率）: サンプリング設計がフレームごとに単一の包含確率を使用する
• Unequal-Probability（不等確率）: サンプリング設計がフレームごとに複数の包含確率を使用する
• Reservoir（リザーバー）: サンプリング設計が固定された空間を使用し、固定サイズの出力を持つ

私たちの目標は、テレメトリデータのプロデューサーがサンプリング設計を選択する際の柔軟性をサポートしつつ、サンプリングされたテレメトリデータの利用者が使用されたサンプリング設計に依存しないようにすることです。

Sampling without replacement

私たちが関心を持っているのは、テレメトリ収集における一般的なケース、つまりイベントのストリームを処理しながらサンプリングが行われ、各イベントがちょうど1回だけ検討されるケースです。 この形式のサンプリング設計は 非復元抽出 (sampling without replacement) と呼ばれます。 特に断りのない限り、テレメトリ収集における「サンプリング」は常に非復元抽出を指します。

完全なデータフレームに対してあるサンプリング設計を実行すると、その結果は、それぞれが既知の非ゼロの包含確率を持つ、選択されたサンプルイベントの集合になります。 サンプルフレームからサンプルを計算した後には、他にもいくつか関心のある量があります。

• サンプルサイズ (Sample size): 非ゼロの包含確率を持つイベントの数
• 真の母集団合計 (True population total): フレーム内のイベントの正確な数。未知の場合がある
• 推定母集団合計 (Estimated population total): フレーム内のイベントの推定数。サンプルから計算される

サンプルサイズは計算された後には常に既知ですが、そのサイズが事前にわかっているかどうかは設計によって異なります。 確率的サンプリング方式では、推定母集団合計が真の母集団合計の期待値に等しいことが要求されます。

Adjusted sample count

上記のモデルに従うと、すべてのイベントは 調整カウント という概念を定義します。

• イベントがサンプルに選択されなかった場合、調整カウント はゼロです。
• そうでない場合、調整カウント はその包含確率の逆数です。

イベントの調整カウントは、個々のイベントによって表されるサンプルフレームの推定母集団合計に対する期待される寄与を表します。

包含確率の逆数を使用することは、確率に対する私たちの直感と一致します。 おおよそ言えば、「N分の1」の包含確率で選択された項目は、それぞれNとしてカウントされます。

この直感は統計学によって裏付けられています。 この式は母集団合計のHorvitz-Thompson推定量として知られており、すべての 非復元 サンプリング設計に適用できる汎用の統計的「推定量」です。

サンプルデータが正しく計算されていると仮定すると、サンプルデータの利用者は、すべてのサンプルイベントを、それ自身と同一のコピーが 調整カウント 回発生したかのように扱うことができます。 すべてのサンプルイベントは、調整カウント個分の自分自身のコピーを代表しています。

これが機能するためには、1つの本質的な要件があります。 選択手順は 統計的に不偏 でなければならず、これはそのプロセスがすべての起こりうる結果を等しく考慮することが求められることを意味する用語です。

Sampling and variance

上記で概説した不偏サンプリングを使用することで、個々のサンプルにはそれぞれ独立して調整カウントが割り当てられているため、サンプルの任意の部分集合について母集団合計を推定することが可能になります。

統計的バイアスと分散の間には自然な関係があります。 近似的なカウントには分散が伴いますが、これはサンプルサイズによって制御できる事実です。 不偏サンプルにおいて分散は避けられませんが、サンプルサイズが大きくなるにつれて分散は小さくなります。

これは、期待される分散の高さから小さなサンプルサイズが問題であるかのように聞こえるかもしれませんが、これは単にこの手法の制約に過ぎません。 分散が高い場合は、より大きなサンプルサイズを使用してください。

分散を下げるための簡単なアプローチは、時間をまたいでサンプルフレームを集約することで、これにより一般にカウント対象の部分母集団のサイズが大きくなります。 たとえば、1分間のサンプルから引き出された個別名別のスパンレートの推定値は分散が高いかもしれませんが、1時間分の1分間サンプルフレームを1つの集計データセットにまとめると、（スパン名の数が固定されていると仮定すれば）分散が低下することが保証されます。 これは必然です。 なぜなら、データは不偏のままであるため、データが多いほど分散は低くなるからです。

Conveying the sampling probability

調整カウントや包含確率をエンコードするいくつかの方法を、状況やプロトコルに応じて以下で議論します。 ここでは、特定の種類のイベントに限らず、サンプリングされたテレメトリイベント全般をどのようにカウントするかに焦点を当てます。 次のセクションで見るように、トレーシングにはさらなる複雑さが伴います。

この調整カウントまたは包含確率をエンコードする方法はいくつかあります。

• OTLPのprotobufメッセージ内の専用フィールドとして
• OTLPのSpan、Metric、Log内の非記述的な属性として
• 専用フィールドを設けない方法

Encoding adjusted count

調整カウントを、範囲 [0, +Inf) の浮動小数点数または整数として直接エンコードすることができます。 数値が大きいほど代表性が高いことを意味するため、これは概念的にサンプリングを理解しやすい方法です。

この説明を踏まえると、整数ではない調整カウントが生成される可能性があることに注意してください。 調整カウントは近似値であり、整数の期待値は分数のカウントになりうるからです。 整数の逆数となる包含確率を使用すれば、浮動小数点の調整カウントを避けることができます。

Encoding inclusion probability

包含確率を、範囲 [0, 1) の浮動小数点数として直接エンコードすることができます。 これはStatsd形式に典型的な方法で、各行にオプションの確率が含まれます。 この文脈では、この確率は一般に「サンプリングレート」とも呼ばれます。 この場合、数値が小さいほど代表性が高いことを意味します。

Encoding base-2 logarithm of adjusted count

調整カウントの底2の対数（つまり包含確率の底2の対数の負の値）をエンコードすることができます。 整数フィールドを使用し、調整カウントと包含確率を2のべき乗に制限することで、小さな非負整数を使って調整カウントをエンコードできるようになります。 この場合、数値が大きいほど指数関数的に代表性が高いことを意味します。

Multiply the adjusted count into the data

メトリクスのSumやHistogramのポイントのように、データ自体がカウントを保持している場合、調整カウントをそのデータに掛け合わせることができます。

この手法は、カウントや合計の期待値は保存されるものの、データが分散に関する情報を失ってしまうため、あまり望ましくありません。 また、調整カウントが整数値でない場合、丸め誤差が生じる可能性もあります。

Trace Sampling

サンプリング手法は常にデータ収集と分析のコストを下げることを目的としていますが、特にトレースの収集と分析においては、Tracerのオーバーヘッドを削減するかどうかによってアプローチを分類できます。 Tracerのオーバーヘッドは、サンプリングされないトレースのスパンを記録しないことで削減され、これには、新しいスパンコンテキストが作成された時点、場合によってはすべての属性がわかる前にサンプリングの決定を行うことが必要です。

トレースは、そのトレースの一部であったすべてのスパンが収集されたときに完全であるといいます。 Tracerのオーバーヘッドを削減するためにサンプリングが適用される場合、一般に完全なトレースが引き続き生成されることが期待されます。 Tracerのオーバーヘッドを下げつつ完全なトレースを生成するサンプリング手法は、ヘッドトレースサンプリング (Head trace sampling) 手法として知られています。

不完全なトレースを避けるためには、サンプルトレースを生成し収集するかどうかの決定は、ルートスパンが開始する時点で行わなければなりません。 そして、完全なトレースを収集できると仮定すると、ルートスパンの調整カウントが、トレース内のすべてのスパンの調整カウントを決定します。

Counting child spans using root span adjusted counts

ルートスパンの調整カウントは、次のロジックに基づいて、その各子スパンの調整カウントを決定します。

• ルートスパンは不偏サンプリングを使って選択されたため、adjusted_count 個分の同一のルートスパンを代表するとみなされます
• コンテキストの伝播は 因果関係 (causation)、つまりあるスパンが別のスパンを生み出すという事実を伝えます
• ルートスパンは、そのトレース内の各子スパンが生成される原因となります
• サンプリングされたルートスパンは adjusted_count 個分のトレースを代表し、サンプリングされたトレース内の子スパンごとに adjusted_count 回分の発生の原因を表します

この推論を使うことで、システム内のすべてのルートスパンから収集されたサンプルを定義でき、これにより母集団内のすべてのスパンの数を推定できるようになります。 ルートスパンの単純な確率サンプルを取ることを考えます。

1. ルートスパンに対する Sampler の決定では、初期のスパンプロパティを使って包含確率 P を決定します
2. 確率 P で疑似ランダムな選択を行い、真であれば RECORD_AND_SAMPLE を返します（これにより、すべての子コンテキストでW3C Trace Contextの is-sampled フラグが設定されます）
3. ルートスパンに 1/P に等しいスパン調整カウント属性をエンコードします
4. W3C Trace Contextの is-sampled フラグが設定されているすべてのスパンを収集します

サンプリングされたすべてのスパンを収集した後、それぞれについてルートスパンを特定します。 ルートスパンの調整カウントを、関連するトレース内のすべての子スパンに適用します。 サンプリングされたすべてのスパンの調整カウントの合計は、母集団のスパンの総数に等しくなることが期待されます。

サンプルスパンをその調整カウントとともに保存し、乱数源が十分に良質であると仮定すれば、サンプリングされたスパンに対する任意のクエリを使って母集団のカウントを外挿できます。 サンプリングされたスパンは、その調整カウントがわかった後、スパンの母集団に対する近似的なメトリクスに変換できます。

ルートスパンの調整カウントのみを使うこの分析のコストは、ルート以外のスパンをカウントする前に、すべてのルートスパンを収集しなければならないという点にあります。 ルートスパンの調整カウントをインデックス化し検索するコストにより、この分析をリアルタイムで実行することは比較的高コストになります。

Using parent sampling probability to count all spans

Samplerにおいて RECORD_AND_SAMPLE を返すかどうかを決定するためにW3Cの is-sampled フラグが使用される場合、ルートスパンを先に特定することなくサンプルスパンをカウントするには、親サンプリング確率に関する情報をコンテキストを通じて伝播させる必要があります。 ルートの代わりに親サンプリング確率を使用することで、トレース内の個々のスパンは、ParentBased サンプラーを使うサブトレース内の子孫のサンプリング確率を制御できるようになります。 このような手法は 親サンプリング (parent sampling) 手法と呼ばれます。

親サンプリング確率は、子スパンがサンプリングされる原因となる確率と考えることができます。 この変数を維持するPropagatorは、条件付き確率の規則に従わなければなりません（MUST）。 このモデルでは、各スパンの調整カウントは、トレース内のルートの調整カウントではなく、その親の調整カウントに依存します。 それでも、サンプリングされたすべてのスパンの調整カウントの合計は、母集団のスパンの総数に等しくなることが期待されます。

これは、親サンプリング確率を保持するコンテキスト内で発生する（つまり引き起こされる）他の形式のテレメトリにも適用されます。 たとえば、ログイベントやメトリクスのエグゼンプラーが生成される際に、現在の親サンプリング確率の逆数に等しい調整カウントを付けて記録することができます。

この手法により、ルートスパンを先に特定することなく、スパンやログをメトリクスに変換できるようになり、ルートスパンを先に収集してインデックス化する場合と比べて大きなパフォーマンス上の利点があります。

いくつかの親サンプリング手法について、以下のセクションで議論し、次のすべての基準を満たす能力の観点から評価します。

• Tracerのオーバーヘッドを削減する
• 完全なトレースを生成する
• スパンがカウント可能である

Parent sampling for traces

上記で述べた要件を満たすSampler実装についての詳細です。

Parent Sampler

Parent サンプラーは、すべてのスパンが正常に記録されていれば、完全なトレースを保証します。 Parent サンプリングの欠点は、トレース内のルート以外のスパンからTracerのオーバーヘッドに対する制御を奪ってしまうことです。 リアルタイムのspan-to-metricsアプリケーションをサポートするには、このSamplerは、子スパンを開始する時点で有効なコンテキストのサンプリング確率または調整カウントを伝播させる必要があります。 これについては OTEP 168（作業中） でさらに詳しく説明されています。

親サンプリング確率を伝播する際、Parent サンプラーによって記録されたスパンは、sampler.adjusted_count という名前のSpan属性を使って、対応する SpanData に調整カウントをエンコードすることができます。

TraceIDRatio Sampler

OpenTelemetryのトレーシング仕様には、TraceIDに基づく決定論的なサンプリング決定を使用する確率的サンプリング用に設計された組み込みのSamplerが含まれています。 このSamplerは、OpenTelemetryバージョン1.0の仕様がリリースされる前には完成しておらず、TODOとトレースのルートのみに使用することを推奨する注記 を付けたまま残されました。 OTEP 135はその解決策を提案しました。

TraceIDRatio サンプラーの目標は、トレーシングの決定を協調させつつ、各サービスにTracerのオーバーヘッドに対する制御を与えることです。 各サービスは独立してサンプリング確率を設定し、協調された決定によって一部のトレースが完全になることが保証されます。 トレースは、TraceID比がトレース全体にわたる最小のSampler確率を下回るときに完全になります。 TraceID比サンプリングと互換性のある部分トレースの分析 のための手法が開発されています。

TraceIDRatio サンプラーには、完全性をテストする上でもう1つの難点があります。 外部情報を使わずに、トレース内に欠落しているリーフスパンがあるかどうかを知ることは不可能です。 1つのアプローチとして、OpenCensusからOpenTelemetryへの移行の過程で失われた、各スパンの子の数をカウントする方法 があります。

期待される子の数がない場合、トレースが完全であることを保証するために、トレース全体にわたる最小のSampler確率を知る方法が必要になります。

TraceIDRatioでサンプリングされたスパンをカウントするために、各スパンは sampler.adjusted_count という名前のSpan属性を使って、対応する SpanData にその調整カウントをエンコードすることができます。

Dapper’s “Inflationary” Sampler

GoogleのDapperトレーシングシステムは、大規模なトレース収集のコストを制御するためのサンプリングの使用について説明しています。 Dapperの初期のSamplerアルゴリズムは、「インフレーショナリー (inflationary)」アプローチと呼ばれており（論文には掲載されていませんが）、ここで再現します。

この種のSamplerは、以下に示す条件付き確率の式を使って、トレース内のルート以外のスパンがトレーシングの確率を引き上げることを可能にします。 この方法で生成されたトレースは完全な部分木であり、必ずしも完全なトレースではありません。 この手法は、特に高スループットのサービスがときおり低スループットのサービスを呼び出すシステムで成功します。 低スループットのサービスは、そのサンプリング確率を引き上げることを意図しています。

この手法を使用するには、トレース内で新しい「サブルート」のサンプリングを開始する確率を計算するために、（Parent サンプラーについて説明した）入ってくるContextの親包含確率と、それがサンプリングされたかどうかを伝播させる必要があります。

条件付き確率の標準的な表記法を使うと、P(x) は x が真である確率を表し、P(x|y) は y が真であるという条件のもとで x が真である確率を表します。 確率の公理から、次のことが成り立ちます。

P(x)=P(x|y)*P(y)+P(x|not y)*P(not y)

変数は次のとおりです。

• H: 有効な親コンテキストの親包含確率。親コンテキストがサンプリングされたかどうかとは独立している
• I: 開始されるスパンに対するインフレーショナリーサンプリング確率
• D: 新しいサブルートを開始するかどうかの決定確率

このSamplerはサンプリング確率を下げることができないため、新しいスパンが H >= I の状態で開始される場合、またはコンテキストがすでにサンプリングされている場合、新たなサンプリング決定は行われません。 入ってくるコンテキストがすでにサンプリングされている場合、新しいスパンの調整カウントは 1/H になります。

H < I であり、かつ入ってくるコンテキストがサンプリングされていないと仮定すると、次の確率の式が成り立ちます。

P(span sampled) = I
P(parent sampled) = H
P(span sampled | parent sampled) = 1
P(span sampled | parent not sampled) = D

上記の式を使うと、

I = 1*H + D*(1-H)

Dについて解くと、

D = (I - H) / (1 - H)

ここでSamplerは確率 D で決定を行います。 決定が真であっても偽であっても、I を新しい親包含確率として伝播させます。 決定が真であれば、調整カウント 1/I を持つサブルート化されたトレースの記録を開始します。

Proposed Span protocol

OTEP 168 で策定された、一貫性のある親サンプリング確率を伝播するための提案に従い、本提案は親サンプリング確率をエンコードするフィールドを追加することに限定されます。 伝播に関するOTEP 168の提案は、親サンプリング確率を2のべき乗に制限しているため、対応する調整カウントを小さな非負整数を使ってエンコードできます。

OpenTelemetryのSpanプロトコルにはすでにSpanの tracestate が含まれており、これによって利用者は、その提案で規定された規則を適用して親サンプリング確率を計算することで、スパンの調整カウントを計算できます。

親サンプリング確率を伝播するためのOTEP 168の提案では、63個の通常の値と1個の特別なゼロ値を持つ、6ビットの情報を使用します。 tracestate が空である、ot サブキーが見つからない、または p の値を決定できない場合、親サンプリング確率は不明であるとみなされます。

OTEP 168の親サンプリング確率を伝播する提案と組み合わせることで、最新のシステムにおいてサンプリングを有効化すると、ルート・子を問わずすべてのスパンが既知の調整カウントを持つようになるという結果が得られます。 OTEP 168の tracestate 値を持つスパンデータのストリームの利用者は、その調整カウントによってスパンをおおよそかつ正確にカウントできます。

Span data model changes

Spanデータモデルへの追加内容:

### Definitions Used in this Document

#### 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 and recording
the span for export.

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

The Sampler interface and the built-in Samplers defined by OpenTelemetry 
must be capable of deciding immediately whether to sample the child
context.  The term "sampling" may be used in a more general sense.  
For example, a reservoir sampling scheme limits the rate of sample items 
selected over a period of time, but such a scheme necessarily defers its 
decision making, thus "Sampling" may be applied anywhere on a collection 
path whereas the "Sampler" API is restricted to logic that can immediately
decide to sample a trace in side an OpenTelemetry SDK.

#### Parent-based sampling

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

#### Parent sampling

In a tracing context, Parent sampling refers to the initial decision to
sample a span or a trace, which determines the W3C `sampled` flag of
the child context.  The OpenTelemetry tracing data model currently
supports only parent 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 probability equal to the minimum sampling 
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.

In OpenTelemetry, consistent probability samplers are limited to 
power-of-two probabilities.  OpenTelemetry consistent probability sampling 
is defined in terms of a "p-value" and an "r-value", both of which are 
propagated via the context to assist in making consistent sampling decisions.

### Always-on 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 not defined as
a probability sampler with zero probability, because these spans are
effectively uncountable.

### 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 
to make its decisions. Because OpenTelemetry specifies the use of 
consistent probability samplers, any sampler other than a parent-based 
sampler that does not meet all the requirements for consistent probability 
sampling is termed a non-probability sampler.

#### Adjusted count

Adjusted count is defined as a measure of representivity, the number
of spans in the population that are represented by the individually
sampled span.  Span-to-metrics pipelines may be built by adding the
adjusted count of each sample span to a counter of matching spans,
observing the duration of each sample span in a histogram adjusted
count many times, and so on.

The adjusted count 1 means an one-to-one sampling was in effect.
Adjusted counts greater than 1 indicate the use of a probability
sampler.  Adjusted counts are unknown when using a non-probability
sampler.

Zero adjusted count is defined in a way to support composition of
probability and non-probability samplers.  In effect, spans that are 
"recorded" but not "sampled" have adjusted count of zero.

#### Unbiased probability sampling

The statistical term "unbiased" is a requirement applied to the
adjusted count of a span, which states that the expected value of the
sum of adjusted counts across all exported spans MUST equal the true
number of spans in the population.  Statistical bias, a measure of the
difference between an estimate and its true value, of the estimated
span count in the population should equal zero.  Moreover, this
requirement must be true for all subsets of the span population for a 
sampler to be considered an unbiased probability sampler.

It is easier to define probability sampling by what it is not.  Here
are several samplers that should be categorized as non-probability
samplers because they cannot record unbiased adjusted counts:

- A traditional form of "leaky-bucket" sampler applies a rate limit to
  the starting of new sampled traces.  When the configured limit is
  not exceeded, all spans pass through with adjusted count 1.  When
  the configured rate limit is exceeded, it is impossible to set
  adjusted count without introducing bias because future arrivals are
  not known.
- A "every-N" sampler records spans on a regular interval, but instead
  of making a probabilistic decision it makes an exact decision 
  (e.g., every 10,000 spans).  This sampler knows the representivity
  of the spans it samples, but the selection process is biased.
- A "at least once per time period" sampler remembers the last time
  each distinct span name exported a span.  When a span occurs after
  more than the specified interval, it samples one (e.g., to ensure
  that receivers know about these spans).  This sampler introduces
  bias because spans that happen between the intervals do not receive
  consideration.
- The "always off" sampler is biased by definition. Since it exports
  no spans, the sum of adjusted count is always zero.

Proposed Sampler composition rules

複数のSamplerを組み合わせる場合、自然な結果としては、いずれかのSamplerがスパンを記録またはサンプリングすると判断すれば、そのスパンは記録・サンプリングされることになります。 調整カウントを保存する形でSamplerを組み合わせるには、まずSamplerを次のいずれかのカテゴリーに分類する必要があります。

1. Parentベース（ParentBased）
2. 既知の非ゼロ確率（TraceIDRatio、AlwaysOn）
3. 非確率ベース（AlwaysOff、その他すべてのSampler）

Parentベースのサンプラーは、親コンテキストが既知の親確率を含んでいるかどうかに基づいて、実行時に常に他の2つのいずれかに帰着します。

合成サンプラーを構築するために使用できる、これらの各カテゴリーからのSamplerの決定を組み合わせるための規則を以下に示します。

Composing two consistent probability samplers

2つの一貫性のある確率サンプラーが使用される場合、確率が大きい方のSamplerは、定義上、確率が小さい方のサンプラーが選択するであろうすべてのスパンを含みます。 その結果は、最小のp値を持つ一貫性のあるサンプラーになります。

Composing a probability sampler and a non-probability sampler

確率サンプラーが非確率サンプラーと合成される場合、その効果は、不明な確率を既知の確率に変えることです。 確率サンプラーがスパンを選択した場合、その調整カウントが使用されます。 確率サンプラーがスパンを選択しなかった場合、調整カウントはゼロが使用されます。

調整カウントをゼロとすることで、不偏確率サンプラーが選択しなかったスパンを記録できるようになり、統計的バイアスを導入することなく、それらのスパンをバックエンドで受信できるようになります。

Composition rules summary

合成Samplerを作成するには、まず各Samplerの結果をp値と sampled フラグの観点から表現します。 p値は次の3つのカテゴリーに分類されることに注意してください。

1. 不明なp値は、不明な調整カウントを示します
2. 既知の非ゼロp値（範囲 [0,62]）は、既知の非ゼロ調整カウントを示します
3. 既知のゼロp値（p=63）は、既知のゼロ調整カウントを示します

非確率サンプラーは常に不明な p を返し、sampled=true または sampled=false を設定できるのに対し、確率サンプラーは sampled=true を伴う p∈[0,62] を返すか、sampled=false を伴う p=63 を返すかのいずれかに制限されます。 どのSamplerも単独で sampled=true を伴う p=63 を返すことはできませんが、この条件は p=63 と不明な p の合成の結果として生じる場合があります（MAY）。

合成サンプラーは、以下のように、下記の式を使って計算できます。 不明な p は tracestate にエンコードされることは決してありませんが、合成の目的のために、既知のp値を表す6ビットの範囲を1つ超えた p=64 を不明値に割り当てます。 p=64 を割り当てることで、以下の式が単純化されます。

これらの単純な規則に従うことで、任意の数の一貫性のある確率サンプラーと非確率サンプラーを組み合わせることができます。 不明を表す p=64 と sampled=false から始めて、合成p値を、それまでの合成p値と個々のサンプラーのp値のうち小さい方の値に更新します。

p<sub>out</sub> = min(p<sub>in</sub>, p<sub>sampler</sub)
sampled<sub>out</sub> = logicalOR(sampled<sub>in</sub>, sampled<sub>sampler</sub)

合成サンプラーは常に個々のサンプラーの論理和 (logical-OR) です。 p値については、これには2つの効果があります。

1. 2つの一貫性のある確率サンプラーを組み合わせる場合、選択性の低い方のSamplerの調整カウントが採用されます。
2. 一貫性のある確率サンプラーと非確率サンプラーを組み合わせる場合、これは不明な調整カウントを既知の調整カウントに変える効果を持ちます。

Proposed Sampler interface changes

Trace SDK仕様の SamplingResult は、すべてのSamplerが返す新しいフィールドを追加して拡張されます。

- The sampling probability of the span is encoded as the base-2
  logarithm of inverse parent sampling probability, known as "adjusted
  count", which is the effective count of the Span for use in
  Span-to-Metrics pipelines.  The value 64 is used to represent
  unknown adjusted count, and the value 63 is used to represent
  known-zero adjusted count.  For values >=0 and <63, the adjusted
  count of the Span is 2**value, representing power-of-two
  probabilities between 1 and 2**-62.

  The corresonding `SamplerResult` field SHOULD be named
  `log_adjusted_count` because it carries the newly-created 
  span and child context's adjusted count and is expressed as
  the logarithm of adjusted count for spans selected by a 
  probability Sampler. 

組み込みの各Samplerがサンプリング確率を伝えるために tracestate をどのように設定することが期待されているかの詳細については、OTEP 168 を参照してください。

Recommended reading

Sampling, 3rd Edition, by Steven K. Thompson.

A Generalization of Sampling Without Replacement From a Finite Universe, JSTOR (1952)

Priority sampling for estimation of arbitrary subset sums

Stream sampling for variance-optimal estimation of subset sums.

Estimation from Partially Sampled Distributed Traces, 2021 Dynatrace Research report, Otmar Ertl

Acknowledgements

Dapper Samplerアルゴリズムの再構築を手伝ってくれたNeena Dugar氏とAlex Kehlenbeck氏に感謝します。