はじめに

サイバーエージェントの26卒内定者がお届けする、CyberAgent 26th Fresh Engineer's Advent Calendar 12/22の記事です！
（本アドベントカレンダーは、サイバーエージェント26卒の有志がお送りするものです。）
今回はデーターベースにおけるトランザクション/同時実行制御について取り扱います。

トランザクションとは？

まずは銀行システムで口座Aから口座Bに1000円送金する場合を考えてみましょう。
システム内部では以下のデータ処理が行われると考えられます。

x = read(A)
y = read(B)
x := x - 1000
y := y + 1000
write(A, x)
write(B, y)

簡単のためread(X)は銀行口座Xの残高を取得、write(X, c)は銀行口座Xの残高をcに書き換えることを表します。

問題点

上記の例で口座Aから1000円を引き落とした後にエラーが発生したらどうなるでしょう？口座Bへの加算が行われない場合、1000円がどこにも存在しない状態になります。このような状況はデータの整合性は保たれるとは言えません。

x = read(A)
y = read(B)
x := x - 1000
y := y + 1000
write(A, x)
write(B, y) <- Error!!

DBMS視点ではreadやwriteが基本操作となっていますが、アプリケーションの立場では上記の一連の操作(トランザクション)がデータベース処理の単位である必要があります。

ここで一連の操作を一つの論理的な処理単位としてまとめ、処理の完了を保証する仕組みをトランザクション処理（transaction processing）といいます。この仕組みにより複数のデータ処理ステップがある場合、すべてのステップを完了するか、どれか一つでも失敗すると全ての操作を元に戻すことができます。（All or Nothing）

ACID特性

データベースのトランザクション処理において必要とされる4つの特性をACID特性といいます。

原子性（atomicity）
トランザクション内のすべての操作が一つの不可分な単位として扱われることを意味します。つまりトランザクションは「全て成功する」か「全て失敗する」かのいずれかであり、途中で失敗した場合はそのトランザクションによるすべての変更がロールバックされる必要があります。
整合性（consistency）
トランザクションが実行される前後でデータベースの整合性が保たれることを保証します。アプリケーションの実装が大きく影響します。
隔離性（isolation）
トランザクションが他のトランザクションから独立して実行されることを保証します。例えば、あるトランザクションがデータを書き込む途中で別のトランザクションがそのデータを読み取ると一貫性が崩れる可能性があります。そのため、データベースは適切なロックやスケジューリングを用いて並行処理中のトランザクション間で干渉が起こらないようにします。
耐久性（durability）
トランザクションがコミットされた後、その変更はシステム障害や電源障害が発生しても失われてはいけません。これを実現するために多くのデータベースではログファイルやジャーナリングといった仕組みを利用しています。

トランザクションの状態

トランザクションの開始から終了まで、transactionは次の状態をとります。

active
- トランザクション実行中の状態
commit処理中
- commitが呼び出され、commit処理が実行されている状態
abort処理中
- abort処理が実行されている状態
- abortが明示的に呼び出されるか、その他の理由でcommit処理に失敗した場合呼び出される
commit済み
- commitが正常に終了した状態
abort済み
- abortが正常に終了した状態

[補足] ロールバックと補償トランザクション

ロールバック（rollback）
- トランザクション処理中にエラーが発生した場合に、そのトランザクションを開始する前の状態にデータベースを戻す操作のことです。
補償トランザクション（compensating transaction）
単純なロールバックが困難な状況で用いられる手法です。特にマイクロサービスアーキテクチャなどで、一連の操作が複数のサービスにまたがる場合に有効です。
具体例 : 例えば、旅行予約システムでフライト予約とホテル予約が別々のサービスとして管理されている場合などが考えられます。フライト予約後にホテル予約が失敗した場合、フライト予約もキャンセルする必要があります。ここで補償トランザクションを使用する場合もあります。

例であげた送金処理の流れ

トランザクション処理で銀行システムの送金の流れ(DB内部)は以下のようになります。（あくまでもイメージ）

並行処理と直列可能性

並行処理

実際のシステムでは多くのトランザクションを処理する必要があります。トランザクションの処理中には二次記憶の入出力待ちやユーザーの入出力待ちの時間が発生します。このような待ち時間を活用してより多くのトランザクションを処理する機能がデータベースには備わっており、複数のトランザクションを同時に実行することをトランザクションの並行処理といいます。

問題点

