Transactional Information Systems 第１９章演習問題解答

Transactional Information Systemsにおける第１９章演習問題の自分なりの解答。

間違っていたらご指摘ください。

18.1 Q

単一障害仮定の下で独立な障害回復を達成する2PC(2相コミットプロトコル)の状態遷移図を描け。

18.1 A

本書では上図の状態遷移で可能って書いてあるけれど、これでは矛盾しない独立な障害回復は無理では？

具体的な反例として、全参加者(Participant)で準備が完了してyesメッセージを送信してPrepared状態に遷移し、調整者(Coordinator)がそれを受け取ってBuffer状態に遷移した状況を考える。

ここで、調整者が送ったcommitメッセージを参加者1が受け取る前にクラッシュしたとする。このとき、参加者1は回復時に独立にAbortedに遷移し、それを検知した調整者もAbortedに遷移するが、commitメッセージを受け取った他の参加者はCommitted状態に遷移してしまい、これは最終状態なので後から変更されることはない。

→障害が参加者1でしか起こっていないのに矛盾した最終状態になっている。やっぱり駄目では？何かご存知の方、お教えいただければ幸いです。

19.2 Q

プロセス木が以下の図のように形成されていたとき（PC：クライアント、TA：旅行代理店、TW：Travel Wholesaler(旅行業者？)、RC：レンタカー会社、AX：航空会社）、

(1) 階層的な2PCにおけるメッセージの流れと作成されるログは？

(2) どのような最適化を施せるか？

(3) 調整者の役割がTAに委譲された場合、2PCのコストはどうなるか？

(4) 階層的な2PCにおいて、A3がコミットできずnoを投票した場合の処理は？

(5) presumed-abort(PA)の2PCにおいて、A3がコミットできずnoを投票した場合の処理は？

19.2 A

(1) 階層的な2PCにおけるメッセージの流れと作成されるログは？

根ノードのPCから開始し、矢印を辿りながら各プロセスにコミット準備を要求していくことになる。返信は逆向きに根へさかのぼる。

最適化を考えない基本的な2PCにおいては、以下のような流れを辿る。緑がログエントリのファイルへの書き出し、橙がプロセス間のメッセージを指す。

PC：force-begin
PC→TA, RC：prepare
TA：force-begin
TA→TW, A3, A4：prepare
TW：force-begin
TW→A1, A2：prepare
A1, A2：force-prepared
A1, A2→TW：yes
A3, A4, TW：force-prepared
TW, A3, A4→TA：yes
TA, RC：force-prepared
TA, RC：yes
ここまで投票フェーズ、ここから決定フェーズ
PC：force-commit
PC→TA, RC：commit
TA, RC：force-commit
TA→TW, A3, A4：commit
TW, A3, A4：force-commit
TW→A1, A2：commit
A1, A2：force-commit
A1, A2→TW：ack
TW, A3, A4→TA：ack
TA→PC：ack
PC：end

ログのforce-writeは18個、メッセージは28個となる。

これを一般化すると、ノード総数が $n$ 、内部ノード(葉でないノード)数が $i$ とするとき、

force-writeは個
- force-beginが $i$ 個
- force-preparedが $n-1$ 個
- force-commit/abortが $n$ 個
メッセージ数は個
- prepareメッセージが $n-1$ 個
- yes/noメッセージが $n-1$ 個
- commit/abortメッセージが $n-1$ 個
- ackメッセージが $n-1$ 個

(2) どのような最適化を施せるか？

presumed-abort(PA)とpresumed-commit(PC)の2種類でロギングとメッセージングのコストを減らすことを考える。それぞれ、最終的な決定に関する情報が手に入らないときのデフォルトの挙動を決めておくことでコストを減らす手法であり、PAはデフォルトでアボートするバリアント、PCはデフォルトでコミットするバリアントである。

PA
- ロギング
  - beginログエントリのforceが不要になる。回復時に無かったらアボートにして問題ないため。
  - preparedログエントリのforceは必要である。
  - commitログエントリのforceは必要だが、rollbackログエントリは不要である。回復時に無かったらアボートにするため。
- メッセージ
  - コミットの際は基本2PCと同様、commitメッセージとackメッセージの返信が必要である。
  - アボートの際はabortメッセージは必要だが、ackメッセージの返信は不要である。メッセージが届いたことを確認しなくてもアボートしていることを期待できるため。
PC
- ロギング
  - beginログエントリのforceは必要である。無い→ログがGCされているのでデフォルトの動作としてコミットしたものとして取り扱う、あるが終了していない→投票を再開する、と動作を分岐させる必要があるため。
  - preparedログエントリのforceは必要である。
  - commitログエントリのforceは、根でのみ必要である。これは投票の結果がコミットになり決定フェーズに移ったことを記録するため。他のノードは全てデフォルトでコミットすればよいのでforceする必要がない。
  - rollbackログエントリのforceは全ノードで必要である。
- メッセージ
  - コミットの際はcommitメッセージが必要だが、ackメッセージの返信は不要である。
  - アボートの際は基本2PCと同様、abortメッセージとackメッセージの返信が必要である。