# CloudRanger: Root Cause Identification for Cloud Native Systems > Wang, Xu, Ma, Lin, Pan, Y. Wang, Chen — CCGrid 2018 (18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing) ## 概要 クラウドネイティブシステム向け根本原因特定フレームワーク CloudRanger を提案する。クラウドネイティブ環境では数千のマイクロサービスが動的に運用されるため、正確なサービス呼び出しトポロジの取得は現実的でない。本論文はこの制約をブラックボックス仮定によって解消し、観測メトリクスのみから因果インパクトグラフを構築したうえで、2 次ランダムウォークで根本原因を順位付けする手法を提案する。IBM Bluemix 本番環境での検証で、同時代の最高水準手法に対し約 10% の精度向上を実証した。 ## 背景と動機 IBM Bluemix プラットフォームは 200 以上のカテゴリのパブリックマイクロサービスを提供し、1 日 15 億件超の API リクエストを処理する。サービスの異常は高レイテンシ・低可用性として現れ、連鎖伝播して最終的にシステム全体をクラッシュさせる可能性がある。担当 SRE は自動化ツールなしで根本原因の特定に平均 3 時間を要していた。 実際のインシデント例(論文 Table I)では、2 時間の記録期間に 1732 個の API に対し 1100 万点超のメトリクス(レイテンシ/スループット)が収集された。根本原因はメモリ枯渇した Bluemix イベントプロセスコンポーネント(Service API 18 = Event)で、Console → Dashboard の順で遅延が伝播したが、無関係な NLP や IBM Watson API でもレイテンシ増加が観測されており、人手での識別は困難だった。 クラウドネイティブ環境の特有の課題： 1. **動的なサービスインスタンス管理** — コンテナがスケールイン/アウト・再起動・マイグレーションされる中での追跡困難性 2. **ビジネストランザクションのパフォーマンスベースライン設定の困難さ** — 数千サービスの継続的デリバリ環境でのベースライン維持 3. **長い呼び出しパス** — 障害が上流ノードへ逆伝播し、サーキットブレーカー等のクラウドデザインパターンが障害箇所特定を阻害 先行手法 MonitorRank の問題点：実コールグラフが必要だが、Zipkin 等のトポロジ収集インフラの展開は稼働中クラウドプラットフォームへの影響が大きく現実的でない。加えてリソース共有によるサイドイフェクト(ネットワーク帯域の競合など)はコールグラフに現れない。 ## 問題定義 クラウドネイティブシステムを $n$ 個のサービスの集合 $V$ として扱い、各サービスのメトリクスデータを $n \times t$ 行列 $T$（$[T]_{i,j} = t_{i,j}$）で表す。フロントエンドサービス $v_{fe}$ に異常が観測されたとき、$T$ から根本原因サービス集合 $v_{rc} \subset V$ を発見することが目標。コールグラフ等の事前ドメイン知識は一切仮定しない。 ## CloudRanger フレームワーク 4 段階のパイプライン構造（図2）： ![[wiki/sources/_attachments/2018-CloudRanger/fig2a-framework.png]] ![[wiki/sources/_attachments/2018-CloudRanger/fig2b-framework.png]] **段階 1: 異常検知（Anomaly Detection）** 著者らの先行研究（SCC 2017）の動的しきい値法を用いる。オンライン学習アルゴリズムにより動的なワークロード環境に追従し、教師なし学習でサービスごとの異常を検知する。集約ウィンドウの選択が後続処理に大きく影響するため、論文では Bluemix の直接呼び出し関係にあるサービス間の平均遅延の統計値（約 5 秒）を採用した。 **段階 2: インパクトグラフ構築（Impact Graph Construction）** PC アルゴリズムに基づく動的因果関係分析でサービス間の有向非巡回グラフ（DAG）を構築する。API 呼び出しの非巡回性に着目し、DAG の忠実性仮定が成立することを確認している。 **段階 3: 相関計算・較正（Correlation Calculation/Calibration）** 改良ピアソン相関係数（絶対値）でサービス対の相関スコア $c_{i,j} \in [0,1]$ を計算する。サーキットブレーカー等のクラウドデザインパターンが相関パターンを歪める場合に較正を行う。 **段階 4: 根本原因探索（Root Cause Investigation）** インパクトグラフと相関スコアに基づく 2 次ランダムウォークで根本原因候補を順位付けする。 ## インパクトグラフ構築アルゴリズム ![[wiki/sources/_attachments/2018-CloudRanger/fig3-impact-graph-construction.png]] PC アルゴリズム（Algorithm 1）の 4 ステップ： 1. 頂点集合 $V$ 上の完全無向グラフを生成 2. 条件付き独立性検定で辺を除去（$d$-分離を利用） 3. v 構造（$v_i \to v_k \leftarrow v_j$）を方向付け 4. 残りの辺を Rule 1〜3 で方向付け 最終的に全辺の向きを反転させることで「影響の伝播方向」に沿ったインパクトグラフを得る。アルゴリズムの複雑度はグラフの最大次数 $k$ と頂点数 $n$ に対し、最悪ケースで条件付き独立性検定数 $2n k \sum_{i=0}^{k} \binom{n-1}{i}$ 件に抑えられ、指数複雑度のベイジアンネットワーク系アルゴリズムより低い。 Bluemix の 4 サービス（Dashboard・Console・Event・NLP）を例にした構築過程（図3）： - $G1$（完全グラフ）$\to$ $G2$（Event-Dashboard 独立で辺削除）$\to$ 逐次辺削除 $\to$ $G8$（スケルトン）$\to$ Rule 1〜3 で方向付け $\to$ $G9$：**Event → Console → Dashboard** **実際の因果関係と「含意辺」**： ![[wiki/sources/_attachments/2018-CloudRanger/fig4-pymicro-impact-graph.png]] Pymicro シミュレーション環境での検証では、構築したインパクトグラフのスケルトンと方向が実コールグラフとほぼ一致した。さらに実コールグラフに存在しない「含意辺」（Implied edges）が双方向に現れ（例：同一 DB サービスを呼ぶ $S4 \leftrightarrow S5$）、これはリソース共有による暗黙の依存関係を表している。 ## 2 次ランダムウォークによる根本原因特定 1 次ランダムウォーク（MonitorRank）では前のノードからの遷移確率 $p_{i,j}$ のみを考慮する。2 次ランダムウォークでは、2 ステップ前のノード $v_k$ も考慮した遷移確率 $p_{k,i,j}^{\prime}$ を定義し、辺から辺への遷移行列 $M$（$m \times m$）を構築する： $[M]_{u,v} = p_{k,i,j}^{\prime} = \frac{(1-\beta)p_{k,i} + \beta p_{i,j}}{\sum_{l \in O_i} [(1-\beta)p_{k,i} + \beta p_{i,l}]}$ ここで $\beta \in (0,1]$ は 2 ステップ前のノードの影響強度を制御するパラメータ。 3 種類の遷移： - **順方向遷移（Forward）**: インパクトグラフの辺に沿った通常の遷移 - **逆方向遷移（Backward）**: 逆辺への遷移（定数 $\rho \in [0,1)$ で制限）。高相関の現在サービスの全出力先が低相関のとき、誤ったルートへの固執を防ぐ - **自己遷移（Selfward）**: 入出力隣接サービスがいずれも低相関のとき、現在サービスに留まる ランダムウォーク（Algorithm 2）はフロントエンドサービス $v_{fe}$ から開始し、$n$ ラウンド各サービスの訪問回数を記録して降順にランク付けする。 ## 実験結果 **評価指標**: $\text{AC@}k$ = 上位 $k$ 件に実際の根本原因が含まれる確率（$|A|$ 件の異常ケースで平均） **Pymicro シミュレーション環境**（表III）: | 手法 | AC@1 | AC@3 | AC@5 | Avg@5 | |---|---|---|---|---| | Random (RD) | 6.1% | 19.0% | 31.8% | 30.1% | | TBAC (TB) | 23.1% | 45.3% | 61.3% | 47.0% | | MonitorRank (MR) | 25.4% | 87.4% | 89.7% | 73.7% | | **CloudRanger (SR)** | **59.4%** | **89.5%** | **93.3%** | **85.2%** | MonitorRank は**実コールグラフを与えた条件**で比較したにもかかわらず、CloudRanger が上回った。スループットメトリクスではレイテンシより性能が落ちる（シングルフロントエンド・同期型システムでは相関スコアの差別化が困難なため）。 パラメータ感度分析： - $t$（メトリクスサンプル数）: $t=800$ では AC@1 < 20%、$t=1500$ で安定 - $\alpha$（有意水準）: 小さすぎると（0.05）インパクトグラフが不完全になり AC@1 = 66.3%、$\alpha = 0.5$ で 91.1% **IBM Bluemix 本番環境**： ![[wiki/sources/_attachments/2018-CloudRanger/fig6-bluemix-impact-graph.png]] - 異常検知で上位 5% の異常サービスを根本原因候補として絞り込み（1732 API 中） - 構築したインパクトグラフで多くの異常サービスが接続され、WebSocket サーバーや Watson NLP など本インシデントと無関係のサービスを自動的に孤立ノードとして排除 - SRE の判定根本原因（Service 31・30・28・6 = イベントプロセスコンポーネント群）を全てトップ 5 以内に列挙 - 集約ウィンドウ $\omega = 5$ 秒で AC@1 = 98.6%、$\omega = 2$ 秒ですでに AC@1 = 84.9% ## 先行研究との比較 | 手法 | コールグラフ要否 | ランダムウォーク次数 | 教師なし | |---|---|---|---| | MonitorRank (Kim+ SIGMETRICS 2013) | **必須** | 1 次 | あり | | TBAC (Marwede+ CSMR 2009) | 必須 | なし（重み付き相関ランキング） | あり | | **CloudRanger** | **不要** | **2 次** | **あり** | MonitorRank の制限：(1) Zipkin 等の展開コスト、(2) リソース共有依存はコールグラフに現れない、(3) 1 次ランダムウォークは直前ノードのみ考慮。 ## 結論と示唆 CloudRanger は 3 つの優位点を持つ： 1. **ブラックボックス適用性** — 事前定義のサービストポロジが不要で、多様なクラウドネイティブシステムに即時展開可能 2. **ドメイン知識の組み込み可能性** — 相関関数の差し替えや事前定義トポロジの設定で柔軟に拡張可能 3. **高い適応性** — センサーネットワーク・ソーシャルネットワーク・生物ネットワーク等の複雑ネットワークにも適用可能 **後継研究への接続**: Microscope(ICSOC 2018, [[Pengfei Chen]] ら)は CloudRanger の PC アルゴリズムをシステムコール傍受と組み合わせ、Sock-shop で PR@1 88% を達成しCloudRanger を上回った。 ## 関連 - 同一著者の関連研究: [[@2018__ICSOC__Microscope - Pinpoint Performance Issues with Causal Graphs in Micro-service Environments]]（後継・CloudRanger を上回る評価） - 著者: [[Ping Wang]] / [[Pengfei Chen]]（IBM Research China, 後に Sun Yat-sen University） - 所属: [[Peking University]] / IBM Research China - 関連概念: [[根本原因分析]] / [[因果推論ベースRCA]] / [[異常検知]] - 比較手法: MonitorRank（[[@2024__arXiv__Failure Diagnosis in Microservice Systems - A Comprehensive Survey and Analysis]] で PC+ランダムウォークの古典パイプラインとして引用） ## 出典 - Wang P. et al., "CloudRanger: Root Cause Identification for Cloud Native Systems", 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), 2018. DOI: 10.1109/CCGRID.2018.00076