障害モデル

障害モデルは、証明や設計においてどのような異常が発生し得るかを規定する。「1つの障害に耐えられる」というプロトコルは、障害の種類、永続化の仮定、通信条件、障害ドメインと組み合わされて初めて意味を持つ。プロセスの終了、データディスクの喪失、片方向のパケット損失、ノードによるメッセージの偽造は、すべて異なる事象である。

ノードはどのように失敗し得るか

厳密な用法では、Fail-stop は他のノードが停止を確実に識別できるというより強い仮定を含み、crash-stop と同義として常に扱えるわけではない。非同期ネットワークでは、停止したプロセスを極めて遅いプロセスと区別できない場合がある。

Crash-stop の純粋なモデルでは、ノードが回復した後に何を保存するかについて言及しないことがあるが、これは実際のサービスが永続性を必要としないことを意味しない。停電後の再起動で確認済みデータを保持する必要がある製品は、追加のストレージと復旧要件を提示している。

Crash-recovery：コミットメントの忘却自体がプロトコルエラー

Raft ノードが再起動後、自身の任期で誰に投票したかを忘れると、再度投票してしまう可能性がある。Paxos acceptor が既に発行した Promise を忘れると、拒否することを約束した古い提案を受け入れてしまう可能性がある。したがって、永続化はユーザーデータだけでなく、将来の動作を制約するプロトコルの履歴も保存する必要がある。

また、「OSキャッシュへのデータ書き込み」と「障害後の永続化要件を満たすこと」を区別する必要がある。ディスク、コントローラ、ファイルシステムの実際の保証は、障害モデルの一部である。古いノードIDと空のデータディレクトリを持つ新しいマシンを無条件で元のノードの正常な回復として扱うことはできない。

1回の障害で、なぜ2人の候補者が過半数を獲得できるのか

3人の投票者 A、B、C がおり、ログはどちらも最新であると考える。任期 7 で A が自身に1票を投じ、B が A に賛成を返信したため、A は A+B の2票を獲得する。B の投票がメモリにのみ記録され、返信後かつ永続化前に障害が発生した場合、回復時に B は既に A に投票したことを忘れる可能性がある。その後、C が同じ任期で自身に1票を投じ、B が C に賛成すると、A+B と B+C の2つの選挙過半数が存在することになる。

2つの過半数は依然として交差するが、問題は交差点である B が、自身の将来の動作を制約する状態を保持しなかったことにある。したがって、「過半数は必ず交差する」という命題は、「交差するメンバーが投票ルールを違反しないこと」と組み合わされて初めて、完全な安全性の推論となる。

以下では、永続状態を不変のタプルとして簡略化する。durable=False は意図的に誤った早期返信をシミュレートしており、再起動は永続タプルからのみ復旧する。永続化の順序に焦点を当てるため、すべてのリクエストはログの新規性による資格チェックを通ると仮定し、コードは完全な RequestVote を実装しない。

class Voter:
    def __init__(self):
        self.stable = (0, None)
        self.reboot()

    def reboot(self):
        self.term, self.voted_for = self.stable

    def request(self, term, candidate, durable=True):
        if term < self.term:
            return False
        if term > self.term:
            self.term, self.voted_for = term, None
        if self.voted_for not in (None, candidate):
            return False
        self.voted_for = candidate
        if durable:
            self.stable = (self.term, self.voted_for)
        return True

broken = Voter()
assert broken.request(7, "A", durable=False)  # A はすでにこの票を過半数に含めた
broken.reboot()
assert broken.request(7, "C")                # B は誤って別の候補者に投票した

safe = Voter()
assert safe.request(7, "A")
safe.reboot()
assert not safe.request(7, "C")
assert safe.request(7, "A")                  # 重複リクエストでも同じ票を返信可能
assert safe.request(8, "C")                  # 新しい任期では再選択可能
safe.reboot()
assert not safe.request(7, "A")              # 古い任期は依然として拒否される

実際の実装では、これらの状態に依存する応答を送信する前に、プロトコルが要求する永続的なストレージの更新を完了させる必要がある。永続化は完了したが応答が失われた場合、リトライは古い決定を見ることになる。応答が既に送信されたが決定が失われることを許容すると、他のノードは復旧後に成立しなくなったコミットメントに基づいて行動を続ける可能性がある。これらの2つの障害位置における安全性の意味は異なる。Raft Figure 2：応答前に永続状態を更新

タプルの代入は復旧の境界を表現するためのものであり、ファイルシステムの fsync、原子性書き込み、または停電動作を検証するものではない。実際の障害テストでは、プロセス、カーネル、またはマシン全体がどの時点で障害を起こしたか、およびどのストレージ層がデータを保持しているかを明確にする必要がある。

