PostgreSQL のトランザクション & MVCC & スナップショットの仕組み

このページでは PostgreSQL のトランザクション(Transaction)、Multi Version Concurrency Control(MVCC)、スナップショット(Snapshot)の仕組みを説明する。

PostgreSQL の他の記事へのインデックスはここ。

更新履歴
(2016.04.30) 作成。
(2016.09.16) データ定義言語(DDL)のトランザクションを追加。
(2016.09.28) データ定義言語(DDL)の MVCC アンセーフ動作を追加。
(2017.04.07) Combo Command ID の説明が間違っているのを修正。

目次

• 1. はじめに
• 2. トランザクション分離レベル(Transaction Isolation Level)
• 3. Serializable 以外の分離レベルの実現方法
  • 3.1 トランザクションとと可視性(Visibility)
  • 3.2 スナップショット(Snapshot)
  • 3.3 複数のコマンドを含むトランザクションの扱い
  • 3.4 サブトランザクション
  • 3.5 DELETE と UPDATE の扱い
• 4. PostgreSQL のその他の機構
  • 4.1 削除された行の回収
  • 4.2 タプルロック
• 5. Serializable 分離レベルの実現方法
  • 5.1 Serializable の条件
  • 5.2 Predicate Lock
• 6. データ定義言語(DDL)のトランザクション
  • 6.1 テーブルに関する DDL のトランザクションの実現方法
  • 6.2 インデックスに関する DDL のトランザクションの実現方法
    • 6.2.1 INSERT 先行 & CREATE INDEX 後行
    • 6.2.2 CREATE INDEX 先行 & INSERT 後行
  • 6.3 DDL コマンドの一部 MVCC アンセーフな動作
• A. 補足
  • A.1 Combo Command ID (CCI)
  • A.2 トランザクション ID をタイムスタンプ替わりに使えるか？
• 参考文献
• コメント

1. はじめに

リレーショナルデータベース(Relational Database) (以下、RDB と省略)にはトランザクションが存在すると多くの解説に書いてあるが、どの説明を読んでもしっくりこない。 PostgreSQL のソースコードを読んで理解したトランザクションの挙動と仕様を自分でまとめてここに記すことにする。

RDB にはテーブルが存在し、テーブルに問い合わせ(SELECT)・挿入(INSERT)・更新(UPDATE)・削除(DELETE)の 4 つのコマンドを実行することができる。 この4 つ以外に、大量の行を挿入するバルク・コピーや、テーブルに既存の行があれば UPDATE として振る舞い無ければ INSERT として振舞う UPSERT または MERGEコマンドもあるが、基本の 4 つのコマンドの亜種として扱えるので、INSERT/UPDATE/DELETE に絞って説明する。 4 つのコマンドのうち SELECT はテーブルの内容を変更しないが、それ以外の INSERT/DELETE/UPDATE コマンドはテーブルの内容を変更する。 また 1 つの INSERT/DELETE/UPDATE コマンドがテーブルの複数の行を変更することもある。

SELECT * FROM tablename1, tablename2;
INSERT INTO tablename1 (column1, column2, column3) VALUES (1, 100, 'abc');
UPDATE tablename1 SET (column3) = (column3 + 1) WHERE column1 = 1;
DELETE FROM tablename1 WHERE column1 = 1;

SELECT コマンドは複数のテーブルに跨る問い合わせを行う。 つまりテーブルの内容の参照を行う。 INSERT/UPDATE/DELETE コマンドも挿入・更新・削除の条件を合成するために複数のテーブルに問い合わせを行うことができる。 ただし INSERT/UPDATE/DELETE コマンドが変更することのできるテーブルは 1 つに限られる。 つまりコマンドは複数のテーブルの内容を参照し、1つのテーブルの内容を変更することになる。

例えば tablename1 から tablename2 に含まれていない行だけを削除する場合、以下のような SQL コマンドになる。 これは tablename1 と tablename2 の 2 つのテーブルを参照するが、変更は tablename1 だけになる。

DELETE FROM tablename1 WHERE column1 NOT IN (SELECT column2 FROM tablename2);

データベースに接続したユーザーは以上の 4 コマンドを実行し、テーブルの内容を参照したり変更したりする。 データベースには同時に複数の人が接続することも可能なので、ある人が行ったテーブルの内容の変更が、他の人にはどう見えるかということが重要な問題になる。 この文書で解説するトランザクション、MVCC、スナップショットも全てこの点を理解・実現するための仕掛けである。

いくつかの原則がある。

Rule 1

各コマンドは不可分に実行されたように見える。 複数の人が同時にデータベースに接続して、それぞれがコマンドを実行しても各コマンドは順番に実行されたようにみえ、コマンド実行の中間状態は他から見えない。
もし二つのコマンドが衝突した場合、どちらかは一方あるいは両方がエラーとなりコマンドが失敗する。 コマンドが失敗した場合は、中間的な状態は残らずに必ずコマンド実行前に戻される。

Rule 2

トランザクションによって複数のコマンドをまとめることができる。トランザクションは他のトランザクションと不可分に実行されたように見える。
トランザクションはコマンドを BEGIN と COMMIT で囲って表現する。

BEGIN;
UPDATE tablename1 SET (value) = 100 WHERE key = 1;
UPDATE tablename2 SET (counter) = (counter + 1) WHERE key = 1;
COMMIT;

1. と同様に各トランザクションは順番に実行されたように見え、トランザクション実行の中間状態は他から見えない。 もし二つのトランザクションが衝突した場合、どちらかは一方あるいは両方がエラーとなりコマンドが失敗する。 トランザクションが失敗した場合は、途中まで実行された中間的な状態は残らずに必ずトランザクション実行前に戻される。
明示的にトランザクションが使用されない場合、1つのコマンドは1つのトランザクションで実行されたのと同じ扱いになる。

Rule 3

トランザクション内のコマンドは順番に実行されたように振舞う。先行するコマンドがテーブルを変更すると、その次のコマンドには変更されたテーブル内容の内容が見える。 言い換えると、トランザクション内のコマンドはデータベースへの接続者が1人しかいない時と同じように振舞う。

