###### tags: `TransactionalInformationSystems`

# 4章-3 ロックを用いないスケジューラ

ロックを用いずに安全性を保障できるスケジューラは、商用レベルでの利用は限られているが分散システムに有用かつハイブリッドなスケジューラを作るのにも役立つ。

## Timestamp Ordering

TMが全てのトランザクションにタイムスタンプ$ts(t_i)$を割り当てる(ここでは自然数とする)。

衝突するデータ操作をタイムスタンプの順に行う規則がTimestamp Ordering(TO)。

---

### 定理4.15

$Gen(TO)\subseteq CSR$

#### 証明

$Gen(TO)$の衝突グラフの各衝突辺についてタイムスタンプの順序関係が存在するので、閉路があると矛盾する。$\square$

---

スケジューラが既に後のタイムスタンプのステップ$q_j(x)$を出力してしまっており、それ以前のタイムスタンプで衝突する操作$p_i(x)$が入力されてきたとき($p_i$はtoo late)、$p_i(x)$はTO規則に違反してしまうため$t_i$はabortして最初からやり直す必要がある。
too lateの判定のためにbasic TOスケジューラ(BTO)が記録する必要があるのは

1. max-r-scheduled(x): 既にDMに送られた$x$の読み込み操作のうち、最大のタイムスタンプ。
2. max-w-scheduled(x): 既にDMに送られた$x$への書き込み操作のうち、最大のタイムスタンプ。

入力されてきたステップのタイムスタンプが該当する方のmax-scheduledよりも小さいならそのステップを拒否してabortする。

ここでDMはスケジューラが送ってきた操作をその順番通りに実行しなければならない。そのため、スケジューラは衝突する操作の出力を、それ以前に出力した操作が全て実行完了したことが分かるまで待つ。したがって、操作の実行状況をスケジューラとDMの間でやりとりする(handshake)する必要がある。

## Serialization Graph Testing

衝突グラフを動的に保持して更新しながら、そのacyclicityを維持し続けることでCSRを保証する方法。この方法に基づくスケジューラをSGTスケジューラと呼ぶことにする。

操作$p_i(x)$がTMに送られてきたとき、スケジューラは以下の手順を踏む。

1. それが$t_i$から送られた最初の操作なら、グラフ$G$に新たにノード$t_i$を作る。
2. 既に出力された操作$q_j(x)$で$p_i(x)$と衝突しているものがあるなら、辺$(t_j,t_i)$を挿入する。2つの場合が生じる。
1. $G$が閉路を持つ場合。$p_i(x)$は実行できないので$t_i$をabortし、ノード$t_i$と関連する辺を削除する。
2. $G$が閉路を持たない場合。$p_i(x)$は安全なので出力し、既に出力された操作のリストに加える。

SGTの実装には、BTOと同様DMの実行状況を知るためのhandshakeが必要になる。

### 定理4.16

$Gen(SGT)=CSR$

#### 証明

$\subseteq$は明らか。逆は、$s\in CSR$の長さに関する帰納法で示せる。

グラフのノードは、commitしたから削除、というわけにはいかない。安全にノードを削除できる基準が無いと、グラフが際限なく大きくなってしまう。

ここで大事なのは、衝突グラフにおいて
- 閉路上のノードはincoming edgeとoutgoing edgeの両方を持つ
- 既にcommitされたトランザクションのノードは、outgoing edgeが増えてもincoming edgeが増えることはない。

ということ。つまり、「$t_i$が終了したトランザクションで、かつincoming edgeを持たない(sourceである)」ならば、$t_i$をグラフから削除しても問題ない。

### 手法の問題点

理論的にはCSRを全て生成可能という良さがあるが、終了したトランザクションの分も衝突グラフに保持する必要があってメモリ消費が大きいだけでなく、実行中に頻繁に閉路検出アルゴリズムを実行するオーバヘッドも大きい。CCアルゴリズムはデータサーバの実行ループの最も内側に位置しているため、ランタイムオーバヘッドの影響が極めて大きく、実用的になりづらい。

## 楽観的なプロトコル

ここまでのプロトコルは悲観的、つまり全てのステップをいったん止めてserializabilityに違反しそうだったらたちまちブロックするような形式だった。この方式だと、トランザクションのほとんどが簡単な読み込みであるようなケースにオーバヘッドが大きくなりすぎるという問題がある。トランザクション間の衝突による矛盾の発生がめったにないようなケースで、ステップを基本的には素通しし、しかるべきタイミングでserializableか検証する方式が考えうる。validation protocol(検証プロトコル)などと呼ばれる。

検証過程はスケジューラ側でなく、トランザクションの実行過程に組み込む。検証プロトコルにおけるトランザクションは以下の3フェーズを踏むことになる。

1. 読み込みフェーズ: トランザクションの内容を全て実行するが、全ての書き込みはトランザクション固有のプライベートメモリに一時的に保持され、グローバルなデータアイテムには反映されない。
2. 検証フェーズ: commitする準備が整ったトランザクションは検証される。conflict serializabilityを検証し、不正ならabortする。
3. 書き込みフェーズ: データアイテムへの変更が実際に反映される。

(2)と(3)はアトミックに実行される必要があるのに注意。これらの実行中にはその他のトランザクションが全て一時停止されなければならない。このval-writeフェーズの不可分性は実用的には問題になりやすい。

検証フェーズでやることはやはり衝突グラフを閉路フリーにすることで、以下の観察を用いる。

### 補題4.9

$G$をDAGとする。$G$に新しいノードが加えられたとき、新しいノードから伸びる辺がないなら、できるグラフもまたDAGである。

検証プロセスには2種類ある。

- backward-oriented optimistic concurrency control(BOCC): 既にコミットされたトランザクションのリストを参照して検証を行う。
- forward-oriented optimistic concurrency control(FOCC): 並列に走っていて読み込みフェーズにあるトランザクションのリストを参照して検証を行う。

### BOCC

トランザクション$t_j$は、既にコミットされた各トランザクション$t_i$に対し、以下のいずれかを満たせば受理される。

- $t_i$は$t_j$が始まる前に終わっている場合。
- $t_i$のval-writeフェーズが$t_j$のそれより早く終了し、$RS(t_j)\cap WS(t_i)=\emptyset$ つまり$t_i$が書き込んだデータアイテムを$t_j$が読み込むことが無い場合。

これらのケースで$t_i$と$t_j$の間の衝突があるなら、それが$(t_i,t_j)$の方向になっているため補題4.9と合わせてCSRになる。

#### 定理4.17

$Gen(BOCC)\subseteq CSR$

### FOCC

$RS^n(t_i)$を、時刻$n$での$t_i$の読み込み操作集合とする。FOCCにおいて、時刻$n$にトランザクション$t_j$を受理するための条件は、全ての並列に走っているトランザクション$t_i$に対し

$$WS(t_j)\cap RS^n(t_i)=\emptyset $$
が成り立つこと。

#### 定理4.18

$Gen(FOCC)\subseteq CSR$

これら検証プロトコルの良さは、トランザクションが受理されなかったときにabortされるトランザクションを柔軟に選ぶことができる点にもある。さらに、abortせずに一部のトランザクションを待機させることで問題を解決できるケースもある。