# Performance Debugging for Distributed Systems of Black Boxes > [!abstract] 概要 > 興味深い大規模システムの多くは、複数の通信コンポーネントからなる分散システムである。このようなシステムは、性能が悪化するとデバッグが非常に難しくなる。異なる、場合によっては競合するベンダーのソフトウェアで構成され、通常はソースコードを利用できない「ブラックボックス」コンポーネントを含む場合、問題はさらに難しくなる。典型的なソリューションプロバイダの従業員は、このようなシステムを効率よくデバッグするための十分な技能や経験を持たないこともある。本論文の目標は、ブラックボックスノードから構成される分散システムの性能ボトルネックを、比較的熟練度の低いプログラマだけでなく専門家も特定できるツールを設計することである。 > > 私たちは、ノード内部やメッセージの意味を知らず、可能な限り受動的に取得したメッセージレベルのトレースによってこの問題に取り組む。分散システムを通る支配的な因果経路をトレースから推定する、まったく異なる2種類のアルゴリズムを開発した。一方はRPCメッセージの時間情報を用いて呼び出し間の因果関係を推定し、もう一方は信号処理技術を用いる。両アルゴリズムは、特定の因果経路上の特定ノードへ遅延を帰属させられる。類似問題を扱う従来手法と異なり、本方式はアプリケーション、ミドルウェア、メッセージの変更を必要としない。 ## 論文情報 - タイトル: Performance Debugging for Distributed Systems of Black Boxes - 著者: Marcos K. Aguilera, Jeffrey C. Mogul, Janet L. Wiener, Patrick Reynolds, Athicha Muthitacharoen - 媒体: SOSP '03, October 19–22, 2003, Bolton Landing, New York - 発表年: 2003 - 掲載頁: 74–89 ## 概要 本論文の対象は、Webアプリケーションのように複数のベンダー製コンポーネントが通信するシステムである。ソリューションベンダーは、Webサーバ、アプリケーションサーバ、データベース、認証、名前解決、決済などを組み合わせたシステムを提供するが、個々のコンポーネントの内部に詳しいサポート担当者がいても、コンポーネント間の相互作用に起因する性能問題まで効率的に調べられるとは限らない。著者らはこの問題を、低レベルコンポーネント単体の高速化ではなく、ユーザーが観測する遅延を通信経路上のどの処理へ帰属するかという「性能イン・ザ・ラージ」の問題として定式化する。 ツールへの要求は、アプリケーションの意味、ノードの実装、メッセージの意味、通信経路の事前知識を最小限にすること、アプリケーション・ミドルウェア・メッセージ・ワークロードを変更しないこと、対象システムの性能を大きく乱さないことである。結果をリアルタイムに返す必要はなく、デバッグ時のオフライン解析を許容する。目的はプログラマを置き換えることではなく、人間が高遅延の経路と、その経路上で遅延を増やすノードを短時間で絞り込めるようにすることである。 論文が検証を試みる仮説は2つある。第一に、ブラックボックスから得た情報だけで、高遅延の因果パスパターンを有用な精度で見つけ、パターン内の特定ノードへ遅延を帰属できること。第二に、その情報が性能デバッグを行うプログラマにとって有用であることである。本論文が主に評価するのは第一の仮説であり、第二の仮説は読者の判断に委ねている。 ## 問題設定 分散システムを、通信するノードのグラフとして表す。ノードはコンピュータ、プロセス、あるいはより粗いコンポーネントであり、辺は通信可能なノード対を表す。外部からの要求はグラフ上で活動を引き起こす。因果パスは、先行ノードからのメッセージによって各ノードの走査が引き起こされる、ノード走査の系列である。自発的なシステム操作も因果パス上の活動を生成しうる。 図1の多層Webアプリケーションでは、クライアント、Webサーバ、アプリケーションサーバ、データベース、認証サーバが登場する。RPC型システムでは呼び出しと戻りの双方がノード操作を生むため、同じノードが1つのパス上で複数回走査される。さらに、同じ認証サーバでも、呼び出しからデータベース呼び出しまでの処理と、データベース応答からWebサーバへの応答までの処理ではコードパスが異なり、遅延も異なりうる。 本論文では、遅延をノード走査へ帰属できると仮定する。LAN上でネットワーク伝搬・スイッチング遅延が無視できない場合は、長いネットワーク接続をゼロ遅延の接続と仮想的な遅延ノードに分割してモデル化する。対象はRPC型通信に限らず、メールのようにメッセージが任意のノード間を流れ、明示的な呼び出しと戻りを持たないメッセージ型通信も含む。 出力として求めるのは、単に遅いノードの一覧ではない。頻繁に実行され、かつ平均遅延が大きく、システム全体のユーザー観測遅延に大きく寄与する高インパクトな因果パスパターンを特定する。また、同じノードでも呼び出し元やパターンによって影響が違うため、パターンに参加する文脈で大きな遅延を加えるノードを特定する。これは、平坦なプロファイラではなく階層型プロファイラを使わないと、関数自体が遅いのか、不要な場所から頻繁に呼ばれているのかを区別できないという例に対応する。 この研究の非目標は、プログラマを不要にすること、正しい動作の検証や機能障害の原因診断を行うこと、性能のベンチマークや特性評価を行うこと、リアルタイム監視を実現することである。 ![図1に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-01-crop.png]] ## 提案手法 処理は、(1) 通信の露出とトレース、(2) 因果パスとパターンの推定、(3) 結果の可視化の3段階である。オンライン段階では、実負荷または合成負荷の下で、ノード間メッセージを可能な限り完全に収集する。オフライン段階では、ノイズ、欠落、タイムアウト、再試行、非同期時計を含みうるトレースから、複数実行を統計的にまとめた因果パスパターンを復元する。抽象トレースの最小単位は、`(timestamp, sender, receiver)` である。RPCの入れ子法を使う場合は、操作種別と呼び出し識別子も利用する。 ### RPCの入れ子アルゴリズム 入れ子アルゴリズムは、RPC型通信で呼び出しと戻りを組にし、ある呼び出しの実行中に別の呼び出しが行われる関係から因果関係を推定する。たとえば、AがBを呼び、BがCを呼んでからAへ戻る場合、BからCへの呼び出しはAからBへの呼び出しに入れ子になっている。 1. **呼び出し対の抽出**: トレースの各エントリを、送信者、受信者、呼び出し識別子で索引付けした開いた呼び出し表へ入れる。対応する戻りを見つけたら、呼び出し時刻と戻り時刻、送信元・送信先を持つ呼び出し対 `(A, B, t_call, t_return)` として保存する。呼び出し識別子が無い、または再送で一意でない場合は時刻順に対応付け、複数の開いた呼び出しに対して最も早い未対応呼び出しと戻りを結び付ける。ただし、後の呼び出しが先に戻る場合や欠落・余分なメッセージがある場合、このヒューリスティックは誤る。 2. **親候補の列挙**: 子 `(B,C)` の戻りが処理された時点で、より早く開始していてBを呼び出している開いた呼び出し `(A,B)` をすべて候補親とする。1つの子が複数の親候補に入る可能性があるため、単一の時刻比較だけでは因果関係を決定しない。 3. **親候補のスコアリング**: トレース全体で観測した、`A→B` の呼び出しから `B→C` の呼び出しまでの遅延 `delta` の頻度を、`(A,B,C,delta)` ごとのスコアボードに蓄積する。子にN個の親候補があるときは各候補への加算を `1/N` として、曖昧な入れ子を均等に扱う。遅延の範囲を効率よく表すため、`log1.05(delta)` で索引付けした340個の指数幅ビンを用い、1ミリ秒から2時間程度をカバーする。必要ならガウス曲線との畳み込みでヒストグラムを平滑化し、時刻のずれによるピークの分散に耐える。 4. **一意な親の選択**: 生のスコアに、同じ親の下で時間的に重なる子の数、同じ宛先を持つ子の数、子全般の数に基づく3つのペナルティを掛ける。実験では、重複子の係数を決める `x` は約2、同一宛先と一般子の係数 `y,z` は0とした設定が、ワークロード全体で最も予測可能でほぼ最適だった。ただし、個別のワークロードでは異なる係数が良い場合がある。親が同点なら最も早い親を選ぶ。 5. **パスの構築と集約**: 親を持たない呼び出し対を根とし、親子関係を再帰的にたどってパスを作る。同型のパスが既存表にあれば、そのパターンの回数と遅延分布を更新する。各ノードには、そのノード自身と子孫を含む処理時間、各辺には親への入口から子への入口までの呼び出し遅延を集約する。したがって、特定のパターンにおけるノード内部の遅延を、他のパターンの同じノードの遅延と分離して表示できる。 入れ子アルゴリズムは、呼び出し対抽出、入れ子候補探索、パス集約がトレース長 `m` と平均ノード並列性 `p` に依存し、全体の時間・空間計算量は概ね `O(mp)` である。並列性は、各子が持つ候補親数の平均として定義される。 ![図2〜図5に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-02-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-03-crop.png]] ### メッセージ型通信の畳み込みアルゴリズム 畳み込みアルゴリズムは、RPCの呼び出し・戻りを個別に対応付けず、自由形式のメッセージ型通信にも適用する。まず、AからB、BからAのような有向エッジごとにメッセージ列を分離し、各列を時間信号として扱う。入力となるAからBのメッセージ集合を指示関数 `s1(t)`、Bから出るメッセージ集合を `s2(t)` とし、`s2` と時間反転した `s1` の相互相関を計算する。ある時刻差 `d` にピークがあれば、Bから出るメッセージ列に、AからBの列を `d` だけずらしたコピーが現れていることを示す。ピーク位置を因果遅延、ピークの大きさをその遅延で対応するメッセージ数の目安として用いる。 相関値の平均と標準偏差から、局所最大で平均よりN標準偏差以上高い点をスパイクとする。例として `N=4` を使う。近接した候補を別スパイクにしないため、間に平均よりS標準偏差を超えない点を要求する。例として `S=3` が示されている。実装では時間を量子 `mu` で離散化し、区間 `[t*mu,(t+1)*mu)` に含まれるメッセージ数の平方根を信号値とする。平方根は、両信号の同じ区間に `x` 件ずつメッセージがあるとき畳み込みに生じる `x^2` の影響を補正する。 遅延分散が大きい場合は、因果遅延の許容幅 `v` を大きくして、固定遅延からの揺らぎを同じ関係として扱う。低周波のパス、偶然に短いパス、サイクル、負の見かけ遅延を抑える改良も実装に含まれるが、各改良の詳細なアルゴリズムは紙幅の都合で示されていない。畳み込み法は、根ノードから出る各宛先を頂点として再帰的にグラフを作り、見つかった遅延を辺ラベルとして記録する。ただし、出力グラフの頂点は分散システムのノードを複数回含みうるため、元のシステムグラフと区別して「vertex」と呼ばれる。 トレース長をメッセージ数 `m`、出力グラフの辺数を `e`、最長トレースの量子数を `S=T/mu` とすると、空間計算量は `O(m+S)`、高速フーリエ変換による畳み込みを用いた時間計算量は `O(em+eS log S)` である。実測では後者の畳み込み項が支配的だった。量子を細かくすると遅延精度は上がるが、実行時間とメモリ消費が増える。 ![図6・図7に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-04-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-05-crop.png]] ### 2方式の比較と可視化 入れ子法はRPC型通信だけを対象とする代わりに、呼び出しと戻りを1つの木構造へまとめるため、RPCパスを簡潔に表せる。転送されたRPC、呼び出し元への戻りより先に後続呼び出しを出す実装、遅延書き戻しキャッシュのような構造では、現在の実装の入れ子関係が壊れる。一方、畳み込み法は自由形式メッセージを扱えるが、RPCの呼び出しと戻りを別辺として扱うため、実際のパスに加えて部分パスや、同じノードを複数回含む派生パスも出力しうる。 畳み込み法は相関ピークを必要とするため、まれなイベントや遅延分散の大きいイベントを探すのに向かない。入れ子法は全RPCメッセージを調べるのでまれなイベントも扱えるが、頻繁だが無関係なイベントと、まれで重要なイベントを区別する問題は残る。トレースには、畳み込み法なら時刻・送信元・受信先だけでよく、入れ子法ではRPCの呼び出し/戻り識別と、可能なら呼び出し識別子が必要である。 入れ子法の表示は、パターンの総インスタンス数、総遅延、各ノード自身と子孫を含む平均遅延、親入口から子入口までの平均遅延を木に重ねる。畳み込み法の表示は、各有向辺に遅延の集合とメッセージ総数を付けた線形パスであり、遅延は頻度順に並べる。論文の可視化は`dot`による初歩的なグラフで、対話的表示、パス頻度・総遅延による並べ替え、最大遅延ノードの強調は開発中の機能として述べられている。 ![図8・図9に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-06-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-07-crop.png]] ### トレースの収集と統合 理想は、ノードを変更せず通信を受動観測することである。スイッチのポートミラーリングなら、アプリケーションホストへソフトウェアを導入せずにパケットを監視ポートへ複製できる。ホスト上で`tcpdump`を動かす方式もあるが、各地点のトレースを後処理で統合する必要があり、高いパケットレートではキャプチャ装置や入力リンクがボトルネックになる。論文では、特殊なキャプチャカードを用いた研究で毎秒約2,000万パケット、著者らのAlphaServer DS10（618MHz、Tru64 UNIX V5.1A）と`tcpdump`で毎秒25,000パケット強を捕捉できたが、後者には欠落があったと報告している。 ブラックボックス性はノードの粒度とメッセージから情報を抽出する難しさに依存する。パケットからノードをプロトコル層ごとのアドレスで識別し、メッセージ境界を復元し、RPCの呼び出し/戻りや呼び出し識別子を抽出する必要がある。J2EEのようにプロセスやEJB単位で観測したい場合は、PinpointのインターEJBトレースも利用できるが、実行時コストと性能攪乱を伴う。著者らはデバッグ期間だけ計装を有効にするなら、短期的なオーバーヘッドを受け入れる余地があるとしている。アプリケーションが通常生成するログを利用することも排除していない。 複数地点・複数層のトレースは、`timestamp operation sender receiver ID` の共通形式に変換し、時刻順に統合する。NTPによる時計同期は、同一LANでRMS誤差1ミリ秒未満、インターネット全体でも通常5ミリ秒未満という既存結果を根拠に、トレースの時間分解能が粗ければ十分な場合が多いとする。ただし、重複エントリ、異なる層でのノード名の不一致、欠落の扱いは残る。 ## 新規性 従来の性能解析・因果追跡システムの多くは、アプリケーションへのログ埋め込み、J2EEなど特定実装への依存、要求IDの伝播、メッセージ意味の知識、または障害注入を必要とした。本論文は、ノード内部とメッセージ意味をブラックボックスとして扱い、可能な限り受動的なメッセージトレースからオフラインで多ホップの因果パスを推定する点に特徴がある。 また、RPCの構造を利用する入れ子法と、通信形式に依存しない畳み込み法を同一の抽象トレース層の上に示した。両者は、パスの頻度だけでなく、特定パターンでのノード走査遅延を分離して返す。実験では、トレースを収集する段階と推論する段階を分離することで、同じトレースに複数の推論アルゴリズムを適用できる設計も示している。 ## 実験設定 論文の実験トレースは、純粋なブラックボックス受動収集ではない。真の因果パスを評価できるよう、まずホワイトボックス情報を持つトレースを作り、要求IDなどの情報を除いてブラックボックス相当へ変換している。評価対象は、合成の多層トレース、J2EE PetStoreトレース、メールの`Received`ヘッダートレースである。加えて、分散ファイルシステムと組み込みシステムのインターメソッド通信トレースにも適用し、正しい因果パスを見つけたが、詳細結果は示していない。 ### 合成多層トレース `maketrace`は、ノード間メッセージの順序列をテンプレート化したtraceletをインスタンス化する。traceletは特定の因果パス、または複数パスの明示的なインターリーブを表せる。連続呼び出し間の遅延にはパラメータ化したガウス分布を使い、クライアントの思考時間に相当する逐次インスタンス間の遅延は一様乱数とする。設定ファイルでtraceletごとの並列実行数を指定できるため、任意の長さと並列性を持つトレースを生成できる。 多層構成は、クライアントからWS1またはWS2、AP1またはAP2、DB1またはDB2へ至り、AUTHも呼び出しうるロードバランサ型の構成である。追加遅延トレースでは、WS2がAUTHを呼んだ後にAP1またはAP2を呼ぶ間へ200ミリ秒の遅延を挿入した。入れ子法の通常・追加遅延トレースはそれぞれ約20万メッセージである。 ### PetStoreのJ2EEトレース Java Pet Store v1.3.1を、単一ノードのJBoss v3.0.6上、2 CPU・1GHz Pentium III、Linux 2.4.9で実行した。負荷生成器は同じホスト上で24クライアントをエミュレートし、複数のワークロードプロファイルと平均7秒のリクエスト間思考時間を使った。約3時間のトレースを2本取得し、各トレースは約130万メッセージだった。各コンポーネント間呼び出しは2メッセージになる。1試行では葉コンポーネントの遅延を増やし、両アルゴリズムで追加遅延を検出できることを確認した。多くの実験では計算時間を抑えるため、各トレースの先頭2,000秒を用いた。 比較対象は通常構成と、`/mylist.jsp`の各呼び出しへ一定50ミリ秒の遅延を追加した構成である。表1には2,000秒相当の通常トレース252,024メッセージ、追加遅延トレース234,036メッセージのほか、全長の通常1,345,538メッセージ、追加遅延1,288,223メッセージが記録されている。 ### メールのReceivedヘッダートレース RPCを主としない実世界データとして、ある著者が2か月間に受信したメールの`Received`ヘッダーを用いた。11,683通から81,044個の利用可能なヘッダーを得た。解析不能な時刻、`localhost`や`unknown`のように多数の偽接続を生むホスト名、企業メールシステム外の転送ホップは除外した。1通のメールを直接経路として扱わず、各ヘッダーを独立したノード間メッセージとして扱うため、実際のメール経路より難しい問題になるが、これは畳み込み法の用途に合うテストとなる。 ## 実験結果 ### 多層トレース 通常トレースと追加遅延トレースは、入れ子法でそれぞれ約20万メッセージを処理した。ロードバランサによる選択を含むため、少数の抽象パスから多数の具体的パターンが生じ、図11は頻度順に展開された密な出力になる。著者らは、実用的な表示器なら同型グラフ、近い回数、近い遅延のパターンをクラスタ化すべきだと指摘している。 WS2を含む同一パターンを通常と追加遅延で比較すると、図12のWS2からAP1への辺に約200ミリ秒の増分が現れる。値は追加した公称値よりわずかに小さく推定されたが、遅延の責任を正しいノード文脈へ帰属できた。畳み込み法を量子`mu=0.1`で実行した図13でも、RPCの呼び出しと戻りを別々に扱うため長い線形パスが出る一方、追加遅延構成ではWS2付近の遅延が通常構成の約0.02秒から約0.21秒へ増加している。 ![図10〜図13に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-08-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-09-crop.png]] ### PetStore 入れ子法は、通常構成で図14の頻繁なパターンを見つけ、一定遅延構成では図15の同じパターンに`/mylist.jsp`付近の増分を示した。図14のパターン全体は総遅延5.591秒、125インスタンスであり、図15では総遅延22秒、224インスタンスとなる。`/mylist.jsp`の遅延は親ノードとパターン全体の合計にも伝播して見える。図15で観測された増分は公称50ミリ秒より少し大きく見えるが、著者らはLinuxの10ミリ秒時計粒度の影響かもしれないとしている。畳み込み法も類似の結果を返した。 ![図14・図15に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-10-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-12-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-14-crop.png]] ### Receivedヘッダー メールトレースを量子30秒で解析すると、報告された遅延はすべて0秒、すなわち実遅延0〜29秒を同じ量子にまとめた。量子を5秒に下げると、0秒の主ピークに加えて10秒または15秒の副ピークが現れた。原トレースを照合した結果、副ピークは実際の転送遅延だった。図16はこの試行の頻出経路を示すが、ノード名は任意の整数である。 ![図16に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-11-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-13-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-15-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-16-crop.png]] ### 精度評価の定義とパターン順位 真値を、実際にトレース中で実行された因果パスとし、推定パスとの差を偽陰性または偽陽性として数えた。評価単位は、(1) パスパターン、(2) パスインスタンス、(3) メッセージの3種類である。実用上の主目標は、低頻度の誤ったパターンをすべて除くことではなく、頻出パターンを頻度順に並べ、上位N件を残しても真の上位N件を落とさないことである。 図17の入れ子法評価は、`maketrace`による多層トレース202,498メッセージ、平均並列性42で行った。上位N件からの真パターンの欠落率は多くの場合`1/N`で抑えられ、2%の回数差を許容すると近接タイの影響を無視できた。6%の許容では、ほぼすべての偽陰性が消えた。順位27、28付近の真の偽陽性は高いNで真陽性を押し出した。畳み込み法も上位Nパターンを概ね見つけ、主な誤りはタイであった。正しく推定されたパターンについては、パス内部の遅延値は正しい値から数パーセント以内だった。 ### 病的パターンと並列性 図18では、入れ子法を難しくする4種類の病的パターンを試した。`Children-parallel`はBがCを並列に2回呼ぶケースで、3つの子ペナルティをすべて破る通常最悪例だが、遅延偏差が小さい、または並列性が高いと良いケースに変わる。`Children-0/2`は一方のパターンでBがCを直列に2回呼び、他方ではCを呼ばない。`Children-d/cc`は一方でCを2回直列に、他方でDを1回呼び、子スコアボードが無いと同じパターンへ割り当てられない。`Penalty-breaker`は同じ子を複数回呼ぶパスと呼ばないパスを含み、長い2パスの遅延が同じため3つのペナルティのトレードオフを露呈する。 図19では、並列活動が増えるほど誤ったパスインスタンスが増え、真のパスが上位Nから押し出される傾向が見られた。全体として精度は中程度に悪化し、多層ケースで影響がやや強かった。ただし`Children-parallel`は並列性の増加で改善する場合があり、子呼び出しが並列であることを推定する機会が増えたためと解釈されている。図20では、ノード遅延の標準偏差を増やすと一般に精度が悪化し、`Children-parallel`と`Children-d/cc`が特に影響を受けた。 ![図17〜図20に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-17-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-19-crop.png]] ### メッセージ欠落と時計ずれ 受動パケット収集の欠落を模擬するため、`maketrace`にピーク捕捉レートと有限キューを持たせ、キューから溢れたパケットをバースト状に捨てた。キュー長を64パケットに固定し、欠落率0を得る捕捉レートから徐々に下げたところ、必要な捕捉レートは毎秒115〜605パケットの範囲だった。図21では、欠落率約1%未満なら性能への影響がなく、約1〜10%では低下するものの許容でき、10%を超えると結果が悪化した。したがって受動トレースは完全でなくてもよいが、ほとんどのパケットを捕捉できる必要がある。 時計ずれには、比較時の許容窓と、スコアボードのピークを広げる平滑化を用いた。図22はWS2の時計を0〜60ミリ秒速くした多層トレースを、30ミリ秒の固定許容窓で評価したものだ。許容窓だけを有効にすると精度がかえって下がり、許容窓と平滑化を併用した場合が、妥当なずれの範囲で最も良かった。WS2の時計が同じ量だけ遅い場合も別曲線で評価した。入れ子法は、ずれが許容窓の推定値と実遅延の合計より小さいときは偽陰性が少なく、それを超えると急速に悪化した。 ![図21・図22に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-18-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-20-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-21-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-22-crop.png]] ### 畳み込み法の精度 Receivedヘッダートレースで量子を5秒から720秒まで変え、メールメッセージから直接抽出した真値グラフと比較した。全量子で偽陽性率は21〜29%で、量子への依存は小さかったが、360秒以上では最悪の結果になった。100メッセージ未満のパスを除くと、720秒を除き偽陽性率は0%になった。大きな量子は非ゼロ遅延を見つける用途には役立たない。一方、頻出する実パスについては、どの量子でも偽陰性率0だった。 ![図16・図21〜図22に対応する原本ページ] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/fig-23-crop.png]] ![[wiki/sources/_attachments/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes/table-01-crop.png]] ### 実行コスト 入れ子法は1.7GHz Pentium 4、Linux 2.4.20で、畳み込み法は667MHz AlphaServer、Tru64 UNIX V5.1で測定した。いずれも完全には最適化されていない。表1の入れ子法では、通常の多層トレース202,520メッセージを13.8MB、2.27 CPU秒で処理し、2,026,658メッセージの長い多層トレースでも136.8MB、23.97 CPU秒だった。平均並列性45.057の高並列トレース775,254メッセージでは132.1MB、233.61 CPU秒となり、並列性がコストを大きく押し上げた。 PetStoreの2,000秒トレースでは、通常構成252,024メッセージを19.8MB、3.34 CPU秒、一定遅延構成234,036メッセージを18.4MB、2.92 CPU秒で処理した。全長の1,345,538メッセージと1,288,223メッセージでは、それぞれ97.1MB・17.12 CPU秒、93.2MB・16.41 CPU秒だった。これに対して畳み込み法は、多層通常トレース202,520メッセージで0.2MB、6,684 CPU秒、多層追加遅延トレースで0.2MB、6,709 CPU秒、PetStore通常で26MB、12,780 CPU秒、一定遅延で25MB、6,301 CPU秒を要した。 畳み込み法のメールトレースでは、量子5秒で131MB・2,106 CPU秒、量子30秒で36MB・338 CPU秒だった。図23の実測値は、トレース期間を量子で割った`S`に対する`S log S`曲線に沿う。現在の実装では、求める時間精度に対してトレース期間が約100,000倍を超えると実行時間が実用上困難になる。 ## 考察 本方式の中心的な利点は、既存のアプリケーション、ミドルウェア、メッセージ形式を変えず、ベンダーをまたいだシステム全体の性能問題を、因果パスというユーザー要求に近い単位で調べられる点である。入れ子法はRPCの構造を使ってノード内部の遅延を階層的に帰属し、畳み込み法は形式を限定しないため、同一の抽象トレースから異なる観点を得られる。トレース取得と推論をオフラインに分離したことも、デバッグ時だけ計測コストを負担する運用に適している。 一方、評価は主に真値を管理できる合成・計装トレースであり、著者らが望む純粋な受動パケットトレースを用いた実験結果ではない。大規模な実運用Webアプリケーションのトレースは、プライバシー、専有データ、安定性の問題から入手できなかった。受動収集では、メッセージ境界、ノード粒度、呼び出し識別子、重複パケット、時計ずれを扱う追加処理が必要である。したがって、ブラックボックスという適用範囲の広さと、限られた観測情報からの推定誤差の間にトレードオフがある。 ## 強み / 弱点・課題 ### 強み - アプリケーション固有の計装やメッセージ意味を必要としない受動観測を目標にしたこと。 - RPCに適した入れ子法と、自由形式メッセージに適した畳み込み法という相補的な2方式を示したこと。 - パターンの頻度・総遅延だけでなく、特定パターン内のノード走査遅延を分離したこと。 - 合成トレース、PetStore、メールヘッダーで、追加遅延、遅延分散、並列性、欠落、時計ずれ、計算コストを個別に検証したこと。 ### 弱点・課題 - 入れ子法はRPCの呼び出し/戻り構造、呼び出し識別子、適切な対応付けに依存し、転送・非対称応答・遅延書き戻しには未対応である。 - 畳み込み法はまれなイベントや高分散遅延を扱いにくく、RPCでは部分パスや派生パスを過剰に生成する。 - 高い並列性、遅延変動、10%を超えるメッセージ欠落、大きな時計ずれで精度が低下する。少数の誤った低頻度パターンを剪定する際、近接タイや真の高順位パターンの欠落が生じうる。 - 実験に使ったトレースは純粋なブラックボックス受動収集ではなく、現実の大規模アプリケーションにおけるスケールとデータ取得コストは十分に検証されていない。 - 今後の課題として、低頻度だが高遅延の原因、ノード間ロック保持者の特定、時間窓ごとのパス集約、類似パスの統合、より有用な可視化が挙げられている。時間窓化は、短時間だけ頻出するパターンを全期間の低頻度パターンに埋もれさせず、メモリ使用量を抑えて数百万メッセージ超のトレースを扱う狙いを持つ。 ## 出典 - 原本参照（図表番号の原表記）: Figure 1, Figure 2, Figure 3, Figure 4, Figure 5, Figure 6, Figure 7, Figure 8, Figure 9, Figure 10, Figure 11, Figure 12, Figure 13, Figure 14, Figure 15, Figure 16, Figure 17, Figure 18, Figure 19, Figure 20, Figure 21, Figure 22, Figure 23, Table 1 - [[.raw/papers/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes.pdf]] - [[.raw/papers/Performance-Debugging-for-Distributed-Systems-of-Black-Boxes.txt]]