一部のトランザクション機能は例外がある。例えば PostgreSQL の場合、SET TRANSACTION SNAPSHOT コマンドを使った場合など。

2. トランザクション分離レベル(Transaction Isolation Level)

RDB にとって同時実行されるトランザクションは不可分に実行されるのが理想的だが、この制約を実装するのはオーバーヘッドが大きいことが知られている。 そこで性能を重視して不可分性を弱めたトランザクションを使うこともできる。 トランザクションの不可分性の強弱は トランザクション分離レベル(Transaction Isolation Level) として定義されている。 SQL 標準で 4 種類定義されている。 Serializable が理想的で、一番制約の強い、真の意味でのトランザクションだ。 表の中で下に行くほど制約が弱くなる。

Read Committed と Read Uncommitted は明らかに Serializable とは動作が違うが、Repetable Read と Serializable の違いは自明ではない。

まず Repetable Read は、「一度読んだデータは何回読んでも同じ値を返す」ので、読まなかったデータに対する振る舞いが規定されていない。 ここにトランザクションの不可分性に問題が生じる隙がある。

例えば以下のようなテーブルがあったとする。

CREATE TABLE dots (id int, color text);
INSERT INTO dots (id, color) VALUES (1, 'black'), (2, 'white'), (3, 'black'), (4, 'white');

Session1 トランザクション内でテーブル全体を表示する SELECT を 2 回実行し、その間で別の Session2 が Session1 の SELECT の中間でテーブルに新しい行を挿入すると、2 回の SELECT の内容が食い違ってしまうことになる。 そのため他のトランザクションが INSERT した新しい行が、後から見えるようになることがある。 これを ファントム・リード(Phantom Read) と呼ぶ。

BEGIN;
SELECT * FROM dots;
id | color
---+-------
 1 | black
 2 | white
 3 | black
 4 | white

BEGIN;
INSERT INTO dots (id, color) VALUES (5, 'black');
COMMIT;

SELECT * FROM dots;
id | color
---+-------
 1 | black
 2 | white
 3 | black
 4 | white
 5 | black
COMMIT;

しかし PostgreSQL の Repeatable Read の制約は、SQL 標準で規定されたものよりも若干強い。 具体的には PostgreSQL の Repeatable Read は「一度読んだデータを何回読んでも同じ値を返す」ではなく、「トランザクションの開始時点のデータベースのイメージがトランザクション内で維持される」となる。 このため他のトランザクションが INSERT した行も後から見えることはなくなり、ファントム・リードの問題は発生しない。

それでもなお PostgreSQL の Repeatable Read は Serializable の条件を満たさない。 PostgreSQL wiki の SSI に紹介されている例を 1 つだけ挙げる。

例えば REPEATABLE READ 分離レベルで Session1 と Session2 の二つを実行したとする。 Session1 はトランザクションはテーブル内の white の行を black へ変えようとし、Session2 のトランザクションは black の行を white へ変えようとする。 もし 2 つのトランザクションが順番に実行されたように振舞うのであれば、最終的なテーブル内容は全ての行が black になるか全ての行が white になるかどちらかである。 しかし実際に SQL を実行すると black と white とが反転するという結果になる。 これは Serializable の条件に違反する。

SELECT * FROM dots;
id | color
---+-------
 1 | black
 2 | white
 3 | black
 4 | white

BEGIN;
UPDATE dots SET color = 'black' WHERE color = 'white';

BEGIN;
UPDATE dots SET color = 'white' WHERE color = 'black';
COMMIT;

COMMIT;

SELECT * FROM dots;
id | color
---+-------
 1 | white
 2 | black
 3 | white
 4 | black

SQL 標準はトランザクション分離レベルが、規定されたものよりも強い制限を掛けることを許している。 これを利用して PostgreSQL は Read Uncommitted 分離レベルを実際には実装せず、Read Uncommitted 分離レベルを指定すると Read Committed 分離レベルと同じ動作をさせている。 このページでは PostgreSQL を中心に解説するので、以降の説明では Read Uncommitted 分離レベルはないものとして扱う。

3. Serializable 以外の分離レベルの実現方法

トランザクションのナイーブな実現は、1つのトランザクションが参照・更新した行を全てロックして、他のトランザクションからアクセスしてしまうというものである。 ただしこれは性能が非常に悪くなる。

最近の RDB は、1つの行の更新前と更新後の両方内容(あるいは3つ以上の内容)を保存し、トランザクションによって同じ行が異なる内容に見えるようにするという手法を用いる。 これをMulti Version Concurrency Control(MVCC)と呼ぶ。 MVCC を使うと行を読んでいるトランザクションがいても、その行を別のトランザクションが UPDATE したり DELETE したりすることが可能になる。

MVCC の実現方式として一般的なのは Snapshot Isolation (SI) で、PostgreSQL も Snapshot Isolation を用いる。 3 章では PostgreSQL での Snapshot Isolation を説明し、Read Committed 分離レベルと Repeatable Read 分離レベルをどのようにして実現しているかを説明する。

ただし Snapshot Isolation だけでは Serializable 分離レベルの制約を満たさない。 これは 5. で説明する。

3.1 トランザクションと可視性(Visibility)

あるトランザクションがテーブルの内容を変更する時に、同時に走行している他のトランザクションからどのように見えるか考えてみる。 トランザクションによってテーブル内の行が見えるか見えないかを可視性(Visibility)と呼ぶことがある。

可視性の話を簡単にするため、まずテーブルへの操作は SELECT と INSERT だけが可能なパターンを考える。 UPDATE と DELETE を含めたパターンは 3.5 で考える。

