自作DBMSに必要な体系的トランザクション知識（導入・Isolation編）

はじめに

本記事は、自作DBMSを趣味とする筆者が、トランザクション周りの実装を進めるにあたって、自身の中で腹落ちさせるために調べた内容を記事化したものです。
その動機が故に、多少長いですが、頭から読み進めていくことで、（この記事に辿り着く方であればご存知の基礎的な話を除いて、）自然な思考の流れで理解が進むように心がけたつもりではあります。

人類が生み出したソフトウェアの叡智の結晶の1つであるDBMS、その根幹に鎮座するトランザクション理論は、ユーザー視点での「あって当たり前」という感覚とは裏腹に、幾重もの概念や歴史的な背景が入り乱れ、全体像を把握しきることは大変困難です。
従って、本記事に至っても、筆者の理解不足が含まれている可能性は存分にあり、その際はお手柔らかにご指摘ください。

ちなみに、自作と名を打ってますが、ソースコードは一切登場しません。

トランザクションとは

データベースにおけるトランザクションとは、一言で言うと「一連の読み書き操作をまとめたもの」です。
耳タコな例の銀行の送金処理については今更説明しませんが、一連の操作が「全て成功するか」、「全て失敗するか」のどちらかであることが求められるケースは現実的にも多く、トランザクションという概念が必要になる基本的な動機となります。

ただし、具体的にどのような操作をまとめるかはアプリケーション側の責務であり、DBMS側はそれらがビジネスロジック上持つ意味には関与しません。
DBMSはあくまで、一般的なトランザクションというまとまりに対して要求されるいくつかの抽象的な特性を保証することを責務とします。

ACID

トランザクションが保証すべき性質として、ACIDが広く知られています。
基本的なことは今更解説する必要もないかもしれませんが、幾分注意は必要です。

• Atomicity （原子性）
• Consistency （一貫性）
• Isolation （独立性/隔離性）
• Durability （永続性）

特に微妙な立ち位置にいるのはConsistencyです。
これは例えば、「口座残高がマイナスにならない」、「ユーザーIDは重複しない」といった、ビジネスロジックの整合性を保証する性質とされていますが、具体的にどういった整合性を要求するかはアプリケーション側の責務です。
DBMSの提供する型システムや制約はConsistencyを間接的に支援するかもしれませんが、汎用的なトランザクション処理からしたらその具体は関心の埒外です。
かの有名な『データ指向アプリケーションデザイン』でも

ACIDはほとんどマーケティング用語
特にConcistencyはACIDに含まれない

などと、散々に言われてしまっています。

残りのAtomicity、Isolation、Durabilityは、DBMS側が保証すべき特性です。
これらは相互に関連し合っているものの、各々がどういった保証でどういった理論の元で成り立っているのかを分解して考えることで、トランザクション理論の全体像を捉えやすくなると筆者は考えています。

Atomicity （原子性）

Atomicityは、前述の全て成功するか、全て失敗するかを保証する性質です。
もしトランザクションが完了できなかった場合（Abort）、トランザクション開始前の状態にデータベースを戻す必要があります。

実現方法としては、トランザクション中に行った変更操作を記録しておき、Abort時にはそれらを逆順に実行して元に戻す、という方法が考えられます。
Durabilityを考えるともう少しややこしくなるのですが、本記事ではIsolationに焦点を当てるため、この程度に留めておきます。

注意点は、Atomicity自体は単一のトランザクション内で完結する性質であり、複数のトランザクションが同時に実行される状況を直接扱うものではありません。
それはIsolationの役割です。
やはり分けて捉えることが重要です。

Durability （永続性）

Durabilityは、ひとたびCommitされたトランザクションによる変更は、後に障害などが発生しても失われないことを保証する性質です。
もちろん、隕石が落ちてきたらどうしようもないので、トランザクション文脈では、変更内容が不揮発性ストレージ（ディスクやSSDなど）に何らかの形で記録された時点でDurabilityが保証されるとして考えることは多いはずです（単一DBの場合）。

