故障検出

非同期ネットワークにおいて、ノードがメッセージに応答しない場合、それは本当にダウンしているのか、それとも単に遅延しているのか？φ-accrual 故障検出器は「はい/いいえ」ではなく、「ノードが死亡している確率」を出力し、上位プロトコルがビジネスの重要度に応じて判断を下すことを可能にします。SWIM はこの確率計算とゴシップによるメンバーシップ伝播を一体化しています。

故障検出が難しい理由

同期クロックがなく、メッセージ遅延の上限もない非同期ネットワークでは、「ノードのクラッシュ」と「ネットワークの遅延」を完全に区別することは不可能です。タイムアウトに基づく検出は誤検知を引き起こす可能性があります。故障検出器は、この不確実性の中で「最も合理的な」疑念を示さなければなりません。

単純なハートビート

毎 T 秒: ノード A がハートビートを送信 → ノード B
  もし B がタイムアウト（例: 3T）以内に受信しない場合 → A を dead とマーク

問題点: 固定されたタイムアウトは柔軟性に欠けます。ネットワークのジッター（揺らぎ）により誤検知が発生します。タイムアウト値を大きく設定すると、実際のクラッシュに対する検出遅延が増加します。

φ-accrual 故障検出器

alive/dead の二値ではなく、φ: 疑念レベルを出力します。これは、現在ノードが生きていると仮定する可能性がどれほど低いことを示します。上位アプリケーションは、「どの φ 値でフェイルオーバーをトリガーするか」を自由に決定できます。

原理

過去に受信したハートビットの到着間隔の分布（平均 μ、分散 σ²）を記録します。遅延して到着した場合（現在時刻 - 最後のハートビット到着時刻 = t）、φ を計算します：

φ = -log10(P(到着間隔 > t | 分布))

ハートビットが通常 100ms 以内に到着するが、今回は 500ms かかった場合 → 非常にありえない → φ は大きくなります。150ms だった場合 → ジッターの可能性あり → φ は小さくなります。

利点:

適応型: 固定された「3 回のタイムアウト」ではなく、実際のネットワーク条件に基づいて判断
設定可能: 異なるサービスで異なる φ 閾値を使用可能。低レイテンシが重要なサービスでは φ=5 でフェイルオーバー。バックグラウンドサービスでは φ=10

応用例: Akka (JVM アクターフレームワーク), Cassandra (PhiConvictAdaptive 故障検出器)。

SWIM (Scalable Weakly-consistent Infection-style Membership)

現在最も広く使用されている故障検出およびメンバーシップ発見プロトコル（Consul、Serf、Tailscale の基盤）。

プロトコル

各メンバーが独立して実行:

毎 T₁ 秒（例: 1s）:
  1. ランダムにメンバー P を選択
  2. P に PING を送信
  3. もし P が T₂（例: 500ms）以内に ACK で応答しない場合:
     → 間接 PING: ランダムに K 人のメンバー（例: 3人）を選択し、彼らに P への PING を依頼
     → もし K 人全員が ACK を受信 → P は生きている
     → もし K 人全員が ACK を受信しない → P は suspected（疑わしい）とされる

  4. ゴシップを開始:
     - もし P が suspected: ランダムに M 人のメンバーを選択し、ゴシップメッセージを送信: P is suspected
     - ゴシップ受信者: この情報を保存。もし自身が P への PING に成功した場合 → 疑念を反駁（alive メッセージを送信）

SWIM vs ハートビート

ハートビート: 1秒あたり O(N) のメッセージ（各メンバーが他の全メンバーに送信）
SWIM: 各期間ごとにメンバーあたり O(1) の ping + ゴシップ = 極めて低い帯域幅、数千ノードをサポート
SWIM の間接 PING は誤検知を大幅に削減: メンバー間の直接接続はネットワークの局所的な障害によりパケットを失う可能性があるが、複数の他のノードから PING できる場合 → デッドではない

タイムアウト戦略

TCP 接続タイムアウト、RPC デッドライン、ゴシップの疑念タイムアウト——これらはすべて同じ問題です。設計原則:

p99.9 レイテンシに基づいて設定⁠: タイムアウトは p99.9 レイテンシより大きく設定する必要があります。さもないと誤検知率が許容範囲を超えます。
timeout と deadline を区別⁠: timeout = ネットワーク/RPC の待機上限; deadline = 全体の操作の期限（複数回のリトライ後）
指数バックオフ + ジッター付きのリトライ⁠: サンダリングハーデ（雷鳴の群れ）現象を防ぐ → 待機中のすべてのクライアントが同時にリトライし、回復したばかりのサービスをダウンさせるのを防ぐ
タイムアウトの予算配分⁠: 全体のリクエストチェーン（A→B→C→D）の総タイムアウトを各コンポーネントに割り当て → 迅速な失敗により、全体チェーンがブロックされないようにする

参考文献

論文⁠: "The φ Accrual Failure Detector" (Hayashibara et al, 2004)
論文⁠: "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol" (Das et al, 2002)
Serf: serf.io (HashiCorp による SWIM 実装)

キーワード: ハートビート, φ-accrual, SWIM, 間接 PING, ゴシップ, 故障検出器, メンバーシッププロトコル