> Source: https://www.ymotongpoo.com/works/oteps/trace/otep-0168/


# OTEP-0168: 親のサンプリング確率の伝搬

W3C trace contextを使用して、一貫性のある親のサンプリング確率を伝達します。

## 動機 {#motivation}

親のサンプリング確率とは、トレースコンテキストの開始時に関連付けられた確率であり、W3Cの `sampled` フラグを設定するかどうかを決定するために使用され、それによって子コンテキストが `ParentBased` サンプラーによってサンプリングされるかどうかが決まります。
組み込みの `ParentBased` サンプラーが使用されている場合に、スパンからメトリクスへのパイプラインを構築するためには、コンテキストに関連付けられた親のサンプリング確率を知ることが有用です。
スパンからメトリクスへのパイプラインをサポートすることについてのさらなる動機は、[OTEP 170](0170-sampling-probability.md) で述べられています。

一貫性のあるトレースサンプリング決定とは、トレース中のどのノードでも実行できる決定のことであり、部分的なトレースの収集をサポートします。
OpenTelemetryは、この目標を達成することを目指した組み込みの `TraceIDRatioBased` サンプラーを規定していますが、これは未完成のまま残されています(v1.0のTrace仕様における[TODO](../../specification/trace/sdk.md#traceidratiobased)を参照してください)。

私たちは、[W3Cのsampledフラグ](https://www.w3.org/TR/trace-context/#sampled-flag)とともに、`ot` ベンダータグを付けた `tracestate` を使って必要な情報を伝搬するサンプラーのオプションを提案します。
これには(別途)、[OpenTelemetryプロジェクトが `tracestate` 自体をどのように使用するかを規定すること](https://github.com/open-telemetry/opentelemetry-specification/pull/1852)が必要になります。

## 解説 {#explanation}

一貫性のある親のサンプリング確率を伝達するには、2つの情報が必要です。

1. 親のサンプリング確率を表すp値
2. 一貫性のあるサンプリング決定の元となる「ランダム性」を表すr値

この提案では、それぞれの伝搬に6ビットの情報を使用し、確率サンプリングに対して現時点では十分に規定されていない組み込みのTraceIDのランダム性には依存しません。
この提案は、[Otmar Ertlによる研究](https://arxiv.org/pdf/2107.07703)に忠実に従っています。

### 補正カウント {#adjusted-count}

補正カウントの概念は[OTEP 170](./0170-sampling-probability.md)で導入されています。
簡単に言うと、補正カウントはサンプリング確率の観点から次のように定義されます。

| サンプリング確率 | 補正カウント                     | 備考                                                                                                      |
| --                   | --                                 | --                                                                                                         |
| `probability` != 0   | `adjusted_count` = `1/probability` | ゼロでない確率で選択されたスパンについては、補正カウントはそのサンプリング確率の逆数です。 |
| `probability` == 0   | `adjusted_count` = 0               | 確率サンプラーによって選択されなかったスパンについては、補正カウントは0です。                         |

この用語は、確率サンプラーによって選択された(あるいは選択されなかった)項目の代表性を伝えるために使用されます。
確率サンプラーによって選択されなかった項目には、論理的にゼロの補正カウントが割り当てられます。
これにより、それらが他の理由で記録された場合でも、スパン全体の推定個数にバイアスをもたらしません。

### p値 {#p-value}

この拡張のコストを制限するため、また以下に文書化する統計的な理由から、私たちは親のサンプリング確率を2のべき乗に制限することを提案します。
これにより、利用可能な親のサンプリング確率は1/2、1/4、1/8といった値に限定されます。
これらの確率は、補正カウントの底2の対数を使うことで、小さい整数値としてコンパクトに符号化できます。

6ビットの情報を使うことで、2**-62ほどの小さい既知のサンプリングレートまで伝達できます。
値63は、確率0でのサンプリングを意味するために予約されており、これは関連するコンテキストの補正カウントが0であることを伝えます。

伝搬される際、「p値」として知られる値は次の表のように解釈されます。
既知のサンプリング確率に対するp値は、その確率の底2の負の対数です。

| p値 | 親の確率 |
| ------- | ------------------ |
| 0       | 1                  |
| 1       | 1/2                |
| 2       | 1/4                |
| ...     | ...                |
| N       | 2**-N              |
| ...     | ...                |
| 61      | 2**-61             |
| 62      | 2**-62             |
| 63      | 0                  |

[OTEP 170のトレースデータモデルで規定されているとおり](0170-sampling-probability.md)、親のサンプリング確率はエクスポートされるスパンデータに格納でき、スパンからメトリクスへのパイプラインを構築できるようになります。
`tracestate` はすでにOpenTelemetryのスパン内に符号化されているため、この提案はスパンのプロトコルに対する変更を必要としません。
この提案を受け入れるということは、親のサンプリング確率が既知の場合、p値を `tracestate` から導出できるということを意味します。

`p` の値が不明であることを `tracestate` を使って明示的に伝搬することはできません。
単に `p` を省略することで、親のサンプリング確率が不明であることを伝えます。

### r値 {#r-value}

親のサンプリング確率を2のべき乗に限定することで、トレースコンテキストごとに必要なランダム性の量が制限されます。
一貫性のあるサンプリング決定は、r値と呼ばれる特定のランダム変数を伝搬することによって実現されます。

r値についての直感を養うために、`TraceID` の各ビットが一様なランダムビット生成器によって生成される(つまり、各ビットが等確率で0または1になる)シナリオを考えてみましょう。
128ビットの `TraceID` は、したがって128ビットの符号なし整数として扱うことができ、それを2**128で割ることで[0, 1)の範囲の分数に写像できます。
この形式はTraceID比率として知られています。
これで、確率サンプリングは、TraceID比率をサンプリング確率と比較し、TraceID比率がサンプリング確率より小さい場合に `sampled` フラグを設定することで実現できます。

サンプリング確率が1の場合、TraceID比率は例外なく1未満であるため、すべてのTraceIDが受け入れられることが容易にわかります。
確率50%でのサンプリングは、0.5未満のTraceID比率を選択し、これはすべてのTraceIDが2**127未満であること、つまり最上位ビットが0であるすべてのTraceIDに写像されます。
同じ論理により、確率25%でのサンプリングは、最上位の2ビットが0であるTraceIDを受け入れることを意味します。
一般に、正確な確率 `2**-S` は、この例のシナリオでは先頭に `S` 個のゼロを持つTraceIDを選択することと等価です。

ここで規定するr値は、ランダムな62ビット文字列における先頭ゼロの個数を直接記述するものであり、TraceIDの値を特定の位置にランダムビットを持つように構築したり、その一様性に厳密な要件を課したりする必要がない方法で規定されています。
数学的な用語で言えば、r値は次に示す切断幾何分布によって記述されます。

| `r` 値        | `r` 値の確率 | 暗黙のサンプリング確率 |
| ---------------- | ------------------------ | ----------------------         |
| 0                | 1/2                      | 1                              |
| 1                | 1/4                      | 1/2以上                  |
| 2                | 1/8                      | 1/4以上                  |
| 3                | 1/16                     | 1/8以上                  |
| ...              | ...                      | ...                            |
| 0 <= r <= 61     | 1/(2**(-r-1))            | 2**(-r)以上              |
| ...              | ...                      | ...                            |
| 59               | 2**-60                   | 2**-59以上               |
| 60               | 2**-61                   | 2**-60以上               |
| 61               | 2**-62                   | 2**-61以上               |
| 62               | 2**-62                   | 2**-62以上               |

このようなランダム変数 `r` は、最新のコンピューターアーキテクチャの効率的な命令を使って生成できます。
たとえば、ハードウェアサポートを使って先頭ゼロの個数を計算できます。

```golang
import (
    "math/rand"
    "math/bits"
)

func nextRValueLeading() int {
    x := uint64(rand.Int63()) // 63 least-significant bits are random
    y := x << 1 | 0x3         // 62 most-significant bits are random
    return bits.LeadingZeros64(y)
}
```

あるいは、代わりに末尾ゼロの個数を計算することもできます。
以下は(特別な命令を使わない)例です。

```golang
import (
    "math/rand"
)

func nextRValueTrailing() int {
    x := uint64(rand.Int63())
    for r := 0; r < 62; r++ {
        if x & 0x1 == 0x1 {
            return r
        }
        x = x >> 1
    }
    return 62
}
```

r値の計算に関するさらなる例は、[こちら](https://gist.github.com/jmacd/79c38c1056035c52f6fff7b7fc071274)に示されています。
たとえば、値3は先頭ゼロが3個あったことを意味し、1分の1から8分の1までの確率でサンプリングされたことに対応しますが、16分の1以下の確率では対応しません。

### 提案する `tracestate` の構文 {#proposed-tracestate-syntax}

一貫性のあるサンプリングのr値(`r`)と親のサンプリング確率のp値(`p`)は、それぞれのフィールドに対して2バイトのbase16コンテンツを使って、次のように伝搬されます。

```
tracestate: ot=p:PP;r:RR
```

ここで、`PP` はbase16のp値の2バイトであり、`RR` はbase16のr値の2バイトです。
これらの値は不明な場合には省略されます。

この提案は推奨事項として捉えられるべきであり、[OpenTelemetryがその `tracestate` に対して規定する形式](https://github.com/open-telemetry/opentelemetry-specification/pull/1852)に合わせて変更されます。
したがって、base16符号化の選択は単なる推奨であり、`traceparent` がbase16符号化を使用しているために選ばれています。

### 例 {#examples}

次の `tracestate` の値は `sampled=true` を伴います。

```
tracestate: ot=r:0a;p:03
```

これは次のように解釈されます。

```
base16(p-value) = 03 // 1-in-8 parent sampling probability
base16(r-value) = 0a // qualifies for 1-in-1024 or greater probability consistent sampling
```

`ParentBased` サンプラーは、格納された `TraceState` フィールドに `ot=r:0a;p:03` を含め、これにより消費者は8の補正カウントを持つものとしてカウントできます。
`sampled=true` フラグはそのまま設定されたままです。

確率2**-10以上で設定された `TraceIDRatioBased` サンプラーは、`sampled=true` を有効にし、`tracestate: ot=r:0a;p:0a` を通じて新しい親のサンプリング確率を伝えます。

確率2**-11以下で設定された `TraceIDRatioBased` サンプラーは、`sampled=false` を設定し、`tracestate` から `p` を削除して `tracestate: ot=r:0a` とします。

## 内部の詳細 {#internal-details}

サンプリングレートの集合を制限する背後にある理由は、次のとおりです。

- 親のサンプリング確率を伝搬するコストを下げる
- 必要なランダムビットの数を制限する
- 浮動小数点数から整数への丸め誤差を回避する
- 部分的なトレースに関わる数学的処理を扱いやすくする

[部分的にサンプリングされたトレースから統計的推論を行うためのアルゴリズムが公開されており](https://arxiv.org/pdf/2107.07703)、限られた数の2のべき乗のサンプリングレートをどのように扱うかを説明しています。

### `TraceIDRatioBased` サンプラーの振る舞い {#behavior-of-the-traceidratiobased-sampler}

サンプラーは、ゼロ確率の特殊なケース(この場合は `p=63` が使用されます)を除いて、`s` を[0, 62]の範囲の整数として表される2のべき乗の確率 `2**-s` で設定されなければなりません(MUST)。

コンテキストが新しいルートである場合、初期の `tracestate` は、上記で説明したとおり[0, 62]の範囲のランダム性の値 `r` を使って作成されなければなりません(must)。
コンテキストが新しいルートでない場合は、親コンテキストと同じ `r` 値を持つ新しい `tracestate` を出力します。

どちらの場合も、出力される `p` が出力される `r` 以下である場合(つまり `p <= r` の場合)にsampledビットを設定します。

サンプリングされた場合、どちらのケースにおいても、コンテキストのp値 `p` は[0, 62]の範囲にある `s` の値に設定されます。
サンプリング確率が0である場合(`s` が未定義の特殊なケース)は、ゼロ確率に対して規定されている値である `p=63` を使用します。

コンテキストが新しいルートでなく、かつ入力コンテキストのr値が設定されていない場合、実装はユーザーにエラー状態を通知し、入力コンテキストの `sampled` フラグに従うべきです(SHOULD)。

### `ParentBased` サンプラーの振る舞い {#behavior-of-the-parentbased-sampler}

`ParentBased` サンプラーは、この提案によって変更されません。
これはW3Cの `sampled` フラグを尊重し、入力される `tracestate` のキーを子コンテキストにコピーします。
入力コンテキストの親のサンプリング確率が既知であれば、そのスパンの親のサンプリング確率も既知になります。

スパンの親のサンプリング確率は、`tracestate` の `ot` サブキー内で `p` と `r` の両方が定義されている場合に既知となります。
`r` または `p` が定義されていない場合、そのスパンの親のサンプリング確率は不明です。

### `AlwaysOn` サンプラーの振る舞い {#behavior-of-the-alwayson-sampler}

`AlwaysOn` サンプラーは、サンプリング確率100%(つまり `p=1`)の `TraceIDRatioBased` と同じように振る舞います。

### `AlwaysOff` サンプラーの振る舞い {#behavior-of-the-alwaysoff-sampler}

`AlwaysOff` サンプラーは、確率0(つまり `p=63`)の `TraceIDRatioBased` と同じように振る舞います。

## 3ビットでの実例 {#worked-3-bit-example}

これらの表の振る舞いは、より小さい例を使って手作業で検証できます。
次の表は、`r`、`p`、`s` を6ビットではなく3ビットに限定した場合に、これらの式がどのように機能するかを示しています。

`p` の値は次のように解釈されます。

| `p` 値 | 補正カウント |
| -----     | -----          |
| 0         | 1              |
| 1         | 2              |
| 2         | 4              |
| 3         | 8              |
| 4         | 16             |
| 5         | 32             |
| 6         | 64             |
| 7         | 0              |

補正カウント(`p`)の既知の非ゼロ値は1から64までの範囲で7つしかないことに注意してください。
したがって、`r` と `s` の定義済みの値も7つです。
次の表は、`r` とそれに対応する選択確率、および各 `s` に対して計算された補正カウントを示しています。

| `r` 値 | `r` の確率 | `s=0` | `s=1` | `s=2` | `s=3` | `s=4` | `s=5` | `s=6` |
| --        | --                 | --    | --    | --    | --    | --    | --    | --    |
| 0         | 1/2                | 1     | 0     | 0     | 0     | 0     | 0     | 0     |
| 1         | 1/4                | 1     | 2     | 0     | 0     | 0     | 0     | 0     |
| 2         | 1/8                | 1     | 2     | 4     | 0     | 0     | 0     | 0     |
| 3         | 1/16               | 1     | 2     | 4     | 8     | 0     | 0     | 0     |
| 4         | 1/32               | 1     | 2     | 4     | 8     | 16    | 0     | 0     |
| 5         | 1/64               | 1     | 2     | 4     | 8     | 16    | 32    | 0     |
| 6         | 1/64               | 1     | 2     | 4     | 8     | 16    | 32    | 64    |

`s=*` の各列において、`r` の確率と補正カウントの積の総和が1になっていることに注目してください。
たとえば、`s=4` の列では `0*1/2 + 0*1/4 + 0*1/8 + 0*1/16 + 16*1/32 + 16*1/64 + 16*1/64 = 1/2 + 1/4 + 1/4 = 1` となります。
`s=2` の列では `0*1/2 + 0*1/4 + 4*1/8 + 4*1/16 + 4*1/32 + 4*1/64 + 4*1/64 = 1/2 + 1/4 + 1/8 + 1/16 + 1/16 = 1` となります。
私たちは、与えられた確率で `r` が選ばれる場合、`s` のどのような選択も期待値1のスパンを生成すると結論づけます。

## 不変条件のチェック {#invariant-checking}

次の表は、3つのサンプラーのケースが、入力および出力の `p`、`r`、`sampled` の値に関してどのように振る舞うかをまとめたものです。

| サンプラー                | 入力される`r` | 入力される`p` | 入力される`sampled` | 出力される`r`               | 出力される`p`               | 出力される`sampled`         |
| --                     | --           | --           | --                 | --                         | --                         | --                         |
| Parent                 | 未使用       | 期待される     | 尊重される          | チェックされそのまま通過 | チェックされそのまま通過 | チェックされそのまま通過 |
| TraceIDRatio(非ルート) | 使用される       | 未使用       | 無視される         | チェックされそのまま通過 | `s` に設定                 | `p <= r` に設定            |
| TraceIDRatio(ルート)     | 該当なし         | 該当なし         | 該当なし               | ランダム変数            | `s` に設定                 | `p <= r` に設定            |

結果として得られるスパンの親のサンプリング確率が不明になるケースがいくつかあります。

| サンプラー                | 不明になる条件 |
| --                     | --                |
| Parent                 | 入力される `p` がない   |
| TraceIDRatio(非ルート) | 入力される `r` がない   |
| TraceIDRatio(ルート)     | なし              |

入力は、次のように範囲外として認識されます。

| 範囲の不変条件 | 対処                           |
| --              | --                               |
| `p < 0`         | `tracestate` から `p` を削除する         |
| `p > 63`        | `tracestate` から `p` を削除する         |
| `r < 0`         | `tracestate` から `r` と `p` を削除する |
| `r > 62`        | `tracestate` から `r` と `p` を削除する |

`p` と `r` と `sampled` の組み合わせが互いに矛盾するケースがあります。
`sampled` フラグは、式 `p <= r` と等価です。
不変条件 `sampled <=> p <= r` に違反する場合、`ParentBased` サンプラーは、以下で説明するとおり伝搬される値を修正しなければなりません(MUST)。

この違反は常に、`sampled` フラグを尊重し、`p` を63(補正カウントがゼロであることを表す)、または未設定(親のサンプリング確率が不明であることを表す)に修正することで対処されます。

`sampled` がfalseで不変条件に違反している場合は、親のサンプリング確率が不明であることを伝えるため、出力コンテキストから `p` を削除します。

`sampled` がtrueで `p=63`(確率0%を示す)である場合は、ゼロの補正カウントによるサンプリングを許容する特殊なケースとみなすことができ、これにより確率サンプリングが存在する状況下でも非確率的なサンプリングを行うことができます。
`p` を63に設定します。

`sampled` がtrueで `p<63`(ただし `p>r`)である場合は、親のサンプリング確率が不明であることを伝えるため、出力コンテキストから `p` を削除します。

## プロトタイプ {#prototype}

[この提案はOTel-Go SDKでプロトタイプ化されています。](https://github.com/open-telemetry/opentelemetry-go/pull/2177)
OTel-GoのTracing SDKの `Sampler` や `tracestate` のAPIに変更は必要ありませんでした。

## トレードオフと緩和策 {#trade-offs-and-mitigations}

### 命名の疑問 {#naming-question}

この提案は、現在OpenTelemetry仕様の一部である `TraceIDRatioBased` サンプラーのロジックを変更するため、その名前が意味を持たなくなります。
提案されたサンプラーは `ConsistentSampler` と名付けられるかもしれず、既存の `TraceIDRatioBased` サンプラーは非推奨にできます。

多くのSDKはすでに `TraceIDRatioBased` サンプラーを実装しており、これは(2のべき乗ではない)任意の確率でトレースのルートにおける確率サンプリングに使われてきました。
このため、私たちは現在の(規定が不十分な)`TraceIDRatioBased` サンプラーをそのまま残し、TraceIDのビットに関して規定された方法で振る舞うことを伝えるために `ProbabilitySampler` という名前に変更するかもしれません。

### TraceIDのランダム性を使用しない理由 {#not-using-traceid-randomness}

もしTraceIDが少なくとも62個の一様なランダムビットを持つように規定されていれば、上記で説明したランダム性の値をそれら62個のランダムビットの中の先頭ゼロの個数として計算することも可能でしょう。

しかし、これにはW3Cのtraceparent仕様の変更が必要になるため、私たちはTraceIDのビットを使うことを提案しません。

[W3C trace context issue 467](https://github.com/w3c/trace-context/issues/467)を参照してください。

### TraceIDのハッシュ化を使用しない理由 {#not-using-traceid-hashing}

TraceIDをハッシュ化することで一貫性のあるサンプリング決定を行うことも可能ですが、そのようなアプローチは偏りのないサンプリング決定を行うには十分ではないと私たちは考えています。
十分に優れたハッシュ関数を定義・規定すること、まして複数の言語でそれを実装させることは、比較的難しい課題だと見なされています。

ハッシュ化は計算コストも高くつきます。
この提案では、TraceIDをハッシュ化する計算コストを回避するために追加のデータを使用します。

### 2のべき乗への制限 {#restriction-to-power-of-two}

親のサンプリング確率を2のべき乗に制限することは、テールサンプラーが任意の確率を使用することを妨げません。
併せて提案されている[OTEP 170](0170-sampling-probability.md)では、2のべき乗に限定されない `sampler.adjusted_count` 属性の使用について議論されています。
テールサンプリングされたスパンに対する実効的な補正カウントをどのように表現するかについての議論は、このOTEPではなく[OTEP 170](0170-sampling-probability.md)に属します。

親のサンプリング確率を2のべき乗に制限することは、サンプラーが一定期間にわたって任意の実効確率を使用することを妨げません。
たとえば、典型的なトレースサンプリングレートである5%(つまり20分の1)は、60%の時間で1/16のサンプリングを、40%の時間で1/32のサンプリングを選択することで達成できます。

```
1/16 * 0.6 + 1/32 * 0.4 = 0.05
```

### サンプリングされない場合の `p` の伝搬 {#propagating-p-when-unsampled}

一貫性のあるトレースサンプリングでは、スパン自体がサンプリングされない場合であっても `r` 値が伝搬される必要があります。
しかし、コンテキストがサンプリングされない場合には `p` 値を伝搬する必要はありません。
なぜなら、`ParentBased` サンプラーはその決定を変更しないからです。
ある1つのユースケースはGoogleの初期のDapperシステム(「インフレーショナリーサンプリング」として知られる、[OTEP 170](0170-sampling-probability.md#dappers-inflationary-sampler)を参照)で文書化されていますが、同じ効果はこのフレームワークにおける一貫性のあるサンプリング決定を使うことでも達成できます。

### デフォルトの振る舞い {#default-behavior}

一貫性のあるトレースサンプリング決定を行うためには、`r` 値がトレースのルートで設定されなければなりません(MUST)。
この振る舞いは、オプトインまたはオプトアウトのいずれかにできます。
オプトインの場合、ユーザーは `r` の設定、および `tracestate` における `p` の設定と伝搬を有効にする必要があります。
オプトアウトの場合、ユーザーはこれらの機能を無効にする必要があります。
サンプリング機能のコストと利便性は、この選択に依存します。

本著者の推奨は、これらの振る舞いの有用性を示すために、最初はオプトインとすることです。
それが有効であると証明されれば、修正されたW3C trace contextの `traceparent` を使ったデフォルトで有効なアプローチが提案されるかもしれません。
これにより、p値を安価に伝搬できるようになります。

[traceparentヘッダーでサンプリング確率を伝搬することについての、W3C issue trace context issue 463](https://github.com/w3c/trace-context/issues/463)を参照してください。
これにより、デフォルトで有効にするのに十分安価になります。