最も単純な実現方法は、Commitされるたびにその内容をディスクに書き込むことに思われます。
しかし、ディスクアクセスはメモリアクセスに比べてすこぶる低速なため、現実的ではないことは見るも明らかです。
そのため、現実のDBMSでは、メモリ（バッファプール）上でデータの読み書きを行いますが、揮発性メモリを使うトレードオフとして復旧のためのアルゴリズムが要求されます。
WAL（Write-Ahead Log）やARIESという仕組み・アルゴリズムが典型的ですが、本記事ではこちらもこの程度に留めておきます。

Isolation （独立性/隔離性）

Isolationは、複数のトランザクションが同時に実行される状況において互いに干渉しないことを保証する性質です。

干渉しないという表現も曖昧さが残りますが、DBMS側で制御し同時に実行されているトランザクションが常に一つになるように他のトランザクションを待たせておけば（逐次実行）、少なくとも問題は発生しなそうです。
しかし、スループットが出ず現実的でないことは明白です。

そこで、通常は複数のトランザクションをConcurrent（並行）に実行し、各トランザクションの個々の操作は時系列的に入り混じることになります。
しかし、デタラメでいいはずもないので、どのような順序なら許容範囲なのか、部分的に許容されるのか、ということが今後の話の中心となります。

Serializability

題材

今後の話を進めるにあたって、例があった方が分かりやすいので、ある2つのトランザクションを考えます。

$$\begin{aligned} T_{1} &= \bigl\langle\, R_{1}(X),\; W_{1}(X),\; W_{1}(Y) \bigr\rangle\\[4pt] T_{2} &= \bigl\langle\, R_{2}(X),\; W_{2}(Y) \bigr\rangle \end{aligned}$$

• $R_i(X)$はトランザクション$T_i$がデータ項目$X$を読み取る（Read）操作
• $W_i(X)$は同じく$T_i$が$X$に書き込む（Write）操作
• 添字$i$はその操作を実行するトランザクション番号、括弧内の$X$は対象データ項目

※ 以降の図では、X/Yに対する操作をそれぞれ赤/青、Read/Write操作をそれぞれ塗りつぶし無/有で表現しています。

スケジュール

あるトランザクションの集合に対して、含まれる全ての操作の集合を（各トランザクション内での順序を保ったまま）並び替えた列をスケジュールと定義します。

題材のトランザクション集合だと、以下のような並行スケジュールが考えられます。
（これ以外にも沢山あります。）

$$\begin{aligned} S' &= \bigl\langle\, R_{2}(X),\; R_{1}(X),\; W_{2}(Y),\; W_{1}(X),\; W_{1}(Y) \bigr\rangle \\[4pt] \end{aligned}$$

---

$$\begin{aligned} S'' &= \bigl\langle\, R_{2}(X),\; R_{1}(X),\; W_{1}(X),\; W_{1}(Y),\; W_{2}(Y) \bigr\rangle \end{aligned}$$

逐次実行の場合は、それぞれ以下のようになります。

$$\begin{aligned} S_{1,2} &= \bigl\langle\, R_{1}(X),\; W_{1}(X),\; W_{1}(Y),\; R_{2}(X),\; W_{2}(Y) \bigr\rangle \\[4pt] \end{aligned}$$

---

$$\begin{aligned} S_{2,1} &= \bigl\langle\, R_{2}(X),\; W_{2}(Y),\; R_{1}(X),\; W_{1}(X),\; W_{1}(Y) \bigr\rangle \end{aligned}$$

ある並行実行のスケジュールが与えられたとき、「何らかの基準においては、少なくともいずれか一つの逐次実行のスケジュールと等価」と言える基準があるとします。
その場合、その基準の枠内においては、その並行実行は、Isolationが部分的に保証されていると考えることができそうです。

ここは、少し展開が飛躍してしまいますが、広く用いられているConflict Serializabilityという基準について考えていきます。

Conflict Serializability

Conflict Serializabilityは、競合する操作の処理順序に注目する考え方です。

Conflict

まず、Conflict（競合）する操作、を定義します。
以下の3つの条件を全て満たす場合、異なる2つのトランザクション$T_i$と$T_j$にそれぞれ属する操作$op_i$と$op_j$はConflictすると考えます。

