PostgreSQL Isolation について

トランザクションのACID特性のうち、Isolation(隔離性)について整理する。

検証環境

検証には、PostgreSQL 10.5を独自ビルドしたものを利用する。 (gdbでデバッグできるように最適化オプションを無効にした)
参考 PostgreSQL 9.4.4をソースコードからインストールする

# select version();
                                                 version
---------------------------------------------------------------------------------------------------------
 PostgreSQL 10.5 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-28), 64-bit
(1 row)
# uname -a
Linux localhost.localdomain 3.10.0-229.el7.x86_64 #1 SMP Fri Mar 6 11:36:42 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

Isolationとは?

データベースは並行して複数のトランザクションを処理し、その中で様々なデータ操作(SELECT/INSERT/UPDATE/DELETE)を実行する。このとき、各トランザクションからは、あたかもデータベースを占有しているかのように見せたい。そのため、各トランザクションが他のトランザクションからの影響を受けないように隔離(=Isolation)する必要がある。

完全に隔離しようとすると多くの計算コストがかかるため、スループット向上を目的に、複数の Isolation Level が定義されている。

Isolation Level

ANSI/ISO SQL標準の定義は以下の通り。

ansi.png
参考 A Critique of ANSI SQL Isolation Levels

しかし上記の定義は、あいまい、かつ、不十分ということで、A Critique of ANSI SQL Isolation Levelsという論文の中で、以下のような定義が提案された。

ansi2.png
参考 A Critique of ANSI SQL Isolation Levels

ANSI/ISO SQL標準の定義では、Dirty Read/Fuzzy Read/Phantom Readが起きなければSERIALIZABLEだ、というように読める。しかし、SERIALIZABLEは、複数の並行に動作するトランザクションそれぞれの結果が、あたかも1つずつ順番に実行した場合と同じ結果になる必要がある。そのため、Dirty Read/Fuzzy Read/Phantom Readが起きなければ常にSERIALIZABLEだ、とは限らない。

Snapshot Isolationとは?

『ある時点のデータのスナップショットを参照させる』ことで、参照に関する不整合を防ぐための仕組み。MVCCの一種として実装される。

動作イメージは以下の通り。 f:id:kimulla:20200314105832g:plain

トランザクションごとにデータが分離されるため、Dirty Read/Fuzzy Read/Phantom Readが起こらない。また、読み込みが書き込みをブロックしないため、参照が多いシステムでは性能向上が見込める。

ただし、Write SkewやRead Only Skewが発生するため、SERIALIZABLEではない。
参考 PostgreSQL Wiki SSI

また、同じ行を 追加/更新/削除 した場合は先勝ちになる。

Write Skew

更新契機になったデータが変更されたことに気づけないために発生する異常。

以下の例では、SERIALIZABLEならば(トランザクションが逐次実行された結果と同じなら)どちらかの色に統一されるはずだが、そうならない。

f:id:kimulla:20200314105854g:plain

また以下のように、並列に処理したことで業務上の制約を満たせなくなる場合もある。(x=普通預金口座、 y=小切手(check)振出し用当座預金口座 みたいな例)

f:id:kimulla:20200314105902g:plain

Read Only Skew

参照するTxがいることで、順序を確定できなくなる異常。2004年ごろに発見された異常のため、先述の表に記載はない。
参考 A Read-Only Transaction Anomaly Under Snapshot Isolation

checkingが小切手(check)振出し用当座預金口座 、savingが普通預金口座としたときに、合計が0を下回ったら利息をつけて貸し付けるとする。

f:id:kimulla:20200314105928g:plain

以下が相反するので、実行順序が確定できない。

  • t3が読み取った時点で20の預金があるので、利息を払う必要がない(t1 -> t2じゃないとダメ)
  • t2は利息を払っているため、t2->t1じゃないとダメ

PostgreSQLにおける実現手段

PostgreSQLでは、MVCCを用いてIsolationを実現している。

内部的に、データ一貫性は多版方式(多版型同時実行制御MVCC)を使用して管理されています。 PostgreSQL reference 13.1. 序文

ANSIとの対応

ansi.png PostgreSQL reference 13.2. Transaction Isolation

『Allowed, but not in PG』は、ANSI/ISO SQL標準的には発生してもいい異常だが、PostgreSQLでは発生しない、という意味。以下のようにリファレンスに記載されている。

より厳密な動作をすることは標準SQLでも許されています。 つまり、この4つの分離レベルでは、発生してはならない事象のみが定義され、発生しなければならない事象は定義されていません。 PostgreSQL reference 13.2. Transaction Isolation

実装の詳細

PostgreSQLでどのようにSIを実現しているのかの詳細は、以下が参考になる。
参考 The Internals of PostgreSQL
参考 Mvcc Unmasked
参考 PostgreSQL のトランザクション & MVCC & スナップショットの仕組み

以下では、個人的に気になった追加/更新/削除時の部分だけ記載する。

実装には様々な選択肢があり、PostgreSQLはロックを取得する。(MV2PL)
参考 論文紹介: An empirical evaluation of in-memory multi-version concurrency control

