# Principled workflow-centric tracing of distributed systems > [!abstract] 概要 > ワークフロー中心トレーシング(workflow-centric tracing)は、分散システムのコンポーネント内およびコンポーネント間で、因果関係のあるイベント(たとえばリクエストの処理に伴う作業)のワークフローを捉える。分散システムの規模と複雑さが増すにつれ、このようなトレーシングは分散システムの挙動を理解するための重要な道具になりつつある。しかし、資源の会計(resource accounting)や診断といった重要な管理タスクで最大の効果を得るために、こうした基盤をどう設計すべきかについては、根本的な明確さが欠けている。この重要な問題への研究がなければ、ワークフロー中心トレーシングがその潜在力を十分に発揮できない危険がある。そこで本論文は、ワークフロー中心トレーシングの設計空間を整理し、重要なタスクに対するトレーシング基盤の有用性を高めも損ないもする主要な設計選択を述べる。本論文の設計空間と、我々が提案する設計選択は、これまでに開発した複数のワークフロー中心トレーシング基盤の経験に基づく。 ## 論文情報 | 項目 | 内容 | |---|---| | 著者 | [[Raja R. Sambasivan]](CMU)・[[Ilari Shafer]](Microsoft)・[[Jonathan Mace]](Brown)・[[Benjamin H. Sigelman]]([[LightStep]])・[[Rodrigo Fonseca]](Brown)・[[Gregory R. Ganger]](CMU) | | 発表会議 | SoCC 2016(Santa Clara, CA, 2016-10-05 〜 07) | | DOI | 10.1145/2987550.2987568 | | 種別 | 設計空間の整理(実験を伴わない経験ベースの提案論文) | ## 概要 ワークフロー中心トレーシング基盤の有用性を左右する設計上の判断を、5 つの設計軸に整理した論文である。著者らは Stardust、X-Trace、Dapper、Retro、Pivot Tracing の設計経験と、LightStep での運用経験に基づき、各軸の選択肢と得失を示す。資源帰属と性能関連タスクでは適した設計が異なり、一方のために作った基盤を他方に流用すると、結果が悪いだけでなくオーバーヘッドも膨らむと結論する。 ## 問題設定 リクエストのワークフロー(因果関係のあるイベント列、任意で並行性・同期の構造と詳細な性能情報を含む)を捉えるトレーシングは、Dapper の 1% 未満のオーバーヘッドに見られるように常時稼働できる効率に達し、異常診断や定常的な性能問題の診断、資源の使用量帰属、動的モニタリングに役立つことが示されてきた。ところが Pinpoint、Magpie、Pip、Stardust、Mace、Whodunit、Dapper、X-Trace、Retro、Pivot Tracing のように、少しずつ異なる設計の基盤が数年ごとに提案される一方、どの状況でどの設計を選ぶべきかの知見はほとんどない。OpenTracing のような共通 API を作る動きが出ている今、設計の幅とその違いの理由を理解しておかないと、API がトレーシングの有用性を人為的に制限しかねない。 図1(Figure 1): 2 つの読み取りリクエストのワークフロー。1 つ目はテーブルストアのキャッシュに当たり、2 つ目は分散ファイルシステムへのアクセスを要する。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/fig01-request-workflows.png]] 著者らの問いは「ワークフロー中心トレーシング基盤のどの設計判断が、重要な管理タスクへの有用性を決めるか」である。 ## 提案手法 提案は新しいシステムではなく、設計軸の整理と、管理タスクごとの推奨設計である。 図2(Figure 2): ワークフロー中心トレーシングの構造。上位に管理タスク、下位に概念上の選択・中核の構成要素・追加の構成要素がある。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/fig02-tracing-anatomy.png]] **構造**。上位にアプリケーション(管理タスクを実行する側)、下位にトレーシング基盤を置く。基盤は、因果関係を保存する概念上の選択(トレース構築、因果モデル)、中核の構成要素(メタデータ、伝搬用トレースポイント)、追加の構成要素(付加価値トレースポイント、オーバーヘッド削減、保存・再構築)からなる。メタデータを伝搬して因果関係のあるイベントを識別する方式(要ソース改変)を対象とし、ネットワークメッセージやログの相関から因果関係を推定する非侵入型の方法は、精度が低く帯域内実行ができないので焦点から外す。 **管理タスク**。次の 6 種を扱う(表1)。 表1(Table 1): ワークフロー中心トレーシングの主な管理タスクと、それに適した実装。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/table1-management-tasks.png]] - 異常なワークフローの特定(Pinpoint、Pip、Mace) - 定常的な問題を持つワークフローの特定(Dapper、Stardust 改訂版、X-Trace ほか) - 分散プロファイリング(Whodunit、Dapper) - SLO の達成(Retro) - 資源帰属(Retro、Stardust 原版、Quanto) - 動的モニタリング(Pivot Tracing) **5 つの設計軸**。 1. 保存する因果関係([[因果関係スライス]])。真の因果関係は分からないので、Lamport の happens-before 関係のうち有用な部分(スライス)だけを保存する。潜在的な作業(書き戻しキャッシュ内のデータなど)を、最初に投入したリクエストへ帰属させる**サブミッタ保存**と、その実行を引き起こしたリクエストへ帰属させる**トリガ保存**がある。前者は資源帰属に、後者はクリティカルパス上の全作業を示せるので性能診断に必要である。ワークフローの構造(フォーク、ジョイン、並行性)は分散プロファイリング以外の性能タスクで保存が必要である。リクエスト間の因果関係(ロック競合など)を保存する選択肢もある。 2. 因果モデル。パスや有向木は効率的だが表現力が低く、DAG は表現力が高い。ジョインや集約に伴うリクエスト間依存を表すには DAG が要る。 3. 実行方式。管理タスクをトレーシング基盤の外で非同期に行う帯域外(out-of-band)実行と、メタデータにデータを載せて途中で計算する帯域内(in-band)実行がある。帯域外はワークフロー全体を提示するタスクに向き、帯域内はオンライン性が高くデータ量が少ない一方でメタデータが大きくなりうる。 4. 計装(トレースポイントの追加)。伝搬用トレースポイントは正しく入れるのが難しく、システムの同質性に応じて、プログラミングフレームワーク、アスペクト指向によるパターン照合、共通ライブラリ、カスタム計装から選ぶ。付加価値トレースポイントは誤っても基本的な正しさを損なわない。 5. オーバーヘッド削減。帯域外では首尾一貫したサンプリング(coherent sampling)を使う。ヘッドベース、テールベース、ハイブリッドの 3 方式がある。帯域内ではメタデータの厳選、不可逆圧縮、部分実行を使う。 図3(Figure 3): 潜在的な作業の帰属先が、サブミッタ保存とトリガ保存で異なる例。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/fig03-submitter-vs-trigger.png]] 表2(Table 2): 各タスクに適したリクエスト内の因果関係スライス。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/table2-causality-slices.png]] 表3(Table 3): 伝搬用トレースポイント(Table 3a)と付加価値トレースポイント(Table 3b)の追加方法の得失。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/table3-instrumentation-tradeoffs.png]] **推奨設計**(6.1 節)。ワークフロー全体の提示が要るタスクには帯域外実行を、要らないタスクには帯域内実行を勧める。伝搬用トレースポイントはライブラリへの埋め込み、付加価値トレースポイントは既存ログの再利用を、多くの環境に適用しやすい保守的な選択とする。 - 異常な性能問題の特定は、帯域外、トリガ保存、構造の保存、テールベースのサンプリングとする。 - 定常的な問題の特定は同様だが、ヘッドベースでよい。サブミッタ因果や競合スライスを足す場合はテールベースにする。 - 分散プロファイリングは、帯域内、トリガ保存(集約によるメタデータ膨張を避けるため)、構造の保存なし、不可逆圧縮とする。 - SLO の達成は、帯域内、トリガ保存、構造の保存、ジョインでの部分実行による枝刈りとする。 - 資源帰属は、帯域内、サブミッタ保存、DAG、集約後に「集約 ID」へ置き換える方式とする。 - 動的モニタリングは、帯域内、動的計装、部分実行(集計を途中で行う)とし、因果スライスは目的に依存する。 ## 新規性 - 設計空間を 5 軸に整理し、性能関連タスクと資源帰属で推奨が分かれることを明示した。因果関係スライスという軸は、著者らの知る限り既存文献が明示的に扱ってこなかったと述べている。 - 作業の集約が、サブミッタ因果とヘッドベースのサンプリングの組み合わせで、実効サンプリング率を膨らませることを指摘した。 - 既存の実装の設計選択を推奨と並べ、差異の理由を推測した(表4)。 ## 実験設定 実験はない。設計の根拠は、Stardust(原版・改訂版)、X-Trace(原版・改訂版)、Dapper、Retro、Pivot Tracing の設計経験、Spectroscope での診断の経験、LightStep の顧客との対話、および文献調査である。文献調査で自身が開発していない基盤に割り当てた因果スライスなどは「文献から読み取れた範囲での最善の推測」と明記されている。 ## 実験結果 定量評価に相当するのは、著者らの経験と既存論文の数値の引用である。 - Dapper は全トレースポイントをサンプリングするとスループットが 1.5%、応答時間が 16% 悪化するが、0.01% のサンプリングでは応答時間 0.20%、スループット 0.06% に下がる(引用)。 - 集約のあるシステムで 0.1% のヘッドベースサンプリングを行うと、32 件を集約した後のトレースポイントのサンプリング確率は 3.2%、2 段の集約後は 65% に達する。Ursa Minor では入口近くのキャッシュが 32 件を集約しており、10% のサンプリング率で集約後のトレースポイントの 97% が常にサンプリングされ、オーバーヘッドが下がらなかった(Stardust 改訂版の開発時の経験)。 - Ursa Minor の最大ワークフローは約 500 個のトレースポイント、数百 KB だった。テールベースのサンプリングは同時実行中の全ワークフローを完了まで保持するのでメモリが問題になる。 - Retro と Pivot Tracing の対象システム(MapReduce、HDFS、YARN、HBase、ZooKeeper、Spark、Tez)では、パターン照合で拾えない部分に伝搬用トレースポイントを手で足すのに、1 システムあたり 50〜300 行の改変で済んだ。 図4(Figure 4): 因果関係スライスの違いによって考慮が必要になるトレースポイント。集約があるとサブミッタ保存では下流のほぼ全部が対象になる。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/fig04-aggregation-considered.png]] 表4(Table 4): 各管理タスクへの推奨設計(斜体)と既存実装の選択。 ![[_attachments/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems/table4-design-choices.png]] ## 考察 既存実装との差異について、次のように説明している。 - Pinpoint と Mace は異常特定の推奨と違い、パスモデルのためワークフロー構造を保存できない。Pinpoint は主に正しさの異常を対象とするためである。いずれもサンプリングを使わないのは、本番運用や大規模システムを想定していなかったためと推測している。 - Dapper と原版 X-Trace は木を使うためジョインを保存できない。Dapper は同期の少ない並行性の大きいシステムを主な用途としたためである。Google らはトレースを比較してジョイン位置を学習し、木を DAG に整形する研究を進めている。 - Stardust 改訂版と X-Trace 改訂版は、定常的な問題の診断に役立てるための改修の結果、独立に同じ設計へ収束した。資源帰属向けに作られた Stardust 原版は診断には不十分だった。 - Retro は SLO の達成と公平性の保証の両方に使うため、トリガ・サブミッタの両方を保存する。 - Pivot Tracing と Retro は、アスペクト指向の拡張を持つ同質的なシステム向けなので、構造の保存が要らないタスクなら設計選択を変えるだけで幅広いタスクに使える可能性がある。 今後の研究課題として、単一の基盤を動的に構成して全タスクを支える方向(Pivot Tracing がその一歩)、異種システムでの計装負担の軽減と OpenTracing のような標準、既存のログ基盤のワークフロー中心化、制約ベースのリプレイなど新しい帯域外解析、巨大なトレースの意味付け・圧縮・比較・可視化、帯域内解析の限界の探求を挙げる。 ## 強み / 弱点・課題 強み: - 用途によって因果スライスと実行方式の最適解が異なることを、自身の失敗談(Stardust の流用、ヘッドベースサンプリングの効果がなかった件)を根拠に示している。 - 管理タスク・設計軸・既存実装を 1 つの表で対応付け、後続の設計者が判断に使いやすい。 弱点・課題: - 推奨は「最低限必要な選択」であり、定量実験による検証はない。 - 他者が開発した実装の分類は文献からの推測である。 - 5 軸は網羅的でないと著者自身が述べている。 - 2016 年時点の基盤が対象であり、[[トレースサンプリング]]の後続研究や機械学習向けトレーシングは範囲外である。 ## 関連 - ソース: [[@2010__Google__Dapper - A Large-Scale Distributed Systems Tracing Infrastructure]] / [[@2015__SOSP__Pivot Tracing - Dynamic Causal Monitoring for Distributed Systems]] / [[@2007__NSDI__X-Trace - A Pervasive Network Tracing Framework]] / [[@2002__DSN__Pinpoint - Problem Determination in Large, Dynamic Internet Services]] / [[@2003__HotOS__Magpie - Online Modelling and Performance-aware Systems]] / [[@2017__SOSP__Canopy - An End-to-End Performance Tracing And Analysis System]] - 概念: [[分散トレーシング]] / [[因果関係スライス]] / [[トレースサンプリング]] / [[トレーシングオーバーヘッド]] / [[暗黙のコンテキスト伝搬]] / [[クリティカルパス分析]] - エンティティ: [[Raja R. Sambasivan]] / [[Ilari Shafer]] / [[Jonathan Mace]] / [[Benjamin H. Sigelman]] / [[Rodrigo Fonseca]] / [[Gregory R. Ganger]] / [[LightStep]] / [[Carnegie Mellon University]] / [[Brown University]] / [[Pivot Tracing]] / [[Dapper]] ## 出典 - `.raw/papers/2016__SoCC__Principled-workflow-centric-tracing-of-distributed-systems.pdf`