1つのトランザクションに着目した場合、トランザクションは BEGIN コマンドで開始され、COMMIT コマンドを実行すると成功裏に完了する。 COMMIT コマンドではなく、ROLLBACK コマンドを実行するとトランザクションは中断(Abort)し、トランザクション中のコマンドがテーブルに与えた効果は元に戻される。 また RDB 全体が突然停止した場合、次回 RDB 全体が再開した時には、中断されたトランザクションは ROLLBACK コマンドを実行した時と同様に元に戻される。 トランザクションは結局、コミット済み(Committed)かアボート(Abort)(中断もここに含める)すると言える。

一方、複数のトランザクションがある場合、あるトランザクションが他のトランザクションを見た場合、コミット済みかアボート以外に進行中(In Progress)の状態がありえる。

さてトランザクションは開始順に X100、X101、X102、… のようにトランザクションIDを振ることにする。 トランザクションIDは以下、XID と略す。 RDB は発行した XID 毎に、そのトランザクションがコミット済み(Committed)かアボート(Abort)か進行中(In Progress)かを記録するデータ構造も用意する。 XID を発行した直後は進行中(In Progress)で、その後コミット済み(Committed)かアボート(Abort)が決まることになる。 PostgreSQL ではこのトランザクションの状態を記録する配列を CLOG と呼ぶ。

テーブルに対して行が挿入される場合、行の内容と伴に INSERT コマンドが属するトランザクションの XID も記録する。 fig-1 のように X200、X201、X202 のトランザクションが、テーブル T1 に行を挿入したとする。 続く X203 のトランザクションがテーブル T1 をスキャンした場合、X200 の行はアボート(Abort)なので SELECT によってこの行は見えない。 X201 の行はコミット済み(Committed)なので 'def'、'ghi'、'jkl' の行は見える。 X202 の行は進行中(In Progress)なので、(Read Uncommitted を考えないのであれば)見えない。

ただしトランザクションは並行に動作しているので、中間状態が生じる。 X203 のトランザクションがテーブルをスキャンしている間に、X201 が進行中(In Progress)からコミット済み(Committed)に変化したとしたら、テーブル内には X201 が書き込んだ行が複数あるので、'def' の行を読んだ時は進行中(In Progress)だったが、'ghi' の行を読んだ時にはコミット済み(Committed)だったと、1つのコマンドが書いた行すらバラバラに見えるかもしれない。 これはコマンドの途中が見えているということなので、非常によくない。

PostgreSQL を含む幾つかの RDB は進行中(In Progress)のトランザクションを扱うためにスナップショット(Snapshot)を導入することでこの問題を解決する。

3.2 スナップショット(Snapshot)

PostgreSQL のスナップショットは SnapshotData という構造体で、いろいろなメンバー変数が入っているが重要なのは以下の3つのパラメータである。

1. トランザクションは無限に生存しているわけではないので、ある XID (xmin とする) 以下のトランザクションはすでに終了しておりコミット済み(Committed)かアボート(Abort)の二択になっている。 この場合、トランザクション状態の記録(CLOG)を見れば、テーブルの行が見えるか見えないかが決まる。
2. (Read Uncommitted を考えないなら)ある XID 以上 (xmax とする) のトランザクションはまだ開始していないか進行中(In Progress)とみなせる。 端的言うと自分のトランザクションの XID 以上の値は無視できる。
3. xmin と xmax の間のトランザクションはコミット済み(Committed)、アボート(Abort)、進行中(In Progress)の 3 つのモードがありえる。 そこで進行中(In Progress)のトランザクションの XID を配列に記録する(xip[] とする)。

テーブルの行の INSERT された XID は、スナップショットを使って以下の手順でチェックをし、その行が見えるか見えないかを判定する。

1. スナップショットを見る前に、行の XID が自トランザクションの XID と一致するか確認する。一致していれば、その行は見える。
2. 行の XID が xmax 以上なら、その行は見えない。
3. 行の XID が xmin 以下なら、CLOG を参照し、コミット済み(Committed)なら見える。アボート(Abort)なら見えない。
4. 1. にも 2. にも当てはまらない場合、XID が xip[] に一致するか確認する。一致するものがあれば、それは進行中(In Progress)なので見えない。 xip[] に一致するものがなければ、CLOG を参照し、コミット済み(Committed)なら見える。アボート(Abort)なら見えない。

トランザクションがスナップショットを作成するナイーブな方法は、RDB 内にいる生存中のトランザクションの XID を xip[] の配列に格納し、xip[]の最大値と最小値を元に xmin と xmax を決める。 fig-3 の例では、X304 がスナップショットを作成する場合、X304 と同時に進行中(In Progress)なのは X301 と X303 なのでこれが xip[] に格納され、その上下で xmax は X304、xmin は X300 となる。

PostgreSQL の場合、このスナップショットの作成を担当している関数は GetSnapshotData() になる。 GetSnapshotData() が呼び出されると、PostgreSQL インスタンス全体のジャイアントロックを取り、インスタンス内の進行中(In Progress)のトランザクションを列挙する。 比較的重い処理となる。

トランザクション分離レベルが Read Committed でも Repeatable Read でも、スナップショット自体とその判定方法には差がない。 ただし Repeatable Read はトランザクションの最初の位置でスナップショットを 1 回だけ作成してトランザクション内ではそれを維持するのに対して、Read Commited ではトランザクションの最初の位置以外にコマンドが実行される度にスナップショットを撮り直すという違いがある。

3.3 複数のコマンドを含むトランザクションの扱い

1. の Rule 3 で述べたようにトランザクション内に複数のコマンドがあった場合、先行するコマンドがテーブルを変更すると、その次のコマンドには変更されたテーブル内容の内容が見える。 この動作はトランザクション分離レベルによらない。 (Read Uncommitted を考えない場合でも) コミットしていないトランザクションの結果が見えていることになる。

しかしテーブルに実行中のトランザクションと同じ XID の行があれば見えるという論理では、INSERT INTO T1 SELECT * FROM T1 のような同一テーブルを参照しながら変更するようなコマンドで意図しない動作をすることになる。 そのため前述のスナップショットとは別の対処が必要となる。

トランザクション内のコマンドの実行順を番号付けする。 PostgreSQL ではこれをコマンドID(以降、CIと略す)としている。

