> [!abstract] 概要(論文 abstract の日本語訳) > Monarch は Google のグローバル分散インメモリ時系列データベースシステムである。Monarch はマルチテナントサービスとして動作し、主に Google のビリオンユーザースケールのアプリケーションとシステムの可用性・正確性・性能・負荷その他の側面を監視するために使われる。毎秒、システムはテラバイト規模の時系列データをメモリに取り込み、数百万のクエリを処理する。Monarch はリージョン化されたアーキテクチャにより信頼性とスケーラビリティを確保し、グローバルクエリと構成プレーンにより複数リージョンを統合された単一システムとして統合する。分散アーキテクチャの上に、Monarch は柔軟な構成・表現力豊かなリレーショナルデータモデル・強力なクエリを提供する。本論文は Monarch のシステム構造と、リージョン化された分散アーキテクチャ上で信頼性の高い柔軟な統合システムを実現する新規のメカニズムを説明する。また、Monarch を Google のサービスとして開発・運用した 10 年間の経験から得た重要な教訓も共有する。 ## 論文情報 - **タイトル**: Monarch: Google's Planet-Scale In-Memory Time Series Database - **著者**: Colin Adams, Luis Alonso, Benjamin Atkin, John Banning, Sumeer Bhola, Rick Buskens, Ming Chen, Xi Chen, Yoo Chung, Qin Jia, Nick Sakharov, George Talbot, Adam Tart, Nick Taylor (Google LLC) - **媒体**: PVLDB (Proceedings of the VLDB Endowment), Vol. 13, No. 12, pp. 3181–3194, 2020 - **DOI**: https://doi.org/10.14778/3181-3194 - **原本**: `.raw/papers/6348.pdf` ## 概要 Monarch は Google が 2010 年から運用するプラネットスケール・マルチテナント・インメモリ時系列データベースである。前身の [[Borgmon]](2004〜2014 年に拡大)が持っていた「分散管理の運用負担・スキーマなし・distribution 値型非サポート・手動シャーディング」の 4 課題を解決するために設計された。リージョン化された自律的監視サブシステムと、グローバルクエリ・構成プレーンを組み合わせた二層構造が設計の核心である。 ## 問題設定 - **入力**: 数千チームが運用するグローバルユーザー向けサービスから毎秒生成されるメトリクス時系列。エンティティ数は 10 億以上、5 大陸に分散。 - **出力**: (1) 異常検知・アラート、(2) ダッシュボード表示、(3) アドホック診断クエリ。 - **制約**: アラートパスでの可用性最優先(Bigtable・Spanner 等への依存禁止、循環依存回避)。最新データを遅延なく返す必要があり、一貫性より可用性を選ぶ(CAP: AP)。 ## 提案手法 ### アーキテクチャ Figure 1 に示す 3 コンポーネントカテゴリで構成される: **状態保持コンポーネント**: - **Leaf**: インメモリ時系列ストアにデータを保持し、recovery log(Colossus 上)にも書く。クエリ処理・データ移動中も継続動作。 - **Recovery log**: Leaf と同じデータをディスクに保持。長期リポジトリへの書き換えにも使われる(詳細は論文スコープ外)。 - **Global config server + zonal mirrors**: 構成データを Spanner データベースで保持。 **取り込みコンポーネント**: - **Ingestion router**: 時系列キーの location フィールドに基づきデータを適切ゾーンのleaf routerへ転送。 - **Leaf router**: ゾーン内でデータを target range ごとに leaf(3 つのレプリカ)へ転送。range map は range assigner でなく leaf から更新されるため assigner 障害時も継続。 - **Range assigner**: ゾーン内の leaf 間で target range の分割・統合・移動を管理し、負荷(CPU・メモリ)を均衡させる。[Slicer](ref [1])と類似の手法。 **クエリ実行コンポーネント**: - **Mixer(root/zone)**: クエリをサブクエリに分割してleafに送り、結果をマージ。ルートレベル(root mixer → zone mixer → leaf)の 3 階層ツリー。 - **Index server(root/zone)**: FHI(後述)を保持し、クエリファンアウトを制限。 - **Evaluator(root/zone)**: standing query を定期実行して結果を leaf に書き戻す。 ### データモデル 概念的には「**target schema**と**metric schema**を組み合わせたリレーショナルテーブル**」として時系列を保存する(Figure 2)。 - **Target schema**: 監視エンティティを特定するキー列の集合。例えば `ComputeTask` は `user / job / cluster / task_num` の 4 フィールドを持つ。各 target schema の 1 フィールドが location フィールドとして指定され、時系列のルーティング先ゾーンを決定する。 - **Metric schema**: メトリクスの 1 側面を計測するキー列と値列。メトリクス名はファイルシステム的な命名(例: `/rpc/server/latency`)。 - **値型**: boolean / int64 / double / string / **distribution** / tuple をサポート。distribution は double 値の集合をヒストグラム(バケット境界は設定可能)で表現する compact 型であり、統計値(平均・カウント・標準偏差)も保持する。99パーセンタイル・99.9パーセンタイルのレイテンシ分析に不可欠。 - **Exemplar**: distribution の各バケットに 1 つのサンプル値を格納できる。RPC メトリクスであれば Dapper トレース[ref 41]を埋め込むことで、テールレイテンシの原因となった特定リクエストを直接たどれる(Figure 4)。 - **Gauge vs Cumulative**: Gauge は瞬間値(例: キュー長)。Cumulative は開始時刻からの累積(Figure 3)。Cumulative はデータ点が欠落しても意味を保てるため、ジョブスケジューラによる定期再起動が多い分散システムに適する。 ### スケーラブルな収集(Section 4) 4 ステップの書き込みパス: クライアント → Ingestion router(ゾーン選択) → Leaf router(target range → leaf 選択) → Leaf(インメモリ書き込み + recovery log)。 **ゾーン内負荷分散(Lexicographic Sharding)**: target 文字列(schema 名 + フィールド値を連接した文字列)で辞書順にシャードする。同一 target の全 metric は同一 leaf に集約されるため、(1) 書き込みメッセージ 1 件で数百メトリクスを 3 レプリカにまとめて送れる、(2) intra-target join をleafレベルで完結できる。target range の移動中は source/destination 両 leaf が同時に収集・ログを書くため、移動中もデータ可用性を保持する。 **Collection Aggregation**: 数億〜数十億の raw time series をそのまま格納することが不可能なユースケース(例: ディスク I/O をユーザー別に集計)を解決する。クライアントは連続する累積点の**差分(delta)**を送り、leaf router がデルタを同一 leaf set に集めて leaf で集約する。leaf 内では delta をバケット(長さ $T_B$、1〜60 秒)に入れ、**admission window**($T_W = T_D + \text{TrueTime} \text{ uncertainty}$)より古いデルタは棄却して最新性を保つ。バケット確定後はランレングス・デルタ符号化で効率的に格納。実績値: 平均 36 入力時系列 → 1 出力時系列、極端な例では 100 万 → 1。CPU 使用量は代替手法(raw 収集 → standing query で集約)の **25%**。 ### スケーラブルなクエリ(Section 5) **クエリ言語**: リレーショナル代数に類似したパイプライン形式。`fetch → filter → align → join → group_by` の流れで記述(Figure 6)。distribution 値への percentile 抽出、top-N、時間軸集計も可能。 **クエリ実行ツリー**: root mixer → zone mixer → leaf の 3 階層。zone evaluator が生成する standing query は直接 zone mixer に送られる(root を迂回)。 **クエリプッシュダウン(Section 5.3)**: 静的不変量(target schema の location フィールド・シャーディング設計)を使い、操作をできる限り低いレベルで完結させる。例: location フィールドを出力キーに含む `group_by` はゾーンレベルで完結、intra-target join は leaf レベルで完結。Table 3 が効果を示す: | 構成 | FHI | Join | Group by | レイテンシ | Leaf 数 | |---|---|---|---|---|---| | フル最適化 | あり | leaf | leaf | 6.73 s | 68k | | zone join | あり | zone | zone | 242.5 s | 92k | | root join | あり | root | root | 1728.3 s | 92k | | FHI 無効 | なし | leaf | leaf | 67.54 s | 141k | Standing query の **95%** がゾーンレベルで評価され、ルートレベルの cross-zone 書き込みを回避。 **Field Hints Index(FHI)(Section 5.4)**: クエリファンアウトを抑制するため、フィールド値の **トライグラム**(3 文字 n-gram)を fingerprint(int64)にマップするインメモリ index。子ノードが「そのクエリのフィールド述語を持つ可能性がある」かを判定し、偽陽性は replica resolution で後処理される。サイズ: huge-zone-2(15,475 leaf)の FHI は 808 MB。fingerprintの平均サイズは 1.3 バイト/エントリ。抑制率: ゾーンレベル **99.2〜99.6%**、ルートレベル **75.8%**。RE2 ライブラリを使った正規表現述語もトライグラムの集合演算に変換して高速処理。 **信頼性クエリ**: - **Zone pruning**: グローバルクエリで応答しないゾーンをソフトデッドライン後に除外し、クエリ完了を保証。 - **Hedged reads**: プライマリ leaf が遅い場合、等価なフォールバック leaf にクエリを複製して並行実行し、速い方の結果を採用。 ### 構成管理(Section 6) - Global config server(Spanner バックエンド)でスキーマ・retention ポリシー・standing query・アラート設定を一元管理。 - Zonal mirror に複製され、ゾーンコンポーネントはメモリにキャッシュ。config mirror 障害時も stale config で継続動作。 - retention ポリシー: サンプリング頻度・保持期間・ストレージ媒体・レプリカ数・ダウンサンプリング設定を細粒度で管理。 - Standing query: 結果を leaf に書き戻し、高速な繰り返しクエリとアラートに使う。 ## 新規性 | 先行システム | 課題 | Monarch の解決 | |---|---|---| | [[Borgmon]] | 分散管理・スキーマなし・distribution 非対応・手動シャーディング | マルチテナント・リレーショナルスキーマ・distribution 型・自動シャーディング | | [[Gorilla]] | 文字列キーのみ・クエリ言語なし・リージョン障害時のみのレプリケーション | 構造化データモデル・豊富なクエリ言語・planet-scale クエリエンジン + FHI + クエリプッシュダウン | | Prometheus 等 OSS TSDB | 2次ストレージ依存・グローバル構成なし | インメモリ・グローバル構成・クエリ集約・collection aggregation | ## 実験設定と規模(2019年7月) - **規模**: 38 ゾーン(5 大陸)、約 40 万タスク(Leaf 144,000 が最多) - **時系列数**: 約 950 億(Figure 8) - **メモリ使用量**: 約 750 TB(Figure 9) - **取り込み速度**: 約 2.2 TB/s(Figure 11) - **クエリ速度**: 毎秒 600 万(Figure 10)。95% が standing query ## 実験結果 **FHI 抑制効果(Table 2)**: | FHI名 | 子ノード数 | フィンガープリント数 | 抑制率 | ヒット率 | |---|---|---|---|---| | root | 38 | 214,468k | 75.8% | 45.0% | | small-zone-1 | 15 | 56k | 99.9% | 60.5% | | huge-zone-3 | 16,681 | 627,571k | 99.6% | 21.6% | **クエリレイテンシ(Figure 12)**: root クエリの中央値 79 ms、99.9 パーセンタイル 6 秒。large/huge ゾーンの 99.9 パーセンタイルはおよそ 50 秒(9〜23 百万時系列を fetch する standing query)。 **Collection Aggregation**: 取り込み速度は 2018 年 7 月〜2019 年 1 月でほぼ 2 倍に増加。disk I/O 等、数十億時系列キーを持つメトリクスを集約可能にしたことが主因。 ## 考察 - **可用性優先の設計選択**: Bigtable・Spanner への alerting path 依存を断つためインメモリ保持を選んだ。これにより他のほぼすべての Google ストレージが Monarch に依存する「循環依存」を断ち切った。 - **Lexicographic sharding の恩恵**: intra-target join の leaf 完結と、同一 target の全 metric を単一メッセージで送れることで、ゾーン内の水平スケールが可能になった。 - **Limitation**: ゾーン間の一貫性保証は弱い(AP を選んでいる)。非監視ユースケース(quota サービス等)が Monarch をグローバル時系列 DB として使う場合は一貫性低下を受け入れる必要がある。 ## 強み / 弱点・課題 **Strengths**: - インメモリ保持による低レイテンシアラート配信(Bigtable 等への依存なし) - リレーショナルデータモデルにより static 解析・クエリ最適化が可能 - Collection Aggregation で数十億規模の raw series を扱える - FHI により 10,000+ leaf ゾーンを数 GB のインメモリ index で管理 - 95% の standing query がゾーンで完結 → 高い network partition 耐性 **Weaknesses / Limitations**: - 一貫性より可用性を選ぶため、遅延書き込みは棄却・クエリは部分データを返す可能性がある - マルチテナントサービスとしての安定性確保は複雑(usage accounting・データサニタイゼーション・ユーザー分離・トラフィック絞り込みが必要) - コード変更は下位互換性必須であり、ライブアップデートとロールバックを前提とした開発が強制される ## 教訓(Section 9) 1. **Lexicographic sharding** はゾーンを tens of thousands の leaf まで水平スケールさせる基盤 2. **Push-based collection** は discovery service・proxy の依存を排除しアーキテクチャを単純化する 3. **Schematized data model** はクエリの静的解析・最適化を可能にし、Borgmon と比べて運用負担を増やさなかった 4. **System scaling は継続的プロセス**: FHI・collection aggregation・sharded standing query はすべて初期設計後に追加された 5. **Multi-tenancy の課題**: SLO・usage accounting・backward compatibility が継続的な開発上の制約となる