###### tags: `TransactionalInformationSystems`

# 5章-2 Multiversion CC

## Multiversion Timestamp Ordering (MVTO)

TOプロトコルをマルチバージョン向けにフィットしたもの。各トランザクションには開始時のタイムスタンプを割り当てる。入力されてきたデータ操作をバージョン付きのものに変形して処理し、実行結果がさもserialなモノバージョンスケジュールによるものかのようになる。

MVTOの動作は以下の通り。

1. ステップ$r_i(x)$は$r_i(x_k)$に変形される。ここで$x_k$は、$ts(t_i)$以下で最大のタイムスタンプを持つ$x$のバージョンで$t_k \ (k\neq i)$に書き込まれたものである。
2. ステップ$w_i(x)$は以下のように処理される。
1. 読み込み$r_j(x_k)$で$ts(t_k)<ts(t_i)<ts(t_j)$を満たすものが既にスケジュールされているなら、拒否されて$t_i$はabortする。
2. そうでないなら$w_i(x_i)$に変形されたうえで実行される。
3. (任意、回復に有用) コミット$c_i$は、$t_i$が読み込むバージョンを書き込んだ全てのトランザクション$t_j$がコミット$c_j$を終えるまでブロックされる。

このプロトコルが正当であること、つまり
$$Gen(MVTO)\subseteq MVSR$$
であることを示すにあたっては、バージョン順が以下で定義できることを用いる。
$$x_i\ll x_j \Longleftrightarrow ts(t_i)<ts(t_j)$$

### MVTOの正当性の証明(演習問題5.8)

MVTOの出力スケジュールを$m\in Gen(MVTO)$とし、そのバージョン順を$x_i \ll x_j \Leftrightarrow ts(t_i)<ts(t_j)$で定義する。

このとき、$MVSG(m,\ll)$が辺$(t_i,t_j)$を持つとき、$ts(t_i)<ts(t_j)$を持つことを示せば十分である。(→閉路を持たない)

- $G(m)$の辺だったとき($t_j$ reads from $t_i$)、MVTOの規則1から$ts(t_i)<ts(t_j)$。
- バージョン辺だったとき、2つのケースがある。$(t_i,t_j)$というバージョン辺が生じ得るのは
- $x_i \ll x_j$ かつ $r_k(x_j),w_i(x_i)$ が存在するケース。
- ある$r_i(x_k)$と$w_j(x_j)$が存在し、$x_k \ll x_j$ を満たすケース。このケースで$x_j \ll x_i$を仮定すると$ts(t_k)\ll ts(t_j)\ll ts(t_i)$ となり、
- $w_j(x_j)$が$r_i(x)$よりも先にスケジュールされていたとき、MVTO規則1から$r_i(x_k)$でなく$r_i(x_j)$になるはずなので矛盾。
- $r_i(x_k)$が$w_j(x_j)$よりも先にスケジュールされていたとき、MVTO規則2.1から$w_j(x_j)$は拒否されてabortされているはずなので矛盾。
いずれのケースでも矛盾するので$x_i \ll x_j$。

結局、いずれのケースでも$x_i \ll x_j$すなわち$ts(x_i) < ts(x_j)$が成り立つので、MVSGは閉路を持たず、$m\in MVSR$が示された。$\square$

## Multiversion 2-Phase Locking (MV2PL)

2相ロックを用いたマルチバージョン用スケジューラを考える。ひとまずデータのバージョン数は無制限とし、後にこれを2個に制限したものを考える。

バージョンを状態で分類する。

- コミットされたバージョン: 既にコミットされたトランザクションに書き込まれたバージョン
- 現在のバージョン: コミットされたバージョンのうち、直近のもの
- コミットされていないバージョン: まだアクティブなトランザクションに書き込まれたバージョン

スケジューラは、全てのデータアイテムについて、コミットされていないバージョンを高々1つしか許容しない。また、各トランザクションの最後のデータ操作ステップを特別に扱う。

各ステップは以下のように取り扱う。