コマンドは参照しているテーブルの行の XID が自分のトランザクションに属するものの場合、CI もチェックする。

1. 実行中のコマンドの CI よりも前の番号は見える。
2. 実行中のコマンドの CI と一致する番号は見えない。
3. 実行中のコマンドの CI よりも後の番号は存在しない。

INSERT INTO T1 SELECT * FROM T1 はコマンドは、これによって自分の書いた行を自分で読むことを防止している。

3.4 サブトランザクション

SQL は SAVEPOINT コマンドによってトランザクション内にセーブポイント(Savepoint)を設定し、ROLLBACK TO SAVED POINT コマンドによってセーブポイント以降に実行されたコマンドをロールバックすることができる。 ラベルをつけることで複数のセーブポイントを設けることも可能。

BEGIN;
    INSERT INTO T1 VALUES (1);

    SAVEPOINT foo;
    INSERT INTO T1 VALUES (2);
    RELEASE SAVEPOINT foo;

    SAVEPOINT bar;
    INSERT INTO T1 VALUES (3);
    RELEASE SAVEPOINT bar;

    INSERT INTO T1 VALUES (4);
COMMIT;

セーブポイントは BEGIN で囲われたトランザクションブロックの中でだけ利用することができる。 セーブポインタの定義やセーブポインタによるロールバックは、他のトランザクションの可視性には影響を与えない。 そのためトランザクション内の入れ子のトランザクションのであり、セーブポイントはサブトランザクション(Subtransaction)であるとも呼ばれる。

この機能は PL/SQL のような手続き言語で利用され、セーブポイントへのロールバックはループや条件式などと組み合わせて使うのが普通である。 というかそうでなければ意味のない機構だ。

PostgreSQL はセーブポイントの実現のためにサブトランザクションIDを発行する。

fig-5 のように外側から見たトランザクションが X500 であっても、トランザクション内で SAVEPOINT を使うと新しい XID が X501、X502 のようにサブトランザクション ID として割り当てられる。 SAVEPOINT コマンド以降の INSERT コマンドがテーブルに行を挿入する場合、トランザクションID(X500)ではなく、サブトランザクションID(X501、X502)を打つ。

サブトランザクションIDは外部のトランザクションから見るとトランザクションIDと区別はつかない。 その上で、サブトランザクションIDは外側のトランザクションが COMMIT コマンドまたは ROLLBACK コマンドで終了するまでは進行中(In Progress)のステータスとする。 外側のトランザクションが終了するとサブトランザクションも終了する。

ただし ROLLBACK TO SAVED POINT でセーブポイントへのロールバックを行った場合、該当する部分のサブトランザクション ID はアボート(Abort)となる。

3.2 で述べたようにテーブル内の行の可視性の判定では「行の XID の自トランザクションの XID と一致するか確認する」とあるが、サブトランザクションはトランザクションの一部のため、行の XID がサブトランザクション ID の場合も自トランザクションと見做す必要がある。 例の場合、テーブルの行の XID の比較は、X500、X501、X502 の 3 つの値と比較することになる。

3.5 DELETE と UPDATE の扱い

ここまで INSERT だけを考えたが、実際は UPDATE と DELETE が存在する。

PostgreSQL の DELETE はテーブル内の行に自トランザクションの XID を刻印する。 そのため行には INSERT 時の XID と DELETE 時の XID の 2 個の列が必要になるので、INSERT 用を xmin と改称し、DELETE 用を xmax とする。

コマンド ID も概念的には INSERT 用の cmin と DELETE 用の cmax の 2 つがある。 ただし実体は1スロット分しかない。 A.1を参照のこと。

これまでの議論で、INSERT 時に打刻される xmin の可視性があると判定された場合はその行が「見える」ことになるが、同様のロジックで DELETE 時に打刻される xmax の可視性があると判定された場合は(削除されているので)その行が「見えない」ことになる。

fig-6のように一般的に xmin ≤ xmax だが、Read Committed トランザクションの場合には xmin > xmax となることもある。

PostgreSQL の UPDATE は、同一コマンドで古い行の UPDATE と新しい行の INSERT がペアで行われるだけである。 そのため INSERT と DELETE のロジックで対応できる。

SELECT xmin, xmax, cmin, cmax, * FROM T1;

4. PostgreSQL のその他の機構

4.1 削除された行の回収

PostgreSQL は DELETE した場合、xmax を打刻するだけで行自体は放置する。 また UPDATE でも、更新前の行に xmax を打刻し、テーブル内に新しい内容の行を作成してしまう。 テーブルの内容は追記されることになる。

しかしそれではテーブルが削除された行で埋まってディスクを徒に消費してしまうので、削除した行が全てのトランザクションから「見えなく」なった後にその行を回収する。

Vacuum

VACUUM コマンドを実行するとテーブル内の削除行を回収する。 また PostgreSQL インスタンス内の autovacuum プロセスが、一定の周期で VACUUM コマンドを打ったのと同じ処理を行う。

Page Defragmentation

テーブルのページ(8KiB)に閉じた削除行の回収を自動的に行う。 この処理は SELECT/INSERT/UPDATE/DELETE によってテーブルがスキャンされる際に、その裏側で処理される。 具体的には heap_page_prune_opt() の呼び出しが契機になる。

4.2 タプルロック

PostgreSQL は SELECT FOR UPDATE コマンドのような行レベルロックに対応している。

行レベルロックは、DELETE を記録する xmax を流用することで実現している。

CREATE TABLE testtable (c1 int);

INSERT INTO testtable SELECT i FROM generate_series(1, 4) AS i;

BEGIN;
SELECT * FROM testtable WHERE c1 % 2 = 0 FOR UPDATE;
BEGIN
 c1
----
  2
  4
(2 rows)

SELECT xmin, xmax, * FROM testtable ORDER BY c1;
 xmin | xmax | c1
------+------+----
 2042 |    0 |  1
 2042 | 2043 |  2
 2042 |    0 |  3
 2042 | 2043 |  4
