###### tags: `TransactionalInformationSystems`

# 4章-4 ハイブリッドスケジューラ

## ハイブリッドな手法

CCの問題は二つの部分問題に分割できる。

- rw同期: 読み込み操作を書き込み操作と同期させる、もしくはその逆
- ww同期: 書き込み操作を書き込み操作と同期させる

トランザクション間の衝突の定義をこれら部分問題に対応する形に変えてスケジューラを作ったうえで、rw同期スケジューラとww同期スケジューラを組み合わせて動作させるのがハイブリッドスケジューラ。

作ったハイブリッドスケジューラのCSR安全性を示すには、まずrw同期、ww同期のそれぞれについて衝突グラフ$G_{rw}(s), G_{ww}(s)$を作り、それらの和$G_{rw}(s)\cup G_{ww}(s)$に閉路が存在しないことを示す必要がある。

### SS2PL+TO ハイブリッド

- rw同期にSS2PL(ロック解放をトランザクション終了時に行う2相ロックプロトコル)
- ww同期にTimestamp Ordering(衝突ステップの実行順をタイムスタンプ順に行うプロトコル)

を用いた例を考える。

TOにおいて、一般的なケースでは$w_i(x)$を$w_j(x)$の後に受け取って$ts_i(x)<ts_j(x)$だった場合、$w_i(x)$を拒否しなければならなかった。
しかし、ここではww同期にのみTOを使っていることが効かせられる。$w_j(x)$の書き込み結果が最終的に反映されていればいいので、$w_i(x)$を単純に実行しない(無視する)だけでよい。abortの必要がなくなる。これをThomas' Write Rule(TWR)と呼ぶ。

このようにTOの効率化はできるが、SS2PLとTOの協調は注意深く行う必要がある。まず$G_{rw}(s), G_{ww}(s)$のそれぞれに閉路が存在しないことは各プロトコルの正当性により分かる。それらの和に閉路が存在しないことを示すには、以下を言えば十分である。

$$(1) (t_i,t_j)\in G_{rw}(s) \Rightarrow ts(t_i)<ts(t_j)$$

$(t_i,t_j)\in G_{rw}(s)$のとき、$t_j$は$t_i$の握るリソースを必要としているため、$t_i$が該当するロックを解放するまで終わることができない。SS2PLなので、$t_i$は$t_j$が終わる前に終わることになる。したがって(1)は(2)で言い換えられる。

$$(2) t_iが、t_jがコミットする前にコミットするなら、ts(t_i)<ts(t_j)$$

これを実現するためには、コミット直前までタイムスタンプの割り当てを延期する必要がある。結果としてデータアイテムに書き込まれる値の決定もコミット時まで延期することになる。それまではアイテムごとのプライベートワークスペースに保持する。

### パーティショニングされたデータに対するハイブリッド

データアイテムごとに適用されるプロトコルを変える方式で、分散システムを考えると自然に出てくる設定。こちらもプロトコルごとの衝突グラフの和が閉路フリーになる必要がある。

単一のサーバという設定においても、一部の頻繁に変更するデータアイテム、めったに変更しないデータアイテム、一切変更しないデータアイテムのそれぞれでアクセス制御方式を変えたい場合が考えられる。この場合、例えば
- 頻繁に変更するものにはSGT
- 変更が起きにくいものにはFOCC
- 変更が一切起きない者にはCCを行わない

といった分担が考えられる。この場合もグローバルな閉路フリー性を検査する必要がある。

SS2PLとFOCCの組み合わせは閉路フリー性のグローバルな検査を必要としない点で優秀。(どちらもCOCSRであるため、組み合わせてもCOCSRになることが保証される)