Yoshi Yamaguchi

OTEP-0149: ヒストグラムprotobufへの指数バケットの追加

ヒストグラムprotobufへの指数バケットの追加

動機

現在、OTelのprotobufプロトコルは明示的境界バケットのみをサポートしています。 各バケットの境界とカウントは明示的に定義する必要があります。 これは、境界にパターンがあるバケット、たとえば指数（すなわち対数スケール）バケットを転送するには非効率です。 さらに重要なことに、バケットのパターン情報がなければ、受信側はこれらのバケットに対する処理を最適化できない可能性があります。 指数バケットもサポートするプロトコルがあれば、バケットの数にかかわらず境界をわずかなパラメータでエンコードでき、受信側はこれらのバケットが指数であるという知識をもとに処理を最適化できます。

明示的バケット型は、任意のバケット境界のためのフォールバックとして維持されます。 たとえば、Prometheusのヒストグラムは、ユーザーが任意に定義した境界を伴うことがよくあります。

指数バケットが追加される理由は、ロングテール分布を表現するのに非常に優れているためです。 これは、応答時間の測定のようなOTelの対象アプリケーションに共通するものです。 指数バケット（すなわち対数スケールバケット）は、ロングテール分布の広い範囲をカバーするために、線形スケールバケットよりもはるかに少ないバケット数で済みます。 さらに、パーセンタイル・分位数は、全範囲にわたって一定の相対誤差で指数バケットから計算できます。

解説

指数バケットが追加されます。 一般に、バケットの境界は次の形式です。

bound = base ^ exponent

ここで、baseは境界系列のパラメータであり、exponentは整数です。 exponentは正、負、あるいは0のいずれもとり得ることに注意してください。 このような境界は「対数スケール境界」としても一般に知られています。

内部の詳細

追加が提案されているメッセージ型は次のとおりです。

message ExponentialBuckets {
    double base = 1;
    double zero_count = 2; // Count of values exactly at zero.
    ExponentialBucketCounts positive_value_counts = 3;
    ExponentialBucketCounts negative_value_counts = 4; // Negative values are bucketed with their absolute values
}

// "repeated double bucket_counts" represents an array of N numbers from bucket_counts[0] to bucket_counts[N-1].
// With index i starting at 0, ending at N-1, ExponentialBucketCounts defines N buckets, where
// bucket[i].start_bound = base ^ (i + exponent_offset)
// bucket[i].end_bound = base ^ (i + 1 + exponent_offset)
// bucket[i].count = bucket_counts[i]
message ExponentialBucketCounts {
    sint32 exponent_offset = 1; // offset may be negative.
    repeated double bucket_counts = 2;
}

注記:

  • ExponentialBucketsは、#272におけるバケット型の「one-of」の一つとして追加されます。
  • #257に従い、“double"を受け入れるヒストグラムのみが定義されます。
  • #259に従い、バケットカウントの型は"double"です。

トレードオフと緩和策

シンプルさが主要な設計目標です。 このフォーマットは最も一般的なシナリオを対象としています。 現時点では、ExponentialBucketsに準拠しないヒストグラムは明示的バケットとしてエンコードすることができます。 あるヒストグラム型が十分に一般的であれば、新しいバケット型が将来追加されるかもしれません。

以下はExponentialBucketsの制約です。

  • 正の値と負の値のバケットは、同じ"base"を持たなければなりません。
  • バケットは値の全範囲をカバーしなければなりません。 将来的には、ExponentialBucketCountsに、最も高いバケットを超える値と最も低いバケットを下回る値のカウントのために、それぞれoverflow_countとunderflow_countが追加されるかもしれません。 しかし、overflowバケットやunderflowバケットは「純粋な対数スケール」という性質を損ないます。 メモリコストを削減する際には、下記の「マージ」の節で述べる「リスケール」が優先されます。
  • ExponentialBucketCountsは密なバケット向けに設計されています。 最も低いバケットと最も高いバケットの間では、ほとんどのバケットが空でないことが想定されています。 これはテレメトリーアプリケーションにおける一般的なケースです。
  • 全ての境界に掛け合わされる「reference」は含まれていません。 これは常に暗黙的に1です。

先行技術と代替技術

#226は複数のヒストグラム型を一度に追加しようと試みました。 このEPはスコープを指数ヒストグラムのみに縮小します。 そして、ヒストグラム型がカウントフィールドを共有しないことが決定されたため（#259参照）、新しいフォーマットの複雑さはより低くなっています。