(4 rows)

END;

実際に行の xmax が DELETE のために利用されたのか行レベルロックのために利用されたのかは、行毎に存在する t_infomask という行が記録している。 ただし専用のエクステンションを使わない場合には、この情報を見ることはできない。

CREATE EXTENSION IF NOT EXISTS pageinspect;

SELECT ctid, xmin, xmax,* FROM testtable ORDER BY c1;
 ctid  | xmin | xmax | c1
-------+------+------+----
 (0,2) | 2071 | 2072 |  2

SELECT * FROM heap_page_items(get_raw_page('testtable', 0));
 lp | lp_off | lp_flags | lp_len | t_xmin | t_xmax | t_field3 | t_ctid | t_infomask2 | t_infomask | t_hoff | t_bits | t_oid
----+--------+----------+--------+--------+--------+----------+--------+-------------+------------+--------+--------+-------
  2 |   8128 |        1 |     28 |   2071 |   2072 |        0 | (0,2)  |        8193 |        448 |     24 |        |

5. Serializable 分離レベルの実現方法

5.1 Serializable の条件

Serializable 分離レベルの条件は、全てのトランザクションが不可分に実行できることだが、そのためには全てのトランザクションが T1 → T2 → T3 のように論理的な順番をつける必要がある。 この論理的な順番は、トランザクションの開始順でもコミット順でもある必要がないが、必ず全順序関係になる必要がある。

このような順序は、トランザクションがデータアクセスによって生じるし依存関係によって決まる。 2 つのトランザクション T1 と T2 がある場合、その間に依存関係を生じさせるパターンが 3 種類ある。

wr-dependecies

T1 がデータを書き込み、T2 がデータを読んだ場合、2 つのトランザクションに依存関係が発生し T1 → T2 の順序が必要である。 このような依存関係を wr-dependecies と呼んでいる。
T1 が INSERT や UPDATE した行を T2 が参照する場合である。 T1 が DELETE した行を T2 が見ないのも wr-dependecies にあたる。
コンパイラでは true dependecy、マイクロアーキテクチャでは Read After Write(RAW) とも呼ぶ。

ww-dependencies

T1 と T2 が同じ箇所にデータを書き込んだ場合、2 つのトランザクションに依存関係が発生する。 最後のデータを残したのが T2 であれば、T1 → T2 の順序が必要である。 このような依存関係を ww-dependecies と呼んでいる。
コンパイラでは output dependecy、マイクロアーキテクチャでは Write After Write(WAW) とも呼ぶ。

rw-antidependencies

T1 が古いデータを読んだ後に、T2 が同じ箇所に新しいデータを書き込んだ場合、2 つのトランザクションに依存関係が発生し T1 → T2 の順序が必要である。 このような依存関係を rw-antidependecies と呼んでいる。
T1 がテーブル内の行を参照せい、その後に T2 が UPDATE や DELETE した場合である。 コンパイラでは anti dependecy、マイクロアーキテクチャでは Write After Read(WAR) とも呼ぶ。

上記の 3 種類以外に T1 と T2 が同じデータを参照するパターンがある。 マイクロアーキテクチャーでは Read After Read(RAR) と呼ぶ(コンパイラでは特に名前がついてないが対称性から言えば input dependecy と呼ぶべきかもしれない)。 RAR では T1 と T2 の間に依存関係は発生しない。

トランザクションは複数のテーブル、複数の行を変更・参照するが、その全てから生じる依存関係によって、トランザクション間の順序が 1 列に決まる必要がある。 もし正しい順序付けができない場合、まだコミットしていない進行中(In Progress)のトランザクションをエラーとしてアボート(Abort)に遷移させることで解決する。 当然、アボート(Abort)したトランザクションは、テーブルからの参照も変更も無視されるので、他との依存関係を考える必要はない。

参考文献 [2] は SI を拡張した Serializable Snapshot Isolation (SSI) で、この依存性の違反を検出する機構を提唱している。 ポイントを一言で言うとトランザクションがテーブルの内容を参照する際に、参照した行に SIREAD ロック を掛ける。 SIREAD ロックはロックと名前がついているがスレッド/プロセスを待機させる機能は持たない。 後で SIREAD ロックの掛った行に変更を加えるトランザクションがいた場合、SIREAD ロックをとったトランザクションとの間に依存関係を発生させる。 このトランザクション依存関係のグラフに循環ができていなければ、それは依存関係違反とみなす。

5.2 Predicate Lock

PostgreSQL は 9.1 より SSI を適用して Serializable 分離レベルの実現方法している(参考文献 [3])。 適用の前提から考える。

• PostgreSQL の場合、3. で述べた MVCC の機構により、Serializable 以外の分離レベル以外でも wr-dependecies が発生しないことが保証されている。
• PostgreSQL 1 つの行に UPDATE や DELETE を実行する場合、xmax に自トランザクション XID の打刻を打つことになる。 UPDATE や DELETE が他のトランザクションから見えるようになるのは自トランザクションがコミットした後になるが、xmax に進行中(In Progress)の XID の打刻があった場合、その時点でコマンドは失敗する(xmax 用の領域は 1 つしかないし上書きすることはできないから)。 そのため Serializable 以外の分離レベル以外でも ww-dependecies が発生しないことも保証されている。

PostgreSQL は残った rw-antidependencies だけが発生しうる。 そのためにはテーブルの行を参照した時に SIREAD ロックを導入したい。 しかし行レベルロックでは xmax を使ってロックを獲ったが、xmax は 1 箇所しかない。 Serializable 分離レベルであっても、複数のトランザクションが同時にテーブルの行を読むことはできるためここを SIREAD ロックとして使うことはできない。 そこで SIREAD ロックを実現するために、専用のロック・マネージャーを用意する。

PostgreSQL はテーブルからタプルを読み込む場合(例えば heap_fetch())などに SIREAD ロックを掛ける。 SIREAD ロック・マネージャーはメモリ上のみにあるハッシュテーブルで、「SIREAD ロックを獲得する」際にはここに登録する。

