Yoshi Yamaguchi

OTEP-0235: tracestateにおけるサンプリング閾値の伝搬

動機

サンプリングは幅広いトピックです。 ここでは、分散トレーシングシステムの各地点で下される、スパンを収集するかどうかの独立した決定を指します。 1つのスパンが最終的に消費されるまでに、複数のサンプリング決定が下されることがあります。 プロセス内の複数の地点でサンプリングを行う場合、それについて効果的に推論する唯一の方法は、サンプリング決定が 一貫している ことを保証することです。 ここでいう一貫性とは、確率p1であるスパンに対して下された肯定的なサンプリング決定が、確率p2 >= p1で下された場合、同じトレースに属する任意のスパンに対しても肯定的なサンプリング決定を暗に含むことを意味します。

解説

既存の実験的なTraceStateを使った確率的サンプリングの仕様は、2のべき乗の確率に限定されており、TraceIDのランダム性について仮定を置かずに機能するように設計されています。 このシステムは、2のべき乗の間の補間を使うことでしか2のべき乗以外のサンプリングを達成できず、これは不必要に制限的です。 既存のサンプリングシステムでは、1%、10%、75%といったサンプリング確率が一般的であり、補間なしにこれらを表現できるべきです。 また、収集パス(ヘッドサンプリングのパスの外側)における一貫性のあるサンプリングの必要性もあり、traceID固有のランダム性を使うことは、すべてのスパンでtracestateからカスタムの r-value を参照するよりも安価な解決策です。 この提案は、以前の仕様における p 値の代替として、キー th を持つ新しい値を導入します。 p 値は2のべき乗に限定されていますが、この提案における th 値は広範囲の値をサポートします。 この提案は、そこで規定されているキー r を使った r-value によるランダム性の表現を引き続き認めます。 両者のケースを区別するため、この提案ではキー rv を使用します。

一般的なケースでは、トレースの経路全体にわたって一貫性のあるサンプリング決定を行うために、SpanContext に2つの値が存在しなければなりません(MUST)。

  1. 以下で R と呼ばれる、ランダムな(または疑似ランダムな)56ビットの値。
  2. TraceStateで表現される、以下で T と呼ばれる56ビットの 棄却閾値(単に「閾値」とも呼ばれます)。 T は、それ以前のすべての一貫性のあるサンプリング段階で適用された最大の閾値を表します。 現在のサンプリング段階が、それ以前のどの段階よりも大きい値の閾値を適用する場合、それに応じて閾値を更新(増加)しなければなりません(MUST)。

棄却閾値 の考え方の1つは、検討対象となる2^56個のスパンのうち、破棄されるスパンの個数であるというものです。 これは、R >= T であるスパンがサンプリングされることを意味します。

A、B、C の3者が関わる例を示します。

A -> B -> C

ここで、-> は親から子への関係を示しています。

A は、サンプリング確率0.25(棄却確率0.75に相当します)で一貫性のある確率的サンプリングを使用します。 B は、サンプリング確率0.5で一貫性のある確率的サンプリングを使用します。 C はparent-basedサンプラーを使用します。

A がスパンをサンプリングする場合、その送出されるtraceparentは ‘sampled’ フラグがSET(設定)され、送出されるtracestateの ’th’ は 0xc0_0000_0000_0000 に設定されます。 A がスパンをサンプリングしない場合、その送出されるtraceparentは ‘sampled’ フラグがUNSET(未設定)になりますが、送出されるtracestateの ’th’ は引き続き 0xc0_0000_0000_0000 に設定されます。 Bがスパンをサンプリングする場合、その送出されるtraceparentは ‘sampled’ フラグがSET(設定)され、送出されるtracestateの ’th’ は 0x80_0000_0000_0000 に設定されます。 C(parent-basedサンプラーであるため)は、純粋にその親(この場合はB)に基づいてスパンをサンプリングし、決定を下すためにsampledフラグを使用します。 その送出される ’th’ の値は、Bから受け取った値(0x80_0000_0000_0000)をそのまま反映し続け、これはその補正カウントを理解するのに有用です。

この設計では、あるスパンがその収集パスを進むにつれて、th が単調非減少である(そして特に、より低いサンプリング確率を適用する段階では増加しなければならない)ことが要求されます。 しかし、スパンの初期の th に対しては、(たとえば親を持つ場合にその親の th と関連付けるといった)いかなる制限も課されません。 Bの初期の th がAのものより小さいことは許容されます。 一方、後段のサンプラーがAの th を減少させることは許容されません。

このシステムには次の不変条件があります。

(R >= T) = sampledフラグ

