耐故障処理 Fault Tolerance 「分散計算の基礎」　12章 発表者 : 高橋 慧

耐故障処理とは コンピュータでは様々なエラーが発生 これらのエラーを検知して プログラム自体のバグ 外的要因によるプロセスの中断・停止 ネットワークの障害 これらのエラーを検知して エラー処理を行い、終了する 修復して処理を継続する

発表の流れ プロセス単位での耐故障処理 並列システムでの耐故障処理 送信エラーを考慮したbroadcast 簡単なデモ Two Phase Commit Protocol Voting Protocol 送信エラーを考慮したbroadcast Atomic Broadcast

プロセス単位での耐故障処理 プロセスの予期しない終了への対処 問題点 ログによって復帰する バックアップのプロセスが処理を引き継ぐ 常に複数のプロセスが平行して処理を行う 問題点 復帰しても再びエラーになった時は? →ログを資料にデバッグ 何度も計算したとき、結果は一定なのか? →常に結果が同じになる処理のみを考える

簡単なデモ 一定間隔で値をファイルに記録 死んだらログを読んで処理継続 親プロセスと子プロセスが存在 子が死んだら親が子を立ち上げる 別プロセッサからpsの出力を監視 プロセスが死んだら、rshで立ち上げる

並列システムでの耐故障処理 各プロセッサでデータの同期が必要 →同時刻に読むデータは同一(atomic) Two Phase Commit readは自由・writeに許可が必要 全員の同意を得てwrite (commit) エラー処理を行い、処理中断 Voting read、writeとも許可が必要 半数以上の賛成が得られればwrite/readを許可 エラー時でも、残ったプロセッサで処理継続

同期の必要性 プロセッサ間でデータの同期が必要 (データの同期をatomicityと呼ぶ) メッセージ消失によりatomicityを失った例 X=1 X=2 xのatomicityが 保たれていない X=1 (X=1) X=2に変更 X=2に変更 変更の送信に失敗 X=1 X=2 X=2 変更を送信

Two Phase Commitの概要 前提 基本的なアイディア 親プロセスが1つある 通信路は信頼できない abortすると結果は反映されない 全プロセスが同意した場合のみcommit commit / abortは一意 → atomicityの維持

Two Phase Commitの操作 子プロセッサが親にcommitを要求 親は全ての子にcommit_requestを送信 (エラー時)abortを送信 (正常時) ログを取り、agreeを返信し、ブロック 親は子からの返信をある時間待って (一つでもagreeしない時) agreeしたプロセスにabortを送信 (全員がagreeした時) commitを送信し、commit操作 agreeを送信した子は、親からのメッセージによって (abortを受信)　 ログにより復帰し、ブロック解除 (commitを受信) 待機し、commitに必要な処理のみ行う 親はcommitが完了したら、completeを送信 子はcompeteを受信したら、ブロック解除

Two Phase Commitの例 (1) Commitが行われる例 commit request agree complete X=2に更新 Commit完了 受信を確認 Commit操作開始 X=2を送信 X=1 X=2 commit request agree complete commit X=2に更新 agree X=1 X=2 block解除 X=2に変更を要求 ログを取ってblock X=2に更新 X=1 X=2 ログを取ってblock block解除

Two Phase Commitの例 (2) abortされる例 水色がcommit_requestに返信しない場合 commit timeout Abortを決定 Abortを送信 X=1 (X=1) commit request agree abort X=2に変更を要求 X=1 (X=1) No reply block解除 ログを取ってblock ログから復帰 X=1 メッセージを返信できない

Two Phase Commitの特徴 処理時間は一番遅いプロセッサに依存 prepare stateを設けたcommit protocol 　→ますます遅くなる 通信が高速で、頻繁には失敗しないシステムで、処理の確実性を保つのに有用

Votingの概要 前提 基本的なアイディア プロセッサに親子の区別はない 通信路は信頼できない 各プロセッサはデータのコピーを持つ 読み書きするにはvoteをする必要がある quorum(定足数)を満たすと権利を得られる

