###### tags: `TransactionalInformationSystems`

# 10章 実装にともなう諸問題

## ロック管理機構のデータ構造

ロック管理機構の3つの要件：

1. ロックが要求されたとき、ロックの競合を効率良く検出できること。
2. ロックが解放されたとき、そのロックにブロックされていたトランザクションの実行を再開できること。
3. トランザクションが終了したとき、ロックを全て一度に解放できること。

### リソース制御ブロック

まず、ロックの対象となるリソースの識別子をキーとしたハッシュテーブルを持つ。各エントリはリソース制御ブロック(Resource Control Blocks, RCB)へのポインタを保持する。

競合はハッシュテーブルの参照を行うだけで検出できる。

### ロック制御ブロック

共有ロックは同じリソースに対して複数保持でき、また複数のロック要求が待機しうるため、それらをRCBを起点とする連結リストとして保持する。これをロック制御ブロック(Lock Control Blocks, LCB)と呼ぶ。リストの先頭にあるLCBから順にロックが許可されていく。starvationを防ぐため、基本的にLCBの追い越しは認められない。

### トランザクション制御ブロック

最後に、同じトランザクションに属するLCBを全て判定する構造が必要になる。1トランザクションごとに、複数のLCBへのポインタを連結リストとして保持する。これをトランザクション制御ブロック(Transaction Control Block, TCB)と呼ぶ。

マルチスレッドなデータサーバ等では、これらロック管理機構自体にも排他制御のためのラッチが必要になる。しばしばハッシュテーブルのエントリに付属するフラグとして実装される。

このようなRCB,LCB,TCBのハッシュテーブルによる管理は、リソースの種類を問わない(インデックスのキーだろうがページだろうがADTだろうが、識別子さえあればハッシュで管理できる)という点で拡張性が高い。

## 多重粒度ロックと動的なロック昇格

粒度の細かいロックは、並列実行性を高める代わりにロック管理のためのメモリ消費量が大きい。粒度の粗いロックは逆である。複数の粒度のロックをサポートし、トランザクションの特性によってどれを採用するか選択できるようにすればなおよい。

多重粒度ロックを実現するための最大の問題は、粒度の違うロックの間の競合を検出すること。このための方式には、エンジニアが経験的に考案してきた以下の手法が考えられる。

共有ロックをS、排他ロックをXと表記する。それに加えて新たなロックモード、intention lock(IS,IX)を導入する。あるリソースにロックをかけたとき、それより粗い粒度のintention lockを全て取得する。これはオブジェクトモデルにおける延長ロックの概念に似ている。

ついでにもう一つ、テーブル全体をスキャンするが更新は一部しか行わないようなトランザクションのためのロック、SIXも考える。これはSとIXを同時に取得するもので、更新の必要が発生した時にはいつでもそのレコードにXを取得できるのが特徴。

これらロックの間の両立性は以下の表となる。

| | S | X | IS | IX | SIX |
| -- | -- | -- | -- | -- | -- |
| S | + | - | + | - | - |
| X | - | - | - | - | - |
| IS | + | - | + | + | + |
| IX | - | - | + | + | - |
| SIX | - | - | + | - | - |

ロック獲得規則はシンプルで

1. トランザクションは、実行したいread/writeに応じて、任意の粒度のS/Xロックを要求できる。
2. 指定した粒度のS/Xロックが取得される前に、そのリソースを含み、それよりも粗い粒度のリソースに対するIS/IXロックをすべて取得しなければならない。

途中でより粗い粒度のロックに変換したいケースも生じうる(lock escalation)。これは、粗い粒度のロックを要求し、取得完了後に細かい粒度のロックを全解放することで実現される。商用システムでは、RCBやLCBのサイズが肥大化して一定値を超えた際に使用されることがある。

## 透過的なバージョニング

5章で記述してきたような、ROMVに代表されるバージョニングをどのように実現するかも考えていく。

### バージョンプール

最新のバージョンを通常のレコードの位置に配置し、それ以前のバージョンを「バージョンプール」に配置する方法。各バージョンは、タイムスタンプと直前のバージョンへのポインタを持ち、連結リストを辿ることで時系列をさかのぼることができる。

