18章-2 ヘテロジニアスなトランザクション

###### tags: `TransactionalInformationSystems` # 18章-2 ヘテロジニアスなトランザクション ## 18.4 ヘテロジニアスな分散システムにおけるserializability たとえば多数の国にまたがるサーバ群を考えたとき、大抵のトランザクションはある国の中だけで完結するはずであり、必ずグローバルなプロトコルのもとに実行される必要がない。このようなトランザクションのローカルな実行をサポートし、それでいて必要なときにはグローバルな実行も可能なのがヘテロジニアスなシステムである。ホモジニアスなシステムは全てグローバルなトランザクションから構成される一方、ヘテロジニアスなシステムは、それにローカルなトランザクションという概念を組み込むことで実現される。この際、ローカルなトランザクションによって間接的に引き起こされるグローバルな衝突の検出が一つの問題である。また、各サーバが自律的に動ける必要があるため、障害回復において他サーバとのコミュニケーションに頼れないのも厳しい要求になる。 ### ローカル/グローバルなトランザクションサーバ群とそれらが持つデータの定義はホモジニアスなシステムと同じ、$D=\cup^n_{i=1}D_i$。このとき、ある$D_i$のデータアイテムにしかアクセスしないトランザクションを「ローカル」と呼び、それ以外のものを「グローバル」と呼ぶ。グローバルなトランザクションは操作をGTM(Global Transaction Manager)に送信する。各サーバ上ではLTM(Local Transaction Manager)がローカルに走り、そこへGTMが操作を分配する。また、LTMはそれ自身で自律的にローカルなトランザクションを実行管理する。 --- ### 定義：グローバルな履歴 $T_1,\ldots,T_n$を各サーバにおけるローカルなトランザクションの集合、$T$をグローバルなトランザクションの集合とする。また、$s_1,\ldots,s_n$ を $T_i\subseteq trans(s_i)\land T\cap trans(s_i)\neq \emptyset$ を満たすローカルな履歴とする。ここで、グローバルな履歴$s$とは、トランザクション集合 $\cup^n_{i=1}T_i\cup T$ に対する履歴で、各サーバへの射影がローカルな履歴に一致する、すなわち $\Pi_i(s)=s_i$ を満たすものとする。 --- ### 間接的な衝突サイクル $D_1=\{a\},\ D_2=\{b,c\},\ t_1=r(a)w(b),\ t_2=w(a)w(c),\ t_3=r(b)w(c)$ を考える。このとき、$t_3$はローカル、$t_1,t_2$はグローバルなトランザクションである。$t_1,t_2$はGTMがserialに送信、$t_3$はサーバ2のLTMが独自に管理した場合、以下の履歴が生じうる。 $$s_1=r_1(a)\qquad \qquad w_2(a)\qquad \qquad $$ $$s_2=\qquad r_3(b)w_1(b)\qquad r_2(c)w_3(c)$$ グローバルにみると$t_1\rightarrow t_2$の順で実行されていてserialに見えるし、ローカルな履歴もそれぞれCSRなので大丈夫に見えるのだが、実際には衝突のサイクル$t_1\rightarrow t_2\rightarrow t_3 \rightarrow t_1$が生じてしまっている。これは、ローカルなトランザクション$t_3$により、GTMから観測できない間接的な衝突$t_2\rightarrow t_3, t_3\rightarrow t_1$が生まれてしまったためである。このような衝突を避けるため、グローバルなトランザクションは、たとえ直接の衝突が無くても、各サーバでの相対的な実行順を揃える必要がある。また、GTMによって送信されたグローバルトランザクションの操作は全てその順番で実行されるものと仮定する。これはサーバ間のメッセージングで実現する。 --- ### グローバルなserializability #### 定義：直接/間接衝突 $s_i$をローカルな履歴、$t,t'$を $trans(s_i)$に属するトランザクションとする。 1. $t$と$t'$が$s_i$で直接衝突しているとは、ある$p\in t, q\in t'$が存在して$(p,q)\in conf(s_i)$であることとする。 2. $t$と$t'$が$s_i$で間接衝突しているとは、あるトランザクション列 $t_1,\ldots, t_r$ が存在して $(t,t_1),(t_1,t_2),\ldots, (t_{r-1},t_r),(t_r,t')$ がそれぞれ直接衝突していることとする。 3. $t$と$t'$が衝突しているとは、$t,t'$が直接衝突あるいは間接衝突していることとする。間接衝突しているトランザクション同士は可換であることに注意。 #### 定義：グローバル衝突グラフ $G(s_i)$を各ローカル履歴の衝突グラフとする。$s$のグローバル衝突グラフとは、これを全て合わせたもの $G(s)=\cup_{i=1}^nG(s_i)$ と定義する。以下で示すように、$G(s)$の非閉路存在性と、グローバルなconflict serializabilityは等価である。 --- #### 定理18.3 $s_1,\ldots, s_n$ に対し、$G(s_i)$ がそれぞれ閉路を持たないとする（$s_i\in CSR$）。$s$を、$s_1,\ldots,s_n$のグローバルな履歴とする。このとき、 $s$がglobally conflict serializable $\Leftrightarrow$ $G(s)$が閉路を持たない ##### 証明 ($\Rightarrow$) $G(s)$が閉路を持たないと仮定する。このとき、$G(s)$をトポロジカルソートすることでトランザクション間の全順序を得る。したがって、$s$に属するcommitされたグローバルトランザクションはすべて、ローカル履歴$s_i$内でも同じ順にserializeされる。任意の$t<t'$を満たす組に対して、各$s_i$に衝突同値なserial履歴$s_i'$が存在して$t<_{s_i'}t'$を満たす。よって$s$はglobally conflict serializable。 ($\Leftarrow$) $s$がglobally conflict serializableであるが、$G(s)$が閉路を持つと仮定する。一般性を失わず閉路の長さを2とする。仮定からローカル衝突グラフ$G(s_i)$はそれぞれ閉路を持たないことと合わせて、異なるローカル履歴$s_i,s_j$と異なるトランザクションの組$t,t'$が存在して、$G(s_i)$は辺$(t,t')$を持つ一方$G(s_j)$は辺$(t',t)$を持つ。これは定理18.1に反するため矛盾。$\square$ --- 18.5節でグローバルなserializabilityを実現するための方法を考えるが、その前に、**衝突同値性以外の正当性基準**を軽く見ていくことにする。 ### Quasi serializability グローバルなserializabilityは並列性を下げ、また多くのトランザクションをabortしてしまう。パフォーマンスを改善するため、実行順の制御を緩めたい。「準逐次的」な履歴を、次のように定義する。ローカル履歴の集合$\{s_1,\ldots,s_n\}$が準逐次的 $\Longleftrightarrow$ $s_i\in CSR~(i=1,\ldots,n)$ かつ、全順序<が存在して、任意のローカル履歴$s_i$において、「$t_i < t_j~(i\neq j, t_i,t_j\in T)$ $\Rightarrow$ $t_i$のローカルサブトランザクションが$t_j$のそれの開始前に終了する」が成り立つ > 訳注：quasi serialを準serialはダサすぎたので「準逐次的」にします。ここからはserialも「逐次的」にしたいと思います。というかcommitとabortも平文中に出てきたときは普通にコミット・アボートと呼ぶことにします。つまり、**間接的に衝突しているグローバルなトランザクション同士には既に全順序が確立されており、グローバルなスケジューラから見てそれ以上の並び替えが必要ないこと**を要求する。それに加えてローカルにCSRを保証しさえすれば、完全ではなくても準逐次的とでも呼べる状態だ、という主張がこの正当性である。そこで、ローカルな履歴集合 $(s_1,\ldots,s_n)$ について、準逐次的なローカル履歴集合 $(s_1',\ldots,s_n')$ が存在して $s_i\approx_c s_i'~(i=1,\ldots,n)$ であることを quasi serializability と定義する。これはグローバルな履歴にも拡張できる。すなわち、$s$がquasi serializableとは、$\{\Pi_1(s),\ldots,\Pi_n(s)\}$がquasi serializableなことと定義できる。 globally serializableならquasi serializableだが、その逆は言えない。 quasi serializabilityは比較的達成が容易である。トランザクションを受け取ったGTMは、単にそれを逐次的に、一つの操作が終わったことを確認したら次の操作を、というように実行すればよく、LTMは他サーバとの協調を気にせず自身のCSR性を保証していればよい。ただし、ローカルなトランザクションも含めたグローバルな逐次実行順はついぞわからないため、global serializabilityは保証されない。そのためここではこれ以上追求しない。 ## 18.5 Global Serializability の実現方法ここから、GTMにローカルサーバについての知識を追加で持たせることで実現できるアルゴリズムについて考えていく。ローカルサーバがローカルなCSR性を維持してくれることは前提とする。 ### Rigorousness ローカルスケジューラが、ローカル履歴のCSRだけでなくRGを保証すると仮定する。（11章-2でやった通り、SS2PLはRGを保証する） RGの定義を復習すると $$(\forall t_i, t_j \in trans(s)) \\ p_j(x) <_s q_i(x), i\neq j,\ p, q \text{ in conflict }\Rightarrow a_j <_s q_i(x) \lor c_j <_s q_i(x)$$ （衝突する操作は前者のトランザクションの終了を待って実行される） RGはglobal serializabilityを保証する大きな足掛かりになるが、**各サーバでローカルにRGを保証するだけでは不十分**である。なぜなら、以下の例のようにローカルの逐次実行順が矛盾する場合が生じるから。 --- $D_1=\{a,b\},\ D_2=\{c,d\}$、グローバルトランザクションが $t_1 = w(a)w(d),\ t_2=w(c)w(b)$、$t_3,t_4$ がローカルトランザクションとする。 $$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$$ ローカルではどちらもRGが満たされている（どころか逐次的ですらある）のだが、$t_1\rightarrow t_3 \rightarrow t_2 \rightarrow t_4\rightarrow t_1$ という衝突サイクルが生まれてしまっている。原因は$t_1$と$t_2$の逐次実行順が$s_1$と$s_2$で逆であること。 $s_1$だと$t_1\rightarrow t_3\rightarrow t_2$ $s_2$だと$t_2\rightarrow t_4\rightarrow t_1$ --- #### 定義：コミット保留トランザクショングローバルトランザクション$t$がコミット保留されているとは、$t$のデータ操作すべてがローカルサーバに承認されたあとにのみ、GTMがコミット操作を各サーバに送信することとする。 GTMがコミット保留を行うようにすれば、ローカルのRG性と合わせてついに目標が達成される。 #### 定理18.4 $s$ を $s_1,\ldots,s_n$ のグローバル履歴とする。 $s_i\in RG~(i=1,\ldots,n)$ かつ全てのグローバルトランザクションがコミット保留されるなら、$s$はglobally serializable である。 ##### 証明定理18.3より、$G(s)$が閉路を持たないことを示せばよい。そこで、$G(s)$が閉路を持つと仮定して $(t_1,\ldots,t_k)~(t_k=t_1)$ とする。$s_i\in RG\subset CSR$ であることから各$G(s_i)$は閉路を持たず、$G(s)$の閉路は複数のローカル衝突グラフ$G(s_i)$のパスから構成される。$(t_j,t_{j+1})$が$G(s_j)$に含まれると仮定する。RG性から$c_j<_{s_j} c_{j+1}$である。すなわち$s_1$では$t_1$が$t_2$よりも先にコミットし、・・・、$t_{k-1}$が$t_1$よりも先にコミットされることになって矛盾。閉路の形状が異なってもコミット順に矛盾が生じるという本質は同じ。$\square$ --- ### コミット順制御次に、COCSRを利用したglobal serializabilityのための十分条件を与える。ローカルサーバでCOCSRを保証するだけでもやはり不十分である。追加条件として、GTMはあるグローバルトランザクションのコミット中は他のトランザクションのコミットを開始してはならない。 --- #### 定理18.5 $s$ を $s_1,\ldots,s_n$ のグローバル履歴とする。 $s_i\in COCSR~(i=1,\ldots,n)$ かつ、グローバルトランザクションのコミット順がサーバ間で統一されていれば、$s$はglobally serializable。$s\in COCSR$ も言える。 --- 逆も成り立つ。つまり $s\in COCSR \Rightarrow \Pi_i(s) \in COCSR$。 COCSRがグローバルトランザクションのみに要求されているケースにもこれは拡張できる。 #### 定義：拡張コミット順 $s$が extended commit order preserving conflict serializable とは、任意のグローバルトランザクションのペア$t_i,t_j$に対し、$t_i\rightarrow t_j$の順で衝突するならば$c_i<_s c_j$が成り立つこととする。そのような履歴のクラスを$ECOCSR$とする。 COCSRの条件がグローバルトランザクションのみに適用されるため、 #### 系18.1 $COCSR\subset ECOCSR$ ## 18.6 チケットベースの同時実行制御前節の議論から考えると、global serializabilityを保証する第一の方法は、ローカルでRG性 or COCSR性を担保しつつ、GTMのコミット順を少し工夫することである。その一方、ローカルが満たさなければならない条件をCSRに緩めつつ、global serializabilityを保証できる軽量な手法としてチケットベースの手法を導入する。 ### 明示的なチケット GTMが抱える問題はローカルなトランザクションを媒介として起こる間接的な衝突を観測できないため、いつ操作をLTMに送信すればよいのか分からないということ。したがって、そのような間接的な衝突を観測可能な直接的な衝突に変換するというアイディアが生まれる。例えば、$t_1$と$t_2$が間接的に衝突して困っているなら、**$t_1$がアクティブなサーバの全てで特殊なデータアイテムに書き込みを行い、$t_2$では$t_1$と同時にアクティブになったサーバでそのデータアイテムを必ず読み込むことを要求してみる**。すると、$t_1\rightarrow t_2$という逐次実行順はローカルなスケジュールでも強要されるため、間接的な衝突に起因するサイクルを予防できる。グローバルトランザクションが必ずしもシーケンシャルに実行されないケースでもこの手法は適用できる。このような**グローバルトランザクションの実行制御に利用されるデータアイテムを**「**チケット**」と呼ぶ。グローバルトランザクションの各サーバにおけるサブトランザクションは必ずtake-a-ticketという操作を行い、チケットを読み込んでインクリメントして書き戻す。チケットはグローバルトランザクションの逐次実行順を示す論理的なタイムスタンプとしても機能する。なお、チケットを取るタイミングは実行中の任意の時点で良い。他のトランザクションと比較して先に取ったかどうかに基づいて逐次実行順が決定される。 --- #### 定理18.6 あるサーバで、グローバルトランザクション$t_1$がグローバルトランザクション$t_2$よりも先にチケットを取るなら、そのサーバ上では$t_1\rightarrow t_2$という逐次実行順になる。 ##### 証明チケットへの読み書きを$r(I),w(I+1)$と表記する（書き込み時にはインクリメントするためI+1）。あるサーバで$r_1(I)<r_2(I)$だったとき、チケット読み書きの順番は以下のいずれかになる。 - $s_1= r_1(I)r_2(I)w_1(I+1)w_2(I+1)$ - $s_2= r_1(I)r_2(I)w_2(I+1)w_2(I+1)$ - $s_3= r_1(I)w_1(I+1)r_2(I)w_2(I+1)$ これらのスケジュールの中で唯一$s_3$がserializableである。したがって、ローカルサーバがスケジューラでserializabilityを保証しているなら必ず$s_3$のようになり、$t_1$がチケットをインクリメントし終わった後に$t_2$がチケットを読みこむ。このチケットの読み書きは$t_1\rightarrow t_2$という直接的な衝突を引き起こしているため、逐次実行順をそれに定める（他に逆順の衝突が存在したら、閉路の存在によりスケジューラが実行を抑止する）。$\square$ --- このままではチケットを取る順番が閉路を作ったときにserializabilityに反してしまうため、各サーバでチケットを取る順番に関する何らかの制御が必要になる。まず挙げられるのは、サブトランザクションを基本的にはそのまま実行し、コミット時にコミットしても大丈夫か検証する楽観的な手法（Optimistic Ticket Method, OTM）。GTMは**チケットグラフ**を保持し、各サーバでのチケット取得順を辺にする。あるトランザクションのコミット時に、それを巻き込む閉路が生じていたらアボートする必要がある。 OTMはチケット取得順を一切操作しないため、アボートのコストが大きいし、デッドロックを生じる可能性もある。そこで、チケット取得順をサーバ間で同じになるように制御する、より保守的な手法（Conservative Ticket Method, CTM）も考えることができる。 ### 暗黙的なチケットチケット法はローカルサーバのCSR性のみを前提として求めていた。こうすると、グローバルトランザクションでチケットを取得するというだけでは十分でなく、チケットグラフの監視やチケット取得順の制御が必要だった。では、CSRよりももう少し強い性質が保証されていたとき、それを利用してチケット法に活かせないか？実のところ、CSRかつACA(Avoiding Cascading Aborts, 11章1参照) でさえあれば、GTM側でチケットグラフを保持したりチケット取得順を管理したりする必要がなくなるということが分かっている。（復習：ACAはコミットされる前のデータアイテムを読み込まないという条件） --- #### 定理18.7 ヘテロジニアスシステムの各サーバが、自身のローカルスケジュールについてCSRかつACAを保証していて、かつすべてのグローバルトランザクションが各ローカルサブトランザクションでチケットを取得していたとき、生成される履歴はglobally conflict serializableである。 ##### 証明定理18.6より、チケット取得順はローカルでの逐次実行順を反映している。したがって、あと示すべきは、「複数のサーバ間で矛盾する逐次実行順に起因して衝突サイクルが発生したとき、それが少なくとも一つのサーバ上のローカルな閉路として検出されること」である。 $t_i$と$t_j$がグローバルな閉路に巻き込まれていて、サーバAでは$t_i\rightarrow t_j$という順に、サーバBでは$t_j\rightarrow t_i$という順にチケットを取得していた場合を考える。ACA性から、Aでは$t_j$は$t_i$がコミットされるまでチケットを読み書きできないし、Bではその逆である。これは、$t_i$のグローバルコミットが$t_j$の先かつ$t_j$の後という不可能な状況になって矛盾する。このことから、閉路はどちらかのサーバ内でローカルに発生していなければならない。$\square$ --- 多くのスケジューラはACAを自然と保証できているので、定理18.7の方式は非常に実用的である。この方法ではGTMレベルでのチケットグラフ管理が必要ないので、暗黙的なチケット法と呼ばれる。 ### 明示的なチケットと暗黙的なチケットの併用実際の分散システムにおいては、サーバごとに異なるレベルの正当性(CSR, COCSR, RG, ...)のもとで走っていることが多い。これらを統合するにあたっては、最大公約数的にCSRに合わせるのでなく、各サーバに合わせて異なるレベルのチケット法を採用することでパフォーマンスを最適化できる。**チケット法の魅力は、実装が簡単というだけでなく、このように正当性レベルに合わせて柔軟に方式を使い分けられる点にある**。すなわち、 - CSRしか保証していない最弱のサーバ群についてだけチケットグラフを管理すればよく、 - RGやCOCSRを保証していない次弱のサーバ群についてはtake-a-ticket操作を強制すればよく、 - RGやCOCSRを保証している最強のサーバ群についてはそもそもチケットが必要ない。残る懸念事項は、各プロトコルにおいてチケットを取得するタイミングである。例えば、TOを採用しているサーバにおいて、$ts(t)<ts(t')$となったのに、$t'$のチケットが先に取得された場合、$t$は不正となってアボートされてしまう。なので、**TOにおいてはタイムスタンプの発行タイミングとできるだけ近いタイミングでチケットも取得する**ことが推奨される。ちなみに、TOをこのようにして用い、かつGTMがトランザクションの送信を前のものとのタイムスタンプが明確に順序付けられるまで待つようにすれば明示的なチケット管理が必要なくなる。