追加/更新/削除の挙動

PostgreSQLでは同じ行を 追加/更新/削除 した場合、TxがCommit/Abortされるまで待つ。

REPEATABLE READのときは、could not serialize ...のエラーになる。

f:id:kimulla:20200314110013g:plain

Txが待っている間の pg_locks は以下の通り。

SELECT relation::regclass, locktype, virtualxid, transactionid, virtualtransaction, mode, granted  FROM pg_locks  order by virtualtransaction, relation;
  relation   |   locktype    | virtualxid | transactionid | virtualtransaction |       mode       | granted
-------------+---------------+------------+---------------+--------------------+------------------+---------
 pg_locks    | relation      |            |               | 4/743              | AccessShareLock  | t
             | virtualxid    | 4/743      |               | 4/743              | ExclusiveLock    | t
 sample      | tuple         |            |               | 7/879              | ExclusiveLock    | t
 sample      | relation      |            |               | 7/879              | RowExclusiveLock | t
 sample_pkey | relation      |            |               | 7/879              | RowExclusiveLock | t
             | transactionid |            |           592 | 7/879              | ShareLock        | f
             | virtualxid    | 7/879      |               | 7/879              | ExclusiveLock    | t
             | transactionid |            |           593 | 7/879              | ExclusiveLock    | t
 sample      | relation      |            |               | 8/9                | RowExclusiveLock | t
 sample_pkey | relation      |            |               | 8/9                | RowExclusiveLock | t
             | transactionid |            |           592 | 8/9                | ExclusiveLock    | t
             | virtualxid    | 8/9        |               | 8/9                | ExclusiveLock    | t
(12 rows)

locktypeがvirtualxidとtransactionidのもののうち、特に重要なのが、locktypeがtransactionid、かつ、ShareLockを取れていない(grantedがf)もの。これが、Tx2がTx1の完了を待っていることを表している。

トランザクションの実行中は常に、サーバプロセスはその仮想トランザクションID上に排他的ロックをかけます。 もしある永続IDがトランザクションに割り当てられる(普通はトランザクションがデータベースの状態を変化させるときのみに発生します)と、トランザクションは終了するまで永続トランザクションIDに対して排他ロックを保持します。 あるトランザクションが他のトランザクションを特定して終了まで待機しなければならないと判断した場合、他とみなしたトランザクションのIDに対し共有ロックを獲得するように試み、目的を達します。 (仮想IDであるか永続IDであるかは、その状況によります)。 これは、他とみなしたトランザクションが完了し、そしてロックを解放した場合のみ成功します。 PostgreSQL reference pg_locks

PostgreSQLでは、MVCCで追加/更新/削除する場合、ロックを自動で取得する。locktypeがrelation(表)になっているものはコレ。

また、ほとんどのPostgreSQLコマンドでは、参照されるテーブルがそのコマンドの実行中に別の方法で削除もしくは変更されていないことを確実にするために、適切なモードのロックを自動的に獲得します。

ROW EXCLUSIVE SHARE、SHARE ROW EXCLUSIVE、EXCLUSIVE、およびACCESS EXCLUSIVEロックモードと競合します。 UPDATE、DELETE、およびINSERTコマンドは、(参照される他の全てのテーブルに対するACCESS SHAREロックに加えて)対象となるテーブル上にこのモードのロックを獲得します。 PostgreSQL reference 13.3. 明示的ロック

locktypeがtuple(行)になっているものは、行ロックを表す。しかし、リファレンスによると通常は表示されないらしい。grantedがtで行ロック取れていることになっており、よくわからない。誰か詳しい人教えてください。

タプルはロック対象のオブジェクト種類ですが、行レベルロックについての情報はメモリではなく、ディスクに保存されます。 よって行レベルロックは通常、このビューには現れません。 もしプロセスが行レベルロックの待ち状態である場合は、その行ロックを保持している永続トランザクションIDを待つ状態で、そのトランザクションはビューに現れます。

Isolation Level

READ UNCOMMITTED/READ COMMITTED

Non Repeatable Read とPhantom readが発生する。 また表に記載されている異常の他に、Lost Updateが発生する。

Lost Updateは、他方のTxの変更を意図せず上書きしてしまう異常。

f:id:kimulla:20200314110118g:plain

ただし、更新クエリのみで変更処理が完結する場合はLost Updateは発生しない。 (Isolation Levelで述べた通り、Txが完了するのを待って最新のカラムを取得し直すから)

f:id:kimulla:20200314110256g:plain

明示的ロック(Cursol stabiilty)

PostgreSQLでは、明示的にロックを取ることもできる。ロックを取る場合はSELECTで得られるデータが最新版になる。また、処理中はSELECTがブロックされる。これにより、Lost Update を防ぐことができる。
参考 PostgreSQL reference 13.3. 明示的ロック

f:id:kimulla:20200314112151g:plain

REPEATABLE READ

Snapshot Isolationの説明の通り。

SERIALIZABLE

これまで記載した全ての異常を防げる。

その他、参考資料