###### tags: `mksc` `isolation` `postgres`

社内 LT 向けの資料です．

# トランザクションの分離レベルについて

## 今日の内容

- A Critique of ANSI SQL Isolation Levels[^Berenson1995] という 1995 年の重要な論文の話
- 「Oracle の `SERIALIZABLE` と PostgreSQL の `SERIALIZABLE` は異なる」を理解することを目標とする
- Oracle の `SERIALIZABLE` は Serializable ではない[^dbi-oracle]

　　　　　　　　 ,. -‐'''''""¨¨¨ヽ
　　　　 　 　 (.＿＿_,,,... -ｧァﾌ|
　 　 　 　 　 |i i|　 　 }!　}} /／|
　　　　 　 　 |l､{　 　j}　/,,ｨ//｜
　　　　　　　 i|:!ヾ､_ﾉ／ u {:}//ﾍ
　　　　　　　 |ﾘ u' }　 ,ﾉ　_,!V,ﾊ |
　　 　 　 ／´fト､_{ﾙ{,ィ'ｅﾗ　, ﾀ人　　　　　　な…　何を言ってるのか　わからねーと思うが
　　　　 /' 　 ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ　　　　　　 おれも何をされたのかわからなかった…
　　　　,ﾞ　 ／ )ヽ iLﾚ 　u' |　| ヾｌﾄﾊ〉
　　 　 |／_／　 ﾊ !ニ⊇　'／:} 　V:::::ヽ　　　　　　　　頭がどうにかなりそうだった…
　　　 /／ 二二二7'T'' ／u'　__ /:::::::/｀ヽ
　　　/'´r　-―一ｧ‐ﾞＴ´　'"´ ／::::／-‐ 　＼　　　　 催眠術だとか超スピードだとか
　　 / // 　 广¨´ 　/'　　 ／:::::／´￣｀ヽ ⌒ヽ　 そんなチャチなもんじゃあ　断じてねえ
　　ﾉ ' /　 ノ:::::`ー-､___／:::::／/ 　 　 　 ヽ　　}
_／｀丶　/::::::::::::::::::::::::::￣`ー-{:::...　　　 　　　ｲ  もっと恐ろしいものの片鱗を味わった

## 分離レベルについて知っていますか？

ORM を使っていると意識することは少ないのではないかと．

テーブルの内容．

# SELECT * FROM demo;
 id | value 
----+-------
  1 |   100
  2 |   200
  3 |   300
(3 rows)

2 つのトランザクションを並行実行する．

============================== T1 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN
*# SELECT * FROM demo WHERE id = 1;
 id | value 
----+-------
  1 |   100
(1 row)
============================== T2 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN
*# UPDATE demo SET value = value + 1 WHERE id = 1;
UPDATE 1
*# COMMIT;
COMMIT
============================== T1 ==============================
*# SELECT * FROM demo WHERE id = 1;
 id | value 
----+-------
  1 |   101
(1 row)
*# COMMIT;
COMMIT
================================================================

PostgreSQL の `READ COMMITTED` では，このような "好ましくない" 現象が存在し得る．

## 前提知識

- トランザクション
- データベースが保証する一貫性の単位
- 一連のデータアイテムの読み書き + コミット or アボート
- ある述語 (e.g., `WHERE` 句) を満たすデータアイテムを読み書きすることもある
- 形式的には半順序を用いてモデル化するが，ここでは単純のため全順序を用いてモデル化する
- $T_1 = \underline{w_1[y] r_1[P] c_1}$
- $T_2 = r_2[x] r_2[y] w_2[z \in P] a_2$
- リレーショナルデータベース
- 複数のトランザクションを並行に実行して高速に処理する
- 入力されたすべてのトランザクションのすべての操作をどのような順序で実行するかを決めるのがスケジューラーの役割
- スケジューラーの出力をヒストリーという
- $\underline{w_1[y]} r_2[x] \underline{r_1[P]} r_2[y] w_2[z \in P] a_2 \underline{c_1}.$
- $\underline{w_1[y] r_1[P] c_1} r_2[x] r_2[y] w_2[z \in P] a_2.$ (直列実行)
- ヒストリーのパターンによっては，"好ましくない" 現象が起きる
- 別のトランザクションが変更中のレコードを読んでしまったり，更新したはずのレコードが別のトランザクションによって上書きされてしまったり，etc.
- どのような現象を許容するか，どの現象を許容しないか，という条件によってトランザクションの分離レベルが分けられている
- Serializable: 最も制約が厳しい (i.e., 好ましくない現象が起こらない)

## ANSI SQL による分離レベルの定義

- ANSI SQL[^ansi-sql] は，特定のパターンのヒストリーで発生する P1--3 の現象により 4 つの分離レベルを定義している
- P1: Dirty Read
- 実行中のトランザクションが変更したデータアイテムの読み取りが不整合を起こすかもしれない
- パターン
- $\dots w_1[x] \dots r_2[x] \dots c_1 \dots$ or
- $\dots w_1[x] \dots r_2[x] \dots a_1 \dots$
- E.g.,
- 口座間送金を考える
- 口座 A, B の残高はそれぞれ 50 ドルとする
- $T_1$ が口座 A から口座 B への 40 ドルの送金を処理している途中に，
- $r_1[A = 50] w_1[A := 10] \dots$
- $T_2$ が口座 A, B の残高を参照すると一貫性のない状態が見えてしまう
- $\dots \underline{r_2[A = 10] r_2[B = 50]} c_2 r_1[B = 50] w_1[B := 90] c_1$
- P2: Fuzzy Read (Non-Repeatable Read)
- 読み取ったデータアイテムが他のトランザクションにより変更されて不整合を起こすかもしれない
- パターン
- $\dots r_1[x] \dots w_2[x] \dots c_1 \dots$ or
- $\dots r_1[x] \dots w_2[x] \dots a_1 \dots$
- E.g.,
- $T_1$ が口座 A, B の残高を参照している途中に，
- $\underline{r_1[A = 50]} \dots$
- $T_2$ が口座 A から口座 B への 40 ドルの送金を完了すると
- $\dots r_2[A = 50] w_2[A := 10] r_2[B = 50] w_2[B := 90] c_2 \dots$
- $T_1$ は口座 A に 50 ドル，口座 B に 90 ドルの残高があるように見えてしまう
- $\dots \underline{r_1[B = 90]} c_1$
- P3: Phantom
- 述語を満たすデータアイテムがトランザクションの実行中に変更されて不整合が起きるかもしれない
- パターン
- $\dots r_1[P] \dots w_2[y \in P] \dots c_1 \dots$
- $\dots r_1[P] \dots w_2[y \in P] \dots a_1 \dots$
- E.g.,
- $T_1$ が男性の従業員 (この時点では 10 人) のリスト ($P = \{ x \mid x \in \text{従業員の集合}, x \ \text{は男性} \}$) を読み取り，
- $\underline{r_1[P]} \dots$
- その後 $T_2$ が新たな男性の従業員 $y$ を追加し，男性の従業員数 $z$ を更新したとする
- $\dots w_2[y \in P] r_2[z = 10] w_2[z := 11] c_2 \dots$
- $T_1$ が男性の従業員数 $z$ を参照すると，男性の従業員リスト ($r_1[P]$) には 10 件しかないのにもかかわらず，男性の従業員数 ($r_1[z]$) は $z = 11$ 件となって不整合が生じる
- $\dots \underline{r_1[z = 11]} c_1$
- ANSI SQL には含まれないが，Dirty Write という現象もある
- P0: Dirty write
- $\dots w_1[x] \dots w_2[x] \dots c_1 \dots$ or
- $\dots w_1[x] \dots w_2[x] \dots a_1 \dots$

| Isolation Level | P1: Dirty Read | P2: Non-Repeatable Read | P3: Phantom |
|-|-|-|-|
| Read Uncommitted | Possible | Possible | Possible |
| Read Committed | Not Possible | Possible | Possible |
| Repeatable Read | Not Possible | Not Possible | Possible |
| Serializable | Not Possible | Not Possible | Not Possible |

## PostgreSQL がサポートする分離レベル

PostgreSQL がサポートしている分離レベル[^pg-isolation] は次のとおり．

| Isolation Level | P1: Dirty Read | P2: Non-Repeatable Read | P3: Phantom |
|-|-|-|-|
| Read Uncommitted | Allowed, but not in PG | Possible | Possible |
| Read Committed | Not Possible | Possible | Possible |
| Repeatable Read | Not Possible | Not Possible | Allowed, but not in PG |
| Serializable | Not Possible | Not Possible | Not Possible |

"Allowed, but not in PG" となっているのは，PostgreSQL が Serializable Snapshot Isolation (SSI)[^pg-ssi] に基づいてトランザクションを実装しているためである．

### `READ COMMITTED` (default)

Non-Repeatable Read を引き起こしてみる．

============================== T1 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN
*# SELECT * FROM demo WHERE id = 1;
 id | value 
----+-------
  1 |   100
(1 row)
============================== T2 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN
T2=*# UPDATE demo SET value = value + 1 WHERE id = 1;
UPDATE 1
*# COMMIT;
COMMIT
============================== T1 ==============================
*# SELECT * FROM demo WHERE id = 1;
 id | value 
----+-------
  1 |   101
(1 row)
*# COMMIT;
COMMIT
================================================================

Phantom を引き起こしてみる．

============================== T1 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN
*# SELECT * FROM demo WHERE value >= 100 AND value <= 200;
 id | value 
----+-------
  1 |   100
  2 |   200
(2 rows)
============================== T2 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL READ COMMITTED;
BEGIN
*# INSERT INTO demo VALUES (DEFAULT, 150);
INSERT 0 1
*# COMMIT;
COMMIT
============================== T1 ==============================
*# SELECT * FROM demo WHERE value >= 100 AND value <= 200;
 id | value 
----+-------
  1 |   100
  2 |   200
  4 |   150
(3 rows)
*# COMMIT;
COMMIT
================================================================

### `REPEATABLE READ`

Non-Repeatable Read は発生しない．

============================== T1 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN
*# SELECT * FROM demo WHERE id = 1;
 id | value 
----+-------
  1 |   100
(1 row)
============================== T2 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN
T2=*# UPDATE demo SET value = value + 1 WHERE id = 1;
UPDATE 1
*# COMMIT;
COMMIT
============================== T1 ==============================
*# SELECT * FROM demo WHERE id = 1;
 id | value 
----+-------
  1 |   100
(1 row)
*# COMMIT;
COMMIT
================================================================

Phantom は発生しない．

============================== T1 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN
*# SELECT * FROM demo WHERE value >= 100 AND value <= 200;
 id | value 
----+-------
  1 |   100
  2 |   200
(2 rows)
============================== T2 ==============================
# BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
BEGIN
*# INSERT INTO demo VALUES (DEFAULT, 150);
INSERT 0 1
*# COMMIT;
COMMIT
============================== T1 ==============================
*# SELECT * FROM demo WHERE value >= 100 AND value <= 200;
 id | value 
----+-------
  1 |   100
  2 |   200
(2 rows)
*# COMMIT;
COMMIT
================================================================

## Serializable の定義

- ANSI SQL[^ansi-sql] は Serializable を次の 2 通りで定義している
1. P1--3 の現象が発生しない
2. 各トランザクションを直列に実行したものと同等の結果になる
- この定義にはバグがあって，1--2. は同値でない
- より正確には，P1--3 以外にもさまざまな現象が存在する
- E.g., Dirty Write, Cursor Lost Update, Lost Update, Read Skew, Write Skew[^Berenson1995]
- これらの現象は，当時は存在しなかった Snapshot Isolation (SI) に由来する
- Serializable を 1. で定義すると，P1--3 が発生しなくても Write Skew が発生する可能性があるため，2. の定義と同値でないことが明らか
- 製品ごとに何を Serializable とするかの解釈が異なる
- Oracle の `SERIALIZABLE`
- 1\. の定義に従う
- PostgreSQL の `SERIALIZABLE`
- 2\. の定義に従う
- 個人的にはこちらの立場

## 終わりに

- すべては ANSI SQL が悪い
- トランザクションが Two-Phase Locking により実装されていた時代の定義
- Snapshot Isolation (SI) や Multi-Version Concurrency Control (MVCC) が主流な現代は ANSI SQL は適切でない
- PostgreSQL のデフォルトの分離レベルは `READ COMMITTED` なので，普通の人はこんな細かい話を気にする必要ありません
- 逆に言えば，何も気にしていなければ普通に Non-Repeatable Read とか Phantom とかは発生しているので，それを知った上で適切な分離レベルを選択するようにしてください
- 町の電話屋さんでは，この手の仕事に興味のある仲間を募集中です

## 議論

- 分離レベル
- PG の分離レベルのページをこれまでに 4 回ほど参照した (by 専務)
- `SELECT ... FOR UPDATE` があればいい
- DB 側で担保してくれることにもうれしさがあるのでは (e.g., プログラマーが意識しなくてもバグらない)
- Write に強い PG
- IoT 用途，100 TPS (write)，RPi で SD カードで動いて欲しい (by 専務)
- LSM-tree を使っている DB を利用するといいのでは
- PG にも LSM-tree を入れる [取り組み](https://www.postgresql.org/message-id/flat/315b7ce8-9d62-3817-0a92-4b20519d0c51%40postgrespro.ru) がある
- PG のバージョンアップ
- 早くない？ (by 専務)
- 1 年に 1 回メジャーアップデートする方針になった
- データベースクラスタの更新が必要なのでバージョンアップグレードの際は気をつけて

[^Berenson1995]: Hal Berenson, et al. A Critique of ANSI SQL Isolation Levels. Proc. ACM SIGMOD 95, pp. 1-10, San Jose CA, June 1995.
[^dbi-oracle]: Oracle serializable is not serializable - Blog dbi services. https://blog.dbi-services.com/oracle-serializable-is-not-serializable/
[^ansi-sql]: ISO/IEC 9075-2:2016 Information technology -- Database languages -- SQL -- Part 2: Foundation (SQL/Foundation). https://www.iso.org/standard/63556.html
[^pg-isolation]: PostgreSQL: Documentation: 14: 13.2. Transaction Isolation. https://www.postgresql.org/docs/current/transaction-iso.html
[^pg-ssi]: Dan R. K. Ports and Kevin Grittner. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment, Vol. 5, Issue 12, August 2012, pp 1850–1861.