1. $T_i \neq T_j$ （異なるトランザクションである）
2. $op_i$ と $op_j$ が同じデータ項目にアクセスする
3. $op_i$ と $op_j$ の少なくとも一方がWrite操作である

具体的には、以下のペアがConflictします。

• $R_i(X)$ と $W_j(X)$ （Read-Write Conflict）
• $W_i(X)$ と $R_j(X)$ （Write-Read Conflict）
• $W_i(X)$ と $W_j(X)$ （Write-Write Conflict）

Read操作同士、$R_i(X)$ と $R_j(X)$は、Conflictしません。

ちなみに、Conflictする操作のペアが存在すること自体が即座に問題なわけではなく、またこの時点では順序関係はなくただのペア関係という点を念頭においてください。

先ほどから用いている題材の場合は、以下の二つのConflictが存在します。

$$\bigl\{\, \{W_{1}(X),\,R_{2}(X)\},\; \{W_{1}(Y),\,W_{2}(Y)\} \,\bigr\}$$

Conflict Equivalence

あるスケジュールが与えられると、Conflictする操作のペア群に順序関係が生まれます。

例として、先ほどの$S'$スケジュールを考えてみます。

$$\begin{aligned} S' &= \bigl\langle\, R_{2}(X),\; R_{1}(X),\; W_{2}(Y),\; W_{1}(X),\; W_{1}(Y) \bigr\rangle \end{aligned}$$

こちらのスケジュールでは、Conflictする操作のペアは以下のような順序関係となります。

$$\bigl\{\, (R_{2}(X) \;\to\; W_{1}(X)),\; (W_{2}(Y) \;\to\; W_{1}(Y)) \,\bigr\}$$

そして、以下の$T_{2}$, $T_{1}$の順序で逐次実行したスケジュールにおけるConflictの順序関係も同様となります。

$$\begin{aligned} S_{2,1} &= \bigl\langle\, R_{2}(X),\; W_{2}(Y),\; R_{1}(X),\; W_{1}(X),\; W_{1}(Y) \bigr\rangle \end{aligned}$$

ある異なるスケジュール間のConflictの順序関係が全て一致する場合、それらのスケジュールはConflict Equivalentであると言えます。
さらに、あるスケジュールがいずれかの逐次実行のスケジュールとConflict Equivalentである場合、そのスケジュールはConflict Serializableと言うことができます。

Conflict Serializableではない例

$S'$はConflict Serializableを満たしましたが、$S''$はそうとは限りません。

$$\begin{aligned} S'' &= \bigl\langle\, R_{2}(X),\; R_{1}(X),\; W_{1}(X),\; W_{1}(Y),\; W_{2}(Y) \bigr\rangle \end{aligned}$$

Conflictの順序を考えると以下のようになります。

$$\bigl\{\, (R_{2}(X) \;\to\; W_{1}(X)),\; (W_{1}(Y) \;\to\; W_{2}(Y)) \,\bigr\}$$

属するトランザクション間の順序に当てはめると、以下のようになります。

$$T_{2} \;\rightarrow\; T_{1}, \qquad T_{1} \;\rightarrow\; T_{2}$$

ある$T_{1}$に属する操作はある$T_{2}$に属する操作より前に行われるが、別の$T_{1}$に属する操作はある$T_{2}$に属する操作より後に行われるということになります。
簡単に言うと、Cycle（循環）しています。
これを満たす逐次実行のConflict順序が存在しないことも直感的に想像が着くと思います。

実装方法

ある並行実行が許容されるか否かの判断軸（Conflict Serializability）は手に入れましたが、その許容される並行実行を実現するにはどうすればいいでしょうか。
現実のDBMSでは、トランザクションはリアルタイムに流れ込み、完了（Commit/Abort）されるまでどのような操作が行われるかも分かりません。
そうなると、「あとから見ればConflict Serializableだった」という結果を、実行中から保証するための仕組みが必要になってきます。