利点としては

- 現在のバージョンのみアクセスするトランザクションが効率的
- レコード配置が構造化されているデータにも問題なくバージョニングを適用できる
- ガーベジコレクションが行いやすい(バージョンプールを見ればよい)

が挙げられる。

レコードの削除の際には、最新のバージョンに削除フラグを立てることで代わりとする。

#### バージョンプールにおけるガーベジコレクション

もう利用されていないバージョンは削除してストレージを節約したい。

ROMVの場合、read-onlyなトランザクションのうち最も古いものに参照されるバージョンがあったとき、それよりも古いバージョンはもう参照されることが無いので削除してよい。

また、バージョンプールの並べ方を「直後のバージョンが作成されたタイムスタンプ」の昇順にすることで、アクティブなread-onlyトランザクションのうち最も古いもののタイムスタンプを境に、それ以前のものを全てガーベジコレクションしてもよいという性質が成り立つ。そのため、この場合ガーベジコレクションは単にバージョンプール上の一点を指すポインタとして実装できる。

このようなタイムスタンプの付け方は実のところ自然で、なぜならレコードがバージョンプールに移されるのは直後の最新バージョンが作成されたタイミングだから。

### バージョン選択表

現在のバージョンと合わせてバージョン選択表を持つ手法もある。この表には、古いバージョンへのポインタとそのタイムスタンプがそれぞれ保存される。各レコードのバージョン数が極めて少ない場合は有効になりうる。

## トランザクション内での並列性

トランザクションが複数のスレッド(サブトランザクション)を生成し、それらを並列に実行したい(しつつ、逐次実行性を維持したい)場合に、トランザクション内で適用する2PLを考える。

1. トランザクション木の各葉は、データ操作に必要なロックを2PLに従って取得し、トランザクション終了時まで保持する。
2. スレッドを終了するとき、スレッドが保持していたロックは全て親に継承される。
3. スレッドによるロック要求が許可されるのは、そのデータアイテムに競合するロックが存在しないか、あるいは競合ロックを保持しているのがそのスレッドの祖先のみである場合。

ここでのロックの継承はオブジェクトモデルにおける延長ロックと同じ考え方に基づいている。ただ、延長ロックはトランザクション間の並列実行、継承ロックはトランザクション内での並列実行なので目的は異なる。

---

### 定理10.1

マルチスレッドトランザクションのための2PLは、トランザクションがserialかつ、各スレッドもserialに実行されるのと等価なスケジュールを出力する。

---

ちなみに、トランザクション内でのこのような同時実行制御と、トランザクション間のオブジェクトモデルに基づく同時実行制御を組み合わせて行うこともできる。

## チューニングの選択肢

パフォーマンスを向上させるために選択しうる小手先の技術を考えていく。ただし、よく考慮した上で使わないと簡単にinconsistentなデータを生じうるし、パフォーマンスが上がるとも限らないので基本は安全が保証されたシステムの提供する機能を利用すべき。

### 手動ロック

- ロックの粒度をユーザ側で指定できる場合がある。
- lock conversionはデッドロックを起こしやすいため、ユーザ側で「for update」句を使って最初から排他ロックを要求するようなことが可能。
- lock, unlockをユーザが手動で実行できるサーバもある(!?)

### SQL分離レベル

ロックの厳しさによる様々な「分離レベル」が、SQL標準でも定義されており、防ぎたい問題と求めるパフォーマンスに応じてユーザが選択することができる。

---

#### 定義：分離レベル

スケジュール$s$が分離レベル *read uncommitted* で実行されるとは、全てのwrite lockがS2PLに従って制御されることとする。

スケジュール$s$が分離レベル *read committed* で実行されるとは、全てのwrite lockがS2PLに従い、read lockが、少なくともクライアントに発行されたデータサーバ操作の実行期間の間保持されることとする。

スケジュール$s$が分離レベル *serializability* で実行されるとは、そのスケジュールがS2PLで生成可能であることとする。

---

