スナップショット分離と並行性アノマリー

スナップショット分離はなぜ「ほぼ安全」なのか

スナップショット分離（SI）は、各トランザクションが開始時点の一貫したスナップショットを読み、書き込みは MVCC で別バージョンとして積む方式です（→ MVCC の内部実装）。多くの製品が Repeatable Read として実装し、ダーティリード・ノンリピータブルリード・ファントムまで実質的に防ぎます（→ トランザクション分離レベル）。

ところがこれは直列化可能（Serializable）ではありません。SI の世界では、どの単独トランザクションから見ても整合しているのに、同時実行の組み合わせ全体としては「どんな直列順でも生じ得ない状態」が残ることがあります。本稿はその正体である Write Skew と、それを正攻法で潰す SSI の原理を掘り下げます。

まず Lost Update：SI が防げる側

Lost Update（更新の喪失）は、2本が同じ行を読んで計算し、上書きし合って片方の更新が消える異常です。

T1: read x=100  ->  x = 100 - 10 = 90  -> write x=90
T2: read x=100  ->  x = 100 - 10 = 90  -> write x=90   # 合計20減るはずが10しか減らない

SI ではこれを**First-Committer-Wins（先にコミットした者勝ち）**で防ぎます。同じ行に対する並行更新を検知し、後からコミットしようとした側を中断するためです。SELECT ... FOR UPDATE で読み取り時にロックを取るか、製品が自動でシリアライズ失敗を返します。重要なのは、両者が同じ行 x を書くため衝突として観測できる、という点です。

Write Skew：SI が構造的に防げない側

Write Skew は Lost Update とよく似ていますが、決定的な違いがあります。2本が読む行と書く行がずれていて、書き込み同士が衝突しないのです。

古典例は「オンコール医師は常に1人以上いること」という制約です。医師 A と B の2人が当直中で、それぞれが「自分が抜けても相方が残る」と判断して同時に抜けるケースです。

不変条件: count(on_call = true) >= 1
初期状態: A=true, B=true

T1(医師A): read {A,B} -> 当直は2人 -> 自分が抜けても1人残る -> write A=false
T2(医師B): read {A,B} -> 当直は2人 -> 自分が抜けても1人残る -> write B=false
両者コミット成功 -> 結果 A=false, B=false（当直0人で不変条件が破れる）

T1 は行 A を書き、T2 は行 B を書きます。書く対象が別の行なので First-Committer-Wins は発動せず、両方がコミットできてしまいます。しかし直列に実行していれば、後発の側は相方が抜けた後の状態を読み「自分は抜けられない」と判断したはずです。SI では各自が古い（相方がまだいる）スナップショットを読むため、この判断が成立しません。

依存グラフで「なぜ直列化できないか」を見る

並行実行が直列化可能かどうかは、トランザクション間の依存を辺とする依存グラフ（直列化グラフ）で判定できます。グラフに閉路がなければ、辺の向きに従って並べた直列実行と等価です。逆に閉路があれば、どんな直列順とも等価にできない＝直列化不可能です。

依存には3種類あります。

SI は ww と wr を First-Committer-Wins とスナップショットで抑えますが、rw-依存だけは野放しです。Write Skew の依存グラフを描くと、T1 が読んだ B を T2 が書き（T1 -> T2 の rw）、T2 が読んだ A を T1 が書く（T2 -> T1 の rw）ため、rw-依存だけで閉路ができます。これが「SI では検知されないのに直列化不可能」という状態の正体です。

SSI：危険な構造を実行中に検知する

直列化可能スナップショット分離（SSI）は、SI の利点（読みがロックを取らず止まらない）を保ったまま、上の閉路を壊すアルゴリズムです。基盤は Cahill らの研究で、PostgreSQL の Serializable がこれを実装しています。

鍵は、SI 由来の閉路には必ず連続する2本の rw-依存を含む「危険構造（dangerous structure）」が現れる、という定理です。

       rw            rw
Tin --------> Tpivot --------> Tout
              （入りと出の rw が pivot に揃う）

ある1本のトランザクション（pivot）が、自分への入り rw-依存と自分からの出 rw-依存を同時に持つとき、その並びは直列化不可能な閉路の一部になり得ます。SSI はこの「入りと出の rw が1本の pivot に揃った瞬間」だけを危険とみなします。

危険構造を検知すると、SSI は関与するトランザクションのいずれかをシリアライズ失敗（PostgreSQL では SQLSTATE 40001）で中断します。実際のコミット衝突を待たず、依存構造だけで先回りして潰すのが特徴です。中断された側はアプリがそのまま再実行すれば、今度は片方がもう一方の結果を見られる順序で走り、整合します。

防ぎ方の比較

同じ Write Skew でも、対処の層が複数あります。実務では複数を組み合わせます。

FOR UPDATE が効くのは、Write Skew の根が rw-依存（読んだ行が後で書き換わる）だからです。読み取りをロック付き読み取りに変えれば、そのアンチ依存は通常のロック衝突に化け、SI でも First-Committer-Wins と同じ土俵で衝突を検知できます。ただし読む行と書く行が完全にずれている場合は、判断に使った全行を確実にロックする必要があり、漏れると依然すり抜けます。

まとめ

• スナップショット分離は wr・ww 依存（ダーティリード・Lost Update など）を防ぐが、rw-依存（アンチ依存）を抑えないため Write Skew を防げない。
• Write Skew は「複数行を読んで判断し、別の行を書く」処理で起き、書き込みが衝突しないため First-Committer-Wins をすり抜ける。
• 直列化不可能な状態は依存グラフの閉路として現れ、SI 由来の閉路には必ず**連続2本の rw-依存（危険構造）**が含まれる。
• SSI は SIREAD ロックで rw-依存を追跡し、pivot に入り・出の rw が揃った瞬間に片方を中断（40001）して直列化可能性を保証する。読みは止めないが偽陽性があるためリトライ前提で使う。

トランザクションの ACID 全体での位置付けは ACID、ロックと MVCC の基礎は ロックと MVCC も参照してください。