Transactional Information Systems 第５章演習問題解答

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

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

hackmd.io

5.1 Q

以下の3つの履歴について、MVSRやMCSRに属するか、MVSRなら必要なバージョン数についても判定せよ。

$m_1=w_0(x_0)w_0(y_0)w_0(z_0)c_0r_3(x_0)w_3(x_3)c_3w_1(x_1)c_1r_2(x_1)w_2(y_2)w_2(z_2)c_2$

$m_2=w_0(x_0)w_0(y_0)c_0w_1(x_1)c_1r_3(x_1)w_3(x_3)r_2(x_1)c_3w_2(y_2)c_2$

$m_3=w_0(x_0)w_0(y_0)c_0w_1(x_1)c_1r_2(x_1)w_2(y_2)c_2r_3(y_0)w_3(x_3)c_3$

5.1 A

$m_1$

モノバージョンスケジュール $t_0t_3t_1t_2$ とreads-from関係が等しいので $m_1\in MVSR$ 。適切な $t_\infty$ は $t_\infty = r_\infty(x_1)r_\infty(y_2)r_\infty(z_2)$ 。

$m_1$ からバージョン表記を取り除いてもreads-from関係が変わらないので $m_1\in VSR$ ですらある。

$m_2$

モノバージョンスケジュール $t_0t_1t_2t_3$ とreads-from関係が等しいので $m_2\in MVSR$ 。適切な $t_\infty$ は $t_\infty = r_\infty(x_3)r_\infty(y_2)$ 。

バージョン表記を取り除いた場合は、 $c_3$ を手前に出すだけで逐次的なスケジュール $t_0t_1t_3t_2$ になるので $m_2\in VSR$ ですらある。

$m_3$

モノバージョンスケジュール $t_0t_3t_1t_2$ とreads-from関係が等しいので $m_3\in MVSR$ 。適切な $t_\infty$ は $t_\infty = r_\infty(x_1)r_\infty(y_2)$ 。

バージョン表記を取り除いた場合は、もとから逐次的なスケジュールなので $m_3\in VSR$ ですらある。

5.2 Q

マルチバージョンスケジュール

$m=w_0(x_0)w_0(y_0)c_0r_1(x_0)w_1(x_1)r_2(x_1)w_2(y_2)w_1(y_1)w_3(x_3)$

について、 $MVSG(m,\ll)$ が閉路を持たないような $\ll$ が存在するか判定せよ。

5.2 A

$MVSG(m,\ll)$ において、reads-from関係に基づく辺は $t_0\rightarrow t_1\rightarrow t_2$ のみである。

これに辺が追加された際に閉路を生まないような $\ll$ を考えればよい。

MVSGにおける辺追加規則を振り返ると、 $w_j(x_j), r_k(x_j), w_i(x_i)$ があるとき

$t_j\rightarrow t_k$ は常にある (reads-from関係に基づく辺)

$x_i \ll x_j$ なら $t_i\rightarrow t_j$

$x_j \ll x_i$ なら $t_k\rightarrow t_i$

reads-from関係以外で辺を生じうる操作の組み合わせは

$w_0(x_0), r_1(x_0), w_3(x_3)$
$w_1(x_1), r_2(x_1), w_0(x_0)$
$w_1(x_1), r_2(x_1), w_3(x_3)$

$x_0$ がバージョン順で最小であることは自明である。よって、前者二つは $t_1\rightarrow t_3$ 、 $t_0\rightarrow t_1$ という辺を生む。

次に、3つ目の組み合わせは

$x_3 \ll x_1$ なら $t_3\rightarrow t_0$ という辺が生じる。閉路 $t_0\rightarrow t_1 \rightarrow t_3\rightarrow t_0$ が生じるのでダメ。
$x_1 \ll x_3$ なら $t_1\rightarrow t_3$ という辺が生じる。

よって、 $x_1 \ll x_3$ を満たすバージョン順ならば条件を満たす。

全順序を適当に定めて $x_0\ll x_1\ll x_2\ll x_3$ が答えになる。

5.3 Q

no blind writes モデル (データアイテムに書き込む前に必ず読み込まなければならないモデル) では $MCSR=MVSR$ であることを示せ。

5.3 A

$MCSR \subseteq MVSR$ は一般に成り立つので、追加で $MVSR\subseteq MCSR$ を示せばよい。

$m\in MVSR$ な $m$ を考える。逐次的なモノバージョンスケジュール $m'$ が存在して $RF(m)=RF(m')$ となる。