read uncommittedは、そもそもread lockを一切用いないので、データの一貫性が全く保証されない。ただし、読み込みがメインのトランザクションのオーバヘッドが極めて小さいので、正確さが必要ない統計解析などで用いうる。

read committedは、dirty readのように無効な値を読み込む問題は防ぐものの、lost updateは防げない。

serializabilityの他にも、SQL標準や商用システムは「repeatable read」なる分離レベルを設け、phantom problem以外は全て防げる分離レベルと定めているが、それ以外の問題の具体的な定義がなされておらず、いくらかad hocな手法である。

また、マルチバージョンな実行制御に関する分離レベルも定義できる。

#### 定義：マルチバージョン分離レベル

*multiversion read committed* 分離レベルで実行されるトランザクションは、read操作が発行された時点でコミットされているうち最新のバージョンを読み込む。write操作は、トランザクション終了時まで保持される排他ロックで制御される。

*snapshot isolation level* 分離レベルで実行されるトランザクションは、トランザクション開始時点までにコミットされた最新のバージョンを読み込む。また、同時に実行されるトランザクションのwrite setが互いに素である。

multiversion read committedはlost updateを防げない。(ROMVのようでいて、read操作が読み込むバージョンが微妙に異なる)
snapshot isolationの方が強い条件である。ただし、snapshot isolationもserializabilityを完全に保証はせず、以下の例が反例となる。

$$r_1(x_0)r_1(y_0)r_2(x_0)r_2(y_0)w_1(x_1)c_1w_2(y_2)c_2$$

write setが互いに素でreadが最新のバージョンを読んでいるのでsnapshot isolationはこのスケジュールを通してしまうのだが、衝突のサイクルが存在するためMCSRでなく、(実のところMVSRでもなく)、実際$x_0=5,y_0=5,x+y\geq 0$という制約があったときに$t_1,t_2$がそれぞれ$x,y$から$10$ずつ引いてしまい、合計値が負になるという問題が生じる(演習問題10.4)。

ただしsnapshot isolationには、正式な定義に落とし込んで性質を研究しやすいという良さがある。

#### 定義：Snapshot Isolationのフォーマルな定義

マルチバージョンスケジュールがsnapshot isolationであるとは、次の2つの条件を満たすこととする。

1. バージョン関数がread操作に割り当てるバージョンが、直前にcommitされたwrite操作のものである。すなわち、$r_i(x)$は$w_j(x)$で$w_j(x)<c_j<b_i<r_i(x)$ ($b_i$は$t_i$の開始マーカー)を満たすものに割り当てられ、その他の$w_h(x)$で$w_h(x)<b_i$かつ$c_j<c_h<b_i$であるようなものが存在しない。
2. 並列に実行されるトランザクションのwrite setが互いに素である。すなわち、$t_i,t_j(i\neq j)$について、$b_i<b_j<c_i$または$b_j<b_i<c_j$ならば、$t_i,t_j$は同じデータアイテムに書き込まない。

snapshot isolationとMVSRの間には包含関係がない。

---

#### 定義：Snapshot Isolation Serialization Graph (SISG)

マルチバージョン履歴$s$のSISGとは、トランザクションをノードに持つ有向グラフで、以下の辺を持つものとする。

$r_j(x_i)$があるとき辺$t_i\rightarrow t_j$を持つ。$r_k(x_j),w_i(x_i)$の組に対して、

1. $c_i<c_j$ならば $t_i\rightarrow t_j$
2. $c_j<c_i$ならば $t_k\rightarrow t_i$

を持つ。

---

SISGはMVSRにおけるserialization graphの分岐条件$w_i(x_i)<w_j(x_j)$を$c_i<c_j$に置き換えたようなものとなっている。

#### 定理10.2

$s$がsnapshot isolation基準に従うバージョン関数を持ち、書き込むアイテムはその以前に読み込むものとする。このとき、以下の性質が成り立つ。

1. $s\in MVSR \Leftrightarrow$ SISGが閉路を持たない
2. $s$がsnapshot isolated $\Leftrightarrow$ SISGに、あるデータアイテム$x$に由来する辺のみからなるような閉路が存在しない。