さらに PostgreSQL の SIREAD は複数の粒度に対応しており、以下の 3 種類がある。 最小粒度は行単位だが、大量の行に対する SIREAD ロックが獲られると、メモリだけのハッシュテーブルが溢れてしまう。 同一ページに対する行単位 SIREAD ロックが集まるとページ単位のロックへ切り替え、同一テーブルに対するページ単位 SIREAD ロックが集まるとテーブル単位のロックへ切り替えという昇格が行われる。 これによってメモリを節約している。

• 行(タプル)単位(PredicateLockTuple())
• ページ単位(PredicateLockPage())
• テーブル(リレーション)単位(PredicateLockRelation())

INSERT/DELETE/UPDATE コマンドがテーブルに行を書き込む時は write のためのチェック関数(CheckForSerializableConflictIn())を、テーブルから行を読み込む時は SIREAD ロックを獲った後に read のためのチェック関数(CheckForSerializableConflictIn())を呼び出す。 チェック関数は、トランザクション間に依存関係が出来ている場合は "could not serialize access due to read/write dependencies among transactions" というエラーを発生させる。

6. データ定義言語(DDL)のトランザクション

これまで述べてきたように RDB はテーブルに対する SELECT/INSERT/DELETE/UPDATE コマンドなどの データ操作言語(Data Manipulatoin Language; DML) がトランザクションによって制御される。

これに加えて PostgreSQL はデータベース・テーブル・ビューなどを作成・削除・変更する CREATE TABLE/DROP TABLE/ALTER TABLE/TRUNCATE TABLE コマンドなどの データ定義言語(Data Definition Language; DDL) の大部分もトランザクションに従う。

例えばテーブルを作成する CREATE TABLE コマンドを BEGIN コマンドで囲うとトランザクション内では有効である。 しかし ROLLBACK コマンドでトランザクションを破棄すると、作成したテーブルがなかったことになる。

BEGIN;
CREATE TABLE t1 (c1 INT, c2 INT, c3 TEXT);
INSERT INTO t1 (c1, c2, c3) VALUES (1, 100, 'abc');
SELECT * FROM t1;
 c1 | c2  | c3
----+-----+-----
  1 | 100 | abc
(1 row)

ROLLBACK;
SELECT * FROM t1;
ERROR:  relation "t1" does not exist

DML は複数のトランザクションの可視性の判断にも従う。 Session1 と Session2 があった場合、Session1 のトランザクション内で定義されたテーブルはそのトランザクションがコミットするまでは、Session2 のトランザクションからは視る事ができない。

BEGIN ISOLATION LEVEL REPEATABLE READ;
CREATE TABLE t1 (c1 INT, c2 INT, c3 TEXT);
INSERT INTO t1 (c1, c2, c3) VALUES (1, 100, 'abc');

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT * FROM t1;
ERROR:  relation "t1" does not exist
COMMIT;

COMMIT;

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT * FROM t1;
 c1 | c2  | c3
----+-----+-----
  1 | 100 | abc
(1 row)

COMMIT;

DDL をトランザクションに対応させる対応方法をテーブルとインデックスに分けて説明する。 ただしインデックスは CONCURRENTLY をつけない CREATE INDEX コマンドのみを考える。

6.1 テーブルに関する DDL のトランザクションの実現方法

PostgreSQL はデータベース毎に システムカタログ とシステム定義の特別なテーブルを複数持っている(一部のシステムカタログはデータベースに所属するのではなく、データベースクラスタに所属しデータベース間で共有するものもある)。 PostgreSQL のバージョン 9.3 以降はシステムカタログが MVCC 化されている。

システムカタログの中に pg_class というテーブルがある。 CREATE TABLE コマンドでテーブルを作成した場合は、pg_class に特別な「行」が INSERT される。 同様にDROP TABLE コマンドでテーブルを削除下場合は pg_class の該当行が DELETE される。

PostgreSQL の様々なコマンドの実行はシステムカタログを参照してから行う。 特にテーブルに対する操作は pg_class システムカタログを参照してから行うので、DML と同様のトランザクション制御に従うことになる。

付け加えるとテーブルの実体になるファイルは、DROP TABLE/TRUNCATE TABLE コマンドが実行された段階では「削除リスト」に登録されただけで、本当にテーブルの実体ファイルが削除されるのは DROP TABLE/TRUNCATE TABLE コマンドを実行したトランザクションが完了し、その以前に存在した全てのトランザクションが終了した後になる。 これによってあるトランザクションがテーブルを削除しても、別のスナップショットに属するトランザクションは削除されたテーブルを参照し続けることが可能になっている。

6.2 インデックスに関する DDL のトランザクションの実現方法

インデックスに関する DDL として CREATE INDEX/DROP INDEX コマンドがある。 一見して CREATE INDEX/DROP INDEX コマンドは、トランザクションによる可視性の判定に従うように見えるが、実際には非常に悩ましい問題がある。

インデックスにはターゲットとするテーブルが必要である。 テーブルの作成とインデックスの作成は別のトランザクションに分かれることがあるが、その間にもテーブルに対する INSERT/DELETE/UPDATE 操作は実行される。 そのため同じテーブルに対する CREATE INDEX コマンドを実行するトランザクションと、INSERT/DELETE/UPDATE 操作を実行するトランザクション間の競合が発生する。

2 つの問題が考えられる。

1. 先行するトランザクション X1 がテーブル T1 に対して INSERT コマンドを行ったがまだコミットしていない。後行のトランザクション X2 がテーブル T1 に対して CREATE INDEX コマンドでインデックスを作成した時に、インデックスの中に X1 の挿入行を含めるべきか？含めないべきか？
2. 先行するトランザクション X3 がテーブル T1 に対して CREATE INDEX コマンドでインデックスを作成したがまだコミットしていない。後行のトランザクション X4 がテーブル T1 に対して INSERT コマンドを行った場合 X3 が作成したインデックスに X4 の挿入を追加すべきか？追加すべきでないか？