ビザンチン障害：認証は誠実さを意味しない

認証されたノードであっても、A には値 X を、B には値 Y を主張する可能性がある。署名はメッセージの送信者を証明するが、送信者がプロトコルを自動的に遵守させるものではない。実装ミス、メモリ破損、または侵入により、ノードの動作が単純な停止モデルを超えてしまう可能性がある。

古典的な PBFT は、その非同期安全性と最終的な進行に必要な条件下で、f 個のビザンチン障害に耐えるために少なくとも 3f+1 個のレプリカを使用する。直感的には、2f+1 のクォーラム2つは、3f+1 個のノードの中で少なくとも f+1 個で交差し、その中に少なくとも1つの誠実なノードが含まれる。しかし、安全性は誠実なノードがプロトコルの投票およびロックルールを遵守することに依存する。

これは、同期、認証、信頼できるハードウェアなどのモデルすべてにおける統一されたノード数の下限ではない。2f+1 と 3f+1 を比較する際には、仮定を明確にする必要がある。非ビザンチン多数派コンセンサスでは、交差するノードがプロトコルを遵守すると仮定されるのに対し、ビザンチンモデルでは、交差部分が嘘をつくノードだけで構成されるのを防ぐ必要がある。

1つのノードとの交差が、なぜビザンチンモデルでは不十分なのか

3ノード A、B、C のうち、2つの2票集合 {A,B} と {A,C} の交差は A だけである。A が B には X の署名を、C には Y の署名を行える場合、両側は異なる2つの身份の署名を取得できる。認証はこの交差点を誠実なものにはしない。

古典的な 3f+1 構成は、より大きな交差によって最大 f 個の非誠実メンバーを相殺する。集合の大きさから導かれる：

|Q1 ∩ Q2| ≥ |Q1| + |Q2| − N = 2(2f+1) − (3f+1) = f+1。

交差点に f 個の悪いノードがすべて含まれていたとしても、少なくとも1つの誠実なメンバーが残る。以下の表は数式を展開し、「レプリカ数」、「証拠の閾値」、「障害予算」の口径が混同されていないかを確認しやすくしている。

from itertools import combinations

assert (set("AB") & set("AC")) - {"A"} == set()
for f in (1, 2, 3):
    n, q = 3 * f + 1, 2 * f + 1
    quorums = [set(c) for c in combinations(range(n), q)]
    smallest = min(len(a & b) for a in quorums for b in quorums)
    assert smallest == f + 1
    assert smallest - f >= 1

この列挙は集合条件のみをチェックするものであり、PBFT の実装や安全性証明ではない。完全なプロトコルでは、フェーズ、ビュー、シーケンス番号を区別し、誠実なノードがいつ投票し、いつロックし、リーダー交代時にどの証拠を継承するかを規定する必要がある。任意の 2f+1 個のメッセージを取得してコミットを宣言することはできない。異なるビューや異なるログ位置の署名を組み合わせても、同じ決定の有効な証拠は形成されない。PBFT のサービス保証とモデル

交差するノードは、すべての悪いノードを排除するのに十分か？

ここには2種類の交差数がある：あなたが選択した2つの集合が実際に交差する数と、集合の大きさだけを知っている場合に最小保証される交差数である。プロトコルは後者の保証を必要とする。なぜなら、各ラウンドでどのノードが返信するかを事前に指定できないからである。以下では N=7 を固定する。両側でそれぞれ5つのノードを選択する場合、最小交差は3であり、最大2つの非誠実メンバーを差し引いても、少なくとも1つの誠実なメンバーが残る。

$$h_{\min }=\max (0,|Q_1|+|Q_2|-N-f)$$

ネットワーク分断：方向性と規模は2つの次元

分断により、ノードは実行を継続できるが、必要なメッセージを交換できなくなる。対称的な分断は両方向に影響を与えるものを指し、非対称的な分断は一方の方向は通るがもう一方は通らないものを指す。これは「均等分割」や「1つのノードの孤立」によって定義されるものではない。

固定されたメンバー集合において、互いに素な2つの分断がどちらも厳密な過半数を含むことはあり得ない。3+2 の分断において、過半数側のノードがすぐに健全であるとは限らない。再選挙が必要であったり、低速ディスクや過負荷の影響を受けたりする可能性がある。2+2+1 に分断された場合、どの側にも過半数はない。

