# FacGraph ## 概要 北京大学のグループが提案した、マイクロサービスの根本原因診断アルゴリズムである。PC アルゴリズムで時間窓ごとの相関グラフ(SCG)を作り、幅優先順序文字列(BFOS)で正準表現した頂点一意・根あり・同レベル順序不問の頻出部分グラフを掘る。正常時との支持度の残差(RPS)で固有パターンを除き、MapReduce で分散化する。 ## 仕組みの要点 - 入力は遅延とスループットのメトリクス。事前定義のトポロジは要らない。 - 候補生成は根から頂点を昇順に足す方式で、接続コードで辺の有無を展開し、支持度が閾値未満の候補を枝刈りする。 - 支持度の計数は BFOS の 1 文字ずつの比較で、計算量は O(n+m)。 ## 関連 - 本ソース: [[@2018__IPCCC__FacGraph - Frequent Anomaly Correlation Graph Mining for Root Cause Diagnose in Micro-Service Architecture]] - 同じグループの手法: [[@2018__CCGrid__CloudRanger - Root Cause Identification for Cloud Native Systems]] - 概念: [[グラフベースRCA]] / [[PCアルゴリズム]] / [[根本原因分析]]