###### tags: `TransactionalInformationSystems`

# 6章 オブジェクトモデルにおけるSerializability

## 概要

object model、つまり、トランザクションが単純な操作の列でなく、木になったモデルでの同時実行制御を考えていく。

主な困難は2つ：

1. トランザクション内の操作が単なるread/writeだけではなくなる
2. 操作自身が他の操作を再帰的に呼び出すことが可能になる

まずobject modelにおけるシンタックスを定義したのちに、(1)の問題に対処、最後に(2)を解決する。

特に(2)が難しく、view serializabilityなどは直接一般化することができない。代わりに、可換性に基づいた衝突同値性と類似の方法を用いて、木に可換操作を繰り返してserialにできるか、という意味合いでの正当性基準を考える。

## Object Modelにおけるスケジュールと履歴

object modelにおけるトランザクションの定義を2章から引っ張ってくると

### 定義：Object Modelにおけるトランザクション(再掲)

トランザクション$t$とは、ノードラベル付きの木で

- 根のラベルがトランザクションの名前
- 内部ノードラベルがその部分木に対応する手続きを呼び出す操作の名前
- 葉ノードがpage modelにおけるread/write操作
- 葉ノードで同じデータアイテムへの操作であり、かつ少なくとも一方がwriteである$p(x),q(x)$に対して順序が定められている($p<q$または$q<p$)

であるもの。

---

### 定義：Object Modelにおける履歴

$T=\{t_1,...,t_n\}$をトランザクション木の集合とする。ここで、各$t_i\in T$は、ラベル付けされた木のノードとその葉についての半順序からなる組$(op_i,<_i)$である。$T$の履歴$s$とは、半順序を持つ森$(op(s),<_s)$で以下の条件を満たすものと定義する。

1. $op(s)\subseteq \bigcup_{i=1}^nop_i\cup \bigcup_{i=1}^n\{c_i,a_i\}$かつ$\bigcup_{i=1}^nop_i\subseteq op(s)$、すなわち$s$は、$T$の全ての操作と各$t_i$に関する終了操作を含む。
2. $c_i\in op(s)\Leftrightarrow a_i\notin op(s)$
3. $a_i/c_i$は、$t_i$の根を親とする葉ノードである。
4. $\bigcup^n_{i=1}<_i\:\subseteq\: <_s$ つまりトランザクション内の半順序を保存する。
5. $\forall p\in op_i,\ p<_s a_i$ or $p<_s c_i$
6. 異なるトランザクション間の同じデータアイテムへの操作$p,q\in op(s)$で少なくとも一方が書き込みであるような組の間には順序が定まる。つまり$p<_s q$または$q<_s p$。

---

上記の定義での半順序はトランザクションの葉の間にのみ定まっているが、これを内部ノード間の順序にも矛盾なく拡張できる。

### 定義：Tree-Consistent Node Ordering

object modelの履歴$s=(op(s),<_s)$における半順序$<_s$を、以下の手順で任意のノード間の順序に拡張する。

2つのノード$p,q$について、任意の子孫の葉$p',q'$の間に$p'<_s q'$が成り立てば$p<_s q$

このような半順序はtree consistentであるという。

---

これをもってprefixが定義でき、

### 定義：Object Modelにおけるスケジュール

スケジュールは履歴のprefixである。

---

serialなスケジュールの定義も直ちに従い

### 定義：Serialなスケジュール

オブジェクトモデルスケジュールがserialとは、各トランザクションの根同士、および任意の深さのノード同士の間にそれぞれ全順序が定まっていることとする。

(葉の全順序を定めるだけではダメで、内部ノードを織り交ぜて実行しうる)

### 定義：孤立した部分木

スケジュール$s$の内部ノード$p$の部分木が孤立しているとは、以下を満たすこととする。

1. $p$の子孫でも先祖でもない任意のノード$q$について、$q$のすべての葉$w$が$w<_s p$または$p<_s w$を満たす。
2. $\forall i>0$に対し、$p$の子孫で$p$からの距離が$i$であるものの間に全順序が定まっている。

つまり、$p$の部分木が、他の部分木に対しての不可分単位を形成していることを意味する。

---