未解決の疑問

普遍的にマージ可能なヒストグラムに向けて

異なる型、あるいは同じ型でも異なるパラメータを持つヒストグラムのマージは、依然として課題として残っています。 #226には長い議論があります。

マージ手法によっては、アーティファクト（元のデータには存在しない情報）を導入してしまうことがあります。 一般に、バケットの分割はアーティファクトを導入します。 たとえば、バケットの分割に線形補間を使う場合、そのバケット内が一様分布であると仮定していることになります。 「一様分布」は元のデータには存在しない情報です。 一方で、バケットのマージはアーティファクトを導入しません。 同一の境界を持つ二つのヒストグラムのバケットをマージすることは、完全にアーティファクトフリーです。 一つのヒストグラム内で複数の隣接するバケットをマージすることもアーティファクトフリーですが、ヒストグラムの解像度を低下させます。 このようなマージが「ロッシー（lossy）」であるかどうかは議論の余地があります。 この曖昧さのため、本ドキュメントでは「lossy」という用語を使用しません。

指数ヒストグラムの場合、base1 = base2 ^ Nで、Nが整数であれば、二つのヒストグラムはアーティファクトなしにマージできます。 さらに、次のような一連のbaseを導入することができます。

base = referenceBase ^ (2 ^ baseScale)

この系列のbaseを使う任意の二つのヒストグラムは、アーティファクトなしにマージできます。 このアプローチはよく知られており、Google社内での利用やNew Relic Distribution Metricを含む複数のベンダーで使用されています。 UDDSketchの論文にも記述されています。

このような「2対1」の二進マージには次の利点があります。

  • この系列の任意の二つのヒストグラムはアーティファクトなしにマージできます。 これは非常に魅力的な性質です。
  • 単一のヒストグラムは、baseをbase^2に増加させる代償として、2対1マージを使うことで2倍に縮小できます。 「ヒストグラムの解像度低下」と「アプリケーションのメモリ肥大化」との選択に直面した場合、縮小するのが明白な選択です。

ヒストグラムのプロデューサーは、メモリコストを制御するために「オートスケール」を実装するかもしれません。 目標相対誤差と最大バケット数について適切なデフォルト設定があれば、プロデューサーは「自動魔法的」な方法で動作できます。 プロデューサーは目標解像度のbaseから始め、受信データの範囲がメモリ制限を超えるヒストグラムを引き起こす場合には、動的にスケールを変更することができます。 New RelicとGoogleは、社内利用のためにこのようなロジックを実装しています。 これらの企業によるオープンソース版は計画中です。

スケーリングされた指数ヒストグラムの主な欠点は、任意のbaseをサポートしないことです。 baseは2乗による増加、あるいは平方根による減少のみが可能です。 ユーザーの目標相対誤差がその系列上に正確に一致しない限り、より次に小さいbaseを選択せざるを得ず、目標のためにより多くの領域を消費します。 しかし、その代わりに、普遍的にマージ可能なヒストグラムが手に入ります。 これは合理的なトレードオフに思えます。 下記の議論で示されているように、通常、ユーザーは1%、2%、4%程度の誤差から選択することになります。 誤差の目標は正確な科学であることはほとんどないため、限られたメニューから選択することは、ユーザーにそれほど大きな負担を追加しません。

「referenceBase」について合意できれば、普遍的にマージ可能なヒストグラムを手に入れることができます。 #226では、2のreferenceBaseが提案されました。 この系列の一般形は次のとおりです。

base = 2 ^ (2 ^ baseScale)

ここで、baseScaleは整数です。

  • baseScale = 0のとき、baseはちょうどreferenceBaseになります。
  • baseScale > 0のとき、2^baseScale個のreferenceBaseバケットが一つにマージされます。
  • baseScale < 0のとき、referenceBaseバケット（ここではlog2バケット）は2^(-baseScale)個のサブバケットに細分化されます。

実際には、baseScaleの最も興味深い範囲は-4付近であり、そこではパーセンタイルの相対誤差は数パーセント程度になります。 次の表は関心のあるbaseを示しています。 ここでの相対誤差は「squareRoot(base) - 1」から計算されています。 これは、パーセンタイルの計算が相対誤差を最小化するために対数スケールでのバケットの中点を返すことを前提としています。