代表的な方法としては、ロック、古典的なTwo-Phase Locking（2PL）があります。
またまた展開が飛躍してしまいますが、2PLに従った結果得られるスケジュールは必ずConflict Serializableになる、という定理が知られています。

Shared/Exclusive Lock

まずロックの基本形を確認します。

	Shared Lockを保持中	Exclusive Lockを保持中
Shared Lockを取得	OK（取得可）	NG（待機）
Exclusive Lockを取得	NG（待機）	NG（待機）

• Shared Lock（共有ロック）: 読み取り時に取得。互いに共有可。
• Exclusive Lock（排他ロック）: 書き込み時に取得。他のロックと競合。
• 競合した場合は、ロックが解放されるまで待機する。

この辺りは馴染みもあるかと思います。Conflictの定義とも似ていますね。

Two Phase Locking

2PLはロックの取得・解放を二段階の順序で行われるようにさらに厳格にします。
簡単に言えば、ロックを解放し始めたら取得してはいけないという制約です。

1. Growing Phase（成長期）: ロックを取得してよい（解放は禁止）
2. Shrinking Phase（縮小期）: ロックを解放してよい（取得は禁止）

横軸を時間軸、縦軸を一つのトランザクションにおけるロックの取得件数とすると以下のようになります。

証明

「2PLに従った結果得られるスケジュールは必ずConflict Serializableになる」という命題は背理法で証明できます。

1. 2PL に従った結果得られるスケジュール $S$ が Conflict Serializable でないと仮定する。
2. 非 Conflict Serializable なので、トランザクションの競合順序のグラフには
   $T_1 \to T_2 \to \dots \to T_k \to T_1$ の閉路が存在する。
3. 辺 $(T_i, T_j)$ は、あるデータ項目 $X$ について
   $T_i$ が Lock $\!-\!$Unlock を済ませた後に $T_j$ が Lock を取得したことを示す。
4. 閉路を一周すると、どこかの $T_i$ が 最初の Unlock 後に未取得の別項目を Lock せざるを得ない。
5. しかし 2PL では「最初の Unlock 以降は新しい Lock を取らない」と定義されるため矛盾。よって $S$ は必ず Conflict Serializable となる。

といった要領です。

デッドロック

2PLは厳格なロック制御のおかげで整合性は保てるものの、デッドロックが発生しやすいというトレードオフもあります。
デッドロック自体の説明はよく聞くと思うので割愛しますが、 潜在的に起こる以上は検知の仕組みと発生時の対処の決めが必要です。
大雑把に言えば、各トランザクションを頂点としてロック待ちのトランザクション間に有効辺を引いたグラフからCycleを検知、ロック保持/待ち側どちらかをAbortするといった方法が考えられますが、詳しくは省略します。

Cascading Abort

2PLを課せば、ある基準においてはIsolation特性を許容できる並行実行制御を実現できました。
しかし、ここまでの話では、トランザクションがAbortされることを考えていませんでした。
ACIDのIsolationだけに着目しており、Atomicity/Durabilityを無視しています。
（一旦分けて把握することが重要と言いましたが、関連し合っている部分はもちろんあるので難しいところです。）

例として、以下の逐次スケジュールと同形の並列実行を考えます。

$$\begin{aligned} S_{1,2} &= \bigl\langle\, R_{1}(X),\; W_{1}(X),\; W_{1}(Y),\; R_{2}(X),\; W_{2}(Y) \bigr\rangle \\[4pt] \end{aligned}$$

もちろんConflict Serializableですが、2PLの定義では、ロックの取得・解放の順序しか登場しないため、以下のようなパターンが考えられます。

1. $T_{1}$がGrowing Phaseにロックを取り$X$を更新
2. $T_{1}$がShrinking Phaseに入りロックを解放
3. $T_{2}$がその新しい$X$を読み取る（ロックが解放されているため可能）
4. その後$T_{1}$がAbort
5. $T_{2}$が読み取った$X$は元の値にロールバックされる

$T_{2}$はロールバックされた値を読んでいるため、Abortしなければ整合性が保てないと考えられます。
さらに、$T_{2}$をAbortすると、その処理に依存する更に後続のトランザクションも連鎖的にAbortする必要が生じます。
この減少をCascading Abortと言いますが、できれば回避したい事態です。

