ヒストグラムと分位点推定の内部（Prometheus vs Native）

なぜ「ヒストグラムの分位点」が問題になるのか

レイテンシのp99を監視したい。しかし/devops/percentile-latency-statistics/で見たとおり、分位点は順序統計量なので加算も平均もできず、生データを全件保持するのも非現実的です。そこで各サーバーで分布を ヒストグラム に畳み込み、件数だけを集めて合算してから分位点を引きます。問題は、この「ヒストグラムから分位点を読む」工程に構造的な誤差が潜む ことです。本記事はその誤差の正体と、ネイティブヒストグラムやDDSketchがどう誤差を抑えるかを、Prometheusを軸に解説します。

古典的Prometheusヒストグラムの仕組み

古典的（classic）なPrometheusヒストグラムは、メトリクスを複数の 累積バケット に展開します。http_request_duration_seconds_bucket{le="0.1"} のように le（less than or equal、以下）ラベル付きで、「境界値 le 以下に収まった観測数」をカウンタとして公開します。重要なのは 累積（cumulative） である点です。le="0.1" のバケットは0.1秒以下の全件、le="0.5" は0.5秒以下の全件を含みます。最大の le="+Inf" は総件数（_count）に一致します。

le="0.1"  : 12000   ← 0.1s以下の累積件数
le="0.25" : 18500
le="0.5"  : 21000
le="1.0"  : 21800
le="+Inf" : 22000   ← 総件数（_count と一致）

各 le バケット間の 件数の差 が、その区間に落ちた観測数になります。例えば (0.25, 0.5] の区間には 21000 - 18500 = 2500 件が入ったと分かります。バケット境界は 収集時にあらかじめ固定 され、計測中に変えられません。これが後述の誤差の根源です。

histogram_quantile の線形補間と誤差

histogram_quantile(0.99, ...) は次の手順で分位点を推定します。まず総件数に分位点を掛けて目標順位（rank）を出す。次に累積バケットを下から走査し、目標順位を初めて超えるバケットを特定する。そして そのバケットの下側境界と上側境界の間を線形補間 して値を返します。

ここに本質的な近似があります。バケット内のデータが一様（均等）に分布していると仮定して直線で内挿する のです。現実の分布はバケット内で一様ではありません。レイテンシは右に裾を引くため、1つのバケットの中でも下側に密集して上側が疎、ということが普通に起きます。それでも補間は直線を引くので、真の分位点とずれます。

目標が le="0.5" バケット（下端0.25, 上端0.5）に入るとき:
  下端での累積 = 18500, 上端での累積 = 21000
  目標順位     = 21780（22000 × 0.99）
  → 線形補間: 0.25 + (0.5 - 0.25) × (21780 - 18500)/(21000 - 18500)
            = 0.25 + 0.25 × (3280/2500) ... 区間をはみ出すので上端付近にクランプ

誤差を支配するのは バケット幅 です。目標分位点が落ちるバケットが広いほど、補間の自由度が大きく、推定が荒れます。そして固定バケットでは 裾ほどバケットが粗くなりがち です。le=[..., 1, 2.5, 5, 10] のように上限側を間引いて設計するのが通例で、するとp99やp999が (5, 10] のような広いバケットに落ち、補間誤差が最大化します。さらに最後の +Inf バケットには 上側境界が存在しない ため、分位点がそこに落ちると値を内挿できず、Prometheusは直前バケットの上端を返します。つまり 最大の le を超える分位点は原理的に推定不能 です。

加算可能性とマージの条件

ヒストグラムの最大の武器は マージ可能性 です。同じ le 境界を持つ2つのヒストグラムは、対応するバケットの件数を足すだけで合算でき、合算後に分位点を引けば分散環境でも正しい全体のpXが得られます。これが分位点の加算不能問題を回避する正攻法です。

ただし成立条件があります。バケット境界スキームが完全に一致していること です。サービスAが le=[0.1, 0.5, 1]、サービスBが le=[0.2, 0.4, 0.8] のように異なる境界を使うと、対応づけができず単純加算できません。PromQLの sum by (le) (rate(..._bucket[5m])) で系列をまたいで合算する操作も、le が揃っていて初めて意味を持ちます。異なるバケット構成のヒストグラムを正しく統合するには、共通の粗い境界へ再ビニングするか、そもそも境界を統一しておく必要があります。古典ヒストの運用がデプロイ横断で le を固定したがるのはこのためです。

ネイティブ（指数）ヒストグラムの原理