サンプリング決定は、次のアルゴリズムによって伝搬されます。

  • th キーが指定されていない場合、これは非確率的サンプリングが行われている可能性を意味します。
  • そうでなければ、以下で説明するとおり th キーを16進数の値として解析し T を導出します。
  • T が0であれば、常にサンプリングします。
  • T の56ビットと R の56ビットを比較します。 T > R であれば、サンプリングしません。

R の値は、次のように導出されなければなりません(MUST)。

  • Tracestateヘッダーにキー rv が存在する場合、R = rv とします。
  • そうでなく、traceparentヘッダーにおいてRandom Trace ID Flagが true である場合、R はtrace-idの下位56ビットとします。
  • それ以外の場合、R は範囲 [0, (2**56)-1] のランダムな値として生成され(MUST)、キー rv を使ってTracestateヘッダーに追加されなければなりません(MUST)。

R の値を伝搬する望ましい方法は、trace-idの下位56ビットとして伝搬することです。 これらのビットが実際にランダムである場合、W3C trace context仕様で規定されているとおり、random トレースフラグを設定するべきです(SHOULD)。 trace-idのランダム性が不十分な状況(たとえば、複数のトレースをまとめてサンプリングする場合)もあり、そのような場合には rv 値が必要です。

rv と th キーの値は、集合 [0-9a-f] からの最大14個の16進数として表現されなければなりません(MUST)。 th キーについてのみ、末尾のゼロ(先頭のゼロは除きます)は省略できます。 rv キーは常にちょうど14桁の16進数でなければなりません(MUST)。

例を示します。

  • th 値が欠落している場合、非確率的サンプリングが行われている可能性があります。
  • th=4 – th=40000000000000 と等価であり、これは25%の棄却閾値を表し、75%のサンプリング確率に相当します。
  • th=c – th=c0000000000000 と等価であり、これは75%の棄却閾値を表し、25%のサンプリング確率に相当します。
  • th=08 – th=08000000000000 と等価であり、これは3.125%の棄却閾値を表し、96.875%のサンプリング確率に相当します。
  • th=0 – th=00000000000000 と等価であり、これは0%の棄却閾値を表し、常にサンプリングすることを意味します。

T の値は、次のように導出されなければなりません(MUST)。

  • Tracestateヘッダーに th キーが存在しない場合、非確率的サンプリングが使用されている可能性があります。
  • そうでなければ、th キーに対応する値は上記のとおりに解釈されるべきです。

サンプリング決定は、上記に従ってTracestateヘッダーの th キーの値を設定することによって伝搬されなければなりません(MUST)。

TとRの値の初期化と更新

サンプラーには2つの分類があります。

  • ヘッドサンプラー: Tracer によってスパン作成時に呼び出されるSamplerの実装です。
  • ダウンストリームサンプラー: 終了したSpanが与えられたときに、それをシステム内の次のコンポーネントへ破棄するか転送(「サンプリング」)するかを決定する任意のコンポーネントです。 「収集パスサンプラー」または「サンプリングプロセッサー」とも呼ばれます。 テールサンプラー は、トレース内のスパンをバッファリングし、バッファリングされたトレース内の任意のスパンのデータを使ってトレース全体のサンプリング確率を選択する、ダウンストリームサンプラーの特別なクラスです。

このセクションでは、それぞれの種類のサンプラーの振る舞いを規定します。

ヘッドサンプラー

ヘッドサンプラーは、新しいスパンの初期のTraceStateにおける rv と th の値を計算する責任を負います。 その計算に対する主な入力には、(親スパンが存在する場合の)親スパンのトレース状態と、新しいスパンのトレースIDが含まれます。

まず、一貫性のある Sampler が、どのサンプリング確率を使用するかを決定します。 サンプラーはTの値を任意に選択してもよいです(MAY)。 ShouldSample の呼び出しに有効な SpanContext が渡される場合(これは作成されるスパンが子スパンになることを示します)、次のようになります。

  • 親スパンよりも大きいTを選択すると、部分的なトレース(親はサンプリングされるが、その子である現在のスパンは破棄される)が発生すると予想されます。
  • 親スパン以下のTを選択すると、完全なトレース(これが一貫性のある確率的サンプリングの定義です)が発生すると予想されます。

出力されるTraceStateについては、次のようになります。

  • th キーは、サンプラーが実際に使用したサンプリング確率に対応する値で定義されなければなりません(MUST)。
  • 入力のTraceStateに rv 値が存在する場合、それは親スパンの rv と等しい値で定義されなければなりません(MUST)。 そうでない場合、rv は、前述の「Rの導出」アルゴリズムに従い、決定の過程で実効的なRが 生成 された場合に限り、かつその場合には必ず定義されなければなりません(MUST)。