Strict Two-Phase Locking

CascadingAbortを防ぐには、2PLに、ロックはトランザクション終了時まで解放しない、というもう一段の制約を加えます。
これをStrict Two-Phase Lockingと言います。

この制約を設けることで、将来Abortされるかもしれない値は実際に完了（Commit/Abort）されるまで他から読み取られることがないため、CascadingAbortの問題を防ぐことができます。

そもそも現実の実装では「いつロックを解放し始めるか」を一般化し決定しづらいため、トランザクション完了時までロックを保持することで2PLを満たし、結果としてStrict 2PLになっているということも多いはずです。

また細かくは、排他ロックに関してだけ完了時解放の制約を求めるものをStrict 2PL、全てのロックに関して求めるものをStrong(Rigorous) Strict 2PLと言ったりもします。

ANSI SQL-92 Isolation Level

少し話が変わって、Conflict Serializabilityをはじめとして、これまでに登場した概念は馴染みのないもの多いのではないでしょうか。
トランザクションについて学ぼうとすると、Read CommitedやRepeatable Readといった分離レベル、あるいはDirty ReadやPhantom Readといった異常を表す概念に遭遇するはずです。

これはANSI（米国国家標準協会）が1992年に定めたSQLに関する規格、SQL-92のIsolation Levelの定義を由来とします。
世間的にも広く流布している概念ですが、これをそのまま鵜呑みにしてしまうのはいくつかの点で注意が必要です。
まずは、簡単に定義を確認しておきます。

定義

SQL-92 Isolation Levelでは3つのSerializabilityに反するPhenomenon(Anomaly)を定義しています。

Phenomenon	Name	Description
P1	Dirty Read	あるトランザクションから、他のトランザクションのコミットされていない変更が見える
P2	Non-Repeatable Read(Fuzzy Read)	あるトランザクションがある値を2度読み込み、間に他のトランザクションがその値を変更しコミットすると、読み込み結果が変わる
P3	Phantom Read	あるトランザクションが範囲による読み込みを2度行い、間に他のトランザクションがその範囲に値を挿入しコミットすると、読み込み結果が変わる

これらに対応する形で、どこまで防ぐかという観点で、Isolation Levelが定義されています。

Isolation Level	防ぐPhenomenon/Anomaly
Read Uncommitted	なし
Read Committed	P1
Repeatable Read	P1・P2
Serializable	P1・P2・P3

これらは包含関係になっており、上位のIsolation Levelになれば下位のレベルで防ぐ異常も防ぎます。

S2PLとの関係

では、S2PLに従った結果得られる、Conflict SerializableかつCascading Abortを避けるスケジュールは、この定義におけるどこに位置するでしょうか。

Dirty ReadとNon-Repeatable Readは防げていることが分かると思います。
一方で、Phantom Readは、範囲に関してもロックを取るように拡張しないと満たせません。

ということは、ANSIの定義上は、行単位でロックを取るようなS2PLはRepeatable Read相当ということになります。
また、同じSerializableという単語でも、Conflict Serializableといった学術的用語と、ANSIの規格では全く別ということもわかります。

Snapshot Isolationとの関係

先出しになりますが、現代のRDBMSは多くが、MVCC（Multi-Version Concurrency Control）という手法を用い、Snapshot Isolationという別の基準を実現しています。
Snapshot Isolation自体が、1995年の『A Critique of ANSI SQL Isolation Levels』という、ANSIの規格のアンチテーゼのような論文を由来としています。
そういった歴史的背景からも、先ほどのベン図の中には綺麗に収まらない概念です。

• Snapshot IsolationはPhantom Readを防ぐ
  • ANSIの定義上はSerializableとも言える
• しかし、Write Skewという別のAnomalyを引き起こす
  • Write Skewは病院の当直の例が有名です。
• 一方で、Write SkewはS2PLを取っている場合には発生しない

