18章-1 ホモジニアスなトランザクション

###### tags: `TransactionalInformationSystems` # 18章-1 ホモジニアスなトランザクション ## 概要第3部までは、データサーバは単一、すなわち全てのデータが一箇所に集中している状況を想定して同時実行制御や回復を考えてきた。現在ではその仮定は成立しづらく、大規模なアプリケーションでは複数のサーバにデータが分散されていることが普通である。第4部では、そのような分散アーキテクチャでの同時実行制御と回復を考える。 18.2では**ホモジニアス**な分散アーキテクチャでの同時実行制御プロトコルを考える。18.3では、デッドロックの回避法についていろいろなアプローチを検討する。どちらも単純のためにページモデルで考えるが、オブジェクトモデルにも適用できる。ここでホモジニアスとは、複数のサーバが同一のプロトコルを動かしてorマスターのもとに制御され、論理的には単一のシステムであるような分散システムである。この性質から、ユーザから見たときには単一のサーバに見える。よってどのサーバにリクエストを送るかとか考える必要がなく、いわば**分散性が透明**である。ホモジニアスなシステムでのトランザクションの制御は単一サーバとかなり似ているが、ただしトランザクションが複数のサーバをまたがって実行される（**グローバル**）ことに起因する難しさは発生する。 18.4で**ヘテロジニアス**な分散アーキテクチャでのスケジュールの正当性を考える。ヘテロジニアスとは、各サーバが自律的に動作し、単一のサーバ上で動くローカルなトランザクションと複数サーバをまたがるグローバルなトランザクションが混在するシステムである。CSRの概念を拡張するのだが、グローバルなトランザクションだけを見るとserializableでも、ローカルなトランザクションも加えて考えると間接的な衝突が発生するケースがある。 18.5ではこの正当性を実現するにはどうすればいいのか考察する。実のところ、RGやCOCSRのようなルールを各サーバが個別に守るだけでグローバルな正当性が保証されることが分かる。 18.6では、これを踏まえてヘテロジニアスな同時実行制御プロトコルを考える。重要なポイントは、ローカルな衝突をグローバルな観点から観測可能にすること。いわゆる「チケット」というテクニックを使う。 18.7では、オブジェクトモデルのように一般的な操作をサポートするトランザクションへの拡張を考える。 18.8ではデータ共有クラスタでの一貫性維持・同時実行制御を考える。 ## 18.2 ホモジニアスな分散システムでのCC ### 準備知識データが定数個の箇所に分散配置されており、$1\leq i \leq n$番目のサーバがデータの集合$D_i$を保存している。データベースの全体は$D=\cup^n_{i=1}D_i$で表される。単純のため、データは複製されないものとする（各データは単一のサーバにしか存在しない）。全てのトランザクションはグローバル、すなわち複数のサーバにアクセスする可能性がある。全てのサーバが、システムに属する他サーバの情報と各データの位置についての知識を持つと仮定する。受け取った操作を各サーバからローカルな観点で見たとき、それ自体でローカルなトランザクションとみなすことができ、そのようなローカルなトランザクションの組み合わせでサーバごとのローカルなスケジュールが考えられる。一方、serializabilityについて考えるときには、これらを統合したグローバルなトランザクションとして見る必要がある。以下の定義を得る。 --- #### 定義：グローバルな履歴グローバルなトランザクションの集合を$T=\{t_1,\ldots,t_m\}$とし、これらによって生成されるローカルな履歴を$s_1,\ldots,s_n$とする。 $s$が$T$と$s_1,\ldots,s_n$の「グローバルな履歴」であるとは、$s$のローカルな射影が$s_i$と一致する、すなわち$\Pi_i(s)=s_i$が成り立つこととする。 --- 本章ではトランザクションが全て成功すると仮定する。ただし、一般にグローバルなトランザクションが終了するときには、それがアクティブな全サーバでcommitを実行する必要があることに注意。ここでグローバルな履歴の正当性としてconflict serializabilityが改めて定義される。これをローカルなconflict serializablityと区別して**global serializability**と呼ぶ。 --- #### 定義：Conflict Serializability グローバルな履歴$s$がglobally conflict serializableとは、serialなグローバル履歴が存在して$s$と衝突同値であることとする。ローカルな履歴$s$がlocally conflict serializableとは、serialなローカル履歴が存在して$s$と衝突同値であることとする。 --- グローバルなスケジュールを制御するにあたって、**とりあえず各サーバで同じCCアルゴリズムを走らせ、ローカルなスケジュールをCSRにすることを考える**。**ただし、これだけではグローバルなスケジュールはCSRにならない**。なぜなら、あるサーバでは$t\rightarrow t'$というserial順に、他のサーバでは$t'\rightarrow t$という順に制御してしまう可能性があり、グローバルで見ると衝突のサイクルが発生するから。例えば、サーバ1でデータ$x$、サーバ2でデータ$y$を受け持っており、グローバルなスケジュール$s=r_1(x)r_2(y)w_2(x)w_1(y)$を考えたとき、サーバ1で走るローカルトランザクションは$r_1(x)w_2(x)$、サーバ2で走るローカルトランザクションは$r_2(y)w_1(y)$で、それぞれserialなので、各サーバ上のスケジューラはこのスケジュールを許容してしまう。ただ、グローバルで見ると$t_1$と$t_2$の衝突サイクルがあるので不正。 --- ### 定理18.1 グローバルな履歴$s$に属するローカルな履歴を$s_1,\ldots,s_n$とする。$s_i\in CSR~(1\leq i\leq n)$であるとき、以下の条件が成り立つ。 $s$がglobally conflict serializable $\Longleftrightarrow$ トランザクション集合$T$上の全順序関係"<"が存在し、ローカルなserialization順に矛盾しない。 #### 証明 $(\Leftarrow)$ 全順序が存在するが$s$がglobally conflict serializableでないと仮定する。このとき$s$は衝突サイクルを持ち、$t_1<t_2<\cdots<t_m<t_1$となって全順序であることに矛盾。 $(\Rightarrow)$ $s$がglobally conflict serializableであるとき、全順序$<_s$が存在して、任意のトランザクションの組$t,t'$について$t<_st'$もしくは$t'<_s t$が成り立つ。$t<_s t'$を仮定すると、任意のローカル履歴$s_j$におけるserial順で$t$が$t'$の前に来なければならず、全順序$<_s$が条件を満たす。$\square$ --- したがって、このようなトランザクション間の全順序を確立できさえすれば、各サーバでローカルに走るCSRプロトコルでCCを実現できることになる。 ### 分散2PL ここまでの考察を踏まえて、2PLをホモジニアスなシステムに拡張する。各サーバがローカルに2PLを走らせる。つまり、自身が管理しているデータアイテムについて、操作前に排他ロックを取得させ、操作終了後、ロックの解放フェーズに移行し次第、ロックを解放させる。ただし、**ロックの解放フェーズに移行するタイミングは、そのトランザクションが走っているサーバすべてで統一する必要がある**。（あるサーバでロックの解放を始め、他のサーバでは新たにロックを取得するとserializabilityを破壊する）具体的にロックの解放フェーズ統一をどう実現するかでバリエーションが生まれる。 #### プライマリサイト2PL 各データ・トランザクションのロックに関する情報を、全て一つのサーバでまとめて管理する方法。プライマリサーバがグローバルな知識を持っているので自明に制御できるが、プライマリサーバにアクセスが集中するので分散システムの意味が薄い。 #### 分散2PL(D2PL) 各サーバが情報を交換して解放タイミングを強調するプロトコルで、方式は2つ挙げられる。どちらにせよ、サーバ間の情報交換によるオーバヘッドが発生する。 - 各サーバのスケジュールに関する情報をすべてのサーバが持つ。このために常に情報をやり取りする必要があり、コミュニケーションコストが大きい。 - 各サーバは、トランザクションのロックを解放したくなったタイミングで他のサーバに情報を問い合わせ、解放してもいいか確認する。 #### Strong 2PL(SS2PL) 全てのロックがトランザクションのcommitまで保持されるSS2PLを用いれば、おのずとグローバルな解放タイミングの統一が実現される。CSR性だけでなくST性も保証される。 2PLはデッドロックを防げないので、解消のために工夫が必要になる。これは後に考える。 --- ### 分散TO 次はTimestamp ordering（TO）の拡張を考える。 > （復習）各トランザクションにタイムスタンプを割り当て、衝突する操作はタイムスタンプ順に実行されなければならない（逆順になってしまったらabortする）のがTO。とりあえず各サーバで別個にTOを走らせ、めいめいに自由にタイムスタンプを割り当ててしまうとserializabilityが破壊される。例えば、$s=r_1(x)r_2(y)w_2(x)w_1(y)$ では、$x$を持つサーバでは$t_1$に最初のタイムスタンプを、$y$を持つサーバでは$t_2$に最初のタイムスタンプを与えてしまうのでグローバルな視点では矛盾する。したがって、グローバルなタイムスタンプを各トランザクションに割り当てる方法が肝要である。2つの方式（中央集権型と分散型）が考えられる。 - 中央集権型：特定のサーバがタイムスタンプの割り当てに責任を持つ。このサーバへの負荷が大きい。 - 分散型：各サーバが自身で生成したローカルなタイムスタンプと、サーバ識別子を組み合わせてグローバルなタイムスタンプを生成し、他サーバへ通知する。例えば、サーバ$j$がローカルなタイムスタンプ$ts(t_i)$を生成したとき、グローバルなタイムスタンプは$(ts(t_i),j)$ となる。これを辞書順で比較することでトランザクション間を順序付ける。ここでは、分散システムにする意味を踏まえて分散型のタイムスタンピングを採用する。 #### Lamport clock カウンタに基づいていて、かつタイムスタンプの生成があるサーバに偏ると、そのサーバのタイムスタンプは常に他のサーバのものよりも大きくなってしまう。このような問題を解決するために、非同期ネットワークでの論理的な時間の概念を確立させる。そのようなテクニックの一つがLamport clock(ランポートクロック)である。各操作ステップの論理的な時間を$(c,i)$で定義する。ここで$c$はカウンタの値であり、0からスタートしてトランザクションの操作、もしくは他サーバとの送信/受信の度にインクリメントされる値であり、これによってサーバ間の時間を同期する。同じカウンタの値で実行された操作どうしは、トランザクション番号$i$で順序付けることにする。トランザクションの各操作が単調増加なクロックを割り当てられ、また各トランザクションは$i$で区別されるため、論理的な時間は一意に定まることが分かる。 ### その他のプロトコル(分散SGT、楽観的なプロトコル) 衝突グラフをリアルタイムに維持するSGTを分散型にしたプロトコル、分散SGTは、グローバルな衝突グラフを保持するのが難しいので現実での実用化がされていない。楽観的なプロトコルのFOCCやBOCCも、検証フェーズが全サーバのアクセスを必要とすることが大きなオーバヘッドになるため深く追求しない。 ## 18.3 分散デッドロック検出分散2PLを使った場合、デッドロックを検出して適切なトランザクションのロックを解放することが重要な問題になる。ここで注意するのは、ホモジニアスなシステムにおけるデッドロック(待機グラフにおける閉路の生成)は <div style="text-align: center;"> $t_1$が$t_2$のリソース$x$のロック解放を待つ →$t_2$が$t_3$のリソース$y$のロック解放を待つ →$t_3$が$t_1$のリソース$z$のロック解放を待つ </div> という形で起こること。図で示すと以下。 ![](https://i.imgur.com/rwApryn.png) つまり、サーバ内のローカルなロック待機とトランザクションのサーバ間メッセージの待機を交互に繰り返した結果の閉路となる。 ### 中央監視デッドロックを監視する専門のサーバを設ければ容易に解決はするが、これは全体のボトルネックとなる上、情報を集積する間に時間の遅延が生じることによってデッドロックの誤検出が起こる。ただし、各トランザクションの自発的なabortを禁止すれば以下が成り立つ。 --- #### 定理18.2 デッドロックを中央監視しているとき、各スケジューラが2PLを走らせていて自発的にabortしなければデッドロックの誤検出は起こらない。 --- とはいえ、最悪全サーバ間とコミュニケーションしなければならないのはつらいので、トランザクションを実行するサーバ自身が待機グラフを利用して解決するようにしたい。 ### タイムアウトサーバがブロックされてから一定時間実行されなかったらタイムアウトしてトランザクションをabortする方法。これは分散型でも全く同様に実装できるわけだが、タイムアウト時間の設定が難しい。サーバ間コミュニケーションのオーバヘッドがあるからなおさら。 ### 辺追跡各トランザクションは、自身がブロックされたときに、欲しいリソースを持っているトランザクションへ「プローブ」を送信する。プローブにはトランザクション識別子を載せておく。プローブを受信したトランザクションは、それをそのまま自身をブロックしているトランザクションに転送する。これが繰り返された結果、自身の識別子を持つプローブを受信したとき、待機グラフにおける閉路が生じていることが分かる。 ### パス転送辺追跡アルゴリズムでは、プローブを最初に送信したトランザクションの識別子だけが情報として使われていたが、これをより精細にする。具体的には、開始点から現在の点までの待機グラフ上のパスを記録することで、abortするトランザクションの選択を柔軟に行えるようにする。基本的な手順は以下。 1. $\cdots\rightarrow (t_i\rightarrow \cdots \rightarrow t_j) \rightarrow \cdots$ という待機関係があるとき（括弧内はサーバ内のリソース待機、外はメッセージ待機）、$t_i$の識別子が$t_j$のそれよりも小さいなら、サーバは$t_j$から出る辺に向けてこのパスを送信する。 2. サーバがパスを受け取ったとき、既に持っているパスとそれを統合し、出る辺に向けて送信し直す。閉路があればここで検出される。識別子の比較で送信するかどうか決めるのは、同じ閉路について何度も冗長に検出されるのを防ぐため。