2020__WWW__AutoMAP - Diagnose Your Microservice-based Web Application

## Memo ### 問題定義 - マイクロサービスアプリケーションをgrey box，すなわちシステム知識（呼び出しトポロジとサービス機能）なしでいくつかの種類のメトリックだけとして扱う。 - フロントエンドサービス $V_{fe} \in V$, インシデント期間 $l$, サービス個数 $n=|V|$, メトリック種類の個数 m - rawメトリックの集合 $\mathbb{M}$, where $\mathbb{M} = m, \mathbb{M}_{m} = [\mathbb{M}_{m}]_{n\times m}$, $M_{m}$ は $l$ 期間の $n$ 個のサービスの $m$ 番目のメトリック - 目標は $v_{fe}$内で観測された異常を引き起こすサービスセット $v_{rc} \subset V$ を特定すること - メトリックの種類は以下の表の通り。APIリクエストのログレコードから簡単に取得できるものが選ばれている。利用者はメトリックを選択できるとのこと。 ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-07-09_at_9.59.13_AM.png]] （Powerってなんだろうあまりみかけない [24]に読む必要あり) [24] K.RamakrishnanandR.Jain,"Abinaryfeedbackschemeforcongestionavoidance in computer networks," ACM Transactions on Computer Systems (TOCS), vol. 8, no. 2, pp. 158-181, 1990. AutoMapはAPI Proxyを基にして各サービスへのリクエストや各ホストやコンテナの状態を取得する．診断はfront-end serviceで異常が起きたら開始される． P1: rawメトリックのサンプリングインターバルの選択 P2: 複数種類のメトリックの振る舞いグラフを構築 P3: 振る舞いグラフの"+", "-"演算子により，異常のプロファイルを抽出 P4: 行動グラフに沿ってヒューリスティックな根本原因検出アルゴリズムを実行 P5: 結果の検証と精度の算出 P6: メトリック-重み行列を更新する．新たな異常が発生した場合は、P1～P6を繰り返す。 ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-07-09_at_7.08.19_AM.png]] サンプリングのためのインターバルは次の式で決まる。 $\sum_{i=1}^n \frac{The\ number\ of\ calling\ v_{1}}{The \ number\ of\ total\ service\ calling} * (interval\ of\ calling\ v_{i})$ (なぜメトリックのインターバルがサービスの呼び出し頻度で決まるのか？サービスはこのインターバル内で1度は呼び出しされるから) ### 実験 #### データセットとベンチマーク - Pymicro: 16個のマイクロサービス Docker x ZooKeepr - バックエンドサービスの中から1つ選んでランダム異常を注入する - IBM Cloudの20個のインシデント - 15 million metrics, collected during 7200 seconds (1 hour before and 1 hour after the anomaly was detected) from 1732 microservice APIs in total - ベースライン: TBAC [27], [[2013__PER__Root Cause Detection in a Service-Oriented Architecture|MonitorRank]] [23], [[2018__CCGRID__CloudRanger―Root Cause Identification for Cloud Native Systems|CloudRanger]] [30], NetMedic [8] and [[2018__MS-Rank Multi-Metric and Self-Adaptive Root Cause|MS-Rank]] [32] - 相関スコアのTBACでは不十分であることを示す - MonitorRankを比較することで、事前に定義されたトポロジーではなく、振る舞いグラフを利用する利点を示す - NetMedicは階層型ネットワークで、AutoMAPのヒューリスティックランダムウォークの利点を示す - CloudRangerやMS-Rankはサービスの特性やアノマリーは考慮していない。 - 単一メトリックを利用するTBAC, MonitorRank , CloudRangerとはレイテンシとスループットの観点で精度を比較する - PCアルゴリズムの実装には [https://pypi.org/project/pcalg/](https://pypi.org/project/pcalg/) を使う (日本の人の実装だった) - メトリックのサンプリングレートは2秒と5秒 - Intel Xeon 2.4GHz CPU, 16GB RAM running 64-bit Windows Server 2008. (古い) #### 実験と結果解析 - Root cause identification - k =1/ 3/ 5, l = 1440 - 適切にメトリックを選択しないとどのアルゴリズムでも50%以下 - Self-Optimization - NetMedicと比較 - round testを重ねると、10回目で59.7%から93.9%まで向上 - Algorithm parameter - $l$ - $l$はインシデント期間。700 to 1440まで変化させる。 - l = 700の場合、精度は40%以下に低下 - Domain knowledge - $l=200$ ではドメイン知識がアルゴリズムの精度を向上させる。AutoMAP+API 4.9% improvement, AutoMAP+Linked +8.2%, AutoMAP+Direction +5.4% - しかし、 $l=1440$ ではさほどかわらない。サンプル数を増やせばドメイン知識なしで精度を向上できる。 - Algorithm parameters - $α$ and $ρ$ - $\alpha$ 0.01 to 0.50 - $\alpha = 0.50$のとき、4分弱かかる。（IBM Cloudのインシデント情報とはどのようなものでどう利用しているのか） --- 以下はDeepLによる英文和訳になる。 ## Abstract マイクロサービスアーキテクチャの高い複雑性とダイナミクスは、そのアプリケーション診断を非常に困難なものにしています。静的なトラブルシューティングのアプローチでは、頻繁に変化する状況に対応した信頼性の高いモデルを得ることができない可能性があります。サービスの呼び出し依存性を知っていても、間接的な障害伝播が存在するため、より動的な診断メカニズムが不足しています。また，単一のメトリックに基づくアルゴリズムでは，多様なサービスで発生する異常を特徴づけるには単一のタイプのメトリックでは不十分であるため，通常は異常の根本原因を特定できない．そこで、本研究では、複数種類のメトリクスを用いてサービスの相関関係を動的に生成し、自動診断を可能にするツール「AutoMAP」を開発しました。本研究では、サービス間の相関関係を異なる種類のメトリクスで記述するために、異常行動グラフという概念を提案する。本研究では、2つの2値演算と類似度関数を定義し、特定のシナリオにおいて適切な診断指標を選択するための支援を行う。また、行動グラフに沿って、前方・自己・後方ランダムウォークを用いたヒューリスティックな調査アルゴリズムを設計し、サービスの根本原因を特定することを目的としている。本研究では、AutoMAPの優位性を実証するために、プロトタイプを開発し、模擬環境と実運用の企業内クラウドシステムの両方で評価を行った。実験の結果、AutoMAPは90%以上の精度を達成しており、他の選択されたベースライン手法を大幅に上回ることが明らかになった。AutoMAPは、システム知識がなくても、様々なマイクロサービスベースのシステムに迅速に導入することができます。また、精度向上のための様々な専門知識の導入をサポートします。 ## 1. INTRODUCTION マイクロサービスアーキテクチャの出現は、実装、再利用、ウェブアプリケーション開発の独立したスケーリングのための容易な抽象化とモジュール化を促進しています[1]。しかし、サービスとその依存関係が継続的なリファクタリングによって進化しているため、大規模なマイクロサービスベースのWebアプリケーションにおける異常の原因を特定することは、これまで以上に困難になっています[2]。この課題は、以下の3つの側面に根ざしています。動的なアプリケーション構造。サービスの性質が多様であるため、しきい値スキーム[3]のような静的なトラブルシューティングアプローチでは、頻繁に変化する状況に対応した信頼性の高いモデル適用を得ることができない可能性があります[4]。そのため、最近の研究では、システムの構造から始めて、その構造に沿ったパターンを分析して異常を診断するのが一般的です[5, 6]。このような構造、例えばネットワークトポロジーやサービスコールの依存関係は、一般的にログファイルや監査イベント、ネットワークデータパケットなど、さまざまなコンポーネントを監視して収集した過去のデータから抽出されます。このようなデータを収集し、これらの構造を生成するための中央実行コンポーネントを開発するのは時間と労力がかかり、一部のレガシーシステムでは現実的ではありません。 ([3]: H. Wu, A. N. Tantawi, and T. Yu, "A self-optimizing workload management solution for cloud applications," in IEEE 20th International Conference on Web Services (ICWS), 2013, pp. 483-490: IEEE.) 間接的な異常伝播。マイクロサービスアーキテクチャではコンポーネントの粒度が小さくなり、サービスは分散したホストやコンテナ上に存在するようになり、その呼び出しプロセスは直接呼び出しとして同期的に行われたり、メッセージプロキシやパブリッシュ/サブスクライブコンポーネントを介して非同期的に行われたりします。したがって、アノマリーの伝播はもはや呼び出し依存性に縛られることはありません。図1は、WebアプリケーションがAPIゲートウェイを介して異なるホストやコンテナ上で動作するサービスを呼び出す例を示しています。呼び出されていないマイクロサービスに異常が発生しても、同じホストやコンテナ上の他のサービスに影響を与え、異常伝播を引き起こす可能性がある。そのため、サービスの呼び出し依存性を知っていても、間接的な障害伝播が存在するため、より動的な診断メカニズムが不足しています。 ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-07-09_at_12.33.31_PM.png]] 複数のタイプのメトリック。単一のメトリックに基づくアルゴリズムでは，多様なサービスで発生する異常を特徴づけるには単一のタイプのメトリックでは十分ではないため，根本原因の特定に失敗する可能性がある[8]．また、非同期的な呼び出し手順のため、メトリクスが伝搬依存性を直接反映できないことがよくあります。アプリケーションに異常が発生している場合、最新のアーキテクチャは多種多様な健全なメトリクスを提供していますが、関係するサービスの特性に応じて適切にメトリクスを選択する自動化されたメカニズムがまだ不足しています。そのため、マイクロサービスベースのWebアプリケーションの異常に対処するためには、運用チームがシステムの深い領域の知識を維持する必要があります。特に新機能のリファクタリングによってアーキテクチャが急速に進化する場合には、このような知識を更新し続けることは非常に困難です。このような課題を解決するために、我々はいくつかの機能を備えた自動診断ツールを開発することを目指しています：第一に、事前知識がなくても自動的に異常トポロジーを生成できること、第二に、複数の種類のメトリックに基づいてサービスや異常を自動的に特徴付けることができること、第三に、適切なメトリックを選択して根本原因を自動的に検出することができることです。本発表では、AutoMAPを用いたソリューションを紹介する。要約すると、以下のような貢献がある。 1. 我々は，アノマリー行動グラフという概念を提案する．このグラフモデルは，異常が伝播したときのサービス間の相関関係を表すものである．サービスと異常パターンの性質を明らかにするために，行動グラフ上に加算(+)と減算(-)の演算を定義し，それらを利用してサービスと異常のプロファイルを生成する． 2. 異常プロファイル上の類似度関数を設計し、過去の記録から最も関連性の高いメトリックを検索するために利用する。自動化されたメトリック重み学習アプローチと調査アルゴリズムを提案する。このアルゴリズムは、前方、自己、後方のランダムウォークを利用して、ヒューリスティックに根本原因を特定する。 3. シミュレーションと実運用環境（IBMクラウド）での検証を行い、選択したベースラインアプローチとの比較を行いました。実験の結果、AutoMAPは90%以上の精度で他の手法を大幅に上回る結果が得られました。また、AutoMAPが効果的かつ効率的に最適化できることも検証しています。 ## 2. RELATED WORKS 本節では，分散システムにおける根本原因検出に関する関連する研究をレビューする．ネットワークトラフィック解析 [9]、Web アプリケーションの異常検知 [10] およびデバッグ [11]、サービス障害検知 [28] および予測 [29] など、同様の課題に取り組んできた研究がある。例えば，Gertler らは，個々のコンポーネントの監視データを閾値方式で調べることで異常を検出することを提案している[6]．Wang らは，階層型ネットワークシステムモデルを用いてスループットと負荷を細粒度で相関させるボトルネック検出手法を提案している． [7]. しかし、実際には、特に動的なマイクロサービスアーキテクチャにおいては、様々な状況に対応した信頼性の高い閾値を得ることが困難であることがわかっている。 ([7]: Q. Wang et al., "Detecting transient bottlenecks in n-tier applications through fine-grained analysis," in IEEE 33rd International Conference on Distributed Computing Systems (ICDCS), 2013, pp. 31-40: IEEE.) また、決定木[12]、クラスタリング[13, 14]、マルコフ予測モデル[15]などの機械学習技術も、ネットワークの異常ノードを特定するために活用されている。また，パフォーマンスメトリクス[13]やネットワークトポロジー[14]に基づく知識発見に焦点を当てた取り組みもある．このためには、分散監視施設から記録を収集するために中央のマスターノードが必要とされるのが一般的である[16]。これらの記録には、ログファイル、監査イベント、ネットワーク・トラフィック統計、さらには物理システムの感覚的な測定が含まれます。これらのソリューションのほとんどは、事前に定義されたシステムトポロジー[17]またはサービス呼び出し関係[16]を必要とする。その結果、システム・トポロジーを自動的に発見し[18]、その後、ヒューリスティックな方法で異常を特定することで、この問題を探求しています。 [19]. 例えば，異常伝播トポロジーを表現するために「不変グラフ」と呼ばれる構造 [20] が提案されている．静的ネットワーク構造におけるリンクは因果関係の一部を表しているが，マイクロサービスアーキテクチャにおける実際の関係はより動的である． Kim et al. [23]は、リアルタイムメトリック収集システムと異常検出フレームワークMonitorRankを実装しています。これは、ランダムウォーキング戦略に基づいてサービスの根本原因を診断する教師なしのヒューリスティックな方法を提供します。しかし、MonitorRankは、事前のドメイン知識とターゲットシステムのサービス呼び出しトポロジーも必要とします。マイクロサービスベースのシステムでは、呼び出しトポロジーは常に変化するため、地に足のついた真実の呼び出しトポロジーを取得することは、高いコストがかかります。この点を考慮して、CloudRanger[30]やMicroscope[31]では、メトリクス上の統計的特性に基づいてトポロジーを再構成することで、トポロジーを取得しなくてもシステムの異常を診断することができるようにするための手法が提案されている。また，診断に用いるメトリクスの種類をどのように選択するかも重要な課題である．複数の種類のメトリクスをどのように扱うかを議論した論文もある[21]．例えば，NetMedic は小規模な企業ネットワークのために，障害伝播テンプレートを用いて依存関係グラフを生成することを提案している[8]．同様に，Sherlockでは，ネットワーク監視データやシステムログからマルチレベルのメトリクスを用いて，障害関連推論グラフを発見している[22]．大規模なマイクロサービスアーキテクチャは高次元の依存関係を生成するため，実際の根本原因をヒューリスティックに見つけ出し，異なるマイクロサービスの特徴を反映するために最適なメトリックの組み合わせを見つけるための適応メカニズムを設計することが大きな課題となっています．この問題を解決するために、MS-Rank [32]フレームワークは、動的にインプライドメトリックを生成し、過去の診断記録に基づいてメトリック-スキームを選択するための自己適応的なメカニズムを事前に提案しています。また、Magpie [33]、Canopy [34]、WSMeter [35]など、データセンターのパフォーマンス問題を解決するアルゴリズムもある。しかし、これらのアルゴリズムは通常、詳細な通話プロセスデータやネットワークパケット、システム知識を収集する必要がある。AutoMAPの核心的な違いと利点は、シンプルなメトリクスを使用して正確な診断を行うことである。これにより、既存のシステムにAutoMAPを適用するためのコストを効果的に削減することができる。さらに、既存のアルゴリズムの多くは、サービスや異常の過去の特徴を分析して活用していないことにも気付きます。企業レベルの運用保守において、異常診断には、過去の診断経験と異なるサービスの特徴という2つの知識が重要な役割を果たしています。したがって、これらの課題を対象とした本研究の主な相違点と利点は以下の通りである。 - (1)サービスや異常の統計的特性を反映した行動グラフの概念とその算出方法 - (2)サービス/異常の定量化と類似度関数 - (3)特定の異常シナリオに対するメトリックの自動選択機構 - (4)エンタープライズクラウドシステム上での実環境検証、などである。 ## 3 PROBLEM STATEMENT ### 3.1 Problem Definition 問題を一般化するために、我々はマイクロサービスベースのウェブアプリケーションを「グレーボックス」として扱います。私たちはこの問題を形式化しました。ここで、n = |V |、m はそれぞれサービスの数とメトリクスの種類である。ここで，生のメトリクスをMと表記し，｜M| = m，M m = [M m ] n×l，M mはl期間中のn個のサービスのNo.mメトリクスの測定値を記録したものである．表 1 に本研究で使用した主な表記法をまとめた． ### 3.2 AutoMAP この問題を解決するために、我々は、サービスの相関関係を動的に生成し、複数の種類のメトリクスを活用した自動診断を可能にするAutoMAP（Automated Microservice-based Web Applications Patrol）という新しいツールを開発した。図2にそのフレームワークを示す。 ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-05-04_at_1.44.33_PM.png]] AutoMAPは、APIプロキシを利用して、マイクロサービスのリクエストの詳細とコンテナ/ホストの状態を収集します。診断は、フロントエンドサービスに異常が検出された場合に開始される。根本原因検出タスクをいくつかの反復フェーズに分解します。 P1. 生のメトリクスのサンプリング間隔パラメータを選択する。 P2. 複数のタイプのメトリクスを使用して異常動作グラフを構築する。 P3. ビヘイビア・グラフの "+"と"-"操作を使用して、異常のプロファイルを抽出する。 P4. 行動グラフに沿ってヒューリスティックな根本原因検出アルゴリズムを実行する。 P5. 結果の検証と精度の算出 P6.メトリック-重み行列を更新する．新たな異常が発生した場合は、P1～P6を繰り返す。 AutoMAPはシステムの知識を必要としない自動化されたツールです。専門家ではないユーザーでも根本原因を特定することができます。SREにとっては、AutoMAPを利用することで参照診断結果を提供することができ、システムメンテナンスの効率を大幅に向上させることができます。以下のセクションでは、AutoMAPの主なタスクについて詳しく説明します。 ## 4 METRICS ### 4.1 Testbed System and Raw Metrics 本ツールのテストベッドシステムは、トップクラスのクラウドプラットフォームであるIBMクラウドを採用しています。IBM Cloudは、ビッグデータ、IBM Watson、データ分析、モノのインターネット、セキュリティ、DevOps、アプリケーションなど、200以上のカテゴリのパブリックマイクロサービスを実行しています。マイクロサービスの各カテゴリは、サービスインスタンス、API、ランタイムの束を提供しています。大規模なウェブアプリケーションは、これらのサービスの上に構築され、世界中の複数のクラウドセンターにある数百万台のマシン上で実行されており、100万人以上のユーザーにサービスを提供し、毎日15億以上のAPI 2リクエストを生成しています。本研究では、レイテンシ、スループット、消費電力、CPU、I/O、メモリ、可用性の 7 種類のパフォーマンスメトリクスを考慮しています。5 5.1 ビヘイビアグラフの構築と計算ビヘイビアグラフの構築 M = M のメトリクスを使用します(表II参照)。これらのメトリクスは、典型的なものであり、サービスAPIリクエストレコードから容易に取得できるため、選択されていることに注意してください。ユーザーは、特定のタイプの異常を特徴付けるために、他の任意のメトリックを定義して選択することもできます。 ### 4.2 Sampling Interval AutoMAPは、生のメトリクス上で適切なサンプリング間隔を選択することから始まります。このパラメータは、次の診断の精度に直接影響します。メトリクスをサンプリングする頻度が高すぎる場合、例えば1秒ごとにサンプリングすると、実際の呼び出し依存性を反映しない冗長な変動が発生する可能性があります。逆に、より大きな間隔でサンプリングを行うと、多くの効果的なメトリック変化が失われ、伝搬トポロジーを捉えることができなくなってしまう。このような事実を踏まえて，本研究ではマイクロサービスアーキテクチャのためのサンプリング間隔選択アルゴリズムを提案する．このパラメータはシステムの特性に依存する．妥当な選択は，すべてのサービスの呼び出し間隔の統計的平均値である．言い換えれば，あるサービスは，この間隔の間に平均して1回呼び出される．したがって、我々は、リクエスト間隔の頻度加重平均を用いてそれを計算する。 n 次に、コールイン数дvi i=1 とすると、トータルサービスコール数д ∗（コール間隔дvi）となります。ここで vi は V の No.i サービスを表します。実際の運用環境では、異常が直接または間接的に多数のサービスに影響を与えるため、伝搬経路はより複雑になります。多くの場合、専門家でない者は、サービスの機能性やサービス間の呼び出し関係についての事前知識が不足しています。そこで、本研究では、ウェブアプリケーションの開発者やサイトエンジニアが異常を分析するのに役立つように、メトリクスを用いてサービス間の相関関係をモデル化する自動化されたアプローチを構築することを目的としています。 ## 5 BEHAVIOR GRAPH CONSTRUCTION AND COMPUTATION ### 5.1 Behavior Graph Construction マイクロサービスアーキテクチャの呼び出し依存関係は複雑で動的であるため、ウェブアプリケーションのサービス呼び出しトポロジーを分析するために多くの時間を費やす代わりに、経験豊富な SRE は通常、異常のタイプについての直感に基づいてトラブルシューティングを選択します。より具体的には、彼らは、そのメトリクスの観察に基づいて最も疑わしいサービスを選択し、過去の事例と比較します。例えば、多くのI/Oサービスが応答を失った場合、データベース関連のサービスに問題が発生する可能性があります。計算サービスの可用性が低下した場合は、そのコンテナが不安定である可能性があり、さらにホストマシンのハードウェアの欠陥を追跡することができます。このように、SRE の直感的な知識は、過去の診断の経験と、様々なサービスの特性という 2 つの側面を主に含んでいることがわかる。本節では、記録から相関関係を抽出し、類似の異常を発見するためのモデル「Anomaly Behavior Graph」を提案する。正式には以下のように定義する。 Anomaly Behavior Graph. $G(V , E,W )$は、Vの頂点間のインパクト相関（すなわち、サービス）を記述した異常行動グラフであり、ここで $E$はエッジ集合、 $W$はエッジの重み行列である。任意のサービスペア $v_{i}$と $v_{j}$ が与えられたとき， $W_{i,j,k} \in [0,1]$, $\sum_{k=1}^m W_{i,j,k} = 1$．を持つ辺vi →vjは、信頼度Wi,j,kを持つMk。行動グラフを得るためには、まず、**重み付け完全無向グラフから始め、徐々にエッジの重みを取り除き、条件付独立性検定を用いてエッジの向きを揃えていく必要がある**。このプロセスは4つのステップで構成されています。ステップ1. ここで、 ∀i,j ∈[1,n]と∀Mk,k∈[1,m]の場合、Wi,j,k = 1; ステップ2. 各タイプのメトリックMkについて，任意のペアvi,vjの条件付き独立性を検定する．viとvjの間の条件付き独立性が認められた場合，Wi,j,k = 0とする．ステップ3. ステップ3. Wi,j,k = 0の場合、∀k ∈ [1,m]の場合、エッジei,jを削除する。Wi,j,k ←Wi,j,k/||Wi,j|0とする。ステップ４．Ｇ内のＶ構造と残りの辺を配向させる。分かりやすくするために、このプロセスをアルゴリズム1にまとめます。このアルゴリズムの結果は、Mで特徴づけられたサービスV間の相関関係を記述した重み付きCPDAG（completed partially有向非巡回グラフ）です。特に、viとvjが条件付き独立であることを、与えられたvkifP(vi∩vj|vk)=P(vi|vk)P(vj|vk)>0のとき、viの発生とvjの発生が条件付き確率分布において従属事象であることを示す。vi,vjが条件付きで独立している場合に限り、任意の部分集合Sが与えられると、vi,vjはSによって分離されていると呼ぶことにする。Ｓ(vi,vj,k)をviとvjを分離する条件集合とすると、Mkを与え、adj(G,vi,k)をG内のviに接続されたノードの集合（言い換えれば、Wi,j,k = 1を満たす任意のvj）とすると、我々は、すべてのペア（vi,vj）が条件付きで依存しているかどうかをMkを用いて検定する（G,vi,k）。もし、サービスｖｑが存在するならば、（vi,vj）が独立していれば、Ｗi,j,k = 0 とし（すなわち、エッジを除去し）、Ｓ(vi,vj,k)とＳ(vj,vi,k)にｖｑを挿入する。すべての１ステップ隣接ペアとすべてのタイプのメトリクスがテストされると、新しいグラフＧが生成され、条件付け集合のサイズを増加させることによって、このようにして継続する。Ｇ内のすべての隣接組が条件集合のサイズよりも小さくなったときに停止する。この過程で、α∈（０，１）が[[条件付き独立性検定]]の閾値となる。αが0に近づくと、条件付き独立性仮説が受け入れられやすくなり、Gから削除される辺が多くなります。ステップ4では、無向骨格を行動グラフに方向付けする。このためには、fi,j = 1,ej,l = 1, ei,l = 0を満たす三重体(vi,vj,vl)のグラフを探索する。この後、残りの無向辺については、規則１-３を繰り返し適用して、その２つの可能な方向のいずれかが新しいｖ構造または有向サイクルを導入するかどうかを確認する。 Rule1. Orientedgevj -vl asvj → vl, viとvlが隣接していないような、見直された辺vi → vjがあるときはいつでも（そうでない場合は、新しいv構造が生成されます）; Rule2. 規則2. エッジ vi -vj を vi → vj とし，チェーン vi → vl → vj があるときはいつでも（そうでない場合は，有向サイクルが作成される），エッジ vi -vj を vi → vj とします；規則3. ルール 3. エッジ vi -vj を vi → vj とし、2 つの鎖vi -vp →vj とvi -vl →vj が存在する場合はいつでも、vp と vl が隣接していない場合（そうでない場合は、新しい v-構造または有向サイクルが作成されます）、エッジ vi -vj を vi → vj とします。アルゴリズムの複雑さ最悪の場合、条件付きのテストの数は、 m ∗ 2(d) ( i ) で制限されます。計算量 i=0 の複雑さは、m と d に応じて指数関数的に増加します。このアルゴリズムの精度と効率は、領域知識を考慮に入れることで大幅に向上します。具体的には、既知のサービス呼び出し依存性に基づいてエッジを削除したり、その方向を指定したりすることができます。例図3は、Ml at を用いて4つのマイクロサービスからなるデモ動作グラフを構築した場合の詳細を示したものである。このインシデントは、IBM Cloud SREチームによって「パフォーマンスダウングレード」に分類されています。クラウドアプリケーションのユーザーは、Web UIとコマンドラインインターフェース（CLI）のレスポンスが遅いと報告しています。アルゴリズムを開始するために、G1でレベル=0を設定し、すべてのサービスペアの条件付き独立性をテストします。ダッシュボード⊥イベント｜{∅}を見つけるように辺のDashboard⊥AI |{∅}。そこで、G1からエッジのDashboard-EventとDashboard-AIを削除する。G2では、レベル=1のときの独立性をテストし、Event⊥AI|{Dashboard}を見つける。つまり、イベントはDashboardが与えられたAIと条件付きで独立していることがわかる。G3では、Consoleが{Event, Dashboard}が与えられたAIと条件付きで独立していることがわかり、RemoveConsole-AIが与えられていることがわかる。最後のステップでは、連結されたV構造を用いて、エッジの方向をルールチェックしながらスケルトンの方向を決めていく。最後に、Mlat : Event → Console → Dashboardを使って、行動グラフの部分を取得します。同様に、Mio,MemandMavlを使ってEvent→Consoleを見つけます。エッジイベント→コンソール→ダッシュボードは、Mavl を使って検出しています。したがって、図１１１１３に示す重み計算表によれば、イベント→コンソールの重みは（４，０，０，０，０，４，４，４）であり、コンソール→ダッシュボードの重みは（２，０，０，０，０，０，２）である。 ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-07-09_at_12.02.51_PM.png]] Figure 3: Example of behavior graph construction. ### 5.2 Addition Operation and Service Profile ## 6 AUTOMATED ROOT CAUSE DETECTION ### 6.1 Automated Metric Weight Learning 従来、短期的な接続サービスの健全な状態を示すためにレイテンシを選択していましたが、長期的な接続サービスの監視には効果的ではありません。負荷特性は、IO集約的なサービスの健全性を示すために使用できますが、AIやNLPのような計算集約的なサービスには適していません。このことは、単一のタイプのメトリクスでは、多様なサービスで発生する異常を特徴付けることができないことを示しています。本節では、**サービス固有の異常を特徴づけるために最も効果的なメトリクス(または複数のメトリクスの組み合わせ)を見つける**方法について議論します。 AutoMAPでは、経験豊富なSREのマニュアルトラブルシューティングの方法を参考にして、適切な診断指標を選択することを基本的な考え方としています。つまり、過去のインシデントで確認された根本原因がある指標でフロントエンドサービスと高い相関性を示している場合、同様の状況では、根本原因候補のサービスも同じ指標で高い相関性を示しているはずです。そこで、AutoMAPでは、プロファイルの類似性に基づくメトリックの重み学習メカニズムを導入しています。サービス相関と結果精度の測定関数を定義する。サービス相関。Mから行動グラフG(V , E,W )が生成される場合、Cを各サービスペア vi , vj ∈Vのマルチメトリック相関行列とすると、Ck = [Ck ]n×nは、Mkに基づいた相関スコアを記録する。次のように定義される。我々は、2つのメトリック系列の共分散をそれらの標準偏差の積で割ったものを計算し、その結果の絶対値をスコアとして使用します。このスコアは，2つのサービス間の正または負の線形相関の強さを測定する．ci,j,k =1は完全に相関があることを意味し、ci,j,k =0は2つのサービス間に非相関があることを意味する。結果の精度。指標の信頼度を定量化するために、結果の精度を評価する性能測定を導入する。結果の精度が高いほど、アルゴリズムがより正確に根本原因を特定できることを示し、その結果、調査すべき間違った候補が少なくなることを示している。具体的には、異常行動グラフ G とメトリクス M を与え、結果候補を Rn×1、根本原因サービスを vr c とすると、一般的に精度スコアは｜R ∩ vr c |/｜vr c |として計算される。 ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-07-09_at_3.40.24_PM.png]] 図6にAutoMAPにおけるメトリック重み学習の自動化手順を示す。対象となる異常値GAが与えられた場合、過去の記録の中からGAに類似したプロファイルの上位k個を検索し、その結果を{G1,G2, - - - - ,Gk }とする。したがって、GAに対しては、M1からMmまでを個別に考慮して、根本原因とフロントエンドサービスの相関スコアを用いて、提案メトリックの重みを計算します。ここで、wi∈wはGを診断する際のMkの信頼度重みを表し、w=1とする。 k ｋ1 P(Gj)crc,f r,i を精度加重投票として計算する。 j=1 Mk の推奨重みとして，正規化された値を用いる．特に，過去の異常プロファイルが存在しない場合には，デフォルトのメトリックMlatを用いて処理を開始します． ### 6.2 Profile Similarity 本節では，類似した異常プロファイルを探索するための類似度関数を提案する．従来の計測では、グラフトポロジーの距離を比較するのが一般的であったが[26]、AutoMAPではその根源的な異常パターンに着目してプロファイル間の類似度を計測することを目的としている。しかし、AutoMAPでは、プロファイル間の類似度を根元の異常パターンの観点から測定することを目的としています。そのため，この関数はプロファイルのトポロジー，サービスプロファイル，エッジの類似度を同時に測定できるようにする必要がある．類似度関数を以下のように定義します。ProfileSimilarity.Letsim(Gi,Gj)bethessimilarityscoreofanomaly profile Gi,Gj, sim(Gi,Gj)∈[0,1]．sim(Gi,Gj)=1であればGiとGjは同一であり、そうでなければsim(Gi,Gj)=0であればGiとGjは共通の特徴を持たない。GiとGjの類似度の計算は、４つのステップからなる。 ... ### 6.3 Root Cause Detection ![[AutoMAP Diagnose Your Microservice-based Web Appli/ScreenShot_2020-07-09_at_3.47.31_PM.png]] 図 7 は、図 3 および図 4 と同様の事例を用いて構築した動作グラフ（部分）である。なお、この例では、スペースの都合上、ほとんどのユーザドメインの API や通常のサービスは削除されている。グラフを見ると、異常なサービスのほとんどが接続されていることがわかります。そのうちのいくつか（すなわち、Ｓ１、Ｓ１２、Ｓ２７）は、他のサービスとは接続されていないことに気づく。さらに、(S3, S19)と(S4, S11, S23, S25)は相互に接続されていますが、フロントエンドサービスであるS18から分離されているため、根本原因の特定には考慮されません。気になってSREにアドバイスを求める。彼らは、これらのサービスがHTML5ベースのWebSocketサーバとWatson NLPモジュールに属していることを発見しました。これらのサービスは通常、非常に長い接続を持っており、彼らのメトリクスはこの異常な状態では意味がありません。言い換えれば、これらのサービスは他の異常なサービスとは相関関係がありません。したがって、いくつかの無関係なサービスは、動作グラフ構築の段階で考慮から除外することができます。我々の報告によると、このインシデントの根本的な原因は、いくつかのイベントコンポーネントがメモリを使い果たしたことにあります。その後、それはインフラストラクチャ内で伝播し、コンソールを遅くし、最終的にダッシュボードをフリーズさせます。S18から始まり、サービスチェーン「18→13→6」が因果関係「R→C→E」を表していることを観察します。いずれにしても、行動グラフの指示に厳密に従うと、確認できるのはごく一部のサービス（図７では太い緑の線でマークされている）のみであり、それ以外のほとんどのサービスは調査の対象外となる。このように、サービスの呼び出しや伝播が階層化されていくと、異常の特徴が変化していく。そのため、サービス相関スコアを直接利用して根本原因を辿ることは不正確である（階層的サービス相関に基づく代表的なアルゴリズムであるTBAC[27]の実験結果を参照のこと）。実際の運用システムでは、大量かつ多様性の高いマイクロサービスのため、診断は非常に困難です。自動化されたツールがない場合、IBM Cloud SRE チームは、各インシデントの根本原因を特定するのに平均 3 時間を費やしています。 ### 6.4 Heuristic Random Walk Algorithm AutoMAPは、動的でヒューリスティックなアルゴリズムを採用し、根本原因を特定します。これは、従来のトラブルシューティングの操作をシミュレートしています。具体的には、フロントエンドサービスから開始し、サービス呼び出しトポロジを辿り、異常とのメトリック相関関係に基づいて各サービスを徐々に調査していきます。**より多くの調査パスで対象となるノードは、根本原因である可能性が高い。この直感的な観察に基づいて、前方遷移、自己遷移、後方遷移の3種類の遷移を持つランダムウォークアルゴリズムを提案する。** 前方遷移。根本原因診断の基本的な考え方によると、訪問者はv jをその相関関係に比例して訪問する、すなわちcj,fe,k.cj,fe,k.を訪問する。したがって、前方遷移確率行列Pは次のように定義される。ここで、OiはGA内のノードviのアウトネイバーノードの集合である。自己遷移。自己遷移は、訪問者が現在訪問しているサービスに長く滞在するように促します。pisを訪問ノードviの自己遷移確率とすると，pi,iの差と，in-隣り合うノードの最大遷移確率によって決定される．と vi の外側の隣人である．したがって ere Ii は GA のノード vi の近傍ノードの集合である。後方遷移。もう一つのケースは、訪問者が低い相関スコアを持つ特定のサービスを訪問している場合、すべてのアウトネイバーサービスが与えられた異常値との相関が低い場合、訪問者は離れる方法を見つけることができない場合があります。そこで、我々はこの問題を解決するために、ランダムウォークをより動的なものにするために後方遷移を設計する。具体的には、pb を vi からｉ，ｊ GAにおけるvj ∈Iiは、以下のように定義される。ここで、ρ ∈[0, 1]は強度パラメータであり、ρはランダムウォークパスの元のエッジ方向への忠実度を制御する。ρを低く設定すると、訪問者は元の方向に拘束されやすくなります。逆に、ρを高く設定すると、必要に応じて後方に歩くことをより促す。ランダムウォーク。異常行動グラフGAが与えられると、ランダムウォークアルゴリズムは、vf eから始まり、前進、後退、自己遷移の確率を計算し、それらのうちの1つをランダムに選択する。サービスは、訪問者が現在訪問しているノードとその近傍のノードの中から次の対象をランダムに選択することで、順番に訪問される。各サービスの訪問回数を記録し、結果として降順にリストを出力します。なお、ランダムウォークは、アノマリープロファイルではなく、独自の行動グラフGAに基づいて行っています（GAから正常な相関関係を削除しています）。これにより、より多くの候補を検出する確率が高まります。このプロセスをアルゴリズム2にまとめます。 ## 7 EXPERIMENTS AND EVALUATIONS ### 7.1 Dataset and Benchmarks 本研究では、シミュレーション環境と実環境の両方を用いて、AutoMAPの評価を行っています。模擬環境は、[Pymicro 3 と呼ばれるマイクロサービスベースのシステム](https://github.com/rshriram/pymicro)を用いて実装しています。Pymicro 3は、16個のマイクロサービスがDockerコンテナで動作し、Zookeeperで管理されています。これらのマイクロサービスは、あらかじめ設定されたトポロジーに従って相互に作用します。異常をシミュレートするために、各ラウンドでPymicroのバックエンドサービスをランダムに選択し、コンテナをシャットダウンしたりDoS(DoS)攻撃を実行したりしています。私たちの実世界のデータセットは、IBM Cloudの20件のインシデントで構成されています。これらのインシデントは内部で報告され、収集され、IBM SREチームによってどのサービスが根本原因であるか検証されます。各インシデントについて、合計1732個のマイクロサービスAPIから7200秒（異常が検出される1時間前と1時間後）の間に収集された約1,500万個のメトリクスがあります。このデータセットは、主要なシステムドメインのAPIのみを記録しており、そこからほとんどのユーザードメインのAPIを削除しています。いくつかのベースラインアプローチを選択した。TBAC [27]、MonitorRank [23]、CloudRanger [30]、NetMedic [8]、MS-Rank [32]である。TBAC(Timing Behavior Anomaly Correlation)は非ヒューリスティックなアプローチであり、異常メトリックの相関関係に働きかけ、依存関係グラフに基づいて重み付けされた一連の評価を用いて改良したものである[27]。AutoMAPとTBACを比較し、相関スコアのみで根本原因を検出することの不正確さを検証しています。MonitorRankは、あらかじめ定義されたネットワークトポロジーと単一のメトリックに基づいたヒューリスティックアルゴリズムである[23]。AutoMAPとMonitorRankを比較することで、事前に定義されたトポロジーではなく、行動グラフを使用するメリットを検証することができます。NetMedic は従来の階層型コンピュータネットワークを対象としたマルチメトリック診断アプローチである。AutoMAPとNetMedicの比較では、ヒューリスティックランダムウォークの優位性を反映することができる。CloudRangerやMSRankもメトリクスを用いてトポロジーを生成するが、サービスやアノマリーの特性を考慮していない。AutoMAPと比較することで，正確な診断を行うためには，導入時の異常プロファイルが重要であることを反映することができる．これらのアルゴリズムを実行するために同じインシデントメトリクスを使用しています。TBAC, MonitorRank, CloudRanger のようなシングルメトリックに依存したアルゴリズムについては、M lat, M thr の観点から精度を検証した。事前に定義されたトポロジーに依存するアルゴリズムについては、トポロジーの呼び出しの根拠が記録されていないため、M lat上に構築されたビヘイビアグラフを用いて実行している。top-k と top-1 から k までの平均精度（avg-k と呼ぶ）を用いて、異なるアルゴリズムを比較します。テストの各ラウンドでは、異なるメトリクスのスコアとして avg-5 の精度を選択し、AutoMAP のスコア行列を更新する。プロトタイプシステムはPythonと[[Pcalg]]パッケージ([https://pypi.org/project/pcalg/](https://pypi.org/project/pcalg/))を用いて実装しています．アルゴリズム1では、条件付き独立性を決定するために[[カイ二乗検定|χ2-test]][25]を使用しています。メトリックのサンプリング間隔は、Pymicroでは2秒、IBM Cloudでは5秒とした。実験は、Intel Xeon 2.4GHz CPU、16GB RAM、64ビットWindows Server 2008を搭載したワークステーションで行いました。実験結果はすべて、20回のテストを平均して得られたものです。 ### 7.2 Experiments and Results Analysis 7.2.1 根本原因の特定。最初の実験では、k =1/3/5, l = 1440の場合に、選択したアルゴリズムの精度を比較します。AutoMAPとMS-Rankについては、10ラウンドの最適化を行った結果の精度を記録した。図8は、IBMクラウドのインシデントを用いた実験結果をまとめたものです。一般的に、結果精度の面では、AutoMAPが他のアルゴリズムよりも優れていることがわかります。具体的には、上位1位で64.4％、上位5位で93.9％の結果精度を示している。他のアルゴリズムでは、適切な指標を選択しないと結果精度が50%以下になることが多い。模擬システム-Pymicroで得られた実験結果を表4にまとめると、IBM Cloudのインシデントで得られた結果と同様の結果が得られています。根本原因の検出は、相関スコア（TBAC）だけに基づいていると不正確であることがわかりました。また、静的アルゴリズム（TBAC、NetMedic、MonitorRank、CloudRanger）と比較して、ランダムウォーク方式の方がより高い精度で根本原因を特定できることがわかりました。また、MS-Rank アルゴリズムと比較して、AutoMAP にアノマリープロファイルを導入することで、特に上位 1 位と上位 3 位の結果の精度を効果的に向上させることができます。 7.2.2 自己最適化。7.2.2.2 自己最適化機構の有効性を検証するために、複数回の実験を行い、従来のNetMedic解との比較を行った。実験は、IBM Cloud のインシデントを用いて、k =1/3/5、l = 1440 の場合に実施した。結果は図9に示されており、テストのラウンド数を増やすとAutoMAPの精度が大幅に向上することがわかります。例えば、精度は59.7%(k = 5)から10回目で93.9%に上昇しています。AutoMAPはNetMedicと比較して大きな優位性を示しています。NetMedicは自己最適化をサポートしていないため、急激に変化するシステムアーキテクチャの中では不安定です。 7.2.3 アルゴリズムパラメータ - ℓ. 3 つ目の実験では、異なるパラメータが AutoMAP に与える影響を評価します。IBM クラウドのインシデントについて、l を 700 から 1440 に増加させた場合の AutoMAP の精度を比較しています。AutoMAPにより多くのメトリクスを入力した場合、つまりパラメータlを大きく設定した場合、図10に示すように、サービス間の相関関係がより正確になっていることがわかります。lが小さいと精度に大きな影響があり、例えばl=700の場合は精度が40%以下に低下します。図10は、マルチメトリック最適化をサポートするためのデータがより多くあるため、lが高いほど精度がより早く向上することを示しています。 7.2.4 ドメイン知識この実験では、領域知識の効果を検証する。本実験では、AutoMAPにおいて異なる種類の知識を用いた5つの強化手法を提案している（表IV参照）。本実験では、第1回および第10回のAutoMAPの結果を比較した。表5と図11は、IBM Cloudのインシデントを用いた実験から得られた結果をまとめたものです。領域知識で強化されたアルゴリズムは、オリジナルのAutoMAPに対して異なる影響を与えていることがわかります。例えば、l = 200の場合、特に行動グラフに情報を追加する3つのアルゴリズム（AutoMAP+API 4.9%改善、AutoMAP+Linked +8.2%改善、AutoMAP+Direction +5.4%）では、ドメインナレッジがアルゴリズムの精度を向上させるのに役立ちます。しかし、l=1440の場合には、アルゴリズムを強化しても精度は向上するものの、導出された行動グラフはヒューリスティック診断に使用するには十分であることがわかります。このことは、より多くのサンプリングデータが利用できるようになると、領域知識の役割が弱くなることを明確に示しています。 7.2.5 アルゴリズムのパラメータ - αとρ. 最後の実験では、AutoMAPの重要なパラメータであるαとρの影響を分析しました。結果を図12と図13に示します。αの影響を観察するために、αを0.01から0.50に増加させたところ、全体の実行時間が直線的に増加することがわかりました（図12参照）。α = 0.5 の場合でも、完全なデータセットを処理するのに 4 分以内であることがわかりました。次に、αとρの効果を分析するために、追加の実験を開発しました。が精度に与える影響を調べました（図13）。αを0.01から0.50に増加させ、異なるlでの精度を比較すると、データセットがスパースな場合（例えば、l=200の場合）、αが高いほど精度が高くなることがわかります。これは、AutoMAPが相関を特徴づけるのに十分なメトリクスを持っていないためです。αを低く設定すると、行動グラフのエッジ数が少なすぎて訪問者のアクセス性を確保できず、結果の精度が低くなる可能性があります。一方、より多くのメトリックレコードを使用してAutoMAPを実行する場合、異なるαを使用した場合の影響は明らかではありません。その結果、比較的小さなαを選択することができ、相関グラフがより基底真実と一致するようになります。また、全データセット(l = 1440)を処理する場合、αを大きくした方がより正確な結果が得られるとは限らないことがわかりました。最後に、後方遷移パラメータρの影響を評価するために、2つの環境（α＝0.01、l＝200とα＝0.50、l＝1440）を設定し、異なるρを用いた場合の精度を比較した。図14に示すように、ρが小さい場合、ランダムウォークアルゴリズムがより多くのパスを選択するためには、より高いαが必要であることがわかる。また、ρを１に近い値に設定しても精度は大きく向上しないため、適度な後方遷移パラメータ、例えばρ＝０．