私たちが普段接する、MySQLやPostgreSQLやOracleといったRDBMSはMVCCを実装していますが、それがANSIの定義とは相容れない概念にも関わらず、Isolation LevelとしてはSQL-92の用語を使っています。
よく耳にする「MySQLはRepeatable ReadでもPhantom Readを防ぐ」といった矛盾もうこういった背景があります。

Snapshot Isolation

少々順序が前後しましたが、Snapshot Isolation(SI) の定義を簡潔に整理します。

1. あるトランザクションは、開始時点までにコミットされた全行の最後の値をスナップショットとして保持し、以降の読取りでは常にそのスナップショットを参照する。
2. あるトランザクションは、開始以降に他のトランザクションによりコミットされた更新と、自身の更新が競合した場合にAbortする。

読取りは常にスナップショットを使うため他トランザクションの更新と競合せず、実装上も読み取りのための共有ロックを取る必要が生じません。
そのため、2PLで弱点だったロック待ちやデッドロックが発生しやすいという問題が緩和されています。
Write同士は競合するため、引き続きロック機構が必要となることが多いです。

MVCC （Multi-Version Concurrency Control）

Snapshot Isolationはあくまで仕様なので、それをどのように実装するかはDBMS側に委ねられています。
MVCC（Multi-Version Concurrency Control）という実装手法が有名です。
これは、同じデータ項目に関して複数のバージョンを実際に保存する実装を取ります。

最後にPostgreSQLを参考(あくまでPostgreSQL-Likeで厳密ではないです)に、MVCCをどう実装するかを駆け足で見ていきます。

行（Tuple）

一般的なRDBMSでは「テーブルの行（Tuple）」が更新対象です。
PostgreSQLでは、行ヘッダに2 つのトランザクション識別子 (tx_id)を追加します。

	意味
xmin	行を挿入したトランザクションのtx_id
xmax	行を削除したトランザクションのtx_id（初期値はNULL）

トランザクション識別子は、一意かつ単調増加（前後関係）が分かるように採番します。

DML

各種DMLの操作時にはどのような変更を行うか考えます。

操作	変更点
INSERT	xmin ← 自tx_id, xmax ← NULL
UPDATE	旧行: xmax ← 自tx_id、新行: xmin ← 自tx_id, xmax ← NULL
DELETE	旧行: xmax ← 自tx_id

UPDATEは「古いバージョンを削除 → 新バージョンを挿入」の 2 ステップで行います。

可視性ルール

各トランザクションは、開始時点での他の完了(Commit or Abort)しているトランザクションと未完了のトランザクションの一覧を持ちます。
行をスキャンする際には、以下を両方満たす行のみを可視と判定します。

1. xmin が 開始時点でCommit済み
2. xmax が NULL または 開始時点でAbort済み または 開始時点で未完了

書込み競合とAbort

「開始以降に他のトランザクションによりコミットされた更新と、自身の更新が競合した場合にAbortする」という、Snapshot Isolationの制約を満たすために、書き込み時には以下のような手順を取ります。

1. 書込み対象行にWriteロック取得を試みる
2. 開始時点で未完了のトランザクションが先に書き込みを行なっていればロック待ちとなる
3. 他のトランザクションが完了（Commit or Abort）すると、ロックが解除される
4. xmaxが、Commitされていたら自身をAbort、Abortされていたら処理を進める

Serializable Snapshot Isolation

Snapshot Isolationでは、前述の通りWrite SkewというAnomalyが発生する可能性があります。
これを解決する、Serializable Snapshot Isolationが現代では定義され、PostgreSQLはこれを実装していますが、今回は割愛します。

おわりに

筆者の理解の限界から、最後の方は駆け足になってしまいましたが、とりあえずIsolationに関する基礎は、順を追ってできる限り平易に解説できた気がします。
自作DBMSという酔狂な試みだけでなく、普段実務で触るMySQLやPostgreSQLなどのトランザクション周りの挙動に関しても、幾分かは推測しやすくなったのではないでしょうか。

今回はIsolationのみに着目しましたが、まだDurability、途中で障害が起きた際にも不整合が起きないようにする仕組み、についてはほとんど触れてません。
余力やニーズがあれば、いつになるか分かりませんが、後編の記事を書こうと思います。