## Memo ## Memo with LLM ### 論文情報 - **論文タイトル**: 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) - **カンファレンス名**: VLDB 2025 (The VLDB Endowment, Vol. 18, No. 8) - **発表年**: 2025年 ### 論文概要 本論文では、Prometheusなどの時系列監視システムにおけるルールクエリの運用コストと遅延を削減するため、近似ファーストなクエリフレームワーク「PromSketch」を提案している。PromSketchは、ウィンドウベースの近似クエリフレームワークとスケッチベースの事前計算を組み合わせることで、中間キャッシュとして機能し、大幅なパフォーマンス改善を実現している。 ### 詳細解説 #### 問題設定 時系列監視システム（[[Prometheus]]、[[VictoriaMetrics]]など）は、システムコンポーネントから時系列メトリクスを収集し、周期的なウィンドウベース集約（ルールクエリ）を実行する。しかし、ルールクエリの運用コストとクエリ遅延が高いという問題がある。入力は様々なシステムコンポーネントからの時系列データサンプル（メトリクス値、タイムスタンプ、ラベル）で、出力は統計的集約結果（分位値、トップK、カーディナリティなど）である。 #### 提案手法 PromSketchは以下の2つの主要なアイデアに基づいている： 1. **拡張されたスライディングウィンドウモデル**: Exponential Histogram（EH）をベースとして、連続する区間を指数関数的に増加するサイズのバケットに分割し、中間結果をキャッシュする。これにより任意のサブウィンドウクエリに対応可能。 2. **スケッチとの組み合わせ**: - **EHKLL**: EH + KLL sketch による分位値推定 - **EHUniv**: EH + Universal sketching による複数統計（エントロピー、distinct counting、L2ノルムなど）の同時推定 - **Uniform Sampling**: 平均、標準偏差などの統計用 数式的には、EHは最新ウィンドウW = (t-T, t)を非重複バケットB₁, B₂, ..., Bₗに分割し、各バケットでスケッチを維持する。クエリ時は対象となるバケットを線形マージしてファイナル結果を得る。 #### 新規性 従来のExact監視システム（VictoriaMetrics等）は効率的なストレージエンジンやパラレル処理により遅延を削減するが、重複したデータスキャンと計算の問題は解決していない。既存の近似手法（サンプリング、固定スライディングウィンドウスケッチ）は精度や汎用性に制限がある。PromSketchは以下の点で新規性がある： - 時系列監視システム向けの初のエンドツーエンド近似中間キャッシング設計 - EHと異なるタイプのスケッチ（KLL、Universal Sketching）の組み合わせ - 理論的な精度保証の提供 #### 実験設定 **データセット**: - 合成データ（Zipf分布、均等分布、動的分布） - 実世界データ（Electronic Power dataset、Google Cluster data v3、CAIDA datasets） **評価指標**: - クエリ遅延、挿入スループット、メモリ使用量 - 精度：分位値には[[K-S検定|Kolmogorov-Smirnov検定]]、その他にはMean Relative Error (MRE) **ベースライン**: Prometheus、VictoriaMetrics、Uniform Sampling #### 実験結果 **コスト削減**: - Prometheusと比較して1332倍のクエリ処理コスト削減 - VictoriaMetricsと比較して4倍以上のコスト削減 - 全体的に5%以下の平均誤差を維持 **遅延改善**: - Prometheusと比較して最大203倍の遅延削減 - VictoriaMetricsと比較して最大158倍の遅延削減 **スループット**: - EHKLL: 10M samples/s - EHUniv: 2M samples/s - Uniform Sampling: 100M samples/s - 統合システムでは1.3×-7.2×のスループット低下（アルゴリズムにより異なる） **メモリ効率**: 1M-sample windowで時系列あたり約3MBのメモリ使用量で5%誤差目標を達成。 論文では、クラウド環境での1000ノードKubernetesクラスターの監視において、月額$405,080から$48,227.8（Prometheus統合）または$2,898（VictoriaMetrics統合）への大幅なコスト削減例も示されている。 ## Abstract Prometheusなどのタイムシリーズモニタリングシステムは、基盤となるシステムインフラストラクチャの可観測性を得る上で重要な役割を果たしている。これらのシステムは、様々なシステムコンポーネントからタイムシリーズメトリクスを収集し、周期的なウィンドウベース集約（すなわち、ルールクエリ）上でモニタリングクエリを実行する。しかし、広く採用されているにもかかわらず、ルールクエリの運用コストとクエリ遅延は依然として高い。本論文では、ルールクエリにおけるウィンドウの重複に関連した反復的なデータスキャンとクエリ計算に関する主要なボトルネックを特定し、モニタリングシステムの中間キャッシュとしての近似ファーストクエリフレームワークであるPromSketchを提案する。これは、近似ウィンドウベースクエリフレームワークとスケッチベース事前計算を組み合わせることで、低い運用コストとクエリ遅延を可能にする。PromSketchは、PrometheusとVictoriaMetricsに統合可能なスタンドアローンモジュールとして実装され、Prometheusの時間集約クエリの70%をカバーしている。我々の評価では、PromSketchはPrometheusとVictoriaMetricsに対して最大2桁のクエリ遅延削減を達成し、統計全体で最大5%の平均誤差でPrometheusと比較して3桁、VictoriaMetricsと比較して少なくとも4倍のクエリ処理の運用ドルコストを削減することを示している。