分散システムの本質的な問題

定義

分散システムの問題は「確率的な障害」ではなく「構造的な不確実性」。単一マシンでは確定的だった前提（メッセージ到達、時刻の正確さ、プロセスの継続実行）が、分散環境では崩れる。

ネットワークの非信頼性

部分障害（Partial Failure）

単一マシン:
  計算が失敗するか成功するかのどちらか（確定的）

分散システム:
  リクエストを送った → 応答が来ない
  
  なぜ応答がないのか:
    - リクエストが届いていない
    - リクエストは届いたが、処理中にノードがクラッシュ
    - 処理は完了したが応答パケットが失われた
    - 応答は来ているが遅延している
  
  → タイムアウトだけでは区別できない

ネットワークフォールトは例外的ではない：
スイッチの再設定、NICのバグ、ファイアウォールルールの変更、パケットロス。中規模のデータセンターでも月に数十件のネットワーク障害が記録される。

タイムアウトの難しさ

タイムアウトが短い:
  → 遅延しているノードをクラッシュと誤検知
  → 不必要なフェイルオーバー
  
タイムアウトが長い:
  → 本当のクラッシュの検出が遅い
  → ユーザーは長時間待たされる

適切なタイムアウト値は実際の遅延分布から決める必要がある（経験則や p99 + safety margin が出発点）。

時刻の信頼性

2種類のクロック

クロック	用途	問題
時刻クロック（ToD Clock）	現在時刻（Unix timestamp）	NTPで調整されるため逆行することがある
単調クロック（Monotonic Clock）	経過時間の計測	マシンをまたいで比較できない

タイムスタンプを信頼できない理由

マシンAのクロック: 10:00:00.000
マシンBのクロック: 10:00:00.003（3ms進んでいる）

マシンAで書き込み（ts=000）
マシンBで書き込み（ts=003）

Last Write Wins でマシンBの値が「新しい」と判断される
→ 実際にはマシンAの書き込みが後だったかもしれない

NTPの精度は通常数十ms程度。金融取引のような精度が必要な場合はGPSクロックやPTP（IEEE 1588）が必要。

Googleの Spanner：TrueTime APIで時刻の不確かさを区間として表現。[earliest, latest] でコミット前に不確かさが解消されるまで待つ。

プロセスの停止（GC停止とその他）

JVMのGC（ガベージコレクション）:
  → 数分間すべてのスレッドを停止することがある（Stop-the-World GC）
  → プロセスは生きているが応答しない
  → 外から見るとクラッシュと区別できない

その他の停止原因:
  - コンテキストスイッチ（vmのhypervisorによる）
  - ページングによるディスクアクセス待ち
  - システムコールのブロック

このため「ノードが応答しないこと」と「ノードが死んでいること」は区別できない。

システムモデル：何を仮定するか

分散アルゴリズムを設計する際、フォールトについての仮定を明示する。

ネットワークモデル

モデル	仮定
同期ネットワーク	遅延に上限あり
部分同期ネットワーク	通常は上限あり、時々外れる
非同期ネットワーク	遅延の上限なし（最も現実的）

ノードフォールトモデル

モデル	動作
クラッシュ-ストップ	故障したら停止（最もシンプル）
クラッシュ-リカバリ	故障後に再起動しうる
ビザンチン	恣意的な誤動作（悪意ある行動を含む）

ほとんどのシステムはクラッシュ-リカバリモデルを想定して設計する。ビザンチン耐性は航空・宇宙・ブロックチェーンなど特殊な用途。

正しさと安全性

安全性（Safety）：「悪いことは起きない」= 状態が不正にならない
活性（Liveness）：「良いことがいつかは起きる」= 最終的に応答が来る

分散アルゴリズムは通常、安全性を常に保証し、活性はフォールトが解消された後に保証する（解消されない場合は保証できない）。

フォールトを前提とした設計原則

冪等性（Idempotency）：同じリクエストを複数回送っても結果が同じ
タイムアウトとリトライ：成功かどうか不明でもリトライできる操作設計
フェンシングトークン：古いリーダーが誤って書き込まないよう単調増加トークンで制御

Zookeeperからfencing token = 33 でロック取得
ストレージ: token 34以上しか受け付けない

古いリーダーがtoken 33で書き込み → 拒否
新しいリーダーがtoken 34で書き込み → 許可

出典・参考文献

Martin Kleppmann, Designing Data-Intensive Applications (2017) Chapter 8
Leslie Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System” (1978)
James Hamilton, “On Designing and Deploying Internet-Scale Services” (2007)

定義