1. ステップが$t_i$の最後のステップでない場合。
1. $r(x)$には、現在のバージョンorコミットされていないバージョンを割り当てて直ちに実行する。
2. $w(x)$は、直近に$x$に書き込んだトランザクションが終了するまでブロックする。(コミットされていないバージョンを1つしか許容しない)
2. ステップが$t_i$の最後のステップである場合、以下のトランザクションが全てコミットされるまでブロックされる。
1. 現在のバージョンを読み込んでいるトランザクション$t_j$のうち、同じデータアイテムを$t_i$が上書きしてしまうもの。
2. $t_i$が何らかのバージョンを読み込んだ$t_j$。

### 2V2PL

MV2PLプロトコルをさらに制限し、データアイテムごとに2つのバージョンしか許容しないものを考えて2V2PLとする。
つまり、アクティブなトランザクションが$x$に書き込んだとき、$x$の変更前の値と変更後の値を1つずつ保存する必要があることになる。
このバージョニングに恩恵を受けるのは主に読み込み操作となる。(書き込み操作をしている間にも、古い値を確認することで平行に読み込みを進められるため)

2V2PLは新たな種類のロックを追加して3つとする。

- read lock: 読み込みは現在のバージョンの値から。
- write lock: 書き込みはコミットされていないバージョンに対して。
- certify(commit) lock: トランザクションの最後のステップの前に全てのデータアイテム$x$に対して行われるロック$cl(x)$で、コミットされていないバージョンを確定して現在のバージョンとする。

各ロックの共存可能性は以下。

| | $rl(x)$ | $wl(x)$ | $cl(x)$ |
| - | -------- | -------- | -------- |
| $rl(x)$ | + | + | - |
| $wl(x)$ | + | - | - |
| $cl(x)$ | - | - | - |

これらのロック規則を守ることで結果的に前述のMV2PLの条件が守られる。

read lockがかけられないのはcommit lockがかかっているときのみ(=トランザクションの最後のみ)であるため、従来の2PLと比べて読み込みの効率が大きく上がっている。

commit lockの存在により、2PL性が自動的にSS2PL性につながっていることに注意。(全ロックをトランザクションの最後に解放する)

### 2V2PLの正当性の証明(演習問題5.8)

キーポイント3つ
- コミット順で適切なバージョン順を定義できる
- コミットされていないバージョンは1つしか存在できないため、同じデータアイテムに書き込む2つのトランザクションの最終ステップ$f_i, f_j$について$x_i\ll x_j \Leftrightarrow f_i < f_j$が一意に定まる
- cerify lockのおかげで、現在のバージョンを読み込んでいるreaderがある間はそのアイテムをコミットしたいwriterがブロックされる

2V2PLの出力$m \in Gen(2V2PL)$を考える。certify lockの性質からコミットの全順序が一意に定まる。$m$のバージョン順$\ll$をコミットの順で定義して、このとき$MVSG(m,\ll)$が閉路を持たないことを示せばよい。

ここで、「トランザクション$t_i$におけるある操作ステップが実行されたとき、MVSG上でそれを原因として$t_i$から伸びる辺は、$t_i$の後にコミットされたトランザクションに対してしか生じない」ことを示せば十分である。

まず、$r_i(x)$が実行された状況を考える。$r_i(x)$から、$t_i$以前にコミットされるトランザクション$t_j$への辺$(t_i,t_j)$が生じるには、
- reads-from辺は$t_i$の側がreadであるため生じ得ない。
- バージョン辺が生じるには、$x_k\ll x_j \ll x_i$な$t_k$が存在して$w_k(x_k)\rightarrow r_i(x_k)\rightarrow w_j(x_j)$という関係が成り立つ必要がある。したがって$t_i$は$t_j$がコミットする前に$x$を読み込む必要があるが、これはロックの規則からありえない($t_i$がひとたび$x$にread lockをかけると、$t_j$は$t_i$がコミットを終えるまでコミットできず、仮定に反する)。

次に、$w_i(x)$が実行された状況を考える。$t_i$以前にコミットされるトランザクション$t_j$への辺$(t_i,t_j)$が生じるには、
- reads-from辺の場合、$w_i(x_i)\rightarrow r_j(x_i)$となる必要がある。$t_i$がコミットされた後に$t_j$の操作が実行されてしまうためありえない。
- バージョン辺が生じるには、$w_j(x_j), r_k(x_j)$も存在して$x_i \ll x_j$が成り立つ必要がある。$x_j\ll x_i$と矛盾するのでこれはありえない。

