###### tags: `TransactionalInformationSystems`

# 5章-1 Multiversion Serializability

## 概要

4章のCCは、各データアイテムは一つのオリジナルしか存在しないという想定の下で考案されていた。

本章では、各データアイテムについて、複数のコピーが存在することを許容する。すなわち、変更を経てきた複数のバージョンを保存し、必要に応じて過去のバージョンの値を読み込むこともできるということである。データに関して履歴を保存するためのメモリが必要になるが、serializabilityは拡張されることになる。(より多くのパターンのスケジュールが正当なものとして許容できるようになる)

トランザクションから見たデータアイテムはバージョンの概念を持たないことに注意。バージョニングはトランザクションに対して透明である。CADやソフトウェアリポジトリなど、ユーザが版を明示的に知る必要があるアプリケーションはあるが、ここではそのケースを考えない。

以下のように進む。

- read/writeモデルの拡張
- 拡張したserializabilityの定義
- バージョンが無制限に保持可能という前提について再考
- マルチバージョンな制御を実現するアルゴリズムを複数考える

## マルチバージョンスケジュール

バージョンが透過的であることから、トランザクションのモデルには変更が無く、操作の意味が変わる。$r(x)$は既存のあるバージョンの$x$を読み込むことに、$w(x)$は新しいバージョンの$x$を作ることになる。

---

### 定義：バージョン関数

$s$を、初期化トランザクション$t_0$と最終トランザクション$t_\infty$を持つ履歴とする。$s$のバージョン関数とは、ステップを引数にとる関数$h$であり、各読み込みステップに対し、それ以前の同じデータアイテムへの書き込みステップのうち一つを関連付けるものである。書き込みステップが引数のときはそのままそのステップを返す。

つまり、

1. ある $w_j(x)<_s r_i(x)$ が存在して$h(r_i(x))=w_j(x)$ ($r_i(x)$は$x_j$を読み込む)
2. $h(w_i(x))=w_i(x)$ ($w_i(x)$は$x_i$に書き込む)

ということ。

### 定義：マルチバージョンスケジュール

$T=\{t_1,\ldots, t_n\}$をトランザクション集合とする。

1. $T$のマルチバージョン履歴とは、ペア $m=(op(m),<_m)\ (<_mはop(m)の順序)$ で以下の条件を満たすものとする。
1. あるバージョン関数$h$が存在して$op(m)=h(\bigcup^n_{i=1}op(t_i))$
2. 任意の$t\in T$と$p,q\in op(t)$に対し$$p<_t q \Rightarrow h(p)<_m h(q)$$
3. $h(r_j(x))=r_j(x_i)\ (i\neq j, c_j \in m)$のとき、$c_i$もまた$m$に属しており$c_i<_m c_j$である。
3. マルチバージョンスケジュールとは、マルチバージョン履歴のprefixである。

1.3の条件がないと$CP(m)$(コミットされたトランザクションへの射影)が履歴でなくなってしまうために必要。

---

3章の定義における古典的なスケジュールは、マルチバージョンスケジュールの特殊化と考えることができる(全ての読み込みステップが、データアイテムの最新バージョンを読み込むケース)

### 定義：モノバージョンスケジュール

バージョン関数が、読み込みステップに対して直近の同じアイテムへの書き込みステップを割り当てるようなマルチバージョンスケジュールを「モノバージョンスケジュール」と呼ぶ。(最新の版しか保持しないため)

## マルチバージョンにおけるView Serializability

トランザクションからは同じシンタックスに見えるスケジュールでも、マルチバージョンにおいては複数のセマンティクスが生じ得る。
よって、新たな意味でのView Serializabilityを定義する必要がある

### 定義：Reads-From関係

$m$をマルチバージョンスケジュール、$t_i,t_j\in trans(m)$とする。

$m$のreads-from関係を以下で定義する。

$$RF(m):=\{(t_i,x,t_j)\mid r_j(x_i)\in op(m)\}$$

### 定義：参照同値

