###### tags: `TransactionalInformationSystems` # 7章 オブジェクトモデルにおけるConcurrency Control ## 概要 前章で定義した削減可能性に基づき、実用的なCCアルゴリズムを考えていく。 最初に階層的なスケジュールにフォーカスする。正当性の保証は、出力スケジュールが前章で定義した木削減可能性を満たすことによる。これは、層間スケジュールをそれぞれ従来のページモデルスケジューラで制御し、それを組み合わせることで実現できる。特に一般的なのは2PL。 さらに、層をまたいでロックを保持する概念を発展させることで、一般のオブジェクトモデルに対するスケジューラも考える。ただしこちらは複雑な機構を必要とし、性能面での問題が大きい。 可換性については、オブジェクト・層ごとに表の形で与えられると想定する。基本は状態に依存しない可換性の下で議論し、最後の節でのみ返り値可換性を考える。 ## 平坦なトランザクションに対するロック 同一のオブジェクトに対する操作の可換性テーブルは、そのままロックの競合可能性と解釈できる。 すなわち、可換な操作同士であれば同時にロックをかけることができ、また非可換な操作であれば排他ロックになる。 異なるオブジェクトへの操作は表に関係なく可換とみなせる。 このような、ページモデルと類似の発想から得たロックに基づいて、平坦なオブジェクトモデルスケジュールはページモデルと全く同様に制御することができ、2PL,S2PL,SS2PLなどが使える。 ## 階層的なロック 階層的なスケジュールを木削減可能にするための良い手段は、各層間スケジュールをそれぞれOCSRにしてしまうこと。そこで、各層に対し2PL or S2PL or SS2PLを適用することを考える。 $n$層スケジュールに対する層化2PLを以下の規則で与える。 1. ロック獲得規則：$L_i$の操作$f(x)$で親が$p$であるものが到着した時、その実行が開始する前に$x$に対する$f$モードロックが獲得されなければならない。これを$L_i$ロックと呼ぶ。 2. ロック解放規則：$f(x)$で親が$p$であるものが獲得した$L_i$ロックが一度解放された後は、$p$の他の子はもう$L_i$ロックを獲得することが許されない。 3. サブトランザクション規則：$L_i$操作$f(x)$が終わったとき、$f(x)$の子によって獲得された$L_{i-1}$ロックが全て解放される。 このサブトランザクション規則のおかげで、トランザクション全体が終わらずとも、サブトランザクション終了時点でそれ以下のロックを全て解放することができ、高い並列性を実現することが可能になる。 --- ### 定理7.1 層化2PLは木削減可能なスケジュールのみを出力する。 #### 証明 規則1と2により各層間スケジュールがOCSRなので、定理6.2から木削減可能である。$\square$ --- 単一のページにしかアクセスしないような操作同士は、OSに提供されるセマフォよりももっと単純なラッチによって制御することができる。ページヘッダのビットを立てることで疑似的にロックを示すという極めてシンプルな方法であるためオーバヘッドが少なく、商用のシステムでは頻繁に利用されている。 層化2PLは任意の数の層に対して適用できる一般的なアルゴリズムであるが、実用面では層が多いほどスケジューラの動作が重くなっていくため、層の数はできるだけ少なく保ちたい。だいたい2層か3層。そこで、一部の層を選んで、それ以外を無視してしまうことで実質的に層の数を減らす選択的な層化2PLを考えることにする。 $n$層スケジュールの層集合$L_n,...,L_0$の部分集合$L_{i_0},...,L_{i_k}, i_\nu > i_{\nu+1}, i_0=n,i_k=0$による選択的な層化2PLとは、以下の規則に基づくロックである。 1. ロック獲得規則：$L_{i_\nu}$の操作$f(x)$で親が$p \in L_{i_{\nu-1}}$であるものが到着した時、その実行が開始する前に$x$に対する$f$モードロックが獲得されなければならない。これを$L_{i_\nu}$ロックと呼ぶ。 2. ロック解放規則：$f(x)$で親が$p \in L_{i_{\nu-1}}$であるものが獲得した $L_{i_\nu}$ ロックが一度解放された後は、$p$の他の子はもう$L_{i_\nu}$ロックを獲得することが許されない。 3. サブトランザクション規則：$L_{i_\nu}$操作$f(x)$が終わったとき、層$L_{i_{\nu+1}}$の$f(x)$の子孫によって獲得された$L_{i_{\nu+1}}$ロックが全て解放される。 ## 一般のトランザクション森に対するロック 層化2PLをより一般化し、階層的でないようなスケジュールへ適用することを考える。 --- ### オブジェクトモデル2PL 1. ロック獲得規則：操作$f(x)$で親が$p$であるものが到着した時、その実行が開始する前に$x$に対する$f$モードロックが獲得されなければならない。 2. ロック競合規則：操作$r(x)$(*requester*)についてのロックが許可されるのは、以下の条件のいずれかを満たすとき。 1. $x$に対する競合するロックが存在しないとき。 2. $x$に対する競合ロックを持つすべてのトランザクションについて、操作$h(x)$(*holder*)のためにそのロックを保持しているものとすると、$h(x)$へのロックが延長ロック(retained lock)かつ、$r,h$の祖先$r',h'$で、可換かつ$h'$が既に終了しているようなものが存在するとき。 3. ロック解放規則：$f(x)$で親が$p$であるものが獲得したロックが一度解放された後は、$p$の他の子はもうロックを獲得することが許されない。 4. サブトランザクション規則：操作$f(x)$が終わったとき、$f(x)$の子によって獲得されたロックは全て延長ロックに変換される。 5. トランザクション規則：トランザクションが終了するとき、子孫のロックは全て解放される。 新しく延長ロック(retained lock)なる概念が導入される。これは、スケジュールが階層的でなく、一部の操作が一部の層をバイパスすることが許されており、そのようなケースの正当性も正しく保証するため。 $L_i$層のサブトランザクション終了時にそれ以下のロックを全て解放してしまうと、$L_i$層を経由せず$L_{i-1}$以下を直接操作するトランザクションが到着したとき、たとえそれがserializabilityを壊すものだったとしても、ロックが競合しないため全て実行されてしまう。これを防ぐため、サブトランザクション終了後も、それ以下の層のロックを「延長ロック」という特殊な形で保持しておく。このロックは、同じレベルで見たときに可換かつ延長ロック側が既に終了しているときには無視するものとする。こうすることで、トップダウンの衝突チェックをすべてクリアしてきた(=バイパスしないまっとうな)操作には延長ロックは影響を与えない。 バイパスが存在し、かつロック競合規則に違反するケースでも、セマンティクスを踏まえてみると許容されうる場合もあるのだが、プロトコル側ではセマンティクスを知り得ない以上、エラーを想定して保守的にブロックする必要がある。 --- ### 定理7.2 オブジェクトモデル2PLは木削減可能なスケジュールを出力する。 #### 証明 ## ハイブリッドアルゴリズム 複数の層で別のスケジューラを用いることももちろんできる。 ページレベルは他のレベルよりも読み込み操作の割合が多くなるので、それ向けに最適化された楽観的なプロトコルやROMV(Read-Only Multiversion Protocol)が有効になりやすい。よって、スケジューラの構成としては、例えば - レコードレベル$L_1$には2PL、ページレベル$L_0$にはFOCC - $L_1$には2PL、$L_0$にはROMV が考えられる。 --- FOCCも2PLもOCSRなので、 ### 定理7.3 2層スケジュールに対して、$L_1$に2PLを、$L_0$にFOCCを適用するハイブリッドスケジューラの出力は木削減可能になる。 --- ### 定理7.4 2層スケジュールに対して、$L_1$に2PLを、$L_0$にROMVを適用するハイブリッドスケジューラの出力は木削減可能になる。 #### 証明 ROMVの出力はCSRではないので、出力されたスケジュールに木の変形規則を適用してserialにできることを別途示す必要がある。木の変形は層ごとに順次適用していけるので、まずページレベルの操作を並び替えることでレコードレベルの操作を全て孤立にして枝刈りし、最後にレコードレベルの操作を可換性に基づいてserialに並び替えればよい。 ここで、レコードレベルの並び替えは2PLのOCSR性により可能であり、問題になるのはページレベルの並び替えのみである。 ページレベルでも、updaterトランザクション同士は2PLに基づいて制御されているので問題なく、考えるべきはread-onlyトランザクションが絡んだ場合である。ROMVの性質から、read-onlyトランザクション内のread操作は、それと並列に進行するトランザクション内のwriteと可換である。その一方で、read-onlyトランザクション開始前に終了したトランザクションのwrite操作とは非可換になる。この規則に基づいて、レコードレベル操作間の(順序が定義されている組の)順序を変えることなく全ての操作を孤立にできる。$\square$ --- 定理7.4の逆構成は、レコードレベルの操作をFetch, Modifyのみ許せばOKになる。レコードの削除に関しては、実際にレコードを消すのではなく削除マーカーを付けるものと考えることで組み込める。 ### 定理7.5 $L_1$の操作がFetch, Modify, Store, Eraseであるような2層スケジュールに対して、$L_1$にROMVを、$L_0$に2PLを適用するハイブリッドスケジューラの出力は木削減可能になる。 これに加えて$L_0$の2PLをラッチで簡易に制御するような形式が商用データベースで用いられる。 ---