以上より、MVSGの辺はコミット順に則する向きにしか生じず、したがって$m\in MVSR$である。$\square$

## Multiversion Serialization Graph Testing (MVSGT)

SGT(Serialization Graph Testing)をマルチバージョン向けにフィットしたもの。

SGTでは正確な衝突グラフを一つ保持できたが、MVSGTではそれはできない。代わりに、複数種類のマルチバージョン衝突グラフのスーパーグラフを構築し(=複数のスケジューラを組み合わせ)、その全てに閉路が存在した時点でserializabilityに反する、というような判定を行う。

まず、単一のスケジューラを定義する。マルチバージョン衝突グラフ$G$を、$t_0$から他の全てのノードへの辺を伸ばすことで初期化する。全てのステップを処理し終わったとき、$G$は衝突グラフの全ての辺を含むことを期待する。

$r_i(x)$がスケジューラに入力される場面を考える。$t_i$が読みうる$x$のバージョンのうち、以下のトランザクションに書き込まれたバージョンを除外する。

1. $t_j$で、$t_i$から始まるパス上にあるもの。serialで同値なスケジュールでは$t_i$の後に実行されるため、遅刻しているといえる。
2. $t_j$で、パス$t_j\rightarrow t_k \rightarrow t_i$があって$t_k$も$x$に書き込むもの。serialで同値なスケジュールでは$t_i$は$t_k$から読み込んでしまうため、到着が早過ぎる。

つまり、早すぎも遅すぎもしないトランザクションによって書き込まれたバージョンが候補になり、その中から何を選ぶかで複数種類のスケジューラが生じうる。

ここでマルチバージョン衝突グラフは以下のように維持する。

1. $w_i(x)$がスケジュールされたとき、$r_j(x)$が既にスケジュールされている全ての$t_j$に対して辺$(t_j,t_i)$を追加する。これによって$G$はMVSGのスーパーグラフになる。$G$が閉路を持つなら$w_i(x)$は実行されず、持たないなら新しいバージョンを作成する。
2. $r_i(x)$がスケジュールされていて、読み込むバージョンが$w_j(x)$によるものだったとき、辺$(t_j,t_i)$を加える。$t_j$は遅刻していないことから、これは$G$に閉路を作らない。これに加えて、既にスケジュールされていて遅すぎも早すぎもしない各ステップ$w_k(x)$に対し辺$(t_k,t_i)$あるいは$(t_i,t_k)$が追加される。

## Read-Onlyなトランザクションのためのプロトコル

データインテンシブな現代のアプリケーションでは、大量のデータを読み込んで解析する長大なトランザクションが並行で走りうる。この間データの更新ができないとすればパフォーマンスが著しく悪化する。

読み込みのみのトランザクションだけにでも本章のマルチバージョンプロトコルを採用したハイブリッドにすることで、わずかな複雑さの上昇で大きく時間効率を上げることができる。

トランザクションのうち、データへの書き込みを含むものにはupdaterとマークする。

1. updaterは古典的なS2PLで処理するが、書き込みには新しいバージョンを作成する。読み込む値は直近に書き込まれた値になる(バージョン関係なく)。各バージョンは、トランザクションのコミット時刻のタイムスタンプで順序付けられる。(つまり、updaterはバージョニングの恩恵を受けず、read-onlyトランザクションのためだけに複数バージョンを保存することでオーバヘッドを最低限にする)
2. read-onlyなトランザクションはMVTOと類似なタイムスタンププロトコルで処理する。各トランザクションには開始時のタイムスタンプが付けられる(updaterにはコミット時のタイムスタンプが付けられていたのと対照的)。

つまり、read-onlyなトランザクションは、開始時点でコミットされていた中での最新のバージョンを読み込む。これがRead-only multiversion protocol (ROMV)。

### ROMVの実装

複雑さはかなり抑えられているが、それでも実装には非自明な問題が付きまとう。

#### read-onlyトランザクションに使われることがなくなった古いバージョンをGCできる必要がある。

