# 障害検出器 ## 定義 障害検出器(failure detector)は、分散システムにおいて障害が発生したプロセスやアクセス不能なプロセスを識別し、それらをアルゴリズムから除外することで、活性(liveness)を保証すると同時に安全性(safety)を維持する機能を果たすローカルサブシステムである。非同期の分散システム(タイミングの前提を一切置かないシステム)で障害を検出するのは極めて困難であり、これはプロセスがクラッシュしたのか、それとも実行速度が遅いだけで応答に長い時間がかかっているのかを区別できないためである。障害はリンクレベル(メッセージの喪失・遅延)またはプロセスレベル(クラッシュ・実行の遅さ)で発生し、遅れと障害を常に区別できるとは限らない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] p.201) 障害検出器の品質は 2 つの特性で評価される。 - **完全性(completeness)**: すべての障害のないメンバーが最終的にプロセスの障害を認識でき、アルゴリズムが実行を続行して最終的な結果に到達できるという特性。「いずれかのプロセスが障害を発生した場合、障害検出機能はその障害を必ず検出しなければならない」という活性の定義に対応する。 - **正確性(accuracy)**: プロセスの障害が正確に検出されたかどうかを示す特性。正常なプロセスに障害が発生していると誤って判断すること(偽陽性)や、既存の障害を検出できないこと(偽陰性)は正確性を損なう。「あるプロセスに dead のマークを付けた場合、そのプロセスは実際に停止していなければならない」という安全性の定義に対応する [LAMPORT77] [RAYNAL99] [FREILING11]。 完全性と正確性は調整可能なパラメータの関係にあり、効率性(障害検出の速さ)が高くなれば精度は低くなる可能性があり、精度が高くなれば通常、効率性は低くなる。精度と効率性を兼ね備えた障害検出機能を構築することはおそらく不可能であり、障害検出機能は偽陽性・偽陰性を生成することが許容される [CHANDRA96]。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] p.202) ## 代表的な実装アプローチ - **ping / ハートビート**: リモートプロセスへの定期的な問い合わせ(ping)、またはプロセス自身による定期的な生存通知(ハートビート)によって状態を維持する。精度が ping 頻度とタイムアウトの選択に依存し、他プロセスから見た可視性を捕捉できないという欠点を持つ(例: Akka のデッドライン障害検出機能)。 - **タイムアウトフリーな Heartbeat アルゴリズム [AGUILERA97]**: ハートビートのカウンタベクトルのみで障害を検出し、タイムアウトに依存しないため非同期システムの前提下でも動作する。全プロセス対がフェアパスで接続されていることを前提とする。 - **ハートビートのアウトソーシング(SWIM [GUPTA01])**: 直接応答がないプロセスについて、ランダムに選んだ複数の第三者プロセスに間接確認を依頼することで、判断の責任をグループ全体に分散する。 - **Phi-Accrual Failure Detector [HAYASHIBARA04]**: 障害を二者択一でなく連続した尺度として扱い、ハートビート到着間隔の分布から疑わしさのレベル φ を確率的に計算する。モニタリング・解釈・アクションの 3 サブシステムからなる。Cassandra や Akka で採用されている。 - **ゴシップ方式の障害検出サービス [VANRENESSE98]**: 各メンバーが他メンバーのハートビートカウンタとタイムスタンプのリストを保持し、ランダムな近くのノードへ定期的に配信・マージすることで単一ノードのビュー依存を避ける。詳細は [[ゴシッププロトコル]] を参照。 - **FUSE [DUNAGAN04]**: 個々のプロセス障害をグループ全体の障害へ転換して伝播させる。障害を検出するのではなく、通信できないことそのものを伝播の手段とする「問題記述の反転」的アプローチ。 (Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] §9.1〜§9.4) ## 合意アルゴリズムとの関係 障害検出機能は多くの合意アルゴリズムおよびアトミックブロードキャストアルゴリズムにとって必要不可欠な要素である。非同期システムでは FLP の不可能性によりいかなるプロトコルも合意を保証できないが、Chandra と Toueg の研究 [CHANDRA96] は、数えきれないほどの誤りを犯す障害検出機能であっても合意問題の解決に利用できることを示した。障害検出機能はモデルを増強し、精度と完全性の間でトレードオフを行うことによって合意問題の解決を可能にする。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] §9.5) ## 横断的知見 - 現時点では [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] が唯一のソースであり、横断的な突き合わせはまだ蓄積できていない。[[ゴシッププロトコル]] 側では、本章が記述する「ハートビートのアウトソーシング」が [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]] の間接プロービング(ping-req)機構の平易な言い換えであることを記録済みであり、詳細な比較は [[ゴシッププロトコル]] の横断的知見を参照。 - **合意アルゴリズムは障害検出器のハートビート実装を、「誰が疑わしいか」ではなく「リーダーが健全か」という一点に単純化して再利用する**: 本ページが記録する「本書9章はリーダー選出(次章)・合意(後続章)がどの実装アプローチを暗黙の前提として採用しているか、章を追って確認する必要がある」という未解決の問いに対し、[[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]]は具体的な答えを与える。ZAB(§14.2.2)はリーダー・フォロワーの双方がハートビートに頼って互いの生存を判断し、リーダーがフォロワーのクォーラムからハートビートを受け取れなければ自らリーダーの座を退いて選出を再開する。Raft(§14.4.2)はリーダーがフォロワーへ定期的にハートビートを送信して任期を維持し、`electionTimeout` の間にハートビートが届かなければフォロワーが選出を開始する。いずれも本ページが分類する「ping/ハートビート」アプローチの直接の応用だが、対象が任意の他プロセスではなく「単一のリーダー」に絞られているため、完全性・正確性のトレードオフが「クラスタ全体の誰が生きているか」から「今のリーダーはまだ生きているか」という一段狭い問題に単純化されている。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.2.2, §14.4.2) - **PBFT のビュー変更は、ハートビート型の障害検出とは異なり「疑いの表明」自体がプロトコルメッセージとして合意対象になる**: 本ページが分類してきたping/ハートビート・SWIM・Phi-Accrual・ゴシップ・FUSEはいずれも「障害検出器がローカルに判定し、その判定結果を上位のアルゴリズムが利用する」という構図を共有するが、[[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.5.1が示すPBFTのビュー変更は、プライマリの障害を検出したノードが単独で判定を下すのではなく、ビュー変更通知をブロードキャストし$2f$件の一致するビュー変更イベントを新プライマリが収集して初めて新ビューへ移行する。つまりPBFTでは「障害検出」自体が(ビザンチン障害を許容するがゆえに)単一ノードの判定を信用できず、合意アルゴリズムのサブプロトコルとして扱われる。これは本概念が前提とする「障害検出器はローカルサブシステムである」という一般定義の限界がビザンチン環境で露呈する具体例であり、[[ビザンチン障害]]ページが記録するPBFTの閾値設計と表裏一体である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] §14.5.1, [[ビザンチン障害]]) ## 未解決の問い - 完全性/正確性のトレードオフは、[[部分故障]] が扱う非決定性という理論的性質からどの程度必然的に導かれるか。両者を接続する形式的な議論は本概念にまだ蓄積されていない。 - [[グレイ障害]] が扱う「Observer/App の観測非対称性」は、本概念の偽陽性/偽陰性のトレードオフとどう関係するか。Phi-Accrual Failure Detector の連続的な疑わしさの尺度 φ は、二値判定(alive/dead)ではなく劣化の度合いを扱う点で、グレイ障害的な状態表現に近いようにも見えるが、この対応は未検証。 - SWIM の Suspicion サブプロトコル(alive → suspected → faulty の離散状態遷移)と Phi-Accrual の連続尺度 φ は、どちらも「即座に 2 値判定しない」という同じ問題意識への異なる解だが、両者の精度・検出速度のトレードオフを定量比較した文献はあるか([[ゴシッププロトコル]] の未解決の問いとも関連)。 - 本書 9 章はビザンチン障害の不在を明示的に前提とする。ビザンチン障害を許容する障害検出器の設計として14章はPBFTのビュー変更(単独ノードでなく$2f$件の一致するビュー変更イベントで判定する)を示したが、これがPing/ハートビート等の他アプローチと比べどこまで一般化できるかは未検証。 - 合意(14章)はZAB・Raftのハートビートベースリーダー障害検出という形で本概念の「ping/ハートビート」アプローチを採用していることを確認した。EPaxos・Flexible Paxos等、14章が扱う他のPaxos亜種がどの障害検出アプローチ(あるいは障害検出器を明示的に持たない設計)を前提としているかは未確認。レプリケーション(11章)についても同様に未確認。 ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 9 障害検出]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 14 合意]] - 概念: [[ゴシッププロトコル]] / [[部分故障]] / [[システムモデルと安全性・活性]] / [[分散コンセンサス]] / [[グレイ障害]] / [[ビザンチン障害]] - エンティティ: [[Apache Cassandra]] / [[Akka]] ## 出典 - Alex Petrov, *詳説 データベース*, オライリー・ジャパン, 2021, 9 章. - Alex Petrov, *詳説 データベース*, オライリー・ジャパン, 2021, 14章, §14.2.2/§14.4.2(ZAB・Raftのハートビートベース障害検出), §14.5.1(PBFTのビュー変更).