1. のパターンでも 2. のパターンでも、インデックス作成中に新たに挿入された行分のデータを追加すると MVCC 違反になりそうである。 一方、インデックスに挿入行を追加しないと、後のトランザクションがインデックスを参照した時に情報の欠落ができる。 これに対して PostgreSQL はインデックスはテーブルの一部なので MVCC がどうあろうとテーブルの内容=インデックスの内容となるようにデータ管理する、CREATE INDEX 直後のインデックスは古いトランザクションからは問い合わせ(SELECT)時に利用できないとすることで矛盾を回避している。

6.2.1 INSERT 先行 & CREATE INDEX 後行

PostgreSQL はコマンド種類によって複数のレベルのテーブルレベルロックを獲得する。 この節の情報によると、

• INSERT/UPDATE/DELETE コマンドは、コマンド実行に先立ち対象となるテーブルの ROW EXCLUSIVE ロックを獲得する必要がある。
• CREATE INDEX コマンドはインデックス作成に先立ちインデックス元のテーブルの SHARE ロックを獲得する必要がある。
• INSERT/UPDATE/DELETE/CREATE INDEX コマンドは全て実行に ACCESS SHARE ロックを獲得する必要がある。

ロックは複数のトランザクションで同時に獲得できるものと、同時に獲得できないもの(競合するもの)の2種類がある。 下記の表で X をつけたものは競合する。

結果として以下のようになる。

• INSERT/UPDATE/DELETE コマンドの必要とする ROW EXCLUSIVE ロックは ROW EXCLUSIVE ロック同士と競合しないので、複数のトランザクションが同じテーブルに対して同時に INSERT/UPDATE/DELETE コマンドを実行できる(同一行の競合はテーブルレベルロックではなく4.2節で紹介したタプルロックで回避する)。
• CREATE INDEX コマンドは SHARE ロックを必要とするが、SHARE ロック同士が競合するので、同じテーブルに対する CREATE INDEX コマンドは競合する。後から来たほうが待機させられる。
• ROW EXCLUSIVE ロックと SHARE ロックも競合するので、CREATE INDEX コマンドと INSERT/UPDATE/DELETE コマンドは競合する。後から来たほうが待機させられる。

さらに大事なのは通常ロックは獲得した後、トランザクションの終わりまで保持されるということである。 INSERT/UPDATE/DELETE コマンドを実行したトランザクションは、そのコマンド内で ROW EXCLUSIVE ロックを獲得するがコマンドが終了しても解放しない。 トランザクションの終わりで自動解放されるのを待つ。 CREATE INDEX コマンドは SHARE ロックも同様である。

結果として先行するトランザクションが INSERT コマンドを行った場合、後行のトランザクションの CREATE INDEX コマンドはロックの解放まで待機するので 矛盾は生じないことになる。

BEGIN ISOLATION LEVEL REPEATABLE READ;
INSERT INTO t1 (c1, c2, c3) VALUES (1, 100, 'abc');

CREATE INDEX i1 ON t1 (c1);
--- ここでコマンドがロックを待って待機する

COMMIT;

--- Session1 の COMMIT 後にコマンドが成功する

6.2.2 CREATE INDEX 先行 & INSERT 後行

先行するトランザクションが CREATE INDEX コマンドを行った場合、後行のトランザクションの INSERT コマンドを実行するパターンはもう少し難しい。

以下のようなパターンでは INSERT コマンドを実行している時点で、インデックスを作成したトランザクションはコミットし CREATE INDEX コマンドが獲得した SHARE ロックは解放されている。 そのため INSERT コマンドは実行されるが、Sessoin 2 のトランザクション内ではインデックス I1 は不可視である。

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT txid_current();

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT txid_current();

CREATE INDEX i1 ON t1 (c1);
COMMIT;

INSERT INTO t1 (c1, c2, c3) VALUES (1, 100, 'abc');
COMMIT;

実は INSERT コマンドが挿入すべきインデックスを探す場合には通常のスナップショットを使ってシステムカタログを視ていない。 INSERT コマンドの対象となったテーブルに対する全てのインデックスにエントリを追加している。

これは以下のように PRIMARY KEY 制約や UNIQUE 制約を設定するとはっきりする。 ALTER TALBE コマンドで PRIMARY KEY 制約や UNIQUE 制約を後から設定すると、内部的にはインデックスが作成されるので、CREATE INDEX コマンドと同様である。

まず以下のようなテーブルがあったとする。

CREATE TABLE t1 (c1 INT, c2 INT, c3 TEXT);
INSERT INTO t1 (c1, c2, c3) VALUES (1, 100, 'abc');

Session 1 側で ALTER TABLE コマンドで UNIQUE 制約を課すと、その時点で一意性インデックスが作成される。 このインデックスの作成前から存在する Session 2 に対して INSERT コマンドを実行すると、ユニーク制約違反のエラーが発生する。 トランザクションの可視性とは異なるパターンでインデックスが視えていることになる。

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT txid_current();

BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT txid_current();

ALTER TABLE t1 ADD CONSTRAINT u1 UNIQUE (c1);
COMMIT;

INSERT INTO t1 (c1, c2, c3) VALUES (1, 100, 'abc');
ERROR:  duplicate key value violates unique constraint "u1"
DETAIL:  Key (c1)=(1) already exists.

プログラム的には INSERT 実行時に追加すべきインデックスのリストは RelationGetIndexList() で取得する。 この中で引数 snapshot を NULL にして systable_beginscan() を呼び出している。 これが最新のシステムカタログを返すスナップショットを意味になるため、説明した動作になる。

SELECT txid_current();

まとめると

• CREATE INDEX/DROP INDEX コマンドなどはトランザクション可視性の判定に従う。
• 別トランザクションが作成したインデックスが問い合わせ(SELECT)から利用可能になるのはトランザクション可視性の判定に従う。
• INSERT コマンドが挿入対象とするインデックスはトランザクション可視性の判定に従わない。存在する全てのインデックスに挿入する。
• インデックスの作成と INSERT/UPDATE/DELETE コマンドの競合はテーブルレベルロックをトランザクションの終わりまで掛け続けることで回避する。

