RDBMS(Relational Database Management System)について勉強しましたので、メモをとります。

目次

RDBMSとは
Race Conditionとは
RDMBSでのRace Conditionを防ぐ方法
Transactionとは
TransactionのIsolation Levelの話
Deadlock降臨
まとめ

RDBMSとは

RDBMSとはRD(Relational Database)のモデルに基づいてデータを管理(保存、更新など)するシステムのことです。Oracle、Mysql、Microsoft SQL Server、PostgreSQLなどが該当します。
元となるEdgar F. Coddさんが提唱したRelational Modelには細かいルールがたくさんありますが、RDBMSの特徴は最低限二つあります。

1.データの関連性に基づき、テーブル形式で表示できます。
例： user Table

ID	Name	Level
1	Alfred	10
2	Baison	20
3	Cathy	30

2.データに対する関連性に基づいたオペレーションを提供できます。
例：SQLによるCRUD(create, read, update, delete)オペレーションを処理できます。

Race Condition

Race Conditon(レース　コンディション)とは複数なエージェント(DBを操作できるプロセス、スレッドなど)が同時に同じデータにアクセス(読み出す、書き込むなど)するときに起きるデータに不整合が生じる現象です。
例：

Time	UserA	HP	UserB
1	get HP	100	get HP
2	set HP = HP -10	-	set HP = HP - 10
3	get HP	90	get HP

例えばゲームの中ユーザーAとユーザーBが協力してボスを討伐します。ボスの初期HPは100とします。
二人のユーザーがTime=1の時から同時に攻撃を仕掛けましたが、Time=3の時ボスには一回しかダメージが入っていません。Race Conditonではこのようにデータの不整合が起きます。

RDMBSでのRace Conditionを防ぐ方法（排他制御）

RDMBSでは主にTransaction(トランザクション)システムを使ってRace Conditionを防ぎます。Race Conditionを防ぐ方法として、データに同時に一人しか取れないロックを掛けて、ロックを取った人しかアクセスできないようにします。他の人がデータにアクセスしたい場合、ロックを取った人がロックを開放のを待たなければなりません。
RDBMSとRedisなどのKVS(Key Value Store)ではcas(check and set)というpessimistic locking(悲観的ロック)システムを使用して排他制御を行なっています。データにはロックを表すステートを持っています。アクセスを試みるエージェントはまずロックの状態をcheckして、0であれば(ロックが取られていない状態)、それを1にsetしてデータにアクセスします。ここではあらかじめデータがロックされる可能性が高い（悲観的）と想定し、操作を行う前にロックを確認します。
実はRedisにもTransactionがあります（Watch,Multi,EXEC,DISCARD）、違いはRDBMSのTransactionはRoll Backできますが、Redisはそれができません。RDBMSではTransactionの中でエラーが起きたらTransactionの開始する前の状態に巻き戻してくれますが(Roll Back)、Redisではエラー以降部分の操作を続けます。

Transactionとは

Transactionとはデータへの複数のオペレーション（操作）を含む論理的なユニットです。同じデータに対して、同時複数なTransactionがあっても、最終的にcommit（操作をデータに反映）できるのは一つだけです。Transactionシステムを使うことで、データへの並列なアクセスをシリアライズでき、Race Conditionを防げます。

Transactionの例、MySQL 5.7 Reference Manualより：

START TRANSACTION;
SELECT @A:=SUM(salary) FROM table1 WHERE type=1;
UPDATE table2 SET summary=@A WHERE type=1;
COMMIT;

Race Conditionを防ぐなどの目標を達成するために、TransactionはACID要件を満たさないといけません。

ACIDとは

ACIDとはAtomicity、Consistency、Isolation、Durabilityの四つTransactionが持つべき性質です。

Atomicity(原子性):一連の操作を含むTransactionは不可分であり、操作は全て完了あるいは全て実行されないの二状態しかありません。つまり途中のどれかの操作が実行できない場合、全操作をRoll Backします。
Consistency(一貫性・整合性):データへ操作はルールを満たします。ルールの例：INT型のフィールド（コラム）に文字列が入っていない、データ操作後db内データ構造（b-treeなど）が壊れていない。
Isolation(分離性):Transactionがお互い分離・独立であることを保証します。主にはRace Conditionを起こさせない。
Durability(永続性):Transactionが完了する時データへの操作が永続的にシステムの保存されます。たとえ電源落ちなどの理由でシステムがフェイルしてもTransactionが反映されることを保証します、詳しくは別の記事で考察しました:MysqlのInnoDBエンジンにおけるデータ操作考察

