クイズ 非同期システムにおいて，1プロセスがクラッシュ故障する可能性がある場合，次のアルゴリズムで非ブロッキング原子コミットが解けないことを示せ アルゴリズム V(=Yes or No)を高信頼ブロードキャスト 全プロセスから値を受信した場合 すべてYesならコミットを決定 そうでなければアボートを決定.

Presentation on theme: "クイズ 非同期システムにおいて，1プロセスがクラッシュ故障する可能性がある場合，次のアルゴリズムで非ブロッキング原子コミットが解けないことを示せ アルゴリズム V(=Yes or No)を高信頼ブロードキャスト 全プロセスから値を受信した場合 すべてYesならコミットを決定 そうでなければアボートを決定."— Presentation transcript:

1 クイズ 非同期システムにおいて，1プロセスがクラッシュ故障する可能性がある場合，次のアルゴリズムで非ブロッキング原子コミットが解けないことを示せ アルゴリズム V(=Yes or No)を高信頼ブロードキャスト 全プロセスから値を受信した場合 すべてYesならコミットを決定 そうでなければアボートを決定 全プロセスから受信する前に一定時間T経過した場合： アボートを決定

2 3.5 プロセス多重化 プロセスを多重化し故障に対処する手法 Stateless Server Stateful Server
状態を持たないサーバ（静的に与えられたデータの読み出しのみを実行） 多重化が容易 Stateful Server 状態を持つサーバ 多重化には，複雑な機構が必要

3 多重化サーバ op(arg) ok(res) Client process pi Nonreplicated server x x
Invocation Response Nonreplicated server x x Replicated server x Replica x1 Replica x2 Replica x3

4 例．FIFOキュー enqueue(a) dequeue() ok(res) Client process pi
Invocation Response FIFO Queue Service Replicated server x Replica x1 Replica x2 Replica x3 Client process pj Invocation Response enqueue(b) dequeue() ok’(res’)

5 Erroneous Execution enqueue(a) dequeue() Client process pi ok(b) ok(a)
FIFO Queue Service Replica x1 a b Replica x2 b a Replica x3 ok(b) ok (a) Client process pj enqueue(b) dequeue()

6 多重化のアプローチ 3.5.1 能動的多重化 (Active replication)
3.5.3 受動的多重化 (Passive replication) 1つのReplicaのみが処理を実行 p1 p2 p3 P Q p1 p2 p3 P Q Update

7 3.5.1 能動的多重化 op(arg) ok(res) Client process pi Replica x1 Replica x2
Invocations Responses Replica x1 Replica x2 Replica x3 Atomicity (原子性) 命令が実行されるなら，正常な全Replicaが実行 Order (順序) 同じ順序で命令を処理 Determinism (決定性)

8 原子性，順序 満たされない場合 状態の不整合が起こる Client process pi Replica x1 Replica x2
状態が異なる Replica x3 Client process pj

9 原子性，順序 正常なすべてのReplicaに，同じ順序でメッセージを配送する手段が必要 → 原子ブロードキャスト Client
process pi Replica x1 状態が一致 Replica x2 Replica x3 Client process pj

10 決定性 決定性 Determinism 非決定性の要因 初期状態と，それまでの処理の過程から一意に結果が定まること
各replicaの処理は決定的(deterministic)でなければならない そうでなければ状態の一貫性が無くなる． 非決定性の要因 例．マルチスレッド

11 多重化とグループ通信 グループ通信機能を下部に用いることで，容易に多重化を実現 グループ通信システムの例
ISIS, Horus (Cornell University) アプリケーション 受容 (deliver) 原子ブロードキャスト等 グループ通信 受信(receive) 送信 オペレーティングシステム