ここで特に制約をせずに実行すると問題が起きそうです。
例えば2つのトランザクションが同時に同じ銀行口座の残高を更新するケースを考えてみます。

初期残高: 口座Aの初期残高は1000円
トランザクション1: 口座Aに500円を預け入れる
トランザクション2: 口座Aから300円を引き出す

これらが以下の順で実行されたらどうでしょうか？

// 初期残高
balance = 1000

// トランザクション処理
T1: tmp1 = read(balance)       // T1がbalanceを読み取る (tmp1 = 1000)
T2: tmp2 = read(balance)       // T2も同時にbalanceを読み取る (tmp2 = 1000)

T1: tmp1 = tmp1 + 500          // T1が計算を実行 (tmp1 = 1500)
T2: tmp2 = tmp2 - 300          // T2が計算を実行 (tmp2 = 700)

T2: write(balance, tmp2)       // T2がbalanceに700を書き込む (balance = 700)
T1: write(balance, tmp1)       // T1がbalanceに1500を書き込む (balance = 1500)

最終的なbalanceは1500になりますが、本来期待される正しい結果は、1000+500−300=1200となるはずで、データの不整合が起こっています。
これらはACID特性の隔離性（isolation）に反する順序でデータ処理を実行したことに起因します。このような不整合が起こらないように処理することを同時実行制御（concurrency control） といいます。

直列可能性（serializability）

並列実行される複数のトランザクションが、あたかも1つずつ順番に直列的に実行されたかのような結果になれば問題なさそうです。
並行して実行されたトランザクションが直列に実行された場合と同じ結果になることを保証する特性を**直列可能性（serializability) **といいます。
直列可能性はデータベース設計における最も厳密な整合性保証です。

直列可能性の判定

スケジュールの導入

説明のためにスケジュールという概念を導入します。
スケジュールは複数のトランザクションがどのように実行されるかを示す順序のことです。各トランザクションの読み取り（Read）や書き込み（Write）操作が含まれます。スケジュールは直列スケジュールと非直列スケジュールに分類でき、直列スケジュールと等価なものを直列可能スケジュールといいます。
以下のスケジュール1（S1）ではT1がデータAを読み書きし、その後 T2がデータBを読み書きします。

S1:
T1: Read(A), Write(A)
T2: Read(B), Write(B)

ここで次の表記法で書き直してみます。

$S_i$　　：スケジュール$i$
$R_i(A)$：トランザクション$T_i$による項目$A$のread
$Q_i(A)$：トランザクション$T_i$による項目$A$のwrite
$C_i$　　：トランザクション$T_i$によるcommit
$A_i$　　：トランザクション$T_i$によるabort

競合等価

スケジュールの等価性を定義するための手段として例えば競合等価があります。
競合等価とは、2つのスケジュールが同じ競合操作（同じデータに対する読み書きや書き込み）の順序を持っている場合を指します。
特にスケジュールが競合直列可能スケジュールと競合等価であるとき, 競合直列可能といいます。

スケジュール$S$が競合直列可能か否かを判定するためには先行グラフを用いることで判断することができます。

$S$に参加する各トランザクション$T_i$に対してノード$N(T_j)$を作成する
$R_i(A)$が$W_j(A)$もしくは、$W_i(A)$が$R_j(A)$に先行するとき, 有向エッジ$N(T_i)$→$N(T_j)$を引く
$W_i(A)$が$W_j(A)$に先行するとき, 有向エッジ$N(T_i)$→$N(T_j)$を引く
できた図にサイクルができなければ競合直列可能であるといえます。

例)スケジュール$S$が
$$R_1(A)R_1(B)R_2(A)R_2(C)W_1(B)C_1R_3(B)R_3(C)W_3(B)C_3W_2(A)W_2(C)C_2$$
であるとき、先行グラフは以下のようになります。

サイクルができていないのでこのスケジュールは競合直列可能であるといえます。

直列可能性との関係

競合直列可能なスケジュールであり、かつ厳格なスケジュールである場合に直列可能であるといえます。
厳格性についてはまた別の機会に取り扱おうと思っています。

さいごに

今回はトランザクション処理の基本概念からACID特性、ロールバックと補償トランザクション、さらに並行処理と直列可能性について解説しました。また、競合等価と先行グラフを用いた競合直列可能性の判定についても触れました。
次回は厳格性やロック、トランザクションの分離レベルについて取り扱おうと考えています。

参考文献