TransactionのIsolation Level(分離レベル)の話

TransactionにはIsolationという性質を持っています、それゆえTransaction間のRace Conditionを防げます。しかしRDBMSは違うレベルのIsolationを実装しています(ANSI/ISOのSQL基準に定義されています)。完全にTransactionをシリアルに並べて実行すれば完全にRace Conditionを防げますが、データアクセスの効率が悪くなります(同時に1ユーザーしかボスのHPを見れないとか)。
効率を考えて、現在のRDBMSは普通四つのIsolation Levelを実装しています。これらはあくまで論理的な定義なので、各RDBMSには独自な実装があります。ここでは伝統な2PKの実装とMysql(5.7.19)が実装したIsolation Levelを説明・検証していきたいです。

2 Phase Locking

2 Phase Locking(2PK)は並行性制御(concurrency control)の手法の一つです。前述ではデータにロックを掛けると説明しましたが、2PKではロッックをRead Lock(読み出すロック)とWrite Lock(書き込むロック)に分けます。ロックを取ったエージェントでしか対応操作を行えません。加えて、ロックを取る時にルールがあります。

Read Lockはシェアできます。一つのTransactionが特定のデータレコード（テーブルのRow）のRead Lockを取得しても、他のTransactionは同じデータレコードのRead Lockを取得できます。Read Lockは主にSqlのSelect文が実行される時取ります。
Read LockとWrite Lockは排他的です。一つのデータレコードのRead Lock/Write Lockが取られたら、他のTransactionはこのデータレコードのWrite Lock/Read Lockを取得できません。
Write Lockはシェアできません。一つのデータレコードのWrite Lockが取られたら、開放されるまで他のTransactionはこのWrite Lockを取得できません。

他のディテールはWikiへgo~

四つのIsolation Level

制約の厳しい順で各Isolation Levelを説明していきます。

Serializable

Transactionがアクセスするデータに対して、Read Lock、Write Lockを取り、commit時開放します。加えて、WHERE SQL文などに応じてRange Lockも取っています。
例えばuserテーブル

ID	Name	Level
1	Alfred	10
2	Baison	20
3	Cathy	30
に対して

TransactonA

BEGIN;
SELECT * FROM user
WHERE Level BETWEEN 10 AND 30;
COMMIT;

を実行したら、Commitされるまで現在テーブル内にある三レコードに加えて、Level=15の様なレンジ内のレコードを他のTransactionは更新できません。

TransactionB

BEGIN;
/* T = 2*/
INSERT INTO user(ID,Name,Level) VALUES ( 4, 'Den', 15 );
/* T = 3*/
COMMIT;

MysqlでのSerializable

MysqlではSerializable LevelのTransactionの中の全てのSELECT文をSELECT... LOCK IN SHARE MODEに変換します。
上記のようなuserテーブルを用意し、LevelでIndexを作成してから、TransactionAを開始：

MysqlTransactonA

>BEGIN;
/* T = 1*/
>SELECT * FROM user
WHERE Level BETWEEN 10 AND 30;
+------+--------+-------+
| ID   | Name   | Level |
+------+--------+-------+
|    1 | Alfred |    10 |
|    2 | Baison |    20 |
|    3 | Cathy  |    30 |
+------+--------+-------+
3 rows in set (0.00 sec)
/* T = 4*/
>COMMIT;

TransactionBでは

MysqlTransactionB

>BEGIN;
/* T = 2*/
INSERT INTO user(ID,Name,Level) VALUES ( 4, 'Den', 15 );
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction
/* T = 3*/
>COMMIT;

という風にTransactionAでロックを取られたデータを更新しようとしたら、まずはtimeoutまで待つ、それでもロックが開放されなければ諦めます。

Repeatable Reads

