# Root Cause Detection in a Service-Oriented Architecture ## 書誌情報 | 項目 | 内容 | |---|---| | 著者 | [[Myunghwan Kim]]（Stanford University）、Roshan Sumbaly・Sam Shah（[[LinkedIn]]） | | 発表 | ACM SIGMETRICS 2013（Pittsburgh, PA, USA, 2013-06-17〜21） | | 論文種別 | 学術論文（査読付き会議録） | | システム名 | MonitorRank | | 評価データ | LinkedIn 本番異常データ（3 ヶ月間、レイテンシ 25 件・エラー数 71 件・スループット 35 件） | ## 概要 本論文はサービス指向アーキテクチャ（SOA）における根本原因（root cause）検知の問題を扱い、**MonitorRank** と呼ぶ教師なしアルゴリズムを提案する。MonitorRank は、ユーザーリクエストの呼び出し連鎖を表すコールグラフ上でメトリクスのパターン類似度（pattern similarity）を確率重みとしたランダムウォークを実行し、根本原因候補センサーを順位付けするものである。LinkedIn の本番異常データで MAP（平均適合率）が TBAC 比 26〜51% 向上することを実証した。 ## 問題設定と背景 ### サービス指向アーキテクチャにおける障害診断の困難さ LinkedInは約 400 のサービスを複数データセンターの数千台のマシン上で運用しており、ユーザーリクエスト 1 件に対してフロントエンド → ミドル層 → データ層という 3 層のコールグラフが形成される。異常発生時の根本原因特定が困難な理由は次の 3 点に集約される。 1. **依存の複雑さ**: コールチェーンが推移閉包をなし、ステートフル・ステートレス・直列・並列などの多様な通信が混在する 2. **センサー数の爆発**: サービス数 × API 数 = センサー数（`<サービス, API>` の組み合わせ）が膨大で、各センサーが数百のメトリクスを生成する 3. **コールグラフの信頼性限界**: 外部要因（同居配置・ハードウェア障害・ボット行動）により、コールエッジのない 2 つのセンサーが同時に異常を示すことがある ### 問題の形式化 時刻 $t$ にフロントエンドセンサー $v_{fe}$ のメトリクス $m$ に異常が観測されたとき、他のセンサーのメトリクス $m$ とコールグラフを入力として、根本原因センサーの順位付きリストを出力することが目標である。 $\text{入力: } \text{異常フロントエンドセンサー } v_{fe}, \text{メトリクス } m, \text{時刻範囲 } T$ $\text{出力: } \text{根本原因候補センサーのランク付きリスト}$ ## MonitorRank アーキテクチャ MonitorRank は 3 つのサブコンポーネントで構成される。 ![[wiki/sources/_attachments/2013SIGMETRICS13-MonitorRank/fig2-monitorrank-subcomponents.png]] *Figure 2: MonitorRank のサブコンポーネント構成。破線は定期的な更新を示す。* ### 1. メトリクス収集システム（Metrics Collection） 全センサーのメトリクスを `<サービス, API>` 粒度で収集し、時間分割データベースに格納する。LinkedInでは Kafka を介したパブリッシュ・サブスクライブ型パイプラインで 1 分粒度に集約する。標準インターフェース（レイテンシ・スループット・エラー数）により新規センサーが自動登録される。 ### 2. バッチエンジン（Batch-mode Engine） Hadoop 上で定期実行され、以下の 2 つの出力を生成する。 **コールグラフ生成**: 各メトリクスデータポイントに付与されたユニバーサルIDをキーとして、呼び出し元・呼び出し先センサー名を結合し有向グラフを構築する。定期的な再生成によりサービス進化に追従する。 **疑似異常クラスタリング（Pseudo-anomaly Clustering）**: コールグラフでは捉えられない外部要因（同居配置など）を歴史的データから学習する。以下に詳述する。 ### 3. リアルタイムエンジン（Real-time Engine） 監視チームが「フロントエンドセンサー・メトリクス・異常時刻範囲」を入力すると、バッチエンジンの成果物を使って根本原因スコアを計算し、順位付きリストを返す。 ## 疑似異常クラスタリング ### 外部要因の問題 ![[wiki/sources/_attachments/2013SIGMETRICS13-MonitorRank/fig3-external-factor.png]] *Figure 3: 外部要因の影響。$v_1$ と $v_2$ が同一ハードウェアに同居する場合、$v_3$ との相関が低くても $v_1$-$v_2$ 相関が高くなる（矩形領域）。これはコールグラフで捉えられない。* センサー $v_1$ と $v_2$ が $v_3$ の呼び出しを共有しているだけなら、$v_1$-$v_2$ の相関は $v_1$-$v_3$ の相関に依存するはずである。しかし実際には、$v_1$ と $v_2$ が同一ハードウェア上に同居している場合、$v_3$ との相関がほぼゼロでも $v_1$-$v_2$ の相関が高い（矩形クラスタ）という現象が LinkedIn の本番データで観測された。 ### 条件付きクラスタリングの定式化 シード（種）のフロントエンドセンサー $v_{fe} = v_1$ に対し、歴史的な疑似異常時刻 $t_1, \ldots, t_M$ それぞれで「各センサーが同じ外部要因の影響下にあるか」をクラスタリングする。 外部要因が共通のセンサー群 $n_1, \ldots, n_c$ のパターン類似度スコア $S_i^{(t)}$ を次のようにモデル化する: $S_i^{(t)} \sim \begin{cases} \mu^{(t)} + \epsilon^{(t)} & i \in \{n_1, \ldots, n_c\} \\ \mathcal{N}(0, \delta^2) & \text{それ以外} \end{cases}$ これを最適化問題として定式化し、L1 正則化（Lasso）で疎なクラスタを抽出する: $\min_{\mu^{(t)}, x} \frac{1}{2} \| S^{(t_k)} - x \|_2^2 + \frac{\delta^2}{2} |x|_1$ Lasso の解 $x^*$ に基づいて「アクティブセット」$A_k = \{v_i | x_i^* > 0\}$ を各疑似異常時刻について算出し、支持数閾値 $\theta$ でフィルタリングして最終クラスタとする。この処理は Hadoop 上で並列実行され、定期的に更新される。 ## ランダムウォークアルゴリズム ### パターン類似度スコア リアルタイムエンジンの第 1 ステップとして、異常観測フロントエンドセンサー $v_{fe}$ に対して各センサー $v_i$ のパターン類似度スコアを計算する: $S_i = \text{Sim}(m_i, m_{fe})$ 実装では**スライディングウィンドウ相関**（60 分ウィンドウ）を用いる。パターン類似度は根本原因と障害の伝播方向に沿って高くなるが、季節性などの共通要因による偽陽性を含む。 ### 基本的なランダムウォーク コールグラフ $G = \langle V, E \rangle$ 上でパターン類似度 $S_j$ を辺の強度として遷移確率行列を構築する: $Q_{ij} = \frac{A_{ij} S_j}{\sum_j A_{ij} S_j}$ Personalized PageRank（PPV）を以下の方程式で計算する: $\pi_{PPV} = \alpha \pi_{PPV} P + (1-\alpha) u$ ここで $u$ は異常関連センサーへのテレポーテーション確率（パターン類似度 $S$ を利用）、$\alpha$ はテレポーテーション確率定数。 ### 3 つの拡張 **自己エッジ（Self-edge）**: ランダムウォーカーが強制的に隣接ノードへ移動するのを防ぐ。各ノード $v_i$ の自己エッジ強度を $\max(0, S_i - \max_{k: e_{jk} \in E} S_k)$ とすることで、高類似度ノードへの滞留を促しながら無関係ノードへの落ち込みを防ぐ。 **後退エッジ（Backward-edge）**: コールグラフはフロントエンド → バックエンド方向が主であるため、ランダムウォーカーが無関係なブランチに「自然な罠」として嵌まる問題を解消する。 ![[wiki/sources/_attachments/2013SIGMETRICS13-MonitorRank/fig4-natural-trapping.png]] *Figure 4: 自然な罠の例。フロントエンド $v_1$ の異常を $v_2$ のみが引き起こしているとき、ウォーカーが $v_3$-$v_7$ 枝に落ちると次のテレポーテーションまで $v_2$ を訪問できない。* 後退エッジの強度は順方向 $e_{ij}$ の強度 $S_j$ に対して $\rho S_i$（$\rho \in [0, 1)$）に設定する。$\rho$ が高いほどコールグラフ方向に制限的、低いほど柔軟に探索する。 これらを統合した拡張隣接行列 $A'$ は: $A'_{ij} = \begin{cases} S_j & e_{ij} \in E \\ \rho S_i & e_{ji} \in E, e_{ij} \notin E \\ \max(0, S_i - \max_{k: e_{jk} \in E} S_k) & j = i > 1 \end{cases}$ **外部要因の組み込み**: リアルタイムに現在のパターン類似度スコアをバッチ学習済みクラスタと照合し、最も適合するクラスタ $C^*$ を選択する: $C^* = \arg\max_C \frac{\min_{c \in C} S_c}{\max_{c' \notin C} S_{c'}}$ 適合クラスタが検出されたとき、クラスタ内センサーのスコアを加算してからランダムウォークを実行する。 ### 計算量 疑似異常クラスタ照合に $O(N_C |V|)$、ランダムウォークに $O(|E|)$ かかり、全体で $O(N_C |V| + |E|)$ となる。コールグラフが疎であることを前提とすれば $O(|V|^2)$ より十分小さくリアルタイム処理が実現できる。 ### MonitorRank の理論的保証 連鎖グラフ $v_1' \to v_2' \to \cdots \to v_m'$ において、$V'$ 内のノードのパターン類似度スコアがすべて $p \leq 1$ であり $V'$ 外は 0 であるとき、鎖の末端ノード $v_m'$ の定常確率が最大となる（定理 1）。これは「根本原因が明示的な因果連鎖として存在するとき、ランダムウォークは確実にそれを特定できる」ことを保証する。 ## 実験評価 ### データセット LinkedIn の専任監視チームが収集した本番異常ラベルデータ（3 ヶ月分）: | メトリクス | 件数 | |---|---| | レイテンシ | 25 件 | | エラー数 | 71 件 | | スループット | 35 件 | ### ベースライン手法 - **RS（ランダム選択）**: ドメイン知識のない人間が取りうる最低限の戦略 - **NEP（Node Error Propensity）**: センサーのエラー数を異常尺度とする - **SC（Sudden Change）**: 現時刻前後のメトリクス平均比を根本原因スコアとする - **TBAC（Timing Behavior Anomaly Correlation）**: コールグラフを信頼できる有向非巡回グラフ（DAG）として扱う相関ベース手法（当時の最先端） ### 評価指標 - **PR@K**: 上位 K センサーに真の根本原因が含まれる確率（K = 1, 3, 5） - **MAP（Mean Average Precision）**: 順位の良さを重み付き平均で測定 ### 主な結果 | メトリクス | 指標 | RS | NEP | SC | TBAC | MonitorRank | |---|---|---|---|---|---|---| | レイテンシ | MAP | 0.143 | 0.206 | 0.559 | 0.497 | **0.754** | | エラー数 | MAP | 0.091 | 0.465 | 0.659 | 0.442 | **0.818** | | スループット | MAP | 0.210 | 0.634 | 0.210 | 0.714 | **0.779** | MonitorRank はすべてのテストセット・評価指標で最良であった。TBAC に対する MAP 改善率は平均 51.4%、最良ヒューリスティック手法に対しては平均 25.7%。PR@1 での改善は特に顕著で、スループットの場合は TBAC（0.971）に対し MonitorRank が 1.000 を達成した。 ### サブコンポーネント分析 ![[wiki/sources/_attachments/2013SIGMETRICS13-MonitorRank/fig6-subcomponent-effects.png]] *Figure 6: 各サブコンポーネントの効果。PS のみ → PS+PAC → PS+RW → ALL の順に改善する。ランダムウォーク（RW）の寄与が最大、疑似異常クラスタリング（PAC）が PR@3 付近で 5% 程度の追加改善をもたらす。* - **パターン類似度のみ（PS）**: ベースライン以上だが偽陽性が多い - **ランダムウォーク追加（PS+RW）**: PR@1 で PS 比 14.2% 改善。コールグラフによる絞り込みが効く - **疑似異常クラスタリング追加（PS+PAC）**: PR@3 付近で約 5% 追加改善。外部要因による誤判定を解消 - **全コンポーネント（ALL = MonitorRank）**: 全指標で最良 また TBAC（コールグラフを強い依存グラフとして扱う）は、ランダム探索（PS）より悪化することがある（Figure 7）。これはコールグラフが実際には信頼できる依存グラフでないことを裏付ける。 ## 主要な主張・貢献 1. **コールグラフを「信頼できる依存グラフ」として扱わない設計が重要**: 外部要因（同居配置・ハードウェア共有）や異種呼び出し（直列・並列）により、コールエッジは真の依存を表さないことが多い。TBAC のように強い依存仮定を置くと性能が随時型（PS）より悪化しうる。 2. **Personalized PageRank のコールグラフへの適用**: テレポーテーション確率ベクトルとしてパターン類似度を使用することで、「根本原因に関連するセンサーへ preferential にジャンプ」という設計を実現した。 3. **リアルタイム実行可能な教師なし設計**: バッチ処理（クラスタリング）とリアルタイム処理（ランダムウォーク）の分離により、本番の数百サービスに対してもサブ二次時間で根本原因を特定できる。 4. **本番ラベルデータによる評価**: 合成データではなく LinkedIn 実運用の異常ラベルデータを使い、実際の監視チームの判定を正解として評価した。 ## 位置付けと関連研究との差異 本論文が 2013 年に提案した MonitorRank は、その後の根本原因分析研究が取り組む「コールグラフ + ランダムウォーク」系手法の原型となった。 - [[因果推論ベースRCA]] に属する CloudRanger・MS-Rank・AutoMap は PC 系アルゴリズムで因果グラフを推定した上でランダムウォーク / PageRank を適用するが、MonitorRank は「因果グラフを推定しない」代わりに「実測コールグラフを確率的に使う」という設計である。因果探索のコストを回避しながら類似のグラフ走査効果を得る点が特徴。 - VScope・Mona-lytics は手動ルールベースの設定を必要とするのに対し、MonitorRank はドメイン知識不要の教師なし手法である。 - TBAC（[23]）は同じくコールグラフ + 相関を使うが、コールグラフを強い依存グラフとして扱う点で MonitorRank と対照的である。 ## 未解決の問いと限界 - **複数フロントエンド同時異常への対応**: 複数の遷移確率行列を重ね合わせる拡張を将来課題として挙げるが、本論文では未実装・未評価 - **Personalized PageRank の $\alpha$ および後退エッジ定数 $\rho$ の調整**: 実験での設定値は示されるが、最適値の体系的なチューニング方法は未論述 - **メトリクス方向依存性**: スループット異常はフロントエンド → バックエンド方向に伝播するのに対し、レイテンシ・エラー数はバックエンド → フロントエンド方向に伝播する。実装では方向を切り替えることで対処しているが、混合障害への対応は課題として残る - **外部要因クラスタリングの精度**: Lasso の超パラメータ（$\delta$, $\theta$）の設定が最終性能に影響するが、その選択指針は示されていない ## 関連 ### エンティティ - [[Myunghwan Kim]]（Stanford University、本研究の第一著者） - [[LinkedIn]]（本研究のデータ提供者・実装先） - [[Stanford University]]（Myunghwan Kim の所属機関） ### 概念 - [[因果推論ベースRCA]]（本論文はその「グラフ走査系」の原型） - [[マイクロサービスコールグラフ]]（MonitorRank の入力グラフ） - [[根本原因分析]]（本論文の主題） - [[AIOps]]（広義の応用領域） ## 出典 - [[@2013__SIGMETRICS__Root Cause Detection in a Service-Oriented Architecture]](Myunghwan Kim, Roshan Sumbaly, Sam Shah, ACM SIGMETRICS 2013)