### 短いトランザクション

トランザクション分割の話題が8章で出たが、どこでトランザクションを分割するか自動で決めるのは難しい問題である。一つ確かに効果的といえるのは、ユーザの入力待ちになった時間でトランザクションを一度終わってしまうこと。

例えば飛行機予約であれば、座席情報を取得してユーザに報告した段階で最初のトランザクションを終了してしまう。そうすると、もちろん予約の成功は保証されなくなる(実際に予約を試みるまでの間の時間に他の予約が入ってしまう可能性がある)のだが、そのようなことが起きる頻度は低く、やり直してもらえばいい。
最近では、座席情報を調べた段階で仮予約を生成し、それが一定時間で無効になるような設定によってユーザの利便性が向上している。

### マルチプログラミングレベルの制限

同じデータアイテムに対するロック要求が大量に集中すると、並列トランザクションの大半がブロックされてしまい、処理が遅々として進まなくなる(thrashing)。これはデッドロックが全くない状況でも起こりうるし、デッドロックも起こったら尚更酷いことになる。これを防ぐための手段の一つは、データサーバがmultiprogramming level(MPL)を制限すること、つまり、同時に並列実行されるトランザクションの数をシステムが制限すること。

新しく発行されたトランザクションはトランザクション許可キューに入れ、MPLが適切な値の時にキューからトランザクションを取り出して実行開始する。

MPLの値自体を20ぐらいの値に設定したり、トランザクションの種類ごとに個別の上限を設定したりすることもできるが、次の節で説明するように、MPLでない負荷指標を用いた自動制御も考えられる。

## 負荷制御

並列実行されるトランザクションの数が多すぎると、ロックの頻繁な衝突による極端な速度低下が起こる。その一方で少なすぎても実行速度は遅くなる。これらの間にある最適な点は、実行されるトランザクション群の性質やシステム構成によって違ってくるため、一律な答えは存在しない。したがって、適切な点をある程度自動で推定し、システムの状態を維持する仕組みが必要になる。

### フィードバック駆動方式

ある種の負荷指標である「衝突率」、または類似の指標を観測し、一定値を上回ったらなんらかの処置をとる方式。

1. 許可による制御：衝突率が一定を下回るまで、新しく到着するトランザクションの実行を許可しないことで負荷を下げる。
2. 中止による制御：衝突率が一定を下回るまで、一部の実行中トランザクションをabortすることで負荷を下げる。

abortされたトランザクションを再開するタイミングとしては、それをブロックしたトランザクションが全て終了したタイミングが経験的に良いとされる。

abortするトランザクションを選択する基準としては、
- 保持しているロックの数が少なく、
- 多くのトランザクションにブロックしブロックされている

ようなものが好ましい。ただ、これだけだと同じトランザクションが何度もabortされるstarvationの危険があるので、保持ロック数$\times$abortされた回数 の値が最小なトランザクションを選択するのが一つの現実的な選択肢。

また、負荷指標をどのように定義するかも重要な話題になってくる。

トランザクションが全て似たような性質であるときは、「ブロックされているトランザクションの割合」が負荷指標として十分で、例えばそれが30%を上回ったら処置をとるなどが考えられる。その一方で、様々なワークロードが存在する場合には指標として不十分で、例えば以下で定義される「衝突率」の方がより適切になる。

$$\frac{全トランザクションの合計保持ロック数}{ブロックされていないトランザクションの保持ロック数}$$

トランザクションに、保持するロック数に基づいて重みづけするということ。処置の基準は、多くの場合において1.3が最適であることが経験的に確かめられている。

### 待機深度の制限

トランザクションごとに、その実行状況に基づいて定まる待機深度(wait depth)を定義する。

- 実行中トランザクションの待機深度は0。
- 待機深度$i$のトランザクションによってブロックされているトランザクションの待機深度は$i+1$。

そこで、待機深度が2以上であるようなトランザクションの存在を許さない(ブロック連鎖上のどれかをabortする)ことで、負荷を減らす方式が考えられる。

