分散システムリファレンス

Table of Contents

1. データベース Anomaly
   1. 基本的な Anomaly
   2. 複合的な Anomaly
   3. 実装依存の Anomaly
   4. 分離レベルの防止状況
2. 参考文献

データベース Anomaly

データベースの Anomaly (異常) とは、複数のトランザクションが並行実行される際に発生する、データの一貫性を損なう異常な状態や現象の総称。これらはデータベースのサポートする適切な分離レベルやロック機構を使うことで防止できる。Anomaly が発生すると直列実行 (Serializable) では起こりえない状態が生じ、システムの不変条件 (invariant) が崩れて深刻なバグにつながる可能性がある。以下の P (phenomenon) や A の分類は Critique 論文 [1] で定義されている。

基本的な Anomaly

P0: Dirty Write

発生条件	あるトランザクションが他のトランザクションのみコミット値を上書き。
防止手段	すべての分離レベルで防止

P1: Dirty Read

発生条件	あるトランザクションが他のトランザクションの未コミット値を読み取る。
防止手段	READ COMMITTED 以上

P2: Non-Repeatable Read, Fuzzy Read, Inconsistent Read

発生条件	あるトランザクション内で複数回読み取った値が変わる。
防止手段	REPEATABLE READ 以上

P3: Phantom

発生条件	あるトランザクション内で複数回範囲検索を行ったときに結果の集合が変わる。
防止手段	SERIALIZABLE、またはギャップロック付きの REPEATABLE READ (MySQL など)、Read-Only トランザクション

複合的な Anomaly

P4: Lost Update

発生条件	2 つの Read-Modify-Write パターンのトランザクションを並行実行するとき片方の更新が喪失する。
具体例	初期状態: \(c=0\) Tx1: \(c=0\) を読む Tx2: \(c=0\) を読む Tx1: \(c\) に 1 を加算して \(c=1\) を書く Tx2: \(c\) に 1 を加算して \(c=1\) を書く 最終状態: \(c=1\) で Tx1 の更新が喪失
防止手段	REPEATABLE READ 以上、SELECT FOR UPDATE (locking read)、楽観的ロック

A5A: Read Skew, Inconsistent Read

発生条件	あるトランザクション内で関連する複数の値を読む間に別のトランザックションが更新する。
具体例	不変条件: \(x+y=1\) 初期状態: \((x,y)=(1,0)\) Tx1: \(x=1\) を読む Tx2: \((x,y)=(1,0)\) を読む Tx2: \((x,y)=(0,1)\) を書く Tx1: \(y=1\) を読む Tx1 の状態: \((x,y)=(1,1)\) で不変条件に違反
防止手段	REPEATABLE READ 以上、SELECT FOR UPDATE、Read-Only トランザクション (一貫したスナップショット)

A5B: Write Skew

発生条件	2 つのトランザクションが互いに異なる値を読んで異なる値を更新。
具体例	不変条件: \(x=1 \lor y=1\) 初期状態: \((x,y)=(1,1)\) Tx1: \((x,y)=(1,1)\) を読む Tx2: \((x,y)=(1,1)\) を読む Tx1: \(x=1\) を確認し \(y=0\) を書く Tx2: \(y=1\) を確認し \(x=0\) を書く 最終状態: \((x,y)=(0,0)\) で不変条件に違反
防止手段	SERIALIZABLE、SELECT FOR UPDATE (locking read)

Read Only Anomaly

発生条件	読み取りトランザクションの存在により Serializability が矛盾
具体例	初期状態: \((x,y)=(0,0)\) Tx1: \((x,y)=(0,0)\) を読む Tx2: \(x=0\) を読む Tx2: \(x\) に 5 を加算し \(x=5\) を書く Tx3: \((x,y)=(5,0)\) を読んでユーザに報告 Tx1: \(x=y=0\) を確認し \(y=7\) を書く (\(x\ne y\) なら何もしない) 最終状態: \((x,y)=(5,7)\) 最終状態は Tx1 → Tx2 の順に直列実行した結果と説明できるが、Tx3 の観測結果は Tx2 → Tx1 の順でしか起きえない
防止手段	厳密な SERIALIZABLE (Serializable Snapshot Isolation 等)、すべてのトランザクションで同一のスナップショット時刻を使用

実装依存の Anomaly

P4C: Cursor Lost Update

発生条件	カーソルを使った読み取りでロックを取らずに更新
防止手段	SELECT FOR UPDATE、CURSOR STABILITY

分離レベルの防止状況

1. ^*1MySQL の REPEATABLE READ はギャップロックで防止。PostgreSQL は発生。
2. ^*2MySQL の MVCC では REPEATABLE READ でも防止。
3. ^*3トランザクション分離に Snapshot Isolation を使う実装 (MySQL, PostgreSQL, Oracle, TiDB, YugabyteDB) では発生しうる。DB2 や SQLServer のようなロックベースの実装では防止可能。

参考文献

1. BERENSON, Hal, Phil BERNSTEIN, Jim GRAY, Jim MELTON, Elizabeth O'NEIL and Patrick O'NEIL. A Critique of ANSI SQL Isolation Levels. In: Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data. San Jose, CA, USA: ACM, 1995, pp. 1-10. ISBN 0-89791-731-6. DOI: 10.1145/223784.223785.