Votingの操作 (準備) 各プロセッサがデータのコピーを持っている データの更新回数(version) も付随している 各プロセッサは、アクセスモードを記憶している write mode (一人だけread/writeアクセス) read mode (全員read onlyアクセス) noaccess mode (全員アクセス不可) vote結果待ち mode voteによりデータアクセスのモードを切り替える 各プロセッサはvoteのための票数(votes)を持つ

Votingの操作 r/w したいプロセッサ(幹事)がvote_requestを送信 各プロセッサは自分のmodeに応じてvote (noaccess)　自分のvotesとversionを返信、結果待ち (それ以外) 　反対を返信 幹事は最新のversionを持つ賛成票を集計し、 quorumを満たせば、read modeに入ることを送信 満たさなければ、vote失敗を送信 幹事は自分のデータが古い場合、最新のものを入手 writeの場合は変更したデータを送信 各プロセッサはデータとversionを変更 操作が終わったら、noaccessモードに戻る

Votingの例 quorum = 3、votesは全プロセッサで1とする [成立] [失敗] 賛成: 1,3,4 賛成: 1,3,4 [1] request ver.3 [1] request ver.3 agree ver.2 [2] agree ver.2 [5] disagree ver.2 agree ver.2 [2] agree ver.2 [5] disagree ver.2 [3] agree ver.3 [4] agree ver.3 [3] agree ver.3 [4] network failure 賛成: 1,3,4 　 無効: 2 反対: 5 賛成: 1,3,4 　 無効: 2, 4 反対: 5

quorumの設定 同時に二つのwriteが起こらない →w > v/2 writeとreadは並存しない →r + w > v read_quorum=r, write_quorum=w, ∑votes=vとする。 同時に二つのwriteが起こらない →w > v/2 writeとreadは並存しない →r + w > v writeが頻繁に発生→wを小さく writeがあまり起こらない→wを大きく w=vなら、two phase commitと同じ

votesの設定 信頼でき高速なプロセッサは票数を多く c=8, w=5 c=4, w=3 成立するのは 成立するのは [1] 1msec votes=3 [2] 10msec votes=2 [1] 1msec votes=1 [2] 10msec votes=1 [3] 10msec votes=2 [4] 100msec votes=1 [3] 10msec votes=1 [4] 100msec votes=1 c=8, w=5 成立するのは {1,2} (10ms) {1,3} (10ms) {1,2,3} (10ms) {1,2,4} (100ms) {1,3,4} (100msec) {2,3,4} (100ms) {1,2,3,4} (100msec) c=4, w=3 成立するのは {1,2,3} (10ms) {1,2,4} (100ms) {1,3,4} (100ms) {2,3,4} (100ms) {1,2,3,4} (100ms)

Votingの特徴 近いプロセッサだけで同意が成立 voteの票数やquorum、さらにタイムアウトや賛否の決め方を変更し、柔軟な運用ができる さらに耐故障性を高く Dynamic Vote Quorum Reassignment 不均質で信頼性の低いシステムで有効

atomic broadcastの概要 前提 基本的なアイディア 任意の一プロセッサがbroadcastする 全員の同期が必要 メッセージが失われる可能性がある 基本的なアイディア メッセージの到着と順序の同一性を保障 到着したメッセージは一度バッファに入る 全プロセッサでメッセージが到着したら受信

atomic broadcastの操作 送信者がメッセージをbroadcast。msgにはIDがある 受信者はメッセージが到着したら以下の操作を行う もしキューに同一IDのメッセージがあれば受信しない 到着時のlamport clockをpriorityとして設定 “undeliverable”マークを付け、キュー(priority付き)に入れる 送信者は指定時間返信を待ち、 返信が来ないプロセッサに先と度同じIDを用いて再送信 全ての返信を受信したら、その中で最大のpriorityをbroadcast 受信者はpriorityを受信したら メッセージのpriorityを更新し、”deliverable”マークをつける キューの先頭から”deliverable”なメッセージを順に受信する

まとめ 耐故障性には処理の冗長性が不可欠 完全な耐故障は存在しない →性能と耐故障性のトレードオフ 耐故障プログラムを書くのは大変 (伝令のパラドックス) →性能と耐故障性のトレードオフ 耐故障プログラムを書くのは大変 →下層で信頼性を確保(TCPとIPの関係)