> [!abstract] 概要(arXiv abstract の日本語訳) > Prometheus のような時系列モニタリングシステムは、基盤となるシステムコンポーネントのオブザーバビリティを得るうえで重要な役割を果たす。これらのシステムは各種コンポーネントから時系列メトリクスを収集し、周期的なウィンドウベースの集約(すなわちルールクエリ)に対してモニタリングクエリを実行する。しかし広く採用されているにもかかわらず、ルールクエリの運用コストとクエリレイテンシは依然として高い。本論文では、ルールクエリにおけるウィンドウの重複に起因する、繰り返しのデータスキャンとクエリ計算に関わる主要なボトルネックを特定し、モニタリングシステムの中間キャッシュとして働く近似優先(approximation-first)のクエリフレームワーク PromSketch を提示する。これは近似ウィンドウベースのクエリフレームワークとスケッチベースの事前計算を組み合わせることで、低い運用コストとクエリレイテンシを実現する。PromSketch は standalone モジュールとして実装され、Prometheus と VictoriaMetrics に統合でき、Prometheus の aggregation over time クエリの 70% をカバーする。評価では、PromSketch は Prometheus・VictoriaMetrics に対してクエリレイテンシを最大 2 桁削減し、クエリ処理の運用ドルコストを Prometheus 比で 2 桁、VictoriaMetrics 比で少なくとも 4× 削減しつつ、統計量横断で平均誤差を最大でも 5% に抑える。ソースコードは https://github.com/Froot-NetSys/promsketch で公開されている。 ## 論文情報 - **タイトル**: Approximation-First Timeseries Monitoring Query At Scale - **著者・所属**: [[Zeying Zhu]](University of Maryland)、[[Jonathan Chamberlain]](Boston University)、[[Kenny Wu]](University of Maryland)、[[David Starobinski]](Boston University)、[[Zaoxing Liu]](University of Maryland) - **媒体**: PVLDB(VLDB 2025 採録)。DOI: 10.14778/3742728.3742732 - **発表年**: 2025(arXiv プレプリント投稿 2025-05-15) - **arXiv ID**: 2505.10560 - **コード**: [[Froot-NetSys promsketch]](https://github.com/Froot-NetSys/promsketch、Go 約 5K 行) ## 概要 時系列モニタリングの周期的ルールクエリ(alerting / recording rule)は、重複するウィンドウに対して繰り返しデータをスキャンし計算し直すため、運用コストとレイテンシが高い。PromSketch は生データや最終結果ではなく**中間結果**を in-memory にキャッシュする近似クエリキャッシュで、Exponential Histogram(EH)による任意サブウィンドウ対応のスライディングウィンドウフレームワークと、KLL・Universal Sketching を可証明な誤差保証つきで組み合わせる。Prometheus・VictoriaMetrics に約 30 行のパッチで統合でき、平均誤差 5% 以下でレイテンシを最大 2 桁、クエリ処理コストを Prometheus 比約 400× 削減する。 ## 問題設定 - **入力**: 時系列メトリクス(`ρ = (l, t, v)`、`l` は `m` 個のラベル次元、`t` は timestamp、`v` は値)のストリーム。ユーザーは PromQL で**ルールクエリ**(recording rule = 結果を保存、alerting rule = 条件で通知)を定義し、評価間隔 `T_eval` ごとに直近ウィンドウ `T_q` 上の集約クエリ `q` を周期実行する。 - **出力**: 各評価時刻における集約統計量(quantile、count、distinct、entropy、L2 norm、avg など)の近似値。ズームイン診断のため任意のサブウィンドウ `(t1, t2) ⊆ W` も問い合わせ可能。 - **前提**: ルールクエリは本質的にスライディングウィンドウクエリであり、連続する評価ウィンドウや複数ルールが**同じ重複区間**を繰り返し参照する。本研究は**時間次元の集約クエリ**(aggregation over time)を最適化対象とし、ラベル次元の集約は将来課題とする。 - **規模感**: 1000 ノード × 1000 メトリクスのクラスタで月 2680 億サンプル、10 並行ルールクエリを毎分実行、各クエリ 80 億サンプル処理。100K〜100 万サンプルのウィンドウを扱う(DDoS 検知など)。 ## 提案手法 - **アーキテクチャ(Fig. 4)**: PromSketch は in-memory の近似キャッシュ。data ingester がサンプルをバックエンド TSDB と PromSketch キャッシュの両方に並列挿入する。ルールクエリが発行されると querier がまずキャッシュ(時間範囲・統計関数)を確認し、ヒットすれば低レイテンシで推定値を返し(fast query path)、ミスすれば元の TSDB クエリエンジンへフォールバックして生データをスキャンし厳密値を計算する(slow query path)。 - **中間結果キャッシュという設計判断**: 生データキャッシュは重複クエリ計算を削減できず、メモリも肥大化する。最終結果キャッシュは事前定義していないドリルダウンクエリを最適化できない。そこで両者の中間として、Exponential Histogram のバケット(buckets)という中間結果を保持し、クエリ時にバケットを線形マージして任意サブウィンドウの結果を得る。 - **EH を SH より選ぶ理由**: Exponential Histogram(EH)は非重複バケットを保ち、新規挿入は最新(最小)バケットへの償却 `O(1)` 挿入で済む(加法的マージ性のみ要求)。Smooth Histogram(SH)は重複バケットを保ち減算性を要求、挿入は各アクティブバケットへの `O(log N)`。EH はバケットが小さく内部データ構造も小さいため大規模取り込みで有利。 - **EHKLL(Alg. 1、quantile 系)**: 各 EH バケットに KLL sketch を持たせ quantile を維持。クエリ `(t1, t2, φ)` では `t1`・`t2` を含む 2 バケットを特定し、その間の KLL を EH に基づきマージして `φ`-quantile を返す。`quantile_over_time` / `min` / `max` をカバー。集約 rank 誤差は `ε_EHKLL ≤ 2ε_EH + ε_KLL` と証明。メモリは `O((1/ε_KLL) log²log(1/δε_KLL) · (1/ε_EH) log N)`。 - **EHUniv(Alg. 2、GSum 系)**: 各 EH バケットに **Universal Sketch** を持たせ、`G = Σ g(f_i)` 形式の GSum 統計を 1 つのスケッチインスタンスで複数同時に推定する(L0=distinct、L1=count、L2 norm、entropy、TopK)。統計ごとに別スケッチを持つ素朴解の per-statistic 労力とメモリ重複を回避する。`O(ε⁻⁴ log³N log M log δ⁻¹)` ビット。 - **実装上の工夫**: (1) **hybrid map/sketch** — 小さいバケット(サイズ 1,2,4…)は厳密な item frequency map、大きいバケットは Universal Sketch を使い、メモリと更新時間を削減し小バケットの精度を上げる。map がしきい値を超えたらスケッチへ変換。(2) **one layer update** — 挿入ごとに最下層の sampled layer のみ更新。(3) **pyramid memory** — 上層に大きい Count Sketch、下層に小さいものを割り当てる。(4) avg/sum/stddev/variance などは sliding window **uniform sampling** で近似対応。 ## 新規性 既存の近似手法に対し、PromSketch は次を初めて実現したと主張する(§1 contributions): (1) 様々な時間範囲・統計量に対する**エンドツーエンドの近似中間キャッシュ設計**を時系列モニタリングに導入、(2) Exponential Histogram と複数種のスケッチ(KLL・Universal Sketching)の**組み合わせ**で多様なウィンドウ・統計量を支援、(3) そうした構成の保証を**解析的に証明**。既存のスライディングウィンドウスケッチ(WCSS・MicroscopeSketch 等)は固定ウィンドウ・特定統計に限られ、サブウィンドウクエリを支援しない。SQL 向け事前計算(LindormTSDB 等)は sum/max など基本統計と固定区間に限られる。サンプリング(Thanos のダウンサンプリング等)は quantile など複雑統計で精度が劣化する。 ## 実験設定 - **テストベッド**: 単機 = Ubuntu 20.04、32 コア Intel Xeon Gold 6142(2.6GHz)、384GB DRAM、1TB SATA HDD。クラスタ = 3 サーバ、各 24 コア AMD 7402P(2.8GHz)、128GB DRAM、1.6TB NVMe SSD、100Gbps NIC。 - **実装**: Go 約 5K 行のプラグイン。Prometheus(release-2.52)と VictoriaMetrics(release-v1.102.0)に統合。Grafana Mimir 等にも移植可能。 - **データセット**: 合成 = Zipf 分布(`Pr(k)=(1+k)^-1.01`)1000 万サンプル、Uniform 1000 万、Dynamic(Zipf/uniform/normal を遷移)。実トレース = Electronic Power(Power)、Google Cluster data v3(Google、`start_time` を時刻、`average_usage.memory` をメモリ使用量に)。EHUniv 評価は CAIDA の送信元 IP トレース(NYC Equinix backbone、2018-12-20=CAIDA2018、2019-01-17=CAIDA2019)。 - **比較対象**: (1) Prometheus、(2) VictoriaMetrics 単機版、(3) Uniform Sampling(サンプリング率可変、配列ベースキャッシュ層)。 - **評価指標**: ルールクエリレイテンシ、挿入スループット、メモリ使用量、精度(厳密統計に対する Mean Relative Error)、運用コスト。quantile/min/max は Kolmogorov-Smirnov 検定(KSTest)で CDF 差を評価。パラメータは `k_KLL=256`・`k_EH=50`(EHKLL、5% KSTest 誤差)、`k_EH=20`(EHUniv、5% 相対誤差)。 ## 実験結果 - **運用コスト(Table 1)**: 1000 ノードクラスタ・月 2680 億サンプル・10 ルールクエリ毎分の見積もり。クエリ処理コストは AWS Prometheus の $11,520 → PS-PM(PromSketch+Prometheus)$28.6(約 400× 削減)。VictoriaMetrics の $7,443 以上 → PS-VM $1,833 以下(4× 以上削減)。ストレージ・取り込みコストは増やさない。 - **クエリレイテンシ(Table 4、単機・10K 時系列)**: EHKLL で quantile を Prometheus 比最大 203×・VictoriaMetrics 比最大 78× 高速化。EHUniv で distinct/entropy/L2 norm を Prometheus 比最大 231×・VictoriaMetrics 比最大 158× 高速化。10% uniform sampling で avg/stddev を Prometheus 比 135×・VictoriaMetrics 比 21× 高速化。VictoriaMetrics 側の改善幅が小さいのは同システムが avg をデータキャッシュで最適化済みのため(ただし quantile/distinct は最適化しない)。 - **コスト-精度(Fig. 6)**: 最小サブウィンドウ(10K サンプル)でも 5% 未満の誤差を保ちつつ、厳密ベースライン比でコストを EHKLL 75×・Sampling 10×・EHUniv 5× 削減。 - **挿入スループット(Fig. 7)**: PromSketch 単独で EHKLL 10M samples/s、EHUniv 2M samples/s、10% uniform sampling 100M samples/s。Prometheus 統合時は非キャッシュ Prometheus 比 1.3×〜3.1× の低下にとどまる。スレッド数に対し線形スケール。 - **分散版(Table 5/6)**: VictoriaMetrics クラスタ版に統合し 3 サーバへ分散。総レイテンシを VictoriaMetrics クラスタ比最大 30× 削減。1→3 ノードで挿入スループットが 1.33M/s→3.86M/s と線形スケール。レイテンシは sub-linear speedup(全クエリノードが使われないため)。 - **対 MicroscopeSketch(Fig. 13)**: TopK-frequent item finding で 1.7〜3.3MB のメモリ下、最大 8× 高い挿入スループット・より小さい誤差・高い recall を達成。EH が複数ウィンドウを同時支援できるため。 ## 考察 - **CPU プロファイル(Table 2)**: quantile ルールクエリで Data Scanning が CPU 時間の 41%(Prometheus)/80.2%(VictoriaMetrics)を占め最大ボトルネック。次いで Query computation(27.6% / 11.7%)、Go GC(24.7% / 4.3%)。中間結果キャッシュは両者を同時に削減する。 - **メモリ-精度(§6.2)**: メモリ増で精度向上。4MB で CAIDA 上 L2 norm 2%・entropy 1%・distinct 2% の MRE。EHUniv はメモリが厳密アルゴリズムに近づくとほぼ誤差ゼロ。`k_EH` を大きくするとウィンドウアライメント誤差が減るが(小バケットが exact map になり)メモリは増える。 - **信頼性/順序**: PromSketch 障害時は in-memory キャッシュをストレージの旧データから再構築でき、別インスタンスが新データを受け付ける。out-of-order/重複サンプルは VictoriaMetrics/Prometheus 同様に拒否し、dedup・reorder 後段に置く。 ## 強み / 弱点・課題 - **Strengths**: (1) 繰り返しデータスキャンと繰り返し計算という 2 ボトルネックを中間結果キャッシュで同時に攻める着眼。(2) EH+KLL / EH+Universal Sketch の組み合わせに**可証明な誤差-空間境界**を与えた理論面。(3) 約 30 行パッチで既存 Prometheus/VictoriaMetrics に載る実装の実用性。(4) 単機・分散の双方で評価。 - **Weaknesses / Limitations**: (1) 最適化対象は**時間次元の集約のみ**で、ラベル次元集約は将来課題。(2) Prometheus の aggregation-over-time の 70% カバーにとどまる(残り 30% は非対応)。(3) 近似ゆえ 5% 程度の誤差を許容できる用途に限られる。(4) 分散版のレイテンシ speedup は sub-linear(スケジューラが全クエリノードを使わない)。(5) avg/sum 系は uniform sampling 依存で、quantile/GSum 系ほどの精度保証はない。