3章-3 中断を考慮した/分離性を柔軟にしたSerializability

###### tags: `TransactionalInformationSystems` # 3章-3 中断を考慮した/分離性を柔軟にしたSerializability ## Commit Serializablity CSRは有用な基準であるが、dirty read問題は解決できていない。ここまでの正当性基準としてのserializablityの選択は、トランザクションが失敗しないという理想的な状態に依存していた。実際にはプログラムは中断可能であるべきであり、 1. 現在アクティブなトランザクションも将来的に中断できること。 2. スケジュールの処理はクラッシュしうるため、正当なスケジュールのprefixもまた正当なスケジュールであることが要件として求められる。これらの要件をclosure properties of schedule properties(スケジュールクラスの閉包性)として定式化していく。コミットされたトランザクションへの射影$\Pi_{commit(s)}(s)$には頻繁に言及するため、これを$CP(s)$と表記する。 --- ### 定義：スケジュールクラスの閉包性 $E$をスケジュールのクラスとする。 1. $E$が*prefix closed*とは、$\forall s\in E$に対し$s$のprefixも$E$に属することとする。 2. $E$が*commmit closed*とは、$\forall s\in E$に対し$CP(s)$も$E$に属することとする。 --- この2つの条件を満たす正当性基準(prefix commit closed)であれば、上記の2つの中断可能性を満たせていることになる。まず、FSRとVSRはどちらもprefix commit closedではない。VSRについては単調でないためprefix closedでない。FSRについては反例がある。まあ、FSRとVSRは実用的ではないのであまり気にならない。 CSRに関しては優れている。 ### 定理3.16 CSRはprefix commit closedである。 #### 証明 $s\in CSR$とする。すると$G(s)$は閉路を持たない。したがって、そのトランザクションステップの一部のみ抜き出したスケジュールの衝突グラフも$G(s)$の部分グラフとなり閉路を持たない。特に$G(s')$はそうであり、さらにそこから$commit(s)$でない頂点を除いた$G(CP(s'))$もまた閉路を持たない。したがってprefix commit closedである。$\square$ 次に、このような中断可能性を加えるためFSR及びVSRを修正した概念を定義する。既にコミットされたトランザクションは、どの時刻で見てもserializabilityを満たすように処理されていることを保証する。 --- ### 定義：Commit Serializability $s$がcommit serializableとは、$s$の任意のprefix$s'$について$CP(s')$がserializableであることと定義する。serializableの定義に基づいて各種定義できる。 - CMFSR: commit final state serializable histories - CMVSR: commit view serializable histories - CMCSR: commit conflict serializable histories --- ### 定理3.17 1. CMFSR, CMVSR, CMCSRはいずれもprefix commit closedである。 2. $CMCSR \subset CMVSR \subset CMFSR$ 3. $CMFSR \subset FSR$ 4. $CMVSR \subset VSR$ 5. $CMCSR = CSR$ つまり、commit版でも各種のserializabilityの厳しさの関係は変わらず、またCMCSRは結局CSRそのものである。 #### 証明 (1)と(2)はcommit serializabilityの定義より明らか。CMFSRに含まれてCMVSRに含まれない、またCMVSRに含まれてCMCSRに含まれない反例はそれぞれ $$s=w_1(x)r_2(x)w_2(y)w_1(y)c_1c_2w_3(x)w_3(y)c_3$$ $$s'=w_1(x)w_2(x)w_2(y)c_2w_1(y)w_3(x)w_3(y)c_3w_1(z)c_1$$ (3) $s\in CMFSR$とする。定義より$CP(s) \in FSR$である。ここで一般性を失わず$trans(s)=\{t_1,\ldots,t_n\},commit(s)=\{t_1,\ldots,t_k\},abort(s)=\{t_{k+1},\ldots,t_n\}$とする。すると、$CP(s)$は$commit(s)$のある順列と最終状態同値なので$CP(s)\approx_f t_{\rho(1)}\ldots t_{\rho(k)}$となり、このことから $$s\approx_f t_{\rho(1)}\ldots t_{\rho(k)} t_{k+1}\ldots t_n$$ となるので$s\in FSR$。**↑$CP(s)$の最終状態同値性から直接$s$の最終状態同値性に飛躍する論理が分かっていない。** 推測。abortするものは行われなかったかのように巻き戻されるものだから最後に付け加えるだけで問題なく同値になるのか？でもこれってabortの性質を前提とした答えになってて、これまでこの本でそんな風にabortの性質を都合よく使ったことはなかったんだよな。真相は分からないが、たぶんConflict Serializabilityの定義のところで述べられていたcommit(s)のみの射影のみ考えてもいいよみたいな部分がここを解決してくれるのだろう (4) (3)と同様らしい。 (5) (3)と同様、かつCSRがprefix commit closedだかららしい。$\square$ --- ## Relative Serializability なお、アプリケーションやプログラムの内容に依存して、トランザクションの分離性の許容範囲は変わってくる。 1. トランザクション内のステップの観点。全てのステップが他のトランザクションから見て完全にアトミックに行われる必要があるとは限らない。(一部のステップのみで単位を形成しても良い) 2. 他トランザクションの観点。全ての他トランザクションからアトミックに行われているように見える必要があるとは限らない。例えば、銀行送金で、家族アカウント間で個人間に信用が担保されている場合、家族用のバランス確認用トランザクションはinconsistent readを許容する、といったことがありえる。こういったトランザクション固有の正当性を定式化していく。ただし、ここでは全てのトランザクションインスタンスはあらかじめ与えられているものとし、実用的にはアプリケーションはトランザクションインスタンスの無限の組み合わせを生成しうることにはいったん目をつぶる。また、ステップ間には全順序を想定する。(半順序への拡張も可能) ### 定義：Indivisible Units(不可分な単位) $T=\{t_1,\ldots,t_n\}$をトランザクションの集合とする。$t_j$に対する$t_i$の「不可分な単位」とは、$t_i$内の連続するステップで、それらが実行される間に$t_j$内のステップが実行されることが許されないようなものをいう。 $t_i$の$t_j$に対する不可分な単位の列を$IU(t_i,t_j)$と表記し、$k$番目の不可分な単位を$IU_k(t_i,t_j)$と表記する。このようなinterleaving specificationと矛盾しないようなconflict serializabilityを考えていく。 --- ### 定義：ステップの依存性 1. ステップ$q$が$p$に直接的に「依存する」$p\rightsquigarrow q$ とは、$p$と$q$が$p<_s q$を満たし、 1. 同じトランザクション$t$内のステップかつ$p<_t q$を満たすか、もしくは 2. 別のトランザクションのステップで$p$と$q$が衝突していること、つまり少なくとも一方が書き込みで同じデータアイテムを操作していること、とする 2. 直接依存関係の反射/推移閉包により定義される半順序を依存関係$\rightsquigarrow^*$として定義する。 --- すなわち、依存関係はトランザクション内の内部構造と衝突関係(これはトランザクション間に定義されるもの)から作られる。今考えている設定におけるserialに相当するスケジュールを定義する。 --- ### 定義：相対的にserialなスケジュール $s$ ($trans(s)=T$)が相対的にserialとは、任意の異なるトランザクション$t_i,t_j \in T$に対して以下の条件が成立することとする。ステップ$q\in t_j$が$IU_k(t_i,t_j)$の内部にあったとき、$p\rightsquigarrow^* q$または$q\rightsquigarrow^* p$を満たすような$p\in IU_k(t_i,t_j)\ (p\in t_i)$ が存在しない。 ### 定義：Relative Serializability スケジュール$s$が相対的にserializableとは、ある相対的にserialなスケジュールとconflict equivalentであることと定義する。 --- つまり、$t_j$に対して不可分な$t_i$内の単位$IU_k(t_i,t_j)$の中に$t_j$のステップ$q$が割り込むことが許されるのは、$q$が$IU_k(t_i,t_j)$内のステップと一切の依存性を持たない場合のみであるということ。その条件が満たされた場合に相対的にserialであり、それとconflict equivalentであることがrelative serializabilityの条件。相対的にserializableだがCSRでない例は存在しうる(原則論のconflict serializabilityを満たせてはいないが、与えられた不可分単位の条件によっては許容しうる、つまりその意味についてserializableになりうる場合がある) 各トランザクションの全体をそれぞれ他の全トランザクションに対して1つの不可分単位としたときのrelative serializabilityはCSRと一致する。 --- ここで、相対的にserialでないスケジュールでも、不可分単位の間に割り込んでいる依存関係を持つステップを、不可分単位の後に押し出したり前に引き込んだりする可換操作によって相対的にserialにしうる。この概念を定式化する。 ### 定義：Push Forward & Pull Backward 不可分単位内のステップ $p_i\in IU_k(t_i, t_j) \ (p_i\in t_i)$ に対し、 1. $F(p_i,t_j)$ を $IU_k(t_i, t_j)$ の最後のステップとする。(Final) 2. $B(p_i,t_j)$ を $IU_k(t_i, t_j)$ の最初のステップとする。(Beginning) ### 定義：Relative Serialization Graph (相対逐次グラフ) $s$をスケジュールとする。相対逐次グラフ $RSG(s)=(V,E)$ を、頂点集合 $V=op(s)$ とし、辺集合を以下の4種類から定義する。 1. $p$ と $q$ が同じトランザクション内の連続する操作なら$(p,q)\in E$ (内部辺/I辺) 2. 異なるトランザクションの操作 $p,q$ が $p\rightsquigarrow^* q$ なら $(p,q)\in E$ (依存辺/D辺) (要はI辺と衝突関係を推移的に経由した辺) 3. $(p,q)$ がD辺で $p\in t_i, q\in t_j$ なら、$(F(p,t_j),q)\in E$ (押し出し辺/F辺) 4. $(p,q)$ がD辺で $p\in t_i, q\in t_j$ なら、$(p,B(q,t_i))\in E$ (引き込み辺/B辺) --- ### 補題3.3 $s$が相対的にserialであるとき、$RSG(s)$は閉路を持たない。 #### 証明まず、$(p,q)\in E \Rightarrow p<_s q$を示す。辺の種類で場合分けする。 - I辺については、トランザクション内の連続する操作なので$p<_t q$であり、スケジュールの定義より$p<_s q$。 - D辺については、異なるトランザクションで間接的に依存関係にあるので、$<_t$と衝突関係を推移的に経由するので、こちらもスケジュールの定義より$p<_s q$。 - F辺については、$(r,q)$ s.t. $q\in t_j, r=F(p,t_j),\ r,p\in t_i$ で $(p,q)$がD辺という形を考える。このとき、$p,r\in IU_k(t_i,t_j), p<_s r$であり、$r$が$IU_k(t_i,t_j)$の最後の操作となる。$p\rightsquigarrow^* q$ であることと$s$が相対的にserialであることから、$q$は$IU_k(t_i,t_j)$の終了後に現れる。したがって$r<_s q$である。 - B辺についてもF辺と同様である。$\square$ 以上の補題を用いて以下の定理を示せる。相対的なserializability theorem。 --- ### 定理3.18 スケジュール$s$が相対的にserializable $\Longleftrightarrow$ $RSG(s)$が閉路を持たない #### 証明 $\Longrightarrow$ $s$と衝突同値で相対的にserialな$s'$を考える。$RSG(s)=RSG(s')$を示せば、補題3.3より十分である。 2つのグラフの4種類の辺が全て等しいことを示す。 - I辺については定義から同じである。 - D辺については、スケジュール間の衝突同値性とI辺が等しいことから等しい。(I辺と衝突関係を推移的に経由した辺がD辺のため) - F辺とB辺については、D辺と不可分単位に依存しており、不可分単位は$s$と$s'$に共通であるため等しい。以上から$RSG(s)$は閉路を持たない。 $\Longleftarrow$ $RSG(s)$が閉路を持たないと仮定する。このときそれをトポロジカルソートしたスケジュール$s'$を得ることができる。$s$と$s'$は衝突同値であり、したがって先ほど示したようにRSGは等しく$RSG(s)=RSG(s')$である。このとき$s'$が相対的にserialであることを示せば十分である。 $s'$が相対的にserialでないと仮定する。すると、ある不可分単位に割り込む操作が依存関係を持っている。つまり、ある$q\in t_j$が$IU(t_i,t_j)$の間に現れ、ある$p\in IU(t_i,t_j)$と$p\rightsquigarrow^* q$もしくは$q\rightsquigarrow^* p$である。$r$を$IU(t_i,t_j)$の最後の操作とする。$p\rightsquigarrow^* q$の場合、$RSG(s)$でF辺$(r,q)$が存在する。したがって、$RSG(s)$の任意のトポロジカルソートで$r<q$が成立する。しかしながら$s'$では、$q$が$IU(t_i,t_j)$に割り込んでおり、その最後の操作が$r$であることから$q<r$であり、これらが矛盾する。$q\rightsquigarrow^* p$の場合も同様に示せるため、$s'$は相対的にserialである。$\square$ --- $RSG(s)$の構築は$op(s)$に対する多項式時間で実行可能であり、閉路の存在判定も同様なので、相対的なserializabilityの判定も多項式時間で行うことができる。