Repeatable Readsレベルでは操作対象データのみに対してのにロックを取得し、commit時ロックを開放します。Range Lockを取りません。なのでPhantom Reads現象が起こります。
例：同じくuserテーブルに対して、

TransactonA

BEGIN;
/* T = 1*/
SELECT * FROM user
WHERE Level BETWEEN 10 AND 30;
/* T = 4*/
SELECT * FROM user
COMMIT;

を実行します、TransactionAがcommitする前にTransactionBで

TransactionB

BEGIN;
/* T = 2*/
INSERT INTO user(ID,Name,Level) VALUES ( 4, 'Den', 15 );
/* T = 3*/
COMMIT;

を実行したらT = 4の時点でTransactionAからはT = 1の時存在しなかったLevel=15のレコードが読み取れてしまいます（これぞPhantom Reads）。しかしデータレコードへのRead Lockはcommitするまでずっと保持しますので、SELECTしたレコードが他のTransactionに変更されることがなく、何回読み込んでも同じ値となります(ゆえにRepeatable Readsと呼びます)。

MySQLでのRepeatable Read

高頻度のアクセスを想定したMysqlは実装時2PKに加えMVCCも利用しています。snapshotを合わせて利用してIsolation Levelの要件を満たしています。Transaction内データをSelectする時snapshot(一時のデータの状態)を保存しましたので、Phantom Read現象を回避しました。

MysqlTransactionA

/* T = 1*/
>SELECT * FROM user
WHERE Level BETWEEN 10 AND 30;
+------+--------+-------+
| ID   | Name   | Level |
+------+--------+-------+
|    1 | Alfred |    10 |
|    2 | Baison |    20 |
|    3 | Cathy  |    30 |
+------+--------+-------+
3 rows in set (0.00 sec)
/* T = 4*/
>SELECT * FROM user
+------+--------+-------+
| ID   | Name   | Level |
+------+--------+-------+
|    1 | Alfred |    10 |
|    2 | Baison |    20 |
|    3 | Cathy  |    30 |
+------+--------+-------+
3 rows in set (0.00 sec)
>COMMIT;
/* T = 5*/
>SELECT * FROM user WHERE Level BETWEEN 10 AND 30;
+------+--------+-------+
| ID   | Name   | Level |
+------+--------+-------+
|    1 | Alfred |    10 |
|    2 | Baison |    20 |
|    3 | Cathy  |    30 |
|    4 | Den    |    15 |
+------+--------+-------+
4 rows in set (0.00 sec)

を実行します、時間Tに合わせてTransactionBで

MysqlTransactionB

>BEGIN;
/* T = 2*/
>INSERT INTO user(ID,Name,Level) VALUES ( 4, 'Den', 15 );
Query OK, 1 row affected (0.00 sec)
/* T = 3*/
>COMMIT;

このようにTransaction内snapshotを作成して読みこむことでRepeatable Reads要件を満たしつつ、Phantom Reads現象も避けれる所謂Snapshot Isolationというもっと実用的なIsolation Levelとなります。
さらにTransaction内更新がある場合：

MysqlTransactionA

>BEGIN;
/* T = 1*/
>UPDATE user SET Name = "Big Boss" WHERE Level = 20;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0
/* T = 4*/
>SELECT * FROM user;
+------+----------+-------+
| ID   | Name     | Level |
+------+----------+-------+
|    1 | Alfred   |    10 |
|    2 | Big Boss |    20 |
|    3 | Cathy    |    30 |
+------+----------+-------+
3 rows in set (0.00 sec)
/* T = 6*/
>COMMIT;

TransactionBでは

MysqlTransactionB

>BEGIN;
/* T = 2*/
>UPDATE user SET Name = "Big Cat" WHERE Level = 20;
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction
/* T = 3*/
>INSERT INTO user(ID,Name,Level) VALUES ( 4, 'Den', 15 );
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction
/* T = 5*/
>COMMIT;

Range Lockまでつけてくれます、Mysql怖るべし（デフォルトがRepeatable Readsなので実用的な機能全部ありますって感じ）。しかしユニークなインデックス(Primary Keyなど)に対するユニークなSELECTを行う場合Range Lockを取らないようで、SELECT... FOR UPDATEを使うべし。

