# Minimizing Faulty Executions of Distributed Systems > [!abstract] 概要 > 分散システムの障害実行のトラブルシューティングでは、開発者は通常まずバグを引き起こしたイベント(シグナル)と無関係なイベント(ノイズ)を手作業で分離する。本論文では、この最小化を自動的に実行するツール DEMi を提案する。DEMi を性質の大きく異なる 2 つの分散システム(Raft と Spark)の障害実行に適用したところ、最適実行の 1〜4.6 倍(中央値 1.6 倍)の規模をもつ最小化実行を生成することを確認した。 ## 論文情報 | 項目 | 内容 | |---|---| | タイトル | Minimizing Faulty Executions of Distributed Systems | | 著者 | [[Colin Scott]], [[Aurojit Panda]], Vjekoslav Brajkovic, [[George Necula]], [[Arvind Krishnamurthy]], [[Scott Shenker]] | | 所属 | UC Berkeley, ICSI, University of Washington | | 発表先 | NSDI 2016 (13th USENIX Symposium on Networked Systems Design and Implementation) | | 日付 | 2016年3月16〜18日, Santa Clara, CA | | URL | https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/scott | | 実装 | DEMi (Distributed Execution Minimizer), Scala 約 14,000 行 | ## 概要 分散システムのバグ調査において、ファジングや本番トレースから得られた障害実行には無関係なイベントが大量に含まれる。開発者はその中から障害に本当に必要なイベントだけを手動で抽出する作業から始めなければならない(開発者がデバッグに費やす時間は作業時間の 49% に及ぶとされる)。DEMi はこの最小化を自動化するツールである。 DEMi は Akka アクタフレームワーク上に実装され、AspectJ を用いてイベント配送の完全制御を実現する。ソースコードの解析を必要とせずに動作する点が重要な特徴であり、著者らの知る限り、コード解析なしにこの問題を解くツールは著者らの先行研究 [[Colin Scott]] ほか (SIGCOMM 2014) を除いて存在しない。 ## 問題設定 分散システムをプロセスの集合としてモデル化する。各プロセスは単一スレッドで状態遷移関数に従い決定論的に動作する。イベントは **外部イベント** と **内部イベント** の 2 種類に分かれる。 - **外部イベント**: プロセス起動、強制再起動(クラッシュ回復)、外部メッセージ送信の 3 種。テストオーケストレータが注入する入力。 - **内部イベント**: ネットワークバッファからメッセージを取り出してプロセスに配送する操作。 スケジュール τ は外部・内部の両イベントの有限列である。**最小因果列(MCS: Minimal Causal Sequence)** を、外部イベントの部分列 E' であって、E' を含むスケジュールが不変条件違反を再現し、かつ E' から任意の 1 イベントを除去するとそれ以上短いスケジュールでは再現できなくなるもの、と定義する。 ## 提案手法 ### DEMi のアーキテクチャ ![[_attachments/nsdi16-paper-scott/fig1-example-schedules.png]] **図1**: スケジュールの例。赤が外部メッセージ配送、緑が内部メッセージ配送。最初のサブシーケンスを探索する際、B メッセージが消えたとき、seq フィールドをマスクした原実行に近い初期スケジュールを選択する。 DEMi のスケジュール探索は以下の段階から成る。 1. **外部イベントの最小化(ExtMin)**: デルタデバッギング [Zeller & Hildebrandt 2002] を適用し、外部イベントの部分列を二分探索的に絞り込む。平均 O(log|E|) 回、最悪 O(|E|) 回のオラクル呼び出しで 1-最小部分列を求める。 2. **スケジュール空間の探索**: 各部分列について DPOR(動的部分順序簡約)を用いて非可換スケジュールを探索する。可換イベント(異なるノードに影響する独立なメッセージ配送)は happens-before 関係に基づいて一方のみ探索し、探索空間を削減する。 3. **スケジュール探索戦略 — STSSched と TFB**: - **STSSched**(先行研究 [70] からの継承): 各部分列につき唯一定義されるスケジュール、すなわち原実行でのメッセージフィンガープリントが一致するメッセージのみを同順で配送するスケジュールを最初に試みる。 - **TFB(Type Fingerprints with Backtracks)**: メッセージ型によるマッチング粗化を追加し、DPOR のバックトラックポイントを型一致の保留メッセージに優先的に向ける。これにより STSSched が停滞するケース(履歴依存のメッセージ内容、バッチング)を突破する。 4. **内部イベントの最小化**: 外部イベント最小化完了後、デルタデバッギングを内部イベントにも適用し、保留のまま配送しないメッセージを探索する。 5. **外部メッセージ内容の縮小**: 外部メッセージの構成要素(例: ブートストラップメッセージ内のプロセス ID リスト)を逐次除去し、違反を再現できる最小セットを求める。 ### 5 つの観察 | 観察 | 内容 | |---|---| | #1 原実行に近い探索 | 因果構造が原実行に近いスケジュールほど違反を再現しやすい | | #2 データ独立性 | 一部のメッセージ内容は制御フローに影響しない。フィンガープリント関数でマスクする | | #3 マッチング粗化 | メッセージ型のみで一致を判定することで、内容依存の停滞を回避する | | #4 バックトラック優先化 | 型は一致するが内容が異なる保留メッセージへのバックトラックを優先する | | #5 外部メッセージ内容の縮小 | テスト環境が生成する外部メッセージの内容を可能な限り小さくする | ### 非決定性の制御 非決定性はオラクル呼び出しの再現性を損なう。DEMi は以下の手段で対処する。 - Akka の API 呼び出し(タイマー API など)に AspectJ でフックし、イベント発火のタイミングを完全制御する。 - akka-raft のランダムタイマーには決定論的シードつき乱数生成器を提供する。 - Spark のハッシュマップは実行ごとに順序が変わるため、値をソートしてから選択するよう修正した。 - Spark の TaskRunner スレッドには開始・終了のインタポジションポイントを追加し、アトミックブロックとして扱う。 - 残存する非決定性には「各スケジュールを複数回リプレイする」ストップギャップを設ける。 ## 新規性 ### デルタデバッギングとの対比 Zeller らのデルタデバッギング [Zeller & Hildebrandt 2002] は逐次処理されるテスト入力を対象とする。DEMi はこれを拡張し、**外部イベント列**の最小化に適用する。さらに DPOR で内部イベントのスケジュールを探索する層を追加することで、並行プロセス間のメッセージ配送順序に起因する並行性バグを扱えるようにした。 先行研究 (STSSched, SIGCOMM 2014) は、各外部イベント部分列につき **1 つのスケジュールしか調べない**。TFB は型ベースマッチングとバックトラック優先化により **複数のスケジュールを体系的に探索**し、内容依存の停滞を解消した点が主要な新規貢献である。 ## 実験設定 ![[_attachments/nsdi16-paper-scott/table1-case-studies.png]] **表1**: ケーススタディ概要。E: は外部イベント数を示す。 - 対象システム: akka-raft(Scala 約 2,300 行、初期段階のソフトウェア)と Apache Spark(コアエンジン 3 万行超、広く本番利用) - バグ総数: 10 件(akka-raft 7 件 + Spark 3 件) - ファズテストで初期実行を生成(DEMi がランダムな外部イベント列を注入) - 最適値は著者らが DEMi に手動指示して対話的に構築した最小実行と比較 - 時間予算: 全ケースで 12 時間(43,200 秒) - 実行環境: 2.8GHz Westmere プロセッサ、メモリ 16GB ## 実験結果 ![[_attachments/nsdi16-paper-scott/fig2-minimization-pace.png]] **図2**: raft-58b の最小化ペース。初期に急激に改善し、その後は漸進的となる。 ### 最小化結果 | 指標 | 値 | |---|---| | 最適値に対する比率 | 1〜4.6 倍(中央値 1.6 倍) | | 先行手法(STSSched)に対する削減率 | 1〜16 倍小さい(中央値 4 倍) | - 10 ケース中 6 ケースで最適値の 2 倍以内に収まった。 - raft-58a が最も遠く最適値の 4.6 倍。時間予算を使い切ったため、より優れたスケジュール探索戦略があれば改善できると考察されている。 - 発散スケジュール(原実行で未観測の状態遷移を含む実行)が akka-raft の削減に不可欠であることを NoDiverge 列との比較で示した。 ### 実行時間 - raft-56、raft-58a、raft-42 を除く 7 ケースは TFB 完了まで 10 分以内。 - raft-58a は 43,345 秒(約 12 時間)を費やし 834,972 スケジュールを実行した。 ### 外部メッセージ内容の縮小 9 ノードのクラスタで raft-45 を対象に実験した。ブートストラップメッセージのプロセス ID を 9 個から 5 個に縮小でき、STSSched 後の実行サイズも削減された(表3参照)。 ### 計装オーバーヘッド 計装に必要なコード量(表4): | 項目 | akka-raft | Spark | |---|---|---| | メッセージフィンガープリント定義 | 59 行 | 56 行 | | 非決定性対処 | 2 行 | 約 250 行 | | 不変条件定義 | 331 行 | 151 行 | | テスト設定 | 328 行 | 445 行 | Akka API インタポジション(AspectJ 336 行)はアプリケーション非依存。非決定性対処のデバッグに著者らは約 1 人月を費やした。 ## 考察 - akka-raft のケーススタディから 2 つの知見を得た。(1) ファジングは初期段階のソフトウェアのバグ発見に非常に有効で、2 週間以内に発見・修正できた。(2) 最小化なしのデバッグは時間がかかり、最小化された実行を一手順ずつ追うことが最も効果的なデバッグプロセスであった。 - Spark ケーススタディでは、通信が疎な単純なジョブに対して STSSched が良好に機能した。より複雑なジョブ(中間キャッシュを使うものなど)では TFB が必要になると予測される。 - DEMi のスケジュール探索戦略は、分散システムが本質的に並行システムであることから、より広範なシステムに適用できると著者らは楽観視している。 ## 強み / 弱点・課題 ### 強み - ソースコード解析なしに動作し、ブラックボックス的に適用できる - デルタデバッギング + DPOR + スケジュール探索戦略の統合による体系的探索 - 発散スケジュール(原実行から逸脱した代替実行パス)の探索により、依存関係の多いバグも縮小可能 - 外部イベント列・内部イベント・メッセージ内容の 3 層を段階的に最小化する設計 ### 弱点・課題 - 現状は単一物理マシンに限定(スケール制限) - Akka フレームワーク依存(他システムへの適用には相当な計装コストが必要) - 主として安全性違反を対象。ライブネスやパフォーマンスバグは対象外 - 本番トレースの最小化は未対応(完全なイベント記録と部分順序が必要) - 非決定性の対処にシステム固有の手作業が要る(Spark では約 1 人月) - 外部イベントが互いに依存する場合(メッセージ除去により他のイベントが無効になるケース)は非対応 ## 関連 - [[分散実行最小化]] — 本論文の中心概念 - [[Colin Scott]] — 筆頭著者、先行研究 (SIGCOMM 2014) との連続性 - [[Aurojit Panda]] — 共著者 (UC Berkeley) - [[Arvind Krishnamurthy]] — 共著者 (University of Washington) - [[Scott Shenker]] — 共著者 (UC Berkeley / ICSI) - [[George Necula]] — 共著者 (UC Berkeley) ## 出典 - [[.raw/papers/nsdi16-paper-scott.pdf]] - [[.raw/papers/nsdi16-paper-scott.txt]]