削除してもいいバージョンの十分条件としては

1. 直近にコミットされたバージョンではない (これを削除したらバージョンがなくなってしまう)
2. タイムスタンプが、現在アクティブなread-onlyトランザクションのうち最も古いものよりもさらに古い。

#### 保存できるアイテム数に上限が必要になることがある。

read-onlyトランザクションは、読み込んでいるバージョンが古くなって上書きされてしまったときにabortされる必要が出てくる。

#### バージョンのタイムスタンプをどうやって管理するのか。

コミットされた時点でその時刻をバージョンに割り当てる必要があるのでtricky。

- 各データアイテム自体(ページなど)にタイムスタンプをする方法。
- コミット時に全データアイテムを再訪してタイムスタンプを書き込む必要がある。
- 追加のデータ構造を保持する方法。コミットされたupdaterのwrite setとタイムスタンプを保持する。

### ROMVの正当性の証明(演習問題5.8)

$m\in Gen(ROMV)$を考える。一般性を失わず、updaterを$T_1=\{t_1,...,t_k\}$、read-onlyを$T_2=\{t_{k+1},...,t_n\}$とできる。$\Pi_{T_1}(m)$はS2PLの出力になっているので、これを古典的なスケジュールとみると、衝突同値でserialなスケジュール$s'=t_{\rho(1)},...,t_{\rho(k)}$が存在して$\Pi_{T_1}(m)\approx_c s'$、特に$RF(\Pi_{T_1}(m))=RF(s')$

(=reads-from関係は$T_1$同士と$T_1\rightarrow T_2$でしか生じず、S2PLのおかげで$T_1$同士のreads-from関係はs'が保存している。)

残りは、$s'$のupdaterトランザクションの間にread-onlyを適切に差し込んでserialなモノバージョンスケジュールを作れて、そのreads-from関係が$m$と同一なままであることを示せばよい。

S2PLの性質より、updater間では、同じデータアイテムへの書き込みを行うトランザクションについて、コミットの順番と衝突の方向が等しくなる。したがって、$s'$の同じデータアイテムへのupdaterはタイムスタンプ順に並んでいる。よって、read-onlyな各トランザクション$t'\in T_2$を、$ts(t_{\rho(p)}) < ts(t') < ts(t_{\rho(p+1)})$を満たす$t_{\rho(p)}, t_{\rho(p+1)} \in s'$の間に配置したserialなモノバージョンスケジュール$m'$を考えると、これは$RF(m')=RF(m)$を満たす。$\square$

### ROMVにおいてupdaterスケジューリングを緩和したらどうなるか？(演習問題5.9)

updaterトランザクションにおいて、書き込みに2PL排他ロックを用いるのはそのままで、読み込みには直前にコミットされたバージョンを読むことにすると、このプロトコルはMVSRではない。

(以下証明)

このプロトコルによる出力であるがMVSRに含まれない例を挙げればよい。

スケジュール
$$s=r_1(x)r_2(x)w_2(x)w_2(y)r_1(y)c_2w_1(x)w_1(y)c_1$$
を入力すると、$t_2$がコミットする前の$r_1(y)$では$y_0$の値が読み込まれ、コミット後にはwrite lockが解放されるため$t_1$による書き込み$w_1(x),w_1(y)$も問題なく行われ、どのステップもブロックやabortされることがない。バージョンが割り当てられた出力スケジュールは
$$m=r_1(x_0)r_2(x_0)w_2(x_2)w_2(y_2)r_1(y_0)c_2w_1(x_1)w_1(y_1)c_1$$となる。

このマルチバージョンスケジュールにおいては、$x$について$t_1$が、$y$について$t_2$が$t_0$から値を読み込んでおり、reads-from関係$t_0\rightarrow t_1, t_0 \rightarrow t_2$が同時に成り立つ。

一方、考えうるserialなモノバージョンスケジュール $t_0t_1t_2, t_0t_2t_1$ のどちらにおいても、これらのreads-from関係を同時に成立させることはできない。($t_1,t_2$のどちらも$x,y$を両方上書きするため)

したがってプロトコルの出力$m$がMVSRに含まれず、この改変はMVSR正当性を壊すことが分かる。$\square$