Read Committed

Read Commitedレベルでは操作対象データに対してWrite Lockを取り、commit時まで保持しますが、Read LockはSelectの後すぐ開放します、Range Lockを取りません。ゆえにPhantom Readsに加え、Non-repeatable Readsが起きます。

TransactonA

BEGIN;
/* T = 1*/
SELECT * FROM user
WHERE Level = 10;
/* Name = "Baison"*/
/* T = 4*/
SELECT * FROM user
WHERE Level = 10;
/* Name = "Big Boss"*/
COMMIT;

を実行します、途中からTransactionBで

TransactionB

BEGIN;
/* T = 2*/
UPDATE user SET Name = "Big Boss" WHERE Level = 10;
/* T = 3*/
COMMIT;

このレベルではSELECT後すぐRead Lockを開放しますので、T = 2時Level = 10のレコードになんのロックもかかっていません。したがってTransactionBがレコードを変更してcommitできます。T = 4時TransactionAが再度読み込む時レコードのNameフィールドが変更されました。Readしたフィールドが再現できないNon-repeatable Reads現象が起きます。しかし、TransactionがデータへのWrite Lockはcommit時まで保持するため、どのTransactionでも読み取れるデータはcommitされた状態にあります。ゆえにRead Commitedレベルと呼びます。

MysqlでのRead Committed

TransactionAで

MysqlTransactionA

>BEGIN;
/* T = 1*/
>SELECT * FROM user;
+------+----------+-------+
| ID   | Name     | Level |
+------+----------+-------+
|    1 | Alfred   |    10 |
|    2 | Big Boss |    20 |
|    3 | Cathy    |    30 |
+------+----------+-------+
3 rows in set (0.00 sec)
/* T = 2*/
>UPDATE user SET Name = "Boomeran" WHERE Level = 20;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0
/* T = 7*/
>SELECT * FROM user;
+------+----------+-------+
| ID   | Name     | Level |
+------+----------+-------+
|    1 | Alfred   |    10 |
|    2 | Boomeran |    20 |
|    3 | Cathy    |    30 |
|    4 | Den      |    15 |
+------+----------+-------+
4 rows in set (0.01 sec)
/* T = 7*/
>COMMIT;

TransactionBでは

MysqlTransactionB

>BEGIN;
/* T = 3*/
>UPDATE user SET Name = "From TX B" WHERE Level = 20;
ERROR 1205 (HY000): Lock wait timeout exceeded; try restarting transaction
/* T = 4*/
>INSERT INTO user(ID,Name,Level) VALUES ( 4, 'Den', 15 );
Query OK, 1 row affected (0.00 sec)
/* T = 5*/
>SELECT * from user;
+------+----------+-------+
| ID   | Name     | Level |
+------+----------+-------+
|    1 | Alfred   |    10 |
|    2 | Big Boss |    20 |
|    3 | Cathy    |    30 |
|    4 | Den      |    15 |
+------+----------+-------+
4 rows in set (0.00 sec)
/* T = 6*/
>COMMIT;

MysqlでのRead CommittedではTransactionが更新したデータだけロックを取ります。Range Lockは取りません。したがって、上記のようにPhantom Reads現象が起きます。

Read Uncommitted

Read Uncommittedレベルでは操作対象データに対してWrite Lockを取り、commit時まで保持しますが、Read LockとRange Lockを取りません。したがって、Phantom Reads現象、Non-repeatable Reads現象に加え、Dirty Reads現象も起きます。データを読み込む時Read Lockを取得しないため、他のTransactionの更新後未commitのデータ（Dirtyなデータ）も読めますので、Dirty Reads現象が起きます。

MysqlでのRead Uncommitted

MysqlでのRead UncommittedではANSI/ISO基準のと同じ動作を取ります。

MysqlTransactionA

>BEGIN;
/* T = 2*/
>UPDATE user SET Name = "Big Cat" WHERE Level = 20;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0
/* T = 4*/
>COMMIT

MysqlTransactionB

