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

Transactional Information Systemsにおける第１８章演習問題の自分なりの解答。障害回復の章は重そうなので後回しで、分散トランザクションの話題から。

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

hackmd.io

18.1

例示された半順序スケジュールの実行手順を記述する問。グラフィカルなので略。

18.2 Q

CSRでないグローバルなスケジュールが分散2PLに従って処理される例を記述せよ。

18.2 A

アイテムxを持つサーバ1とyを持つサーバ1にまたがるグローバルトランザクション $s=r_1(x)w_2(y)w_2(x)r_1(y)c_1c_2$ はこれ自体CSRではない。

各サーバでの処理順は

サーバ1： $rl_1(x)$ → $r_1(x)$ → $wl_2(x)$ がブロックサーバ2： $wl_2(y)$ → $w_2(y)$ → $rl_1(y)$ がブロック

両者ブロックされたことでxとyでデッドロックが検出されるのでどちらかがアボート、最終的に逐次的な実行順になる。

18.3 Q

図18.10で示されたwaits-forグラフにおけるpath pushingアルゴリズムの手順を記述せよ。

18.3 A

AがBにパス $(t_1\rightarrow t_3)\rightarrow$ を送出
BがCにパス $t_1\rightarrow t_3\rightarrow t_5, t_1\rightarrow t_3\rightarrow t_6$ を送出
Cで閉路 $t_1\rightarrow t_3\rightarrow t_5\rightarrow t_1$ が検出

18.4 Q

例18.8, 18.11, 18.12でのOptimistic Ticket Method(OTM)の挙動を記述せよ。

18.4 A

例18.8

$s_1=r_1(a)r_3(a)r_3(b)w_3(a)w_3(b)r_2(b)$

$s_2=r_2(c)r_4(c)r_4(d)w_4(c)w_4(d)r_1(d)$

$r_2(b),r_1(d)$ どちらかの実行時点でチケットグラフは $t_1\leftrightarrow t_2$ となって閉路になるため、どちらかのトランザクションがアボートされる。

例18.11

$s_1=w_1(a)c_1r_3(a)r_3(b)c_3w_2(b)c_2$

$s_2=w_2(c)c_2r_4(c)r_4(d)c_4w_1(d)c_1$

$t_1, t_2$ は同じデータアイテムへの書き込みを行わないが、take-a-ticket操作によって強制的に競合を作成される。よって、例18.8と同じく閉路 $t_1\leftrightarrow t_2$ が作られてアボートされる。

例18.12

$s_1=r_1(a)w_3(a)w_3(b)r_2(b)c_1c_3c_2$

$s_2=w_4(c)r_1(c)r_2(d)w_4(d)c_2c_4c_1$

そもそも $c_1,c_2$ の順が各ローカルスケジュールで逆転してしまっており、OTMで管理していたらこのようなスケジュールにはならない。コミット順を無視するにしてもチケットの閉路 $t_1\rightarrow t_3\rightarrow t_2\rightarrow t_4\rightarrow t_1$ が生じるためいずれかがアボートされる。

18.5 Q

定理18.5を証明せよ。

( $s_i\in COCSR$ かつ、グローバルトランザクションのコミット順がサーバ間で統一されていれば、 $s$ はglobally serializable)

18.5 A

コミット順が統一されているので、これを全順序としてみれば、この全順序は $s_i\in COCSR$ のためローカルの逐次実行順に矛盾せず、したがって定理18.1より $s$ はglobally serializable。コミット順と競合する操作の順は全て一致するので $s\in COCSR$ でもある。

18.6 Q

$s \in COCSR$ なら $\Pi_i(s)\in COCSR$ を示せ。

18.6 A

サーバ $i$ における競合もグローバルなコミット順に沿って生じるのでこれは明らか。

18.7 Q

$s\in ECOCSR - COCSR$ をみたすスケジュールの例を挙げよ。

※ $ECOCSR$ : グローバルなトランザクション間でだけ競合に則したコミット順を要求する正当性

18.7 A

$s=r_1(x)r_1(y)w_2(y)c_2c_1$

$s_1=r_1(x)c_1$

$s_2=r_1(y)w_2(y)c_2c_1$

はグローバルトランザクションが $t_1$ のみなので明らかにECOCSRに属するが、yにおける競合がコミット順に則さないのでCOCSRではない。

18.8 Q

各プロトコルにおいてチケットを取得する操作の適切なタイミングを考えよ。

18.8 A

2PL：チケット操作には排他ロックが必要になるので、保持している期間をできるだけ短くしたい。よって、ロックの取得フェーズから解放フェーズへの転換点で実行するとよい。
S2PL, SS2PL：2PLと同じ理由で、排他ロックが解放されるタイミングであるコミット直前に実行するとよい。
BOCC, FOCC：validation(検証)フェーズの開始直前、write setに基づいて各サーバでチケットを取得する。
ROMV：タイムスタンプとチケット取得タイミングを可能な限り同期させるため、
- updaterトランザクションはコミット直前、
- read-onlyトランザクションは開始時にチケットを取る。

18.9 Q

各ローカルスケジュールのMVSR性が保証されている状況でOptimistic Ticket Method(OTM)を考えることはできるか？どんな条件が必要か？

18.9 A

MVSG(Multi-Version Serialization Graph)におけるグローバルトランザクション間のパスがローカルスケジュールによって作られるなら、それがローカルなトランザクションを介した間接的なものであってもチケット上の辺として観測できなければならない。

今やチケットもマルチバージョンであることを踏まえると、チケット取得操作を定義しなおす必要がある。現在アクティブなトランザクションによって書き込まれたバージョンのチケットをすべて読み込み、新しいバージョンを書き込むようにし、読み込んだ全バージョンに応じた辺をチケットグラフ上に作る。

18.10 Q

ローカルスケジュールがsnapshot isolationを満たすとき、グローバルトランザクションについては何が言えるか？

18.10 A

ローカルスケジュールにおいて現在アクティブなトランザクションとwrite setが互いに素な時、グローバルで見ても全く同じことが言える。また、直近のコミットされたバージョンを読み込むという条件も満たされる。

以上より、ローカルスケジュールがsnapshot isolationを満たしているとき、グローバルなsnapshot isolationも達成される。ただし、コミットタイミングが同期されていることは必要である。このことからパフォーマンスは高い。

18.11

グラフィカルなので略。

概要としては、ロックを要求する際、ロック権限を全ページのhomeであるサーバCに要求する。要求した権限が排他ロックで、かつそのページへの権限を他のサーバが持っていた時に限り、サーバCは他サーバへコールバックリクエストを送り、コールバックが承認された時点で改めてロック権限を引き渡す。

u-ar.hatenablog.com

u-ar’s blog

研究や技術について。もろもろ。