scale   #subBuckets base         relative_error
-3       8          1.090507733  4.43%
-4      16          1.044273782  2.19%
-5      32          1.021897149  1.09%

#226のコメントには、なぜ2がreferenceBaseとして選ばれたのかについて、より詳しい説明があります。 要するに、「コンピュータは二進数が好き」だからです。 referenceBaseを選ぶのであれば、なぜそれを2（二進で「10」）にしないのでしょうか。

base10とbase2

代わりに、10進数のreferenceBase（10進）を選ぶこともできます。 これには「人間にとっての親しみやすさ」がある一方で、実際にはその利点はごくわずかです。 下記の表で示されているように、base10では関心のあるbaseScaleは-6付近であり、そこではlog10バケットが64個のサブバケットに細分化されます。 10、100、1000といった境界が現れるのは64バケットごとにすぎません。 「人間にとっての親しみやすさ」の価値はごくわずかです。

scale   #subBuckets base         relative error
-5       32         1.074607828  3.66%
-6       64         1.036632928  1.82%
-7      128         1.018151722  0.90%

base2とbase10を比較するために、ヒストグラムの以下のユースケースをさらに検討してみましょう。

  1. ヒストグラムチャートの表示。 約1.04（約2%の相対誤差）程度のbaseでは、100倍を超える典型的な範囲に対して数百個のバケットが存在します。 これだけの点があれば、生データがbase2かbase10かにかかわらず、比較的滑らかな曲線を描くことができます。
  2. パーセンタイルや分位数の計算。 これはSLOモニタリングでよく使われます。 SLOの例: 「応答時間の99パーセンタイルは100ms以下でなければならない」。 相対誤差を最小化するために、パーセンタイルの計算は通常、対数スケールでのバケットの中点を返します。 そのため、ヒストグラムがbase10であっても、返されるパーセンタイル値は10、100、1000などちょうどの値にはなりません。
  3. 「100を下回る値の割合はどれくらいか」といった質問に答えること。 閾値が10、100、1000などの場合、base10ヒストグラムは正確な答えを与えます。 しかし、10進の世界であっても、10の累乗の数は少数派です。 200や500などの閾値では、base10ヒストグラムはbase2に対して優位性を持ちません。 これらの場合に正確な答えが必要であれば、ユーザーは指数バケットを使う代わりに、これらの境界で明示的バケットを作成するべきです。

したがって、base10指数ヒストグラムの「人間にとっての親しみやすさ」は、大部分が幻想です。 ある程度は、base2対base10の問題はずっと前に答えが出ています。 コンピュータは、base10からの入力をbase2に変換し、base2で処理を行い、最終的な出力をbase2からbase10に変換します。 ヒストグラムの場合、私たちは「double」で入力を受け取りますが、これはすでに二進浮動小数点フォーマットになっています。 これらの数値をbase10境界でバケット化することは、処理の途中で実質的に基数を切り替えることになります。 それは単に複雑さと計算コストを増やすだけです。

普遍的にマージ可能なヒストグラムのためのプロトコルサポート

さて、問題は、普遍的にマージ可能なヒストグラムのサポートを追加するかどうか、そしていつ追加するかです。 いくつかの選択肢があります。

  1. プロトコルに特別なサポートを設けない。 受信側は、baseがreferenceBase系列上のbaseに十分近ければ、baseScaleとreferenceBaseを導出します。 実装は「十分に近い」がどの程度かを決定します。
  2. プロトコルがbaseScaleを明示的に示すことを許可し、referenceBaseは2に固定する。
  3. プロトコルがbaseScaleと任意のreferenceBaseを明示的に示すことを許可する。

本提案は現在、選択肢1で記述されており、後で選択肢2に拡張する道筋を持っています。

// Current. Option 1
double base = 1;

// Future. Option 2. Changing a single value into a member of a new oneof is safe and binary compatible
oneof base_spec {
   double base = 1;
   sint32 base_scale = 99;  // base = 2 ^ (2^base_scale). base_scale may be negative.
}

あるいは、今すぐ選択肢2を実施すべきでしょうか。

将来の可能性

この提案が可能にする将来の変更にはどのようなものがあるでしょうか。

  • 普遍的にマージ可能なヒストグラムのサポート
  • 追加のヒストグラム型の追加