分散システム 7章「フォールトトレラント性」
部分的な障害の発生は単体システムでは起こらない分散システムの問題である
フォールトトレラント性の導入
基本概念
高信頼性とは：
- 可用性 (availability)・・・ある瞬間に正常に稼働している確率
- 信頼性 (reliability)・・・障害を起こすことなくジョブが走り続けられる確率
- 安全性 (safety)
- 保守性 (maintainability)
1時間に1ミリ秒ダウンするシステムは可用性は高いが信頼性は低い。1年に2週間メンテナンスするシステムは前の例より可用性は低いが信頼性は高い。
障害の種類：
- 過渡障害 (transient fault)・・・１度だけ起こるが消滅する
- 間欠障害 (intermittent fault)・・・一時的に障害が現れることが繰り返す
- 永久障害 (permanent fault)
障害モデル
冗長性による障害の隠蔽
冗長性の種類：
- 情報的冗長性・・・誤り訂正符号など
- 時間的冗長性・・・リトライ
- 物理的冗長性・・・余分な装置の付加
三重モジュール (TMR; Triple Modular Redundacy) による冗長性・・・電子回路を 3 重化しゲートの直後に毎回多数決を取る。
プロセスのレジリエンス
レジリエンス＝いくつかのプロセスが故障した場合に、システムの残りの部分に大きなダメージを与えないようにするための技術
設計問題
プロセスグループ・・・同じ役割を担う複数のプロセスを作っておく
- 平坦なグループ・・・全プロセスの役割が同じ
- 階層的なグループ・・・調整プロセスと実行プロセス
障害隠蔽とレプリケーション
Kフォールトトレラント性・・・K個のコンポーネントが故障しても動作する
- 停止するだけなら、K+1個あれば十分
- ビザンチン障害を保つ場合、最低でも2K+1個必要
障害システムにおける同意
- 2 つの軍隊問題・・・5000の軍隊を持つ赤軍が谷に野営。谷を見下ろす位置に3000+3000で2つの青軍が野営。赤軍に勝てるか？→障害のないプロセスしか考えないとしても信頼性のない通信を仮定すると、2つのプロセス間で合意形成はできない。
- ビザンチン将軍問題・・・通信は完全だがプロセスは完全でない場合。mプロセスが裏切りに対して2m+1の正しく動作するプロセスが存在すると正しく動作できるアルゴリズム。
TODO：6章（レプリケーション）を読む
高信頼クライアント・サーバ間通信
TODO: 障害がある場合の遠隔手続き呼び出し
高信頼グループ間通信
- 高信頼マルチキャストの基本手法・・・いくつかの仮定を踏まえた簡単なシステム：受信したらACKを送り、喪失に気づいたら再要求をする
- アトミックマルチキャスト・・・全プロセスに送信されるか、全く送信されないかのどちらか
- 仮想同期 (virtually synchronous)・・・アトミックマルチキャストであって、メッセージが送信されないのは送信者がクラッシュした場合のみ
TODO: 高信頼マルチキャストにおけるスケーラビリティ
分散コミット
分散コミット・・・あるオペレーションはグループ内の全てのメンバによって行われるか全く行われないかのいずれか（アトミックマルチキャストは分散コミットの１例）
1相コミット (one-phase commit) ・・・コーディネーターが実行するかどうかを通知する。参加者の1つが行うことができなくなった場合に、コーディネータに伝えることができなくなって困る。
2相コミット
いくつかのケースでブロッキングしてしまう問題がある。解決策の1つは3相コミットである。
回復
- 後向きエラー回復・・・エラー状態から以前の正しい状態（チェックポイント）へシステムを巻き戻す。
- 前向きエラー回復・・・実行を継続できる新しい状態に戦意させる。発生する可能性のあるエラーを事前に知っておく必要がある。
チェックポイントづくり
- 回復ライン (recovery line) ・・・各プロセスのチェックポイントの組み合わせであって一貫性があるもの
- 独立チェックポイントづくり・・独立にローカルな状態を記録し続ける
- 協調チェックポイントづくり