古典ヒストの根本問題は「バケット境界を事前に固定する」点でした。ネイティブヒストグラム（Prometheusのexponential histogram、OpenTelemetryのexponential histogramに対応）は、境界を 指数的に自動生成 することでこれを解決します。

核心は、バケット境界を base^i の形で定義することです。base = 2^(2^-schema) と置き、各バケットの上側境界を base^i（i は整数のインデックス）とします。schema パラメータが解像度を決め、schema を1上げるとバケット数が倍になり相対精度が倍に細かくなります。観測値 v が来たら、i = ceil(log(v) / log(base)) でバケットインデックスを直接計算し、そのバケットのみをインクリメントします。

schema=2 のとき base = 2^(2^-2) = 2^0.25 ≒ 1.1892
バケット上側境界: ..., 1.000, 1.189, 1.414, 1.682, 2.000, ...
  各バケットの相対幅 = base - 1 ≒ 0.189（全域で一定）
観測 v=1.5 → i = ceil(log(1.5)/log(1.189)) → (1.414, 1.682] のバケットへ

この設計の効果は決定的です。バケット幅が値に比例するため、全域でバケットの相対幅が一定 になります。小さい値は狭いバケットで細かく、大きい値は広いバケットで粗く刻まれ、「値に対する相対誤差」が値域によらず一定に保たれます。古典ヒストのように裾で誤差が膨らむことがありません。しかもバケットは 観測された範囲だけ動的に生成 されるので、事前の le 設計が不要で、想定外に大きい値が来ても自動でバケットが伸びます。

DDSketch：相対誤差保証付き分位点

ネイティブヒストグラムと同じ「指数バケット」の発想を、分位点の相対誤差を理論保証 する形で定式化したのがDDSketch（Distributed Distribution Sketch）です。相対精度パラメータ alpha を与えると、推定分位点 q-hat は真値 q に対し |q-hat - q| <= alpha × q を満たすことが保証されます。例えば alpha=0.01 なら、どの分位点でも誤差は真値の1%以内です。

仕組みは指数バケットそのものです。gamma = (1 + alpha) / (1 - alpha) と置き、バケットインデックスを i = ceil(log(v) / log(gamma)) で定めます。各バケットの相対幅が 2 × alpha 程度に保たれるため、どのバケットから読んだ分位点も真値に対して相対 alpha 以内に収まります。保証が「相対」である点が肝 で、p50だろうとp999だろうと、また値が1msだろうと10秒だろうと、同じ相対精度が約束されます。古典ヒストが特定の値域でしか高精度を出せなかったのと対照的です。

DDSketchもバケット件数の加算でマージできますが、条件は古典ヒストと同型です。相対精度パラメータ（gamma、すなわち alpha）が一致するスケッチ同士でないと正しく合算できません。alpha の異なるスケッチを混ぜると、粗い側に合わせた再量子化が要ります。

運用への落とし込み

• 古典ヒストはleを裾に密に: 監視したいSLO境界（例p99の想定域）の周辺に le を細かく置く。+Inf 直下が広いと裾の分位点が壊れる。
• 裾を測るならネイティブヒスト/DDSketchへ: 相対誤差が全域一定なので、p999のような極端な分位点でも値域に依存せず安定する。事前のレンジ設計も不要。
• マージ条件を揃える: 古典なら le、ネイティブなら schema、DDSketchなら alpha を系列間で統一する。揃っていない分布表現は合算できない。
• 計算順序を守る: 必ず「合算 → 分位点」。avg(histogram_quantile(...)) のような「分位点の平均」を作らない。
• +Inf超えに注意: 分位点が最大バケットを超えると推定不能。総件数と最終バケットの乖離を監視し、レンジ設計の不備を検知する。

まとめ

• 古典的Prometheusヒストグラムは 事前固定の累積バケット で、histogram_quantile は バケット内を線形補間 する。真の分布が非線形である以上、誤差は構造的で、特に 裾の粗いバケット と +Inf 超え で破綻する。
• 誤差を支配するのは バケット幅 と le設計。観測前に分布を知っていないと適切な境界を引けず、裾の精度が出ない。
• ネイティブ（指数）ヒストグラムとDDSketch は境界を base^i／gamma^i で自動生成し、全域で相対誤差を一定 に保つ。DDSketchは相対誤差 alpha を理論保証し、値域や分位点位置に依存しない。
• どの方式も マージ可能だが、境界スキーム（le／schema／alpha）の一致が前提。そして「合算してから分位点を引く」順序を守って初めて誤差保証が意味を持つ。