## Memo ### Summary in Tweet #SRE論文紹介 ソフトウェアシステムのMLを用いた障害診断の文脈ではおそらくはじめてNeurIPSで発表された論文。 障害の根本原因をメトリクス粒度で特定するために、故障を根本原因ノードへの「介入」とみなし、未知の介入対象を持つ介入分布を用いた因果学習の研究成果を適用する。先行研究では、因果学習により生成されるメトリクスをノードとする因果グラフに対して、ランダムウォークなどの別のアルゴリズムでノードをランク付けする。一方でこの論文では、介入を表すノード（F-NODE）を含む因果グラフを構築するPCアルゴリズムの修正版を用いて、F-NODE近傍のノードが根本原因であるとみなしている。 それだけでなく、メトリクス数が増えたときの実行時間が増加する問題の対応策として、分割統治アプローチをとる。先行研究のように各メトリクスをノードとして単一の因果グラフを構築するのではなく、メトリクスのサブセット内で因果グラフを構築し、各因果グラフのF-NODE近傍から根本原因を特定し、上位階層でマージする。 [NeurIPS'22]: Root Cause Analysis of Failures in Microservices through Causal Discovery paper: https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=52853 code: https://github.com/azamikram/rcd ### 0. Metadata - [Root Cause Analysis of Failures in Microservices through Causal Discovery | OpenReview](https://openreview.net/forum?id=weoLjoYFvXY) - NeurIPS Poster Session - https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=52853 ### 1. Standpoints - 監視するメトリクスの増大があり、自動化ツールなしだと [[IBM BluemixのSREの根本原因特定時間]]によると、故障の根本原因特定まで平均３時間を要する例がある。 - メトリクス（特徴）の増大に対して、 [[2018__Middleware__Sieve Actionable Insights from Monitored Metrics|Sieve]]、[[2020__WWW__AutoMAP - Diagnose Your Microservice-based Web Application|AutoMAP]]、[[2018__CCGRID__CloudRanger―Root Cause Identification for Cloud Native Systems|CloudRanger]]では、特徴選択アプローチをとるが、選択されたメトリクスが根本原因メトリクスを含まない可能性がある。さらに潜在変数が導入される可能性もある。 - 観測データのみに依存するため、介入データに存在する潜在的な不変性を利用しない。 - そこで、(1)故障は故障したノードへの介入としてモデル化し、(2)根本原因特定のためには完全なグラフを学習する必要がなく、階層的かつ局所的に学習すればよい。 ### 2. Contributions - 故障を根本原因ノードへの介入と考える。そうすることで、観測データ内だけでなく、観測データと介入データ間の分布不変性を学習に利用できる。 - 局所的な階層的学習アルゴリズムを用いて、故障の根本原因を特定するための新しいアプローチRCDを提案する。 - 合成データセットと[[SockShop異常注入実験の結果]]から生成されたデータでを評価し、プロダクション事例から得られた知見を報告する。 ### 3. Major Ideas - 未知の介入対象を持つ介入分布を用いた因果学習に関する最近の研究[8, 17]のアイデアを用いる - 観測データと介入データの両方から因果関係グラフを学習[9,20,32]に加えて観測データと介入データから未知の介入ノードを特定する研究[8,29]もある。（ [17]は？） - 故障により影響を受けるノードが親に接続されたまま、条件分布が変化するため、ソフトな介入とみなせる。 - FCIではなく[[PCアルゴリズム|PC]]ベースの修正版$\phi$-FCI [8] [[2020__NeurIPS__Causal Discovery from Soft Interventions with Unknown Targets - Characterization and Learning|Jaber+, NeurIPS2020]] を提案する。FCIは交絡因子を考慮するが、本論文では交絡因子がないことを仮定しているため、PCベースとする。 - 正常期間と故障期間の２値変数を追加ノード（F-NODE）として導入する。 - 階層的かつ局所的な因果学習 RCD - 図１(a)に示すように、データセットを小さな部分集合に分割し、$\phi$-P Cを実行して各サブセットから介入目標を見つけるという分割統治アプローチをとる。 - パラメータγを用いてサブセットサイズを制御可能。 - ![[Pasted image 20230414114035.png|300]] - 具体的な根本原因は、[[正規分布]]から異常データセットに変化を与え、その変化をそのサブセットの変数で制御できない変数である。 - 根本原因特定には、F-NODEの近傍のみを学習することにつながる介入目標のみを学習すればよいことが重要な洞察となる。 - F-NODEの近傍から非根本原因ノードを除去するために必要な最小限のCIテストのセットを実行するだけとなるので、計算量が小さくなる。 ### 4. Experimental design & Results - [[causal-learn]]により$\phi$-PCを実装した。[[カイ二乗検定]]を用いた。 - 合成データ作成のために[[pyAgrum]]を使用した。 - γ=5 - 実験回数 100 - ベースライン - [[2019__WWW__ε-Diagnosis - Unsupervised and Real-time Diagnosis of Small-window Long-tail Latency in Large-scale Microservice Platforms|ε-Diagnosis]] : CIテストの重要性を示すための比較対象である。 - [[2020__WWW__AutoMAP - Diagnose Your Microservice-based Web Application|AutoMAP]]: PCによるエッジの重みがメトリクスの独立性になるように修正している。 - [[2022__KDD__Causal Inference-Based Root Cause Analysis for Online Service Systems with Intervention Recognition|CIRCA]] - トラフィック負荷が遅延に影響を与える。これは、2つのサービス間の通信がブロッキング・ コールである場合にのみ成立し、ノンブロッキングでは成立しない - 異常データに対して回帰仮説検定を行い、故障後に予想される正規分布からの変数の偏差を求める。 - パラメトリックな仮定をするツールは厳密な制約の下でのみ適用可能であり、実世界では不十分であることを示したい。 - $\phi$-PC: 根本原因の発見には完全な因果関係グラフの学習は必要ないことを示したい。さらに、実行時間でのRCDの利得も示したい。 - 合成データの実験結果 - ![[Pasted image 20230414115405.png]] - AutoMAPは過去データに依存するので、性能が低い。 - ε-Diagnosisはノード数が多いほど、根本原因を見逃す余地が大きい。 - CIRCAはノード数が多いほど性能が低い。本実験でのデータ生成モデルが特定のパラメトリック分布に従っていないため、回帰に基づく手法に依存するツールでは根本原因の究明が困難である。 - ![[Pasted image 20230414115415.png|300]] - RCDは500ノードでtop-5の根本原因を22秒強で検出できた。（RCDが全ベースラインより良いと本文には書かれているが、図2（b）ではそうなっていない） - $\phi$-PCだけだと、500ノードでは150分以上かかるため、階層型が有効であることが示されている。 - [[Sock Shop]]実験 - [[Locust]]で平均50の正弦波に従うユーザー数を設定した。 - 故障の種類はCPUとメモリのみで、正常時５分間、異常時間５分間のデータ収集。5回ずつ実験し、合計５０個のデータを採取した。 - ![[Pasted image 20230414120137.png]] - $\phi$-PCの性能が低い理由は、通常のデータセットではサンプル数が限られているため、必要な因果構造を学習できないためである。RCDはサンプル数（メトリクス数）が少なくとも学習できる。 - Sock-shopではサービス数が少ないため、ε-DiagnosisがRCDよりも性能が良いケースも少ない。 ### 5. Discussions & Limitations ### 6. Thoughts - 故障を未知の介入として扱う因果学習は、Fault Localizationの分野では最先端のプローチになる。[[2022__KDD__Causal Inference-Based Root Cause Analysis for Online Service Systems with Intervention Recognition|CIRCA]]は、類似のアプローチをとっており、介入認識（IR）というタスクに帰着させているが、本論文では介入をハード介入ではなくソフト介入として扱っていることがおそらく差異である。 - F-NODEを導入するとなぜうまくいくのがまだわからないので、関連研究文献を読む必要がある。 - 全観測データをフラットに扱うと計算量が大きくなるので、階層的に扱いたいというのは以前から考えていたが、それが高度に実現されている。 - Sock Shopの特定精度が顕著に高いというわけではなく、[[2022__arXiv__CausalRCA - Causal Inference based Precise Fine-grained Root Cause Localization for Microservice Applications|CausalRCA]]でも言及されているように、メトリクス粒度での特定は容易ではないことがわかる。CausalRCAのほうが精度は高く見える。 - メトリクス数の増大問題に対して、特徴量削減アプローチではなく、削減により交絡因子が消えることを考慮して、階層的かつ局所的に因果学習して後でマージするアプローチであり、[[research/tsifter/TSifter]]とは対比的である。 - 実験の比較対象として[[2019__WWW__ε-Diagnosis - Unsupervised and Real-time Diagnosis of Small-window Long-tail Latency in Large-scale Microservice Platforms|ε-Diagnosis]]、[[2020__WWW__AutoMAP - Diagnose Your Microservice-based Web Application|AutoMAP]]、[[2022__KDD__Causal Inference-Based Root Cause Analysis for Online Service Systems with Intervention Recognition|CIRCA]]を選んだのはなんでだろうと思ったけど、トップ会議のWWWとKDDに通ってる論文だからだろう。 - [[pyAgrum]]を用いて、合成データを作成しているところが興味深い。時系列データをどのように生成しているのか。[[2022__KDD__Causal Inference-Based Root Cause Analysis for Online Service Systems with Intervention Recognition|CIRCA]]でも同等のシミュレーションを行ったいるため、CIRCAの論文を参照するとよいかもしれない。 ## Abstract ほとんどのクラウドアプリケーションは、多数の小さなサブコンポーネント（マイクロサービスと呼ばれる）を使用し、それらが複雑なグラフの形で相互に作用し合い、ユーザーに全体の機能を提供します。マイクロサービスアーキテクチャのモジュール性は迅速なソフトウェア開発に有益であるが、このようなシステムを障害発生時に迅速に保守・デバッグすることは困難である。我々は、複雑なマイクロサービスアーキテクチャにおける障害の根本原因を迅速に検出するためのスケーラブルなアルゴリズムを提案する。我々の新しい階層的かつ局所的な学習アプローチの鍵となる考え方は以下の通りである。(1) 障害を根本原因への介入として扱い、迅速に検出する、(2) 因果関係グラフの根本原因に関連する部分のみを学習し、コストのかかる多数の条件付き独立性検定を回避する、(3) グラフを階層的に探索する、である。提案手法は拡張性が高く、根本原因に関する有用な知見を得ることができる。一方、従来手法の利用は計算時間が長いため、実現不可能である。我々のソリューションはアプリケーションに依存せず、診断のために収集されたデータのみに依存する。評価として、提案するソリューションとPCアルゴリズムの修正版および根本原因解析のための最新技術を比較した。その結果、top-kの再現性が大幅に改善され、実行時間も大幅に短縮された。