この方式は実装が比較的シンプルで、CPUとI/Oのリソースが豊富なら衝突率ベースの方法と同等のパフォーマンスを発揮する。
一方、データ操作が過密に集中した場合はトランザクションの中断と再開がハイコストになりうる。

## 演習問題

### 10.1 lock escalationがデッドロックを引き起こす例

テーブル$a_1$内にレコード$r_1,r_2$が、テーブル$a_2$内に$r_3,r_4$がある状況を考える。トランザクション$t_1$が$r_1,r_3$にwrite lockをかけ、$t_2$が$r_2,r_4$にwrite lockをかけているとき、$t_1$が$r_1$のロックを$a_1$全体に、$t_2$が$r_4$のロックを$a_2$全体に昇格しようとすると、お互いにレコードレベルのロックの解放待ちになってデッドロックが起こる。

例えばこれがどちらも$a_1$のロック昇格を望むだけなら一方がブロックされるだけなのでデッドロックにならない。

このようなデッドロックは、read/writeもしくはwrite/writeロックの競合時に起きるものなので、どちらも読み込みならば昇格も問題なく行われデッドロックは発生しない。

### 10.2 lock de-escalation(escalationの逆)が意味を成す例

- ロックの粒度を下げる=ロックを一部解放してしまうため、2PLのうち後半の解放フェーズに使わないと安全でない。
- 長いトランザクションの途中で、最初は表全体からデータを読み取り、その後に一部のレコードに対してのみ書き込みを行いたい場合が考えられるが、これは同様の機能がSIXロックモードで実現できるため意味が薄い。

### 10.3 SQL分離レベルの各クラスに属するスケジュールの例

- $r_1(x)c_1 \in \textrm{serializability}$
- $\textrm{repeatable read - serializability}$：後述
- $r_1(x)r_2(x)w_1(x)c_1w_2(x)c_2\in \textrm{read committed - repeatable read}$ (lost updateの原因)
- $w_1(x)r_2(x)c_1c_2\in \textrm{read uncommitted - read committed}$
- $w_1(x)w_2(x)c_1c_2\notin \textrm{read uncommitted}$

repeatable read-serializabilityに入りうるのは、「phantom problemは起こすが他の問題は防ぐ」ようなスケジュール。phantom problemは述語指向のロックのような複雑なロックにおいて起こる問題なので、単純にページモデルでの例は挙げられない。

8章2節の内容を参照して、

- $t_1$ : delete from emp where dep="Service" and pos="Manager"
- $t_2$ : select name, pos, salary from emp where dep="Service"
- $t_1$ : insert into emp values ("Smith", "Service", "Manager", 40000)
- $t_1$ : update emp set dep="Sales" where dep="Service" and pos <> "Manager"
- $t_1$ : insert into emp values ("Stone", "Service", "Clerk", 13000)

こうすると、$t_1$の最初のステップはService部門のManagerのレコードのみロックするため、その削除後の$t_2$のService部門列挙クエリはロックに引っかからず実行できてしまう。実行結果がManagerのいない名簿になってしまっており、意図しない結果になっておりphantom problemが起こっている。

### 10.4 snapshot isolatedな履歴でデータの一貫性を壊す例

snapshot isolationの定義の箇所で記述済み。

### 10.5 snapshot isolationを保証するCC

各アイテムについて、commitされたものと最新のものの2バージョン、およびそれらの書き込みタイムスタンプを保持する。readではcommitされたものを読み込み、writeでは、書き込みたいアイテムの最新のタイムスタンプがそのトランザクションの開始タイムスタンプよりも新しいときに不正状態なのでabortする。commitの段階でそのとき最新のバージョンをcommitされたバージョンに変換する。

### 10.6 MVSRとsnapshot isolationはお互いを包含しないこと

$$r_1(x_0)r_1(y_0)r_2(x_0)r_2(y_0)w_1(x_1)c_1w_2(y_2)c_2 \in \textrm{snapshot isolation} - MVSR$$ $$w_1(x_1)w_2(x_2)c_1c_2 \in MVSR - \textrm{snapshot isolation}$$