>BEGIN;
/* T = 1*/
>SELECT * FROM user;
+------+--------+-------+
| ID   | Name   | Level |
+------+--------+-------+
|    1 | Alfred |    10 |
|    2 | Baison |    20 |
|    3 | Cathy  |    30 |
+------+--------+-------+
3 rows in set (0.00 sec)
/* T = 3*/
>SELECT * FROM user;
+------+---------+-------+
| ID   | Name    | Level |
+------+---------+-------+
|    1 | Alfred  |    10 |
|    2 | Big Cat |    20 |
|    3 | Cathy   |    30 |
+------+---------+-------+
3 rows in set (0.00 sec)
/* T = 5*/
>COMMIT

このように、TransactionBからはTransactionAの未commitの変更が見れてしまい、Dirty Read現象が起きます。

Deadlock降臨

Transactionは一連のオペレーションをまとめています。そして登録されたSql文に応じてデータのロックを取ります。しかし、Transactionが取得したロックが開放されない新しいオペレーションが必要とするロックを取れない場合があります。このような状況をDeadlockと呼びます。
Mysqlでの検証：
まずは二つテーブルを用意します：
user:

ID	Name	Level
1	Alfred	10
2	Big Cat	20
3	Cathy	30

quest:

ID	QuestName	Reward
1	Easy	5
2	Normal	15
3	Hard	25

二つのTransactionを並列で開始する。

MysqlTransactionA

>BEGIN;
/* T = 1*/
>UPDATE user SET Name = "Big Cat" WHERE Level = 20;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0
/* T = 4*/
>UPDATE quest SET QuestName = "OldSet" WHERE Reward = 5;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1  Changed: 1  Warnings: 0
/* T = 6*/
>SELECT * FROM user;
+------+--------+-------+
| ID   | Name   | Level |
+------+--------+-------+
|    1 | Alfred |    10 |
|    2 | BigA   |    20 |
|    3 | Cathy  |    30 |
+------+--------+-------+
3 rows in set (0.00 sec)
>SELECT * FROM quest;
+------+-----------+--------+
| id   | QuestName | Reward |
+------+-----------+--------+
|    1 | OldSet    |      5 |
|    2 | Normal    |     15 |
|    3 | Hard      |     25 |
+------+-----------+--------+
3 rows in set (0.00 sec)

MysqlTransactionB

>BEGIN;
/* T = 2*/
>UPDATE quest SET QuestName = "NewSet" WHERE Reward = 5;
Query OK, 1 row affected (0.00 sec)
Rows matched: 1  Changed: 1  Warnings: 0
/* T = 3*/
>UPDATE user SET Name = "TxB" WHERE Level = 20;
/* T = 4*/
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
/* T = 5*/
>SELECT * FROM user;
+------+---------+-------+
| ID   | Name    | Level |
+------+---------+-------+
|    1 | Alfred  |    10 |
|    2 | Big Cat |    20 |
|    3 | Cathy   |    30 |
+------+---------+-------+
3 rows in set (0.00 sec)
>SELECT * FROM quest;
+------+-----------+--------+
| id   | QuestName | Reward |
+------+-----------+--------+
|    1 | Easy      |      5 |
|    2 | Normal    |     15 |
|    3 | Hard      |     25 |
+------+-----------+--------+
3 rows in set (0.00 sec)

TransactionAとTransactionBがまず別々データレコードAとBのロックを取ります。次にTransactionBがデータレコードAのロックを取ろうと、ロックA待ちの状態に入ります。次にTransactionAがデータレコードBのロックを取ろうとします。ここでDeadlockが発生します。しかしMysqlがうまくDeadlockを発見しTransactionBをRollbackしました。これでTransactionAが続行できて、Deadlockが解消されました。

まとめ

RDBMSはデータを関係性に基づいて管理しています。したがって、特定データにアクセスする時は関連データまでロックすることがあり、排他制御がKVSと比べ複雑になります。排他制御で使用されているTransactionには4つのIsolation Levelがあります。制約の厳しいレベルほど、データアクセスのシリアル性が担保され、デッドロックも起きやすいです。本編では2PKの説明とMysqlで各Isolation Levelを検証し、さらにMysqlのDeadlock解消メカニズムも検証しました。