## Memo
D3S (Debugging Deployed Distributed Systems) は、実行中の分散システムに対して述語ベースのオンライン検査を実施するためのツール。開発者がシステムを停止させることなく、大規模な分散システムの不具合を検出できるように設計されている。システム全体を中断することなく、述語の定義や検査ポリシーを実行時に変更できる柔軟性と、複数のマシンに検査を分散させるスケーラビリティが主要な特徴。
## Memo with LLM
### 論文情報
**タイトル**: D3S: Debugging Deployed Distributed Systems
**著者**: Xuezheng Liu (Microsoft Research Asia), Zhenyu Guo (Microsoft Research Asia), Xi Wang (Tsinghua University), Feibo Chen (Fudan University), Xiaochen Lian (Shanghai Jiaotong University), Jian Tang (Microsoft Research Asia), Ming Wu (Microsoft Research Asia), M. Frans Kaashoek (MIT CSAIL), Zheng Zhang (Microsoft Research Asia)
**発表**: 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI '08)
**発表年**: 2008年4月
### 論文概要
本論文は、実行中の大規模分散システムにおいて、述語ベースの検査を透過的に実施するツールD3Sを提案している。開発者が順序実行型の単純な述語記述スタイルで分散特性を指定すると、D3Sはそれを分散並列方式で検査し、スケーラビリティと障害耐性を実現する。二項計装技術によってレガシーシステムに透過的に機能し、実行時に述語を変更できる特性により、5つの展開システムにおいて重大な正当性バグとパフォーマンスバグを検出することに成功している。
### 詳細解説
#### 問題設定
大規模分散システムのテストと本番環境でのデバッグは重大な課題である。システムの不具合は、機械やネットワークの障害を含む分散シーケンスイベント後にのみ現れることがあり、これらを再現・検出することは困難。実践的なアプローチでは、開発者がローカル状態を記録し、バッファリングして中央マシンに送信、その後スクリプトでグローバル一貫性スナップショットを構成して検査する必要がある。この手動アプローチには以下の課題がある：
- 各マシンのどの状態を記録するかを事前に予測する必要がある
- 過度な監視データ記録はシステムのパフォーマンスを低下させ、過少記録は不具合検出を見落とす
- 中央検査機がシステム全体のデータストリーム（例：500～1000 KB/s×マシン数）に追いつけない可能性がある
- マシン障害時に一貫性のあるスナップショットを近似する計画が必要
#### 提案手法
D3Sは述語ベースのオンライン検査框組を提供する。開発者は以下の流れで述語を記述・実行する：
**1. 述語の記述モデル**
述語は有限個の連続したグローバルスナップショットの集合に定義される関数として表現される。ウィンドウサイズ$n$の述語$P$は以下のように定義される：
$P(t_i) = F(\pi(t_{i-n+1}), \pi(t_{i-n+2}), \ldots, \pi(t_i))$
ここで、$\pi(t)$はタイムスタンプ$t$でのグローバル一貫性スナップショット、$F$はユーザー指定の関数。ほとんどの有用な特性は、ウィンドウサイズ1（現在のスナップショットのみ）で検査可能。
**2. 計算グラフモデル**
開発者は計算段階を有向非環グラフとして組織化する（Dryad風）。各頂点（vertex）は計算段階を表し、開発者は順序実行型C++関数を記述。状態は頂点間を流れるタプルとして表現される。例：ボックスウッドの分散ロックサービスの場合、V0は状態エクスポーザ（3つのフィールド：ClientID、LockID、LockMode）、V1はロック競合検査ロジック。
```cpp
class LockVerifier : public Vertex< V1 > {
virtual void Execute(const V0::Collection & snapshot) {
std::map< LockID, int > exclusive, shared;
while ( ! snapshot.eof() ) {
V0::Tuple t = snapshot.get_next();
if ( t.mode == EXCLUSIVE )
exclusive[t.lock]++;
else shared[t.lock]++;
}
// 競合チェック
for (Iterator it = exclusive.begin(); it != exclusive.end(); ++ it)
if ( it->value > 1 || (it->value == 1 && exist(shared, it->key) )
output.add( V1::Tuple(it->key) );
}
};
```
**3. スケーラブルな検査**
複数のマシンに検査を分散するため、開発者はマッピング関数を指定。この関数は出力タプルを仮想キー空間にマップし、D3Sが複数マシン間でキー空間を動的に分割。同一キーについての状態は同じ検査プロセスで処理される（MapReduceの「Map」フェーズに類似）。
**4. グローバルスナップショットの構成**
論理クロック（Lamportクロック）を使用してタプルに全順序を付与。各プロセスは論理クロック値をメッセージに添付し、受信プロセスは「最大値を採用」規則でクロックを更新。これにより「ハプンス・ビフォア」関係を保全し、一貫性のあるスナップショットを構成可能。
**5. ストリーム処理と増分検査**
連続したタイムスタンプ間で状態の変化が小さい場合、完全なスナップショットでなく差分（デルタ）のみを処理。ExecuteChangeメソッドを使用した増分評価により、不要な送信と処理を削減：
$\text{output}_{\text{new}} = \text{output}_{\text{last}} + \Delta \text{output}$
**6. 障害への対応**
- 検査マシン障害：マスターがフェイルオーバー検査プロセスを起動、同一入力で決定的に再実行
- チェック対象プロセス障害：検査マシンは障害プロセスを一貫性スナップショットから除外（タイムスタンプ$t$でのメンバシップ$M(t)$から削除）
- ハートビート機構：状態を長期間公開しないプロセスについて、定期的にタイムスタンプを送信し、検査機が待機時間を決定
#### 新規性
既存の述語検査・ログ分析手法との主要な相違点：
| 特性 | D3S | 既存手法 |
|------|------|--------|
| 述語表現 | グローバルスナップショット上の順序実行型関数 | 状態収集・順序付けをユーザーが実装 |
| スケーラビリティ | 複数マシンに検査を分散可能 | 中央検査機限定 |
| 透過性 | 二項計装によりレガシーシステム対応 | システム固有の実装が必要 |
| 実行時変更 | 述語を実行時に変更可能 | 通常は再起動が必要 |
| 障害耐性 | 検査システム自体の障害に対応 | ユーザーが対応を実装 |
比較対象：
- **P2 Monitor** (EuroSys 2006): オンライン監視だが、状態の収集・順序付けをユーザーが管理する必要がある
- **Replay-based** (WiDS Checker, NSDI 2007): 大規模システムの完全再生は計算コスト大
- **ログ分析**: 事後分析のため、稀な不具合の検出が困難
#### 実験設定
5つの展開システムで評価を実施：
1. **PacificA** (セミ構造化ストレージシステム)
- 67,263行のコード
- 述語: メンバシップ、グループ一貫性、レプリカ一貫性（計118行）
- テスト構成：8つのストレージノード、4つのクライアントマシン
- データ規模：元データ38GB、実行中に中間テーブル1TB超
2. **MPS** (Paxos実装)
- 6,993行のコード
- 述語：コンセンサス出力の一貫性、リーダー選出（計50行）
- 5ノードクラスタ構成
3. **Web検索エンジン**
- 26,036行のコード
- インデックスサーバーのロードバランス分析（述語81行）
- 250サーバーデプロイメント
4. **i3-Chord** (DHT実装)
- 7,640行のコード
- キー範囲カバレッジ、競合するキーホルダー検査（述語72行）
- 85ノード（7サーバー上）
5. **libtorrent** (BitTorrentクライアント)
- 36,117行のコード
- ピア集合、ダウンロード片、ピア貢献度ランキング（述語210行）
- 57ピア（8マシン上）、52MBファイルダウンロード
**評価指標**：
- 検査オーバーヘッド（CPU、I/O）
- 述語検査までの遅延
- 述語実装の複雑さ（行数）
- 検出されたバグのタイプと数
#### 実験結果
**検出されたバグ**
1. **PacificA: レプリカグループ再構成バグ**
- 複数プライマリ状態の検出
- 原因：MetaServer がクラッシュ後にディスクログをフラッシュせずにレスポンスを送信
- 修正：ログフラッシュを明示的に実行
- 診断時間：従来手法では数日、D3Sで数時間
2. **MPS: リーダー選出スタックバグ**
- 複数ノードが「Promoting」状態に長期間留まる
- 原因：不正なメッセージロス処理でFollowerノードがLearningノードに留まる
- レアケース：ノード障害と復旧後の特定のメッセージ順序
3. **Web検索エンジン: ロードバランス問題**
- 指標 $P_r = (\text{max} - \text{mean})/\text{mean}$
- $P_r > 1$（max > 2×mean）のクエリで著しくスロー
- 原因：単純ハッシュがサーバー間でロードを均等に分散しない
4. **i3-Chord: 可用性・一貫性のトレードオフ分析**
- 3前任者構成：キー範囲カバレッジが100%付近で振動
- 8前任者構成：100%超過なし（一貫性良好）だが、ローカルサンプリングで重複検出
- 振動原因：前任者喪失時にフィンガーテーブルで環を再参加
5. **libtorrent: 2つのバグ検出**
- **ピア集計バグ**: 重複IPアドレスがネイバーリストに存在（300超のネイバーが発生）
- **ピース選択バグ**: 決定的ピース選択で進捗が不均等
**パフォーマンスオーバーヘッド**
- 平均オーバーヘッド：2～3%
- 最大オーバーヘッド：8%（PacificA、高負荷時）
- ネットワーク追加消費：平均0.5% I/O、ピーク時1000 KB/s以下
- 単一述語開始時のスループット影響：不可視
**述語実装複雑度**
- 最大述語：210行（libtorrent）
- 平均述語：100～118行
- 開発者負荷：比較的小さい（順序実行型C++関数のため）
#### まとめと今後の展望
本論文の主な貢献：
1. グローバルスナップショット上の述語検査モデル
2. スケーラビリティと障害耐性を持つランタイム
3. 5つの実システムでの実証的評価
論文は、D3Sがシステム仕様が明確なコンポーネントレベルの述語検査に効果的であり、当時の述語検査手法では困難だった本番環境での動的デバッグを可能にしたことを示している。今後の課題としては、複数協調システム間の相互作用によるバグ検出（データセンター規模アプリケーション）の支援が挙げられている。
## Abstract
大規模分散システムのテストは困難な課題である。システムの不具合の一部は、機械やネットワークの障害が関係する分散シーケンスイベント後にのみ現れるからである。D3Sは、展開されたシステムの分散特性に関する述語を指定し、システムの実行中にこれらの述語を検査することを可能にするチェッカーである。D3Sが問題を発見した場合、問題に至った状態変化の列を生成し、開発者が根本原因をすぐに見つけることができるようにする。開発者は単純で順序実行的なプログラミングスタイルで述語を記述し、一方D3Sはこれらの述語を分散・並列的な方法で検査して、大規模システムへの検査のスケーラビリティと障害耐性を実現する。二項計装を使用することで、D3Sはレガシーシステムで透過的に機能し、実行時に検査する述語を変更できる。5つの展開システムでの評価は、D3Sが非自明な正当性バグとパフォーマンスバグを実行時に検出でき、パフォーマンスオーバーヘッドは少ない（8%未満）ことを示している。