12 (多重化のための)グループ通信 順番を保つために，受信しても一旦bufferingすることが必要 受信 (receipt)
ノードがメッセージを受け取ること 受容 (delivery) プロセスがメッセージを渡すこと (受容，配送） p1 p2 Sender delivery A, B delivery A, B Sender B receipt A, B receipt B, A A Network

13 3.5.2 原子ブロードキャスト プロセス={P1, P2, …} 条件
3.5.2　原子ブロードキャスト プロセス={P1, P2, …} 条件 停止性: 正常なPiがabcast(m)したら，いずれPiはdeliver(m) 一律合意: あるPiがdeliver(m)したなら，正常などのプロセスPjもdeliver(m) 妥当性: deliver(m)したなら，abcast(m)済み 全順序: Pi, Pjがdeliver(m)しており，Piがそれより前にdeliver(m’)しているなら，Pjもそれ以前に，deliver(m’)

14 コンセンサスを用いた原子ブロードキャスト
受信したメッセージの集合を提案値として，定期的にコンセンサス問題を解く コンセサス a propose({b}) decide({a,b}) P1 {b} propose({a,b}) P2 decide({a,b}) {a,b} propose({a,b}) P3 decide({a,b}) {a,b} b

15 3.5.3 受動的多重化 1つのReplicaのみが実際には処理を実行 レプリカの動作は非決定的でもよい Client process pi
Invocation Response Server x Primary replica x1 Update Ack Backup replica x2 Update Ack Backup replica x3

16 主プロセスの故障1 新しい主プロセスを決定 Client process pi Prim(x) = x1 Prim(x) = x2 A
op(arg) Client process pi Invocation Invocation Ｗ Prim(x) = x1 Prim(x) = x2 A Primary replica x1 Update Backup replica x2 Backup → Primary Backup replica x3 新しい主プロセスを決定

17 主プロセスの故障2 Updateを受信したBackupと受信していないBackupが存在→ Replicaの状態の不一致
op(arg) ok(res) Client process pi Invocation with invID Invocation with invID Response B Primary replica x1 Update Backup replica x2 Backup replica x3 Updateを受信したBackupと受信していないBackupが存在→ Replicaの状態の不一致 グループ通信機能が必要

18 3.7 分散チェックポインティング チェックポインティングとロールバックリカバリ（2.2.2） 単一プロセスなら実現は容易
定期的に状態を信頼できる記憶装置に保存し，故障の際にその情報を利用して以前の正常な状態に回復する手法 単一プロセスなら実現は容易 Rollback Process time Checkpoint Checkpoint

19 分散システムにおけるチェックポインティング
分散システムでは通信を考慮する必要がある Inconsistentな（整合性のない）状態 孤児メッセージ(Orphan message)の存在 送信していないのに受信されたメッセージ P1 m1 P2 m2 P3

20 分散システムにおけるチェックポインティング
In-transit message 送信したが受信されていないメッセージ Consistentな（整合性のある）状態 実際に起こりうる状態 In-transit messageは，通常のメッセージ喪失と同様に，通信プロトコルにより対処できる P1 m1 P2 m2 P3

21 ドミノ効果 (Domino Effect) 回復線 (Recovery Line) ドミノ効果
P1 c2,1 c2,2 c2,3 c2,4 P2 c3,1 c3,2 c3,3 c3,4 P3 Recovery line 回復線 (Recovery Line) 孤児メッセージを含まないチェックポイントの集合 ドミノ効果 リカバリラインがドミノ倒しのように後退してしまう現象 ドミノ効果を起こさないようなCheckpointの取り方が必要

22 分散チェックポインティングの種類 非連携 Uncoordinated 連携 Coordinated
各プロセスが非同期的にチェックポイントを取得 ドミノ効果の危険 連携 Coordinated プロセスが協調してチェックポイントを取得 ドミノ効果を防止 通信誘導 Communication-Induced メッセージのやり取りのパターンを基づいて，ドミノ効果が起こらないようにチェックポイントを取得

23 連携チェックポインティング 時間同期を利用したアルゴリズム
同期のとれたクロックを使用 | Ci(t) - Cj(t) |  e 一定時間p毎にチェックポイントを取得 Orphan Messageが起こるシナリオ p e P1 p P2

24 連携チェックポインティング 時間同期を利用したアルゴリズム
チェックポイント後，時間e 経過するまで送信をしない T e T + e P1 P2 T

25 通信誘導チェックポインティング メッセージのやり取りのパターンを基づいて，無用(Useless)チェックポイント が発生しないようにチェックポイントを取得 無用チェックポイント Recoveryに利用できないチェックポイント (例．C3,3) c1,1 c1,2 c1,3 P1 m2 m4 c2,1 c2,2 c2,3 c2,4 P2 m6 c3,1 m1 c3,2 m3 m5 c3,3 c3,4 P3

26 Z-Paths, Z-Cycles Z-Path m1, …, mn はCi,xからＣj,yへのZ-Path
m1はCi,x 以降に送信（プロセスPi） l = 1, …, n-1: mlの受信と，ml+1の送信について，直前のチェックポイントが同じ mnをＣj,y 以前に受信 （プロセスPj） c1,1 c1,2 c1,3 P1 m2 m4 c2,1 c2,2 c2,3 c2,4 P2 m6 c3,1 m1 c3,2 m3 m5 c3,3 c3,4 P3

27 Z-Paths, Z-Cycles Z-Cycle 一つのチェックポイントに対するZ-Path
Useless Checkpointの必要充分条件 c1,1 c1,2 c1,3 P1 m2 m4 c2,1 c2,2 c2,3 c2,4 P2 m6 c3,1 m1 c3,2 m3 m5 c3,3 c3,4 P3

28 通信誘導チェックポインティングの例 Z-Cycleを作らないようにする． 例．論理時計の利用 Idea
チェックポイントを取得したら lc := lc+1 送信メッセージmにはlcを時刻印として添付(tc(m)) メッセージmを受信した際,tc(m) >lcならlc:= tc(m) Idea Z-Pathの時刻印が単調増加ならZ-Cycleにはならない 2 4 5 1 P1 m2 m4 1 2 3 4 P2 m6 m1 m3 m5 4 2 3 P3

29 通信誘導チェックポインティングの例 Idea 方法 Z-Pathの時刻印が単調増加ならZ-Cycleにはならない
受け取ったメッセージ(m2)より小さい時刻印のメッセージ(m1)を送信していたら，m2を受容する前にチェックポイントを取る P1 P1 m2 m2 P2 P2 m1 m1 P3 P3 ts(m1) ≥ ts(m2) ts(m1) < ts(m2)

30 通信誘導チェックポインティングの例 Idea 方法 Z-Pathの時刻印が単調増加ならZ-Cycleにはならない
受け取ったメッセージより小さい時刻印のメッセージを送信していたら，deliverする前にチェックポイントを取る 2 4 5 1 P1 m2 m4 1 2 3 4 P2 m6 m1 m3 m5 4 2 3 P3