耐故障処理 (Fault Torelance System)

耐故障処理
Fault Tolerance
「分散計算の基礎」 12章
発表者 : 高橋慧
Distributed System
Fault Tolerance
耐故障処理とは
• コンピュータでは様々なエラーが発生
• プログラム自体のバグ
• 外的要因によるプロセスの中断・停止
• ネットワークの障害
• これらのエラーを検知して
• エラー処理を行い、終了する
• 修復して処理を継続する
Distributed System
Fault Tolerance
No. 2
発表の流れ
• プロセス単位での耐故障処理
• 簡単なデモ
• 並列システムでの耐故障処理
• Two Phase Commit Protocol
• Voting Protocol
• 送信エラーを考慮したbroadcast
• Atomic Broadcast
Distributed System
Fault Tolerance
No. 3
プロセス単位での耐故障処理
• プロセスの予期しない終了への対処
• ログによって復帰する
• バックアップのプロセスが処理を引き継ぐ
• 常に複数のプロセスが平行して処理を行う
• 問題点
• 復帰しても再びエラーになった時は?
→ログを資料にデバッグ
• 何度も計算したとき、結果は一定なのか?
→常に結果が同じになる処理のみを考える
Distributed System
Fault Tolerance
No. 4
簡単なデモ
1) 一定間隔で値をファイルに記録
死んだらログを読んで処理継続
2) 親プロセスと子プロセスが存在
子が死んだら親が子を立ち上げる
3) 別プロセッサからpsの出力を監視
プロセスが死んだら、rshで立ち上げる
Distributed System
Fault Tolerance
No. 5
並列システムでの耐故障処理
• 各プロセッサでデータの同期が必要
→同時刻に読むデータは同一(atomic)
• Two Phase Commit
• readは自由・writeに許可が必要
• 全員の同意を得てwrite (commit)
• エラー処理を行い、処理中断
• Voting
• read、writeとも許可が必要
• 半数以上の賛成が得られればwrite/readを許可
• エラー時でも、残ったプロセッサで処理継続
Distributed System
Fault Tolerance
No. 6
同期の必要性
• プロセッサ間でデータの同期が必要
(データの同期をatomicityと呼ぶ)
• メッセージ消失によりatomicityを失った例
X=1
X=2
xのatomicityが
保たれていない
X=1
(X=1)
X=2に変更
X=1
変更の送信に失敗
X=2
X=2
変更を送信
Distributed System
Fault Tolerance
No. 7
Two Phase Commitの概要
• 前提
• 親プロセスが1つある
• 通信路は信頼できない
• 基本的なアイディア
•
•
•
•
処理の結果はcommitによって反映される
abortすると結果は反映されない
全プロセスが同意した場合のみcommit
commit / abortは一意 → atomicityの維持
Distributed System
Fault Tolerance
No. 8
Two Phase Commitの操作
• 子プロセッサが親にcommitを要求
• 親は全ての子にcommit_requestを送信
• 子はcommit_requestを受信したら、
• (エラー時)abortを送信
• (正常時) ログを取り、agreeを返信し、ブロック
• 親は子からの返信をある時間待って
• (一つでもagreeしない時) agreeしたプロセスにabortを送信
• (全員がagreeした時)
commitを送信し、commit操作
• agreeを送信した子は、親からのメッセージによって
• (abortを受信)
ログにより復帰し、ブロック解除
• (commitを受信) 待機し、commitに必要な処理のみ行う
• 親はcommitが完了したら、completeを送信
• 子はcompeteを受信したら、ブロック解除
Distributed System
Fault Tolerance
No. 9
Two Phase Commitの例 (1)
• Commitが行われる例
Commitの例
X=2に更新
X=1
受信を確認
X=2を送信
Commit操作開始
Commit完了
X=2
commit agree
commit
request
agree
X=1
X=2に更新
complete
X=2
block解除
X=2に変更を要求
ログを取ってblock
X=1
X=2に更新
X=2
ログを取ってblock
Distributed System
Fault Tolerance
block解除
No. 10
Two Phase Commitの例 (2)
• abortされる例
• 水色がcommit_requestに返信しない場合
timeout
Abortを決定
Abortを送信
X=1
X=2に変更を要求
(X=1)
commit agree
request
abort
X=1
(X=1)
No reply
ログを取ってblock
block解除
ログから復帰
X=1
メッセージを返信できない
Distributed System
Fault Tolerance
No. 11
Two Phase Commitの特徴
• 処理時間は一番遅いプロセッサに依存
• commit中に親がエラーを起こした場合、全
プロセスがブロックしてしまう
• prepare stateを設けたcommit protocol
→ますます遅くなる
• 通信が高速で、頻繁には失敗しないシステ
ムで、処理の確実性を保つのに有用
Distributed System
Fault Tolerance
No. 12
Votingの概要
• 前提
• プロセッサに親子の区別はない
• 通信路は信頼できない
• 基本的なアイディア
• 各プロセッサはデータのコピーを持つ
• 読み書きするにはvoteをする必要がある
• quorum(定足数)を満たすと権利を得られる
Distributed System
Fault Tolerance
No. 13
Votingの操作 (準備)
• 各プロセッサがデータのコピーを持っている
• データの更新回数(version) も付随している
• 各プロセッサは、アクセスモードを記憶している
• write mode (一人だけread/writeアクセス)
• read mode (全員read onlyアクセス)
• noaccess mode (全員アクセス不可)
• vote結果待ち mode
• voteによりデータアクセスのモードを切り替える
• 各プロセッサはvoteのための票数(votes)を持つ
Distributed System
Fault Tolerance
No. 14
Votingの操作
• r/w したいプロセッサ(幹事)がvote_requestを送信
• 各プロセッサは自分のmodeに応じてvote
• (noaccess) 自分のvotesとversionを返信、結果待ち
• (それ以外) 反対を返信
• 幹事は最新のversionを持つ賛成票を集計し、
• quorumを満たせば、read modeに入ることを送信
• 満たさなければ、vote失敗を送信
• 幹事は自分のデータが古い場合、最新のものを入手
• writeの場合は変更したデータを送信
• 各プロセッサはデータとversionを変更
• 操作が終わったら、noaccessモードに戻る
Distributed System
Fault Tolerance
No. 15
Votingの例
quorum = 3、votesは全プロセッサで1とする
[成立]
[失敗]
[1]
request
ver.3
[1]
request
ver.3
[2]
agree
agree
ver.2
ver.2
[3]
agree
ver.3
賛成: 1,3,4
無効: 2
反対: 5
Distributed System
Fault Tolerance
[5]
disagree
ver.2
[4]
agree
ver.3
[2]
agree
agree
ver.2
ver.2
[3]
agree
ver.3
[5]
disagree
ver.2
[4]
network
failure
賛成: 1,3,4
無効: 2, 4
反対: 5
No. 16
quorumの設定
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と同じ
Distributed System
Fault Tolerance
No. 17
votesの設定
• 信頼でき高速なプロセッサは票数を多く
[1]
1msec
votes=1
[2]
10msec
votes=1
[1]
1msec
votes=3
[2]
10msec
votes=2
[3]
10msec
votes=1
[4]
100msec
votes=1
[3]
10msec
votes=2
[4]
100msec
votes=1
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)
Distributed System
Fault Tolerance
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)
No. 18
Votingの特徴
• 近いプロセッサだけで同意が成立
• voteの票数やquorum、さらにタイムアウトや賛
否の決め方を変更し、柔軟な運用ができる
• さらに耐故障性を高く
• Dynamic Vote
• Quorum Reassignment
• 不均質で信頼性の低いシステムで有効
Distributed System
Fault Tolerance
No. 19
atomic broadcastの概要
• 前提
• 任意の一プロセッサがbroadcastする
• 全員の同期が必要
• メッセージが失われる可能性がある
• 基本的なアイディア
• メッセージの到着と順序の同一性を保障
• 到着したメッセージは一度バッファに入る
• 全プロセッサでメッセージが到着したら受信
Distributed System
Fault Tolerance
No. 20
atomic broadcastの操作
• 送信者がメッセージをbroadcast。msgにはIDがある
• 受信者はメッセージが到着したら以下の操作を行う
• もしキューに同一IDのメッセージがあれば受信しない
• 到着時のlamport clockをpriorityとして設定
• “undeliverable”マークを付け、キュー(priority付き)に入れる
• 送信者は指定時間返信を待ち、
• 返信が来ないプロセッサに先と度同じIDを用いて再送信
• 全ての返信を受信したら、その中で最大のpriorityをbroadcast
• 受信者はpriorityを受信したら
• メッセージのpriorityを更新し、”deliverable”マークをつける
• キューの先頭から”deliverable”なメッセージを順に受信する
Distributed System
Fault Tolerance
No. 21
まとめ
• 耐故障性には処理の冗長性が不可欠
• 完全な耐故障は存在しない
• (伝令のパラドックス)
→性能と耐故障性のトレードオフ
• 耐故障プログラムを書くのは大変
→下層で信頼性を確保(TCPとIPの関係)
Distributed System
Fault Tolerance
No. 22

Download Report