$trans(m)=trans(m')$であるような$m,m'$が参照同値であるとは$RF(m)=RF(m')$であることとし、$m\approx_v m'$と定義する。

マルチバージョンにおいては、view serializabilityはserialなマルチバージョンスケジュールと参照同値であると定義するだけでは十分ではない。なぜなら、serialなマルチバージョンスケジュールでさえ、serialなモノバージョンスケジュールと同じreads-from関係を持つ(=従来の意味でのview serializabilityを持つ)とは限らないため。

それを修正して

---

### 定義：Multiversion View Serializability

$m$をマルチバージョン履歴とする。$m$がmultiversion view serializableとは、serialなモノバージョン履歴$m'$で同じトランザクション集合を持つものが存在して$m\approx_v m'$が成り立つことである。

multiversion view serializableであるクラスをMVSRと表記する。

---

履歴に限らないスケジュールにおいても、multiversion view serializableとは、モノバージョン履歴$m'$が存在して$CP(m)\approx_v m'$と定義することができる。

また、古典的なスケジュールにもmultiversion view serializabilityを定義できる。(あるバージョン関数が存在して、それによってマルチバージョンスケジュールに変換したスケジュールのコミット射影がMVSRであること)

ここで、1つの古典スケジュールと複数のマルチバージョンスケジュールが対応することに注意。
- 古典スケジュール→マルチバージョンスケジュールの変換には、何らかのバージョン関数を適用する。(その中で最新バージョンのみ読み込むパターンがモノバージョンスケジュール)
- マルチバージョンスケジュール→古典スケジュールの変換には、同じステップの並びのまま、データアイテムのバージョンをすべて削除する。(=最新バージョンのみ読み込むパターンに強制する)

### 定理5.1

$VSR\subset MVSR$

#### 証明

VSRの履歴に最新のバージョンを読み込むバージョン関数を適用するとマルチバージョン履歴になり、serialなモノバージョン履歴と参照同値なのでMVSRになる。
strictnessは$m=w_0(x_0)w_0(y_0)c_0r_1(x_0)w_2(x_2)w_2(y_2)c_2r_1(y_0)c_1$による。
$\square$

### 定理5.2

与えられたマルチバージョン履歴がMVSRかの決定問題はNP完全である。

#### 証明

VSR決定問題をMVSR決定問題に多項式時間帰着できること、VSR決定問題がNP完全であることより。$\square$

VSR判定にはステップグラフを使ったが、その一方でMVSRの判定はトランザクションをノードの単位にしたグラフで特徴づけることができる。衝突グラフを考えると、$(t_i,t_j)$の衝突が生じ得るのは$w_i(x_i)<_m r_j(x_i)$ というパターンが起きる場合のみである。すなわち、マルチバージョンスケジュールの衝突グラフ$G(m)$が辺$t_i \rightarrow t_j$を持つのは、$m$が$r_j(x_i)$を持つときである。つまり、reads-from関係が同じなら衝突グラフも等しくなる。

### 定理5.3

2つのマルチバージョンスケジュール$m, m'$について、$m\approx_v m' \Longrightarrow G(m)=G(m')$

この逆は必ずしも成り立たない。衝突関係が同じでも全く違うバージョン関数やデータアイテムで実現されている場合がある。

### 定義：バージョン順

データアイテム$x$のバージョン順とは、反射的でない全順序であり、$m$の操作によって書き込まれたバージョンの順番を表す。全データアイテムのバージョン順の併合を$\ll$で表記する。

---

### 定義：Multiversion Serialization Graph (MVSG)

スケジュール$m$とバージョン順$\ll$に対する$MVSG(m,\ll)$とは、衝突グラフ$G(m)=(V,E)$に以下の辺を加えたものである。

互いに異なる$k,i,j$であるような$r_k(x_j), w_i(x_i) \in CP(m)$の組に対し、
- $x_i\ll x_j$ なら $(t_i,t_j)\in E$
- $x_i\gg x_j$ なら $(t_k,t_i)\in E$

意味的には、データアイテムの書き込みと、別バージョンの読み込みがあったとき、
- 書き込みの方が読み込んだアイテムのバージョンより古ければ、書き込んだトランザクション→読み込んだバージョンを書き込んだトランザクション
- 読み込んだアイテムのバージョンが書き込みよりも古ければ、読み込んだトランザクション→書き込んだトランザクション

という辺を新たに発生させる(バージョン辺)

---

したがって、同じ$x$への$w_j(x_j), r_k(x_j), w_i(x_i)$という3つが存在したとき、これらの間の辺には以下の3種のうち2種が同時に存在する。

1. $t_j\rightarrow t_k$は常に存在する。
2. $x_i\ll x_j$なら$t_i\rightarrow t_j$が存在する。(等価なモノバージョンスケジュールにおいて$w_i(x_i)$が$w_j(x_j)$の先にある)
3. $x_j\ll x_i$なら$t_k\rightarrow t_i$が存在する。($w_j(x_j)$が$w_i(x_i)$の先であり、等価なモノバージョンスケジュールでは$x_j$を読み込まなければならない$r_k(x_j)$も$w_i(x_i)$の先にある)

### 定理5.4

$m\in MVSR \Longleftrightarrow$ あるバージョン順$\ll$が存在して$MVSG(m,\ll)$が閉路を持たない

#### 証明

$\Leftarrow$

MVSGが閉路を持たないことから、トポロジカルソートしたserialな履歴$m'$で$RF(m)=RF(m')$なものが存在する。後は$m'$がモノバージョン履歴と見れることを示せば十分である。

ここで$m'$が$r_k(x_j),w_i(x_i)$を含むと仮定する($i,j,k$は互いに異なる)。

$x_i \ll x_j$なら、バージョン辺$t_i\rightarrow t_j$が存在し、$m'$がトポロジカルソートしていることから$t_i <_{m'} t_j$となる。

逆に$x_i \gg x_j$なら、バージョン辺$t_k\rightarrow t_i$が存在して$t_k <_{m'} t_i$。

いずれの場合でも$t_i$は$t_j,t_k$の間を弾き出される。よって、$t_j$と$t_k$の間にアイテム$x$への他トランザクションによる書き込みはなく、これらの間にreads-from関係が成り立つ。したがって、$m'$のデータアイテムからバージョン番号を無くしてもreads-from関係に変化がなく、モノバージョン履歴であることが分かる。

$\Rightarrow$

履歴$m$とバージョン順$\ll$に対し、$MV(m,\ll)$をバージョン辺のみ持つグラフと定義する($MVSG(m,\ll)=G(m)\cup MV(m,\ll)$)。バージョン辺は、バージョン順と$op(m)$の内容にのみ依存し、$m$の操作の並び順には影響されない。よって、$trans(m)=trans(m')$なら$MV(m,\ll)=MV(m',\ll)$ が言える。

ここで$m\in MVSR$と、それと参照同値なモノバージョン履歴$m'$を考える。前述の主張から、任意のバージョン順に対し$MV(m,\ll)=MV(m',\ll)$となる。定理5.3より衝突グラフは等しいので$G(m)=G(m')$でもあり、これらはどちらも閉路を持たない。これらを合わせて$MVSG(m,\ll)=MVSG(m',\ll)$。

ここで、バージョン順$\ll_0$を以下で作る。

$$x_i \ll_0 x_j \Leftrightarrow t_i <_{m'} t_j$$

これは、辺$t_i\rightarrow t_j$が$G(m')$に存在するとき$x_i\ll_0 x_j$を意味する。したがって、閉路を持たない$G(m')$に$MV(m',\ll_0)$を加えた$MVSG(m',\ll_0)$もやはりまた閉路を持たず、$MVSG(m,\ll_0)$もまた然りである。$\square$

適したバージョン順を探さなければならないので、MVSRの所属判定は簡単ではない。ただし、スケジューラがMVSRの条件を満たすスケジュールを生成することは可能である。

## マルチバージョンにおけるConflict Serializability

MVSRのサブクラスを考えていく。

---
### 定義：マルチバージョン衝突

$m$におけるマルチバージョン衝突とは、ステップの組$r_i(x_j),w_k(x_k)$で、$r_i(x_j)<_m w_k(x_k)$を満たすものとする。

---

この衝突の定義は、ここまで考えてきた衝突と全く異なることに注意。(ここまでの意味合いでは同じバージョンに対するwrのみを考えていたが、ここでは真逆のrwで、しかもバージョンは問わない)

#### なぜrwを衝突と考え、wrとwwは除外するのか

wrとwwは、順序を入れ替えても本質的に問題ない、つまりある意味で可換な操作であるが、rwは入れ替えるとserializabilityが変わってくる非可換な操作であるため。

- wwは、**二つの全く異なるバージョンを作成する操作**であり、どちらを選ぶかは読み込みステップに委ねられているため可換。
- wrは、入れ替えた場合、**読み込み操作が読み込めるバージョンの選択肢が1つ減り**、制限されたスケジュールになる。したがって、入れ替え後のスケジュールがMVSRであるなら、元のスケジュールもMVSRとなる。そういった意味で可換。
- rwは、入れ替えた場合、**読み込み操作が読み込めるバージョンの選択肢が1つ増える**ことになる。したがって、入れ替え後のスケジュールがMVSRであったとしても、それは入れ替え後の選択肢を使用した可能性があるため元のスケジュールもMVSRとは言えない。よって非可換。

このように、wrとrwの扱いの間に非対称性があるのが特徴。

### 定義：マルチバージョン削減可能性

履歴$m$がマルチバージョン削減可能であるとは、マルチバージョン衝突するペアを除き、隣接する二つのステップの交換を繰り返すことでserialなモノバージョン履歴が得られることとする。

### 定義：Multiversion Conflict Serializability

履歴$m$がmultiversion conflict serializableであるとは、同じトランザクション集合を持つserialなモノバージョン履歴$m'$が存在して、全てのマルチバージョン衝突が$m$と同じ順番で起こることとする。この履歴のクラスをMCSRと表記する。

すなわち、マルチバージョン削減可能$\Longleftrightarrow$multiversion conflict serializable

### 定理5.6

$MCSR\subset MVSR$

MCSRの所属可能性はマルチバージョン衝突グラフの閉路存在性で特徴づけられる。

### 定義：マルチバージョン衝突グラフ

$m$をマルチバージョン履歴とする。$r_i(x_j)<_m w_k(x_k)$を満たすステップ$r_i(x_j),w_k(x_k)$が存在するとき、辺$(t_i,t_k)$を引いたグラフをマルチバージョン衝突グラフとする。

### 定理5.7

マルチバージョン履歴がMCSRに属する $\Leftrightarrow$ マルチバージョン衝突グラフが閉路を持たない

ただし、衝突同値なserialスケジュールは、マルチバージョン衝突グラフをトポロジカルソートしても得られるわけではないことに注意。
定理5.7は、「衝突グラフが閉路を持たない$\Leftrightarrow$適正な変形操作の列が存在して変形先がserialになる」ことを述べているだけであり、具体的にどのような変形操作を繰り返せばserialになるのかは分からない。スケジューラへの応用としてはMVSRのサブクラスの方が実用的(後述)。

## バージョン数の制限

ディスク空間はそれほど高価ではないとはいえ、バージョンを保存できるリソースには限りがある。したがって、システムが同時に識別・管理できるデータアイテムのバージョン数の上限を定めることには実用的な意味がある。

バージョン数の上限を定める(超過した書き込みについては、最も古いバージョンを上書きする)ことで、無制限な場合にはMVSRであったスケジュールもserializableとは限らなくなる。

バージョン数を$k$個に制限した場合(読み込みは、k個以内の直近の書き込みからしか読み込めない)のview serializabilityを「k-version view serializability」と定義し、そのクラスをkVSRと表記する。

定義からVSRは1VSRと同等であり、任意の自然数kについてのkVSRを全て合わせたものがMVSRに相当する。

$$VSR=1VSR$$
$$MVSR=\bigcup_{k>0}kVSR$$
$$VSR=1VSR\subset 2VSR \subset \ldots \subset MVSR$$