TODO: 新しい スパンについて、ShouldSample は現在、新しいSpanの TraceFlags を知る方法を持たないため、Random Trace ID Flagが設定されているかどうかを判断できず、結果として「Rの導出」アルゴリズムを実行できません。 TraceId を受け取るのと同様に、追加のパラメーターとして TraceFlags を受け取るべきなのでしょうか。

ダウンストリームサンプラー

一方、ダウンストリームサンプラーは、次の規則に従いながら、変更された トレース状態を持つ終了したSpanを出力してもよいです。

  • 選択されたサンプリング確率が1である場合、サンプラーは既存の th を変更してはならず(MUST NOT)、th を新たに設定してもなりません(MUST NOT)。
  • そうでない場合、選択されたサンプリング確率は (0, 1) の範囲にあります。 この場合、サンプラーは max(入力のth, 選択したth) に等しい th を持つスパンを出力しなければなりません(MUST)。 言い換えると、th は減少してはならず(MUST NOT)(以前の段階のサンプリング確率を遡って調整することはできないため)、より低いサンプリング確率が使用された場合には増加させなければなりません(MUST)。 このケースは、ダウンストリームサンプラーがシステム内のスパンのスループットを削減する一般的な場合に相当します。

図

サンプリング決定のフロー

アルゴリズム

th と rv の値は、プロセッサーの能力や実装のニーズに応じて、さまざまな形式で表現・操作できます。 56ビットの値として、これらはバイト配列や64ビット整数と互換性があり、実質的に無視できる程度の精度の損失で64ビット浮動小数点数でも操作できます。

以下の例はPython3で記述されています。 これらは明確さのための例に過ぎず、推奨される実装として示すものではありません。

t値を56ビット整数の閾値に変換する

t値の文字列を56ビット整数の閾値に変換するには、右側を0で埋めて14桁の長さにし、それを16進数の値として解析します。

padded = (tvalue + "00000000000000")[:14]
threshold = int('0x' + padded, 16)

整数の閾値をt値に変換する

56ビット整数の閾値の値をt値表現に変換するには、それを16進数の値として出力します(‘0x’ の接頭辞は付けず、末尾のゼロは省略してもかまいません)。

h = hex(tvalue).rstrip('0')
# remove leading 0x
tv = 'tv='+h[2:]

rvと閾値を比較する

rvと閾値を64ビット整数として与えたとき、rvが閾値以上であればサンプリングするべきです。

shouldSample = (rv >= threshold)

閾値をサンプリング確率に変換する

サンプリング確率は0.0から1.0までの値であり、浮動小数点数を使って2^56で割ることで計算できます。

# embedded _ in numbers for clarity (permitted by Python3)
maxth = 0x100_0000_0000_0000  # 2^56
prob = float(maxth - threshold) / maxth

閾値を補正カウント(サンプリングレート)に変換する

補正カウントは、このサンプルが母集団の中で表しているアイテムのおおよその数量を示します。 これは 1/probability に等しくなります。 これは、非確率的サンプリングによって得られたスパン(th 値を持たないサンプリング済みスパン)に対しては定義されません。

トレードオフと緩和策

この提案は、何が必要かについてSampling SIGで長く続いた交渉と、それを表現するさまざまな代替形式の結果です。 このissueは、議論されたさまざまな形式とそれぞれの長所・短所を網羅的に取り上げています。 この提案は、その決定の結果です。

先行技術と代替技術

既存の r-value と p-value の仕様はこの問題を解決しようとしましたが、2のべき乗に限定されており、これは不十分でした。

未解決の問題

この仕様は、異なる実装オプションの余地を残しています。 たとえば、16進数文字列を比較する方法と、それらを数値形式に変換する方法は、どちらも閾値を扱うための実行可能な代替手段です。

また、一部の実装は(0から1.0の範囲の)サンプリング確率や、サンプリングレート(1/probability)を使うことを好むことも分かっています。 この設計は、少なくとも小数点以下6桁の精度まで、損失なくこれらの形式との相互変換を可能にします。

今後の課題

これにより、サンプリングシステムは、補正が可能な形で一貫性のあるサンプリング情報をダウンストリームに伝搬できるようになります。 たとえば、これによりOTelコレクターのテールサンプリングプロセッサーが、標準的な方法でバックエンドにそのサンプリング決定を伝搬できるようになります。 これにより、バックエンドシステムはデータの表示において実効的なサンプリング確率を使用できるようになります。