ブレインシュラウド（脳分裂）は、本来唯一であるべきサービスの権威に複数の実際の書き込み者が現れることを指す。合法なマルチマスターシステムは並行書き込みを許可し、競合処理を定義しており、複数の書き込み者が存在するからといってプロトコルの失敗と見なすべきではない。シングルマスターシステムでは、クォーラム、任期、または外部フェンシングを通じて、期限切れの書き込み者が効果を引き続き引き起こすのを阻止する必要がある。

時間モデル：どのような条件下で進行が保証されるか

同期モデルでは、関連する処理と通信に既知の上限が存在すると仮定する。非同期モデルではそのような速度の上限は提供されない。部分的同期モデルでは、何らかの最終的な安定条件下で、十分な時間的制約を獲得できることを許容する。これらはプロトコルの推論における仮定であり、「データセンター内ネットワーク」を同期、「公開ネットワーク」を非同期と呼ぶだけの単純なものではない。

FLP は、1つのプロセスの障害を許容する完全な非同期モデルにおいて、決定論的なコンセンサスがすべての許容される実行で終了することを保証できないことを示している。これは、コンセンサスが安全性を実現できないと言っているわけでも、Raft や Paxos が実際の安定したネットワークで動作できないと言っているわけでもない。エンジニアリングプロトコルは通常、安全性ルールを維持し、利用可能なクォーラム、最終的に安定した通信、ランダム化、または障害検出の仮定の下で進行を追求する。Gilbert と Lynch による不可能性結果の考察

タイムアウトは証拠であり、ノード死亡の証明ではない

応答がタイムアウト内に届かない場合、それは相手側の障害、ネットワークの混雑、ローカルのスケジューリング停止、または応答の損失によるものかもしれない。リクエストが相手側で既に有効になっている場合、タイムアウト後のリトライは重複実行を引き起こす可能性がある。障害検出、ビジネスリトライ、および引き継ぎの権限は、それぞれ個別に設計する必要がある。

タイムアウトが短すぎると、ロングテールレイテンシがリトライや選挙を増幅し、逆に負荷を高める。長すぎると、回復が遅れる。エンドツーエンドのレイテンシ分布、停止、許容される偽陽性、および回復目標に基づいて設定し、過負荷時にはリトライを制限する必要がある。P99 などの統計値は観測サンプルを反映したものであり、将来のレイテンシの硬い上限ではない。

φ-accrual などのプローバーは、ハートビート間隔を疑念の度合いに変換し、連続的な証拠を表現するのに役立つ。しかし、それでも完璧な障害判定を提供するものではない。具体的な推論については障害検出を参照。

関連する障害：レプリカ数は障害ドメインに取って代われない

3台のマシンが同じ電源、スイッチ、または同じソフトウェア欠陥を共有している場合、同時に失敗する可能性がある。レプリカを異なる障害ドメインに分散させることで、ある種の関連リスクを低減できるが、共通の制御平面、証明書の期限切れ、または誤ったリリースによる共通障害を排除することはできない。

バックアップとレプリケーションも異なる。誤った削除は、すべてのレプリカに正しくレプリケートされる可能性がある。履歴データの復旧を目的とする場合、バックアップ、保持、および復旧検証を別途定義する必要があり、「3つのレプリカがある」ということですべてのデータ保護要件を満たすものではない。

設計と検証のクイックリファレンス

1. 書き込み成功後に、どのデータを失うことを許容し、どのノードまたはストレージ障害に耐えるか？
2. 再起動時にどのプロトコル状態を保持し、ディスクを失ったノードはどのように再参加するか？
3. ネットワークは片方向の障害、遅延、重複、および分断復旧を考慮しているか？
4. クォーラムがない場合、どの操作を待機させ、拒否するか、または古い状態での読み取りを許可するか？
5. 古いプロセスが復旧した後、実際のリソースはどのようにして期限切れの権限を拒否するか？
6. 安全性チェックは異常な実行をカバーしているか、回復の進行には明確な前提条件があるか？

これらの質問は、障害注入シナリオに直接変換できる。応答前後の障害、永続化後の停電、旧リーダーの隔離後の復旧、遅延された重複リクエスト、およびメンバー変更中のノード再起動などである。期待される結果は、「最後にサービスが起動した」ことをチェックするだけでなく、不変条件と回復条件として記述されるべきである。

参考

• Perspectives on the CAP Theorem：安全性、活性、およびシステムの仮定。
• Raft 論文：非ビザンチンレプリケーションと復旧。
• Practical Byzantine Fault Tolerance：古典的な PBFT モデルとプロトコル。

Keywords: crash-stop, crash-recovery, fail-stop, Byzantine, partition, partial synchrony, FLP, safety, liveness