障害検出器とハートビートの理論（φ Accrual）

障害検出器とは何を解く部品か

分散システムでは「あのノードは落ちたのか、それとも単に遅いだけか」を判定し続けなければ、リーダー選出もフェイルオーバーもレプリカ除外も始まりません。この判定を担う独立した部品が障害検出器（failure detector）です。FLP不可能性が示したとおり、完全非同期では「故障」と「遅延」を確実には区別できません。だから障害検出器は本質的に近似であり、その近似の質を理論として定式化したのが Chandra-Toueg（1996）の分類です。

検出器の出力は単純で、「現在疑っているノードの集合」です。これを各ノードがローカルに持ち、合意やメンバーシップの上位ロジックがその疑いリストを参照します。重要なのは、検出器が間違えてよい前提で設計される点です。間違いをゼロにはできないので、「どういう間違いを、いつまで許すか」を性質として規定します。

完全性と正確性という二軸

障害検出器の良し悪しは、**完全性（completeness）と正確性（accuracy）**という直交する二軸で測ります。

この2つは引っ張り合います。疑いを早く・多く出せば完全性は上がるが、生きたノードまで疑ってしまい正確性が下がる。逆に慎重にすれば正確性は上がるが、故障の検出が遅れて完全性が損なわれる。両方を同時に強く満たすことは非同期系では不可能で、ここに固定タイムアウトの根本的な悩みが現れます。

正確性はさらに強弱で段階化されます。「いかなる正常ノードも一度も疑わない」のが強正確性（strong accuracy）、「少なくとも1つの正常ノードは疑われない」のが弱正確性。そして現実的に重要なのが、頭に「◇（eventually、最終的に）」を付けた版です。

◇P と ◇W：使える検出器のクラス

二軸を組み合わせると検出器のクラスが定義できます。実務で名前を見るのは主に次の2つです。

理論上の白眉は ◇W が「合意を解ける最弱の障害検出器」 だと証明されたことです。つまり、これより弱い保証では非同期合意は解けず、◇W さえあれば Paxos 系の合意が前進できる。RaftやPaxosのタイムアウトは、実質この◇P／◇W相当の検出器を内蔵していると読み替えられます。

固定タイムアウトはなぜ脆いのか

最も素朴な検出器は、ハートビートが一定時間 T 来なければ故障とみなす固定タイムアウトです。これは ◇P を狙った実装ですが、閾値がただ一点しかないことが弱さの源です。

• T を短くすると、一時的な遅延スパイク（GCストール、ネットワーク輻輳、瞬間的な負荷）でも閾値を越え、生きたノードを疑う＝誤検知（正確性の低下）。
• T を長くすると、本当に落ちた場合の検出が遅れ、フェイルオーバーが間に合わない＝復旧遅延（完全性の体感低下）。

問題は、最適な T がそのときのネットワーク遅延分布に依存して動くことです。普段 RTT が 1ms の経路で T を 50ms に置いても、データセンター間で 30ms 揺れる経路では誤検知だらけになります。負荷の時間帯変動でも分布は動きます。静的な一点の閾値では、動く分布に追従できない——これが固定タイムアウトの構造的な脆さです。

φ Accrual：疑いを連続値で出す

この2つの限界——一点閾値と2値出力——を同時に解くのが、Hayashibara ら（2004）の φ Accrual障害検出器（accrual failure detector） です。発想の転換は2段階あります。

1. 検出と判定を分離する。 検出器は「故障か否か」を断じず、疑念度（suspicion level）を連続値 φ で出力する。実際にアクションを起こす閾値は、検出器ではなくアプリ側が用途ごとに決める。
2. 閾値を過去の到着実績から動的に導く。 ハートビートの到着間隔の履歴を統計分布として保持し、「最後のハートビートから今まで経った時間で、まだ次が来ていない」という事象の起こりにくさから φ を算出する。

φ の定義は、最後のハートビートからの経過時間を t としたとき、「正常なら t を過ぎても次が来ていないはずがない確率」を P_later(t) として、

φ(t) = -log10( P_later(t) )

です。P_later は「到着間隔がt以上になる確率」、すなわち到着間隔分布の上側確率（生存関数）です。直感はこうです——経過時間 t が普段の間隔の範囲に収まっていれば P_later は大きく（1に近く）、φ は0付近にとどまる。t が普段あり得ない長さに伸びるほど P_later は急速に小さくなり、その負の常用対数である φ は跳ね上がります。

分布の推定と動的追従

P_later をどう求めるかが実装の核です。代表的な実装（Cassandra や Akka が採用）は、直近の到着間隔をスライディングウィンドウに溜め、その標本平均 μ と標準偏差 σ を逐次計算し、到着間隔が正規分布に従うと仮定して上側確率を出します。経過時間 t に対し、

# 到着間隔 ~ Normal(μ, σ^2) と仮定
# P_later(t) = 1 - CDF_normal(t; μ, σ)  （= 上側確率）
# これを φ = -log10(P_later) に通す

ここが固定タイムアウトとの決定的な違いです。μ と σ が観測のたびに更新されるため、ネットワークの遅延分布が変わればφの基準も自動で動きます。普段ばらつき σ が大きい不安定な経路では、多少の遅れでは φ が上がりにくく(=慎重になり)、安定して σ が小さい経路では小さな遅れでも φ が敏感に反応する。分布の形そのものが閾値を運んでくれるので、人手で T を調整し直す必要がありません。

実務での使いどころ

φ Accrual の真価は、同じ検出器を複数の用途で共有しつつ、判定の慎重さだけを変えられる点にあります。たとえば「軽い予兆ログを出す」のは φ≥1、「リクエストのルーティングから外す」のは φ≥3、「クラスタから完全に除外する」のは φ≥8、というように、ひとつの連続シグナルから複数段の閾値を切り出せます。これは固定タイムアウトの2値出力では原理的に作れない柔軟性です。

ただし万能ではありません。分布を正規分布で近似する実装は、遅延がロングテール（テールレイテンシが支配的な経路）だと上側確率を過小評価し、φ が立ちにくくなることがあります。また起動直後はサンプルが少なく分布が不安定なので、最小標準偏差の下限を設けるなどの保護が要ります。検出が確率的に揺れる以上、判定後の挙動もリトライとバックオフで吸収する設計が前提になります。実際にどう揺れるかはカオスエンジニアリングで遅延注入して観測するのが確実です。

まとめ

• 障害検出器は「落ちたか遅いか」を近似で判定する部品。質は完全性（落ちたら必ず疑う）と正確性（生きたものを疑わない）の二軸で測る。
• 非同期系では両軸を確実には両立できず、最終的にだけ保証する**◇P／◇Wが現実解。◇Wは非同期合意を解ける最弱の検出器**で、Paxos/Raftのタイムアウトはこれに相当する。
• 固定タイムアウトは一点閾値かつ2値出力が弱点。短ければ誤検知、長ければ復旧遅延、遅延分布が動けば最適値も動き、静的な値では追従できない。
• φ Accrual障害検出器は到着間隔分布から φ = -log10(P_later) を連続出力する。**φ=1で誤検知率約10%、2で約1%、3で約0.1%**と、誤検知率を直接スケールで選べる。
• 分布の μ・σ を逐次更新するためネットワークの変化に自動追従し、ひとつのシグナルから用途別に複数段の閾値を切り出せる。ただしロングテール経路では過小評価に注意する。