多くの応用先では、トランザクション木は統一的な規則を持って同じ深さの葉を形成する。例えば、葉はページモデル操作、その上のノードは呼び出した関数、その上のノードはトランザクションの根、といった具合に。これを定式化しておく。

### 定義：階層的な履歴とスケジュール

履歴が階層的であるとは、commit/abortを除くすべての葉の根からの距離が等しいこととする。

すべての葉の根からの距離が$n$であるような階層的履歴を$n$層履歴という。$n$層履歴では、葉の層からの距離が$i$であるような操作を$i$層操作と呼んで$L_i$と表記する。葉は$L_0$、根は$L_n$である。

階層的なスケジュールは、階層的な履歴のprefixとする。

---

なお、ページモデルにおけるスケジュールはここでいうところの1層スケジュールであり、その意味ではオブジェクトモデルの特殊化である。

まったく同じ意味を持つトランザクション群でも、違う木の形状でモデル化できることに注意。例えば、銀行の預金・引き出し操作において、引き出し操作だけを内部ノードを除いて直接ページモデル操作で行うように木の形状を変えることもできる。要はどこまでをモデル化するかという恣意性により発生する違いだが、どちらでも正しくなるような議論を進めていく必要がある。

## "平坦な"トランザクションに対するConflict Serializability

2層スケジュールの中でも、1層操作をオブジェクトへの操作の呼び出しとみなし、アトミックに行われることを要請した特殊ケースを考えていく。

### 定義：平坦なスケジュール

2層スケジュール$s$がflat object schedule(平坦なスケジュール)とは、任意の$p,q\in L_1$に対し以下の2つの条件が成り立つこととする。

1. ($\forall p'\in child(p),q'\in child(q)$) $p'<_s q'$か、または($\forall p'\in child(p),q'\in child(q)$) $q'<_s p'$
2. $\forall p', p'' \in child(p)$に対し、$p'<_s p''$または$p''<_s p'$

つまり、$L_1$部分木のデータ操作の間には全順序が定まっていて、またそれぞれが不可分であること。

平坦なスケジュールでは、ページレベルの操作は$L_1$ごとに完全にシーケンシャルに行われることが保証されている。このため、同時実行制御を考えるという文脈においてはページレベルの操作について全く考える必要が無く、$L_1$をトランザクションの不可分な最小単位とした1層スケジュール(=ページモデルのスケジュール)に抽象化することができる。

次のステップは、このような抽象化したモデルに対する正当性を考えることである。view serializabilityはこの用途に適していない。なぜなら、view serializabilityはreads-from関係をベースにしており、せっかくのページレベルread/write操作をまとめた抽象化が意味をなさないからである。その一方で、conflict serializabilityは、衝突の定義をアジャストすることでこの文脈でも有用になる。

### 定義：可換な操作

$p$と$q$が可換であるとは、すべての考えうる操作列$\alpha, \omega$に対し、$\alpha pq\omega$ と$\alpha qp \omega$が返すパラメータが同じであることとする。

この意味での可換性をシステム側で自動決定するのは不可能であるため、ここではアプリケーション側が操作間の可換性を宣言するものとする。

例えば、ECでの購入トランザクションはそれだけでは可換だが、1万人目の購入者には特別プレゼントといったような副作用が加わると非可換になったりする。このため、オブジェクトとメソッドの間の一対一対応は避け、メソッドが複数のオブジェクトに対して操作を行えると想定する。また、異なるメソッド間のパラメータリストがdisjointだとしても必ずしも可換とは想定しない。

### 定義：可換性に基づく削減可能性

平坦なスケジュール$s$が可換性に基づいて削減可能とは、以下の規則を有限回適用してserialなスケジュールに変換できることとする。

1. 可換規則：$p<_s q$である$p,q$は、以下の条件を満たすとき入れ替えても良い。
1. 両方とも孤立していて可換で、$p<_s r<_s q$を満たす$r$がなく、かつ
2. 異なるトランザクションに属しているか、もしくは同じトランザクション$t_i$に属していて反転が$<_i$に矛盾しないとき。
2. 順序規則：順序付けられていない葉$p,q$は、可換であるとき(どちらも読み込みだったり、異なるデータアイテムへの操作だったりするとき)、任意に順序付けしても良い。