ここで、 $m$ がMCSRの意味でも $m'$ へ帰着できること、すなわち $r_j(x_k) \lt_m w_i(x_i) \Rightarrow r_j(x_k) \lt_{m'} w_i(x_i)$ を示せばよい。

$r_j(x_k)\lt_m w_i(x_i)$ だが $w_i(x_i)\lt_{m'} r_j(x_k)$ と仮定して矛盾を導く。

$m'$ において、 $t_i$ はno blind write性より、ある直近の書き込み $w_l(x_l)$ から読み込む。また、 $t_j$ は、 $r_j(x_k)$ があることから、直近の書き込み $w_k(x_k)$ から読み込む。仮定 $w_i(x_i)\lt_{m'} r_j(x_k)$ と合わせて、これら関連するトランザクションの逐次実行順は

$t_l\rightarrow t_i\rightarrow t_k\rightarrow t_j$

$m'$ がモノバージョンであることから、 $t_l\rightarrow t_i$ と $t_k\rightarrow t_j$ の間には $x$ の書き込みは挟まらない。

ここで $t_k$ はある直前の $x$ への書き込み $w_p(x_p)$ から読み込んでおり、no blind write性から $t_p$ もまた直前の $x$ への書き込みから読み込む。再帰的に考えて、すべてreads-from関係からなる連鎖

$t_l\rightarrow t_i\rightarrow t_{p_1} \rightarrow \cdots\rightarrow t_{p_q}\rightarrow t_k\rightarrow t_j$

が $m'$ において生じていることが分かる。 $RF(m)=RF(m')$ なので、このreads-from関係がすべて $m$ でも成り立つ。したがって

$w_i(x_i)\lt_{m}\cdots \lt_{m} r_j(x_k)$ であり、これは仮定 $r_j(x_k)\lt_m w_i(x_i)$ に反するため矛盾。

以上より $m\in MCSR$ である。 $\square$

5.4 Q

action モデル (各ステップは同一データアイテムへの読み込み＋書き込みからなる) ではMVSR=VSRであることを示せ。

5.4 A

$VSR \subseteq MVSR$ は既に示されているので、あとは $MVSR\subseteq VSR$ を示せばよい。

$m\in MVSR$ を考える。逐次的なモノバージョンスケジュール $m' = t_1t_2\cdots t_n$ が存在して、 $RF(m)=RF(m')$ である。actionモデルであることから、各データアイテムへのactionについて、直前のactionと直後のactionとの間にreads-from関係が必ず存在する。

これが $m$ でも成り立つことから、 $m$ からバージョンを落としたスケジュール $s$ でもこの関係が変化せず、また $m'$ もモノバージョンスケジュールなのでバージョンを落とした $s'$ でも関係が変化しないので $RF(s)=RF(s')$ である。したがって $m \in VSR$ 。 $\square$

5.5 Q

バージョンの定義されていない古典的なスケジュール

$s=r_1(x)r_2(x)r_3(y)w_2(x)w_1(y)c_1w_2(z)w_3(z)r_3(x)c_3r_2(y)c_2$

がマルチバージョンの意味でserializableなことを示し、適切なバージョン順を与えよ。

MVTOや2V2PLプロトコルではどのように処理されるか？

5.5 A

そのままだとreads-from関係が閉路を作るのでVSRでない。

一方、バージョン関数を与えて

$s=r_1(x_0)r_2(x_0)r_3(y_0)w_2(x_2)w_1(y_1)c_1w_2(z_2)w_3(z_3)r_3(x_0)c_3r_2(y_1)c_2$

とすればモノバージョンスケジュール $t_1 t_3 t_2$ とreads-from関係が等しいのでMVSR。

MVTOでの処理

開始順から $ts(t_1) \lt ts(t_2) \lt ts(t_3)$ 。

操作に適宜バージョンが割り当てられていき、

$r_1(x_0)r_2(x_0)r_3(y_0)w_2(x_2)$ → $w_1(y)$ が拒否されて $t_1$ が中止 → $w_2(z_2)w_3(z_3)r_3(x_2)c_3r_2(y_0)c_2$

と進む。

2V2PLでの処理

$t_1$ のコミット時点で、 $x$ へのread lock、 $y$ へのwrite lockを保持し、certify lock待ちで $t_3$ にブロックされる。 $w_2(z)$ が実行され、write lockが競合するので $w_3(z)$ はブロックされる。ブロックされていないのは $t_2$ だけになるが、これも $x$ のcertify lock待ちで $t_1$ にブロックされ、デッドロックとなる。