6.3 DDL コマンドの一部 MVCC アンセーフな動作

2 章 で PostgreSQL の DML コマンドではファントム・リードの問題は発生しないと言った。 しかし DDL コマンドは TRUNCATE と ALTER TABLE において、ファントム・リードに相当する現象が見える。 この問題は PostgreSQL 9.5.4 文書の13.5. 警告に記載がある。

Serializable トランザクション分離レベルの場合、Session 2 が t1 を見ると 3 行分が見えるはずである。 しかし Session 1 が実行した TRUNCATE コマンドが Read Committed のように振る舞い、Session 2 からは t1 は 0 行になっているように見える。

BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT txid_current();

BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT txid_current();

SELECT COUNT(*) FROM t1;
 count
-------
     3
(1 row)

TRUNCATE TABLE t1;
COMMIT;

SELECT COUNT(*) FROM t1;
 count
-------
     0
(1 row)
COMMIT;

このように別のトランザクションが一部の DDL コマンドを実行する前に、そのテーブルにアクセスしていなかったトランザクションは、スナップショット開始点のテーブル状態ではなく、DDL コマンド実行後の状態が見えることになる。

A. 補足

A.1 Combo Command ID (CCI)

xmin と xmax はテーブル内の行の情報を保持する HeapTupleData 構造体 内に t_data.t_choice.t_xmin と t_data.t_choice.t_xmax というメンバー変数として格納されている。 それぞれ 32 ビットの領域を占める。 コマンド ID は、コマンドを実行しているトランザクションが終われば不要になるデータなので t_data.t_choice.t_field3.t_cid という 32 ビット領域に、どちらか一方だけを記録することにする。 基本は INSERT により xmin が記録された場合は t_cid は cmin であり、DELETE により xmax が記録された場合は cmax である。

しかし 1 つのトランザクション中で INSERT と DELETE が繰り返された場合、cmin と cmax の両方が必要になる。 t_cid は 1 つだけになっている。 これを回避するために PostgreSQL は Combo Command ID (CCI) というハックを使う。

これは src/backend/utils/time/combocid.c の中にあるバックエンドプロセスごとの静的変数領域に、cmin と cmax を記録できるハッシュテーブル comboCids を用意しておく。 トランザクション内で INSERT した行が DELETE した場合、comboCids[combocid] に cmin と xmax を記録し、t_cid に combocid を記録する。 同時に HeapTupleData 構造体 の t_infomask に HEAP_COMBOCID のビットを立て、CCI が有効になっていることを記録する。

typedef struct
{
    CommandId   cmin;
    CommandId   cmax;
} ComboCidKeyData;

typedef ComboCidKeyData *ComboCidKey;

typedef struct
{
    ComboCidKeyData key;
    CommandId   combocid;
} ComboCidEntryData;

typedef ComboCidEntryData *ComboCidEntry;

static ComboCidKey comboCids = NULL;

よく考えると CCI は本来は全てのプロセスから共有して見える DB ページ領域に、特定プロセスの内部のハッシュテーブルのハッシュキーが記録されるというキモい仕組みを採用していることになる。

A.2 トランザクション ID をタイムスタンプ替わりに使えるか？

トランザクションID(XID)はトランザクションの開始時点(本当はトランザクション内の最初のコマンドの実行時点)で連番が降られるため、XID から概ね時系列が再現できそうに見える。 しかし実際には以下の問題がある。

XID の周回

XID は 32 ビット値なので、上限を越えると巡回してしまう。

VACUUM 操作による XID の凍結

VACUUM は操作は xmin や xmax が全てのトランザクションから見て確定したトランザクションの場合、その値を「凍結」することで無限に古いトランザクションに変更する。 それでもテーブル内のある時刻よりも前の XID が一括で「凍結」されるのであればよいが、実際には同じ XID の xmin/xmax がある行は凍結され、別の行は凍結されずに残るということがありえる。

実際の凍結の操作は HeapTupleData 構造体の t_xmin や t_xmax を書き換えるのではなく、t_infomask に HEAP_XMIN_FROZEN、HEAP_XMAX_FROZEN のビットを立てることで行われる。 この際、t_infomask に HEAP_XMIN_FROZEN、HEAP_XMAX_FROZEN にビットを立てたという WAL レコードは生成されない。 一方、PostgreSQL 内にある background writer プロセスが凍結した行を含む DB ページをディスクに書き出す。 この時点でシステムがクラッシュした場合、再起動後は同一のテーブル内であっても凍結が行われた DB ブロックと行われなかった DB ブロックが混在することになる。

PostgreSQL としては VACUUM は冪当性のある処理であり xmin/xmax の凍結はクラッシュしても再実行すればよいが、XID から時間の前後を比較する能力が失われることになる。

クラッシュリカバリーによる xmin の付け替え

INSERT/UPDATE/DELETE 操作に対する WAL レコードには xmin や xmax 情報が含まれない。 PostgreSQL がクラッシュした場合、xmin は INSERT 操作を行ったトランザクションの XID ではなく、再起動直後のクラッシュリカバリー処理のトランザクションの XID に書き換わる。

一方、full page write の機能により DB ページ全体が WAL レコードに書き込まれる。 そのようなページは PostgreSQL がクラッシュ後のリカバリー処理でも XID はそのままである。

そのため同じトランザクションに属する操作なのに、クラッシュリカバリー後に別の XID に書き換わったり、書き換わらなかったりする。

参考文献

• [1] Alan Fekete, et.al, Making Snapshot Isolation Serializable, ACM Transactions on Database Systems (TODS) Vol.30 Issue 2, Jun 2005
• [2] Michael J. Cahill, et.al, Serializable Isolation for Snapshot Databases, SIGMOD 2008
• [3] Dan R. K. Ports, Kevin Grittner, Serializable Snapshot Isolation in PostgreSQL, VDBL 2012

コメント