# CRISP: Critical Path Analysis of Large-Scale Microservice Architectures ## 論文情報 - **著者**: Zhizhou Zhang(UC Santa Barbara), Murali Krishna Ramanathan, Prithvi Raj, Abhishek Parwal([[Uber]])([[Uber Technologies]]), Timothy Sherwood([[UC Santa Barbara]]), [[Milind Chabbi]]([[Uber]]) - **発表**: USENIX ATC 2022(2022 年 7 月 11–13 日、カリフォルニア州カールズバッド) - **URL**: https://www.usenix.org/conference/atc22/presentation/zhang-zhizhou - **OSS**: https://github.com/uber-research/CRISP ## 概要(日本語訳) マイクロサービスアーキテクチャは現代のサービス指向ソフトウェアシステムに不可欠な存在となっているが、マイクロサービス間の RPC(リモートプロシージャコール)は深くネストされており、非同期かつ膨大な数に上るため、トップレベルリクエストのエンドツーエンドレイテンシに寄与するサービスを特定することは非常に困難である。本論文では、RPC トレースから**クリティカルパス分析(CPA)**を大規模に行うツール CRISP を提案する。CRISP は(a)特定エンドポイントのトップダウン CPA、(b)全エンドポイントにわたるボトムアップ CPA、(c)オンラインの異常検知という 3 つの性能分析機能を提供する。[[Uber]] の約 4 万エンドポイントで 3 か月の実運用により、5 件のパフォーマンス課題を特定し、将来のハードウェア選定を誘導し、TraceAnomaly 対比で訓練・推論をそれぞれ最大 27.77 倍・66.85 倍高速化しつつ偽陽性アラートを 50% 削減した。 ## 問題設定 - [[Uber]] バックエンドは約 4,000 マイクロサービス・約 40,000 エンドポイントで構成。リクエストは数十段のホップを経て処理される。 - 既存の分散トレーシングツール([[Jaeger]] 等)は大量データを収集するものの**直接的な洞察(インサイト)を提供しない**。 - 個々のトレースには数千のネストした非同期 RPC が含まれており、1 人の開発者が手動で理解することは事実上不可能。 - ボトルネックの特定・TTL 値の設定・障害診断・容量計画に役立つ定量的知見が得られていない。 ## 提案手法 ### クリティカルパスの定義と抽出 クリティカルパスはタスクグラフ `G=(V,E)` における始端から終端への**最大重み路**と定義される(CPA は並列計算での有向非巡回グラフ最長路として古典的に研究されている)。 Jaeger/OpenTracing のスパン形式は親スパンに子スパンの依存情報が含まれないため、子スパンの開始・終了タイムスタンプから「spawn」「sync」イベントを推定し、論理 DAG を構成する。 - **クリティカルパスアルゴリズム(CP)**: 子スパンを終了時刻降順でソートし、最後に終了した子(LFC; Last Finishing Child)の経路を再帰的にクリティカルパスに追加する(擬似コード Listing 1)。 ### クロックスキューへの対処 異なるホストのマシンクロックは NTP 同期にもかかわらずドリフトする。Uber 本番の実測では 118K トレース中 50% 超でスパンのオーバーラップが発生し、P50 オーバーラップ 204µs・最大 1696µs を観測。 2 条件による緩和: 1. 前スパンの終了と次スパンの開始が `threshold(=1ms)` 以内であれば重複と見なさない。 2. 重複区間に他の子の spawn/sync イベントが存在しない。 スパンのオーバーフロー・アンダーフローは親スパンの範囲でクリッピング(切り捨て)し、全体の切り捨て率を 5% 未満に抑えた。 ### CCCT によるトレース集約 クリティカルパスを**呼び出しコンテキスト木(CCT; Calling Context Tree)**として符号化した構造を「クリティカル呼び出しコンテキスト木(CCCT; Critical Calling Context Tree)」と呼ぶ。複数トレースの CCCT を HPCToolkit 方式でマージした重み付き集約 CCCT を構築し、パーセンタイル(P50/P95/P99)ごとのレイテンシを表現する。 ### 3 種類の機能 | 機能 | 対象ユーザー | 説明 | |---|---|---| | トップダウン分析 | サービスオーナー | 特定エンドポイントの CPA をフレームグラフ・ヒートマップで可視化 | | ボトムアップ分析 | 基盤・容量エンジニア | 全エンドポイントに影響する内部 API をランク付けして浮き上がらせる | | 異常検知 | 開発者全般 | CCCT を特徴量ベクタ(SCPV)に変換してオートエンコーダで正常パターンを学習・推論 | ### SCPV を使った異常検知 TraceAnomaly の STV(サービストレースベクタ=全呼び出しパスを符号化)に対し、CRISP は**クリティカルパス上の呼び出しパスのみを符号化した SCPV(サービスクリティカルパスベクタ)**を用いる。特徴次元を最大 25 分の 1 に圧縮し、訓練・推論時間を劇的に短縮。 ## 実験設定 - **環境**: Uber 本番の全バックエンド(約 4,000 マイクロサービス・約 40,000 エンドポイント) - **データ規模**: 1 日あたり約 200GB・約 1,800 万スパン・約 256 CPU 時間 - **評価期間**: 3 か月間 - **異常検知評価**: 6 エンドポイントで 14 日間の本番トレース(訓練 20,000 件・テスト 500 件)を使用 - **ハードウェア**: Intel Xeon Gold 5218(GPU 機)/ Intel Xeon Silver 4214(CPU 機) ## 実験結果 ### トップダウン分析による課題発見例 `getDriverTasks` エンドポイントの差分フレームグラフにより、P50 では現れない `getTaskCompletionStatus`(Cassandra 読み取り)が P95 レイテンシの 47% を占めることを特定。 `createOrder` エンドポイントでは以下の最適化機会を発見: - `decideOrderRisk` が P50 レイテンシの 68% を占有 → キャッシュ活用と並列化を推奨 - `GetVenues`/`GetAccessPts` の不必要なシリアル化 → 並列化可能 - `FareValidate` の不要なサーバーラウンドトリップ → エッジデバイスへの移動 - `GetMarketplaceBenefits` の DB フェッチ → キャッシュ化 ### 異常検知の定量評価 | | TraceAnomaly(STV) | CRISP(SCPV) | |---|---|---| | 訓練高速化(最大) | — | 最大 27.77 倍(GPU) | | 推論高速化(最大) | — | 最大 66.85 倍(GPU) | | Recall(Service 3) | 0.5 | 0.982 | | Recall(Service 5) | 0.5 | 0.982 | | 偽陽性削減 | — | 約 50% | ### ハードウェア選定への活用 CPU クロック 2.2GHz(SKU-A)と 2.4GHz(SKU-B)の比較で、9% のクロック差が P50 レイテンシ 15% 増・テイルレイテンシ 1.5 倍の差を生じさせることをクリティカルパス分析で特定。 ### ボトムアップ分析でのシステム規模の特性 100 万トレース・約 40K エンドポイントの全体的特性: - 1 トレース当たり平均 112 スパン、最大 275K スパン - クリティカルパス上のスパン数は平均 33 件(全体の約 30 分の 1) - クリティカルパス上の固有エンドポイント数は最大 140(全体の最大 1,400 の約 10 分の 1) ## 考察 ### 強み - **規模と実証性**: 4 万エンドポイント・数億トレース・3 か月という産業規模の実証が強力な説得力を持つ。 - **クリティカルパスによる信号圧縮**: 全グラフ比で 1/10 の規模に絞ることで、異常検知の特徴次元が劇的に削減され、訓練・推論の高速化と偽陽性削減が同時に達成される。 - **クロックスキューへの実用的対処**: 「精度 vs 実装の現実」のトレードオフを 1ms 閾値というシンプルな設計で解決し、切り捨て率 5% 未満を実証した。 ### 弱点・課題 - **合成異常による評価**: 異常検知の評価はノードの 20% 除去とランダムな所要時間シャッフルで生成した合成データを使用。実際の異常のラベル付きデータが少ないため、実際の異常種別への一般化能力が不明。 - **ヘッドベースサンプリングとの組み合わせ**: Jaeger はテールベースサンプリングに非対応。クリティカルパスに寄与するレアケースがサンプリングで抜け落ちるリスクは残る。 - **インストルメンテーション前提**: マイクロサービス全体への Jaeger 計装が前提。計装が不完全なサービスでは CPA の信頼性が下がる。 ## 関連 - 概念: [[クリティカルパス分析]] / [[分散トレーシング]] / [[異常検知]] / [[テレメトリ]] / [[トレースサンプリング]] / [[Fault Localization]] / [[マルチモーダル障害診断]] - エンティティ: [[CRISP]] / [[Jaeger]] / [[Uber]] / [[Zhizhou Zhang]] / [[Milind Chabbi]] / [[Timothy Sherwood]] / [[UC Santa Barbara]] - 関連 MOC: [[LLM4SRE - MOC]] / [[分散深層学習 - MOC]] ## 出典 - 本文全体(§1 Introduction, §2 Motivating Example, §3 Background, §4 CRISP Methodology, §5 Critical Path Analysis, §6 CRISP Features, §7 Experience and Evaluation, §9 Conclusions)