### 定義：衝突同値性

2つの平坦なスケジュール$s,s'$が衝突同値とは、それらが同じ操作集合を持ち、$L_1$操作について同じ順番を持っていることとする。

serialなスケジュールと衝突同値なとき、conflict serializableである。

### 定理6.1

$s$を平坦なスケジュールとする。

$s$がconflict serializable $\Longleftrightarrow$ 衝突グラフが閉路を持たない $\Longleftrightarrow$ 可換性に基づいて削減可能

平坦なスケジュールがconflict serializableなケースでも、$L_0$のレベルを見ると衝突グラフが閉路を持っている場合があることに注意。そのようなケースを許容できることに、オブジェクトレベルの操作についてのセマンティックな知識を持ったことの恩恵が現れている。

## Tree Reducibility

平坦なスケジュールから、一般のオブジェクトモデルスケジュールにまで、削減可能性の定義を拡張する。

---

### 定義：Tree-Reducible History

履歴$s=(op(x),<_s)$がtree reducible(木削減可能)とは、以下の規則を有限回適用して木の根の間に全順序を定められることとする。

1. 可換性規則：順序付けられた葉の操作$p<_s q$は、以下の条件を満たすとき順序を入れ替えても良い。
1. 両方とも孤立していて可換で、$p<_s r<_s q$を満たす$r$がなく、かつ
2. 異なるトランザクションに属しているか、もしくは同じトランザクション$t_i$に属していて反転が$<_i$に矛盾せず、かつ
3. 非可換かつ順序付けられているような$p,q$の祖先の組$p',q'$が存在しない。
2. 順序規則：順序付けられていない葉$p,q$は、可換であるとき(どちらも読み込みだったり、異なるデータアイテムへの操作だったりするとき)、任意に順序付けしても良い。
3. 枝刈り規則：孤立した部分木は、枝刈りして根だけにしてもよい。

---

木の枝刈りを許すのがポイントで、高レベルの操作であっても、それ以下の操作が不可分になっていれば実質的に葉とみなせる。

1.3の条件(祖先に関するもの)が加えられた理由は、祖先をそのままにして葉の順序だけ入れ替えると不正なケースが生じてしまうため。
このようなケースはページモデルや平坦なスケジュールでは起こらないが、一般的なオブジェクトモデルになると現れうる。

## Tree Reducibilityの十分条件

木削減可能性は正当性の概念として直感的だが、判定は難しく、制御アルゴリズムのために直接使うことのできるものではない。そのため、木削減可能性の十分条件かつ、CCアルゴリズムを実装するために有用なものを考えていく。

階層的なスケジュールに着目する。階層的なスケジュールのためのスケジューラを考えようとしたとき、各レベルを1層スケジュールとみて個別に古典的なスケジューラを適用し、それを統合するというアイディアが考えられる。

---

### 定義：Level-to-Level Schedule (層間スケジュール)

$s=(op(s),<_s)$を$n$層スケジュールとする。$L_i,L_{i-1}$の層間スケジュールとは、1層スケジュール$s'=(op(s'),<_{s'})$で以下の条件を満たすものとする。

1. $op(s')$は$s$における$L_{i-1}$の操作からなる。
2. $<_{s'}$は$<_s$の$L_{i-1}$の操作集合への制限である。
3. 各トランザクションの根は$L_i$の操作である。
4. 親子関係は$s$のものと同一である。

階層的なスケジュールのうち単一の層のみに注目し、上の層の操作を根とすることで1層のスケジュールに帰着できるということ。

---

このようにスケジュールを層間スケジュールに分割した後にやるのは、各スケジュールのconflict serializabilityを考えることであるが、このときの衝突の意味合いも自動で定義できるものではなく、各操作の間の可換性をアプリケーションの側が与えなければならない。

楽観的な予想としては、こうして分割した層間スケジュールが全てCSRなら元の階層的スケジュールも木削減可能という主張ができそうだが、実際はもう少し厳しくなる。

### 定理6.2

$s$を$n$層スケジュールとする。各$0 < i \leq n$に対し、$L_i,L_{i-1}$の層間スケジュールが全てOCSRであるとき、$s$は木削減可能である。

---

この逆は必ずしも成り立たない。

OCSRを全層に要求するのは少し厳しすぎる条件で、本当に必要なのは「衝突する操作を、違う層で別順にserializeしてしまうこと」を防ぐこと。これを防ぐために有効なのは、高いレベルでの衝突する操作の間には、それ以下のレベルでも衝突が存在すると考えること。

### 定義：Conflict Faithfullness (衝突忠実性)

階層的な$s=(op(s),<_s)$が衝突忠実であるとは、任意の非可換な$p,q\in op(s)$と任意の$i>0$に対して、$p,q$から距離$i$の子孫の中に衝突する組であるような$p',q'$が含まれることとする。

これを導入することで、より緩い条件での木削減可能性保証ができる。

### 定理6.3

階層的なスケジュール$s=(op(s),<_s)$を考える。

$s$が衝突忠実かつ、その層間スケジュールが全てconflict serializableであるとき、$s$は木削減可能である。

#### 証明

根でない層の数$n$についての帰納法で示す。

$n=1$ではページモデルスケジュールを考えればよく、主張は成り立つ。

$n-1$以下で成り立つことを仮定し、$n$層スケジュールを考える。仮定から、第$n-1$層を根とするような部分木を全て枝刈りし、生じるトランザクション森が$n-1$層の非可換操作の実行順序を保存するようにできる。この性質と、$n$層と$n-1$層の層間スケジュールがconflict serializableという性質から、やはり$n$層の操作も全て孤立にでき、よって部分木を枝刈りできる。あとは、この枝刈りも$n$層の非可換操作の実行順を保存するということを示せばよい。二つの$n$層における非可換操作$f,g$が元は$f<g$で入れ替えられてしまったと仮定する。衝突忠実性の定義から、$f$と$g$は$n-1$層に非可換な子$f',g'$を持ち、$f'<g'$であり、$n-1$層の枝刈りステップでもこれが保存されているはずであり、これと矛盾する。よって$f,g$の順も保存されており、$n$層でもやはり成り立つ。$\square$

## 状態に基づいた可換性

さらに並列実行性を高めていくため、可換性をより緩和していくことを考える。

例えば、預金操作と引き出し操作は、一般的な意味での可換性で考えれば非可換である。同額を引き出し・預金する場合、引き出し操作を先にすると預金不足により失敗するというケースが考えられ、入れ替えると違う作用を引き起こすことが分かるため。
ただ、これは逆に言えば、操作に指定する額によっては可換にもなりうるということであり、この際の可換・非可換はデータの状態と操作に与えたパラメータに依存する。

パラメータによっては可換になりうる操作の入れ替えも考慮することで、さらに柔軟なスケジュールを実現しうるわけである。

---

### 定義：状態依存可換性

二つの操作$p,q$がオブジェクト状態$\sigma$で可換とは、任意の可能な操作列$\omega$に対し、状態$\sigma$が与えられた際、$pq\omega$と$qp\omega$が同じパラメータを返すこととする。

---

ただ、状態依存可換性には問題がある

1. 操作は副作用を持つ可能性もあるため、「状態」の定義が難しい
2. たとえ状態の定義が明確になっていたとしても、それを実行中に推定するためのアルゴリズムが必要になる

よって、状態を推定しようとするのはやめ、操作の入出力の値(パラメータ)にのみ着目することで問題をより単純化してみる。例えば、引き出し操作の成功/失敗を出力値として観測可能にすることで、預金残高というオブジェクト状態が間接的に見えていることになる。このアイディアに基づいて返り値可換性を定義する。

---

下矢印で入力パラメータ、上矢印で出力パラメータとする。

### 定義：返り値可換性

$$p(\downarrow x_1,..., \downarrow x_m, \uparrow y_1,..., \uparrow y_n)$$と
$$q(\downarrow x'_1,..., \downarrow x'_m, \uparrow y'_1,..., \uparrow y'_n)$$
が返り値可換であるとは、そのような値が出力される結果になるような任意の可能な操作列$\alpha, \omega$に対し、$\alpha pq\omega, \alpha qp\omega$が同じパラメータを返すこととする。

---