直列化可能スナップショット分離(SSI)の検出アルゴリズム

SSI が解く問題を一言で

スナップショット分離（SI）は読み取りがロックを取らず止まらない一方で、rw-依存（アンチ依存）を抑えないため Write Skew などを許し、直列化可能ではありません（→ スナップショット分離と並行性アノマリー）。直列化可能スナップショット分離（SSI）は、SI の実行モデルをそのまま使いながら、実行中に危険な依存構造だけを検出して片方を中断することで直列化可能性を保証します。鍵は「閉路を直接探さない」点にあります。本稿はこの検出アルゴリズムの理論的根拠と、PostgreSQL の SIREAD ロック実装を内部から解説します。

理論的根拠：危険構造の定理

並行実行が直列化可能かは、トランザクションを節点・依存を辺とする直列化グラフで判定でき、グラフに閉路がなければ直列実行と等価です。SSI の基盤は Cahill・Röhm・Fekete らの研究で、その核心は次の定理です。

       rw-依存          rw-依存
Tin ------------> Tpivot ------------> Tout
                    ^ pivot に入りの rw と出の rw が揃う

なぜ rw が2本かというと、ww・wr 依存は SI が First-Committer-Wins とスナップショットで抑え、コミット順と一致する向きしか残せないからです。残る向きを逆走できるのは rw-依存だけで、閉路を作るにはこの「逆走辺」が連続して2本必要になります。Tpivot（軸）に入りの rw と出の rw が両方ある状態が、閉路に必要な最小の局所条件です。

この定理が実装上決定的に重要なのは、閉路全体を探索する必要がないことです。各トランザクションについて「自分宛ての rw（inConflict）」「自分発の rw（outConflict）」を記録し、その両方を持つ軸が現れたら危険とみなせば済みます。Cahill らの原論文は両者を 1 ビットずつに圧縮しましたが、PostgreSQL は偽陽性削減と早期回収のため各方向の相手の集合をリストで保持します。いずれにせよ、グラフ全体を走査せず各辺の発生時に局所的な判定で済む点が肝です。

検出アルゴリズムの骨子

PostgreSQL の実装は、各トランザクションを表す SerializableXact 構造体に概ね次を持たせます。

rw-依存の辺は2方向から生まれます。ひとつは読み手が先に読み、書き手が後で書く場合で、書き込み時に「この行に誰の SIREAD ロックが付いているか」を見て辺を張ります。もうひとつは書き手が先に書き、読み手が後でその古い版を読む場合で、読み取り時に「自分のスナップショットより新しい版を作った並行トランザクションがいるか」を見て辺を張ります。どちらの経路でも、辺を張った直後に次を判定します。

辺 Ti --rw--> Tj を追加するたびに:
  # 新しい辺の両端それぞれが pivot になりうる
  if Tj.outConflicts が非空:   # 構造 Ti -> Tj -> Tout、Tj が pivot
      危険構造の候補（pivot=Tj, Tin=Ti, Tout=Tj の出先）
  if Ti.inConflicts が非空:    # 構造 Tin -> Ti -> Tj、Ti が pivot
      危険構造の候補（pivot=Ti, Tin=Ti の入元, Tout=Tj）
  # いずれかが成立 -> Tout が既コミットなら即中断、未コミットでも条件成立側を中断

実際には「pivot より先に Tout がコミット済みか」を commitSeqNo で確認し、定理の条件を満たすときだけ中断します。これにより、危険構造のように見えても直列化可能と確定できる並びは中断しません。

SIREAD ロック：データを止めない述語ロック

SSI が rw-依存を観測するには「誰がどこを読んだか」を残す必要があります。これが SIREAD ロックで、名前にロックとあるものの他者の読み書きを一切ブロックしません。役割は「あとでここに書き込みが来たら rw-依存の辺を張れ」という見張りの印です。

ここで本質的なのは、SIREAD ロックが**述語ロック（predicate lock）**として働くことです。範囲検索やインデックススキャンでは「読んだ行」だけでなく「読んだ範囲・ギャップ」に印を付けるため、まだ存在しない行の挿入（ファントム）も rw-依存として捕捉できます。これが SSI が SI 上でファントムを含む直列化可能性を達成できる理由です。インデックスを使った絞り込み読み取りなら印は範囲に限定され、シーケンシャルスキャンだと関係全体に印が付き、後者ほど偽陽性が出やすくなります。

なぜ偽陽性が出るのか

SSI は閉路の有無そのものではなく「連続2本の rw（危険構造）」という必要条件で判定します。危険構造は閉路の必要条件であって十分条件ではないため、危険構造があっても実際には閉路が無い（直列化可能だった）場合があり、これが偽陽性です。グラフ全体を走査すれば偽陽性は消せますが、それは各操作のたびに O(節点数) の探索を要し、SI の軽さを殺します。SSI は意図的に安全側へ倒す近似を選んでいます。

偽陽性の主因:
  ・SIREAD ロックの粒度昇格（行 -> ページ -> 関係）で読み範囲を過大評価
  ・シーケンシャルスキャンによる関係全体への印
  ・危険構造を閉路の十分条件と扱うことによる過剰検出

したがって SSI を使うアプリは、シリアライズ失敗（PostgreSQL では SQLSTATE 40001）を捕捉してトランザクション全体を自動再試行する作りが前提です。再試行時は片方が他方の結果を見られる順序で走り直すため整合します。これは OCC とタイムスタンプ順序 のアボート＆リトライ前提と同じ思想で、SSI は SI に楽観的な検証を後付けした形と見なせます。

PostgreSQL 実装の要点

PostgreSQL は SERIALIZABLE 分離レベルでこの SSI を実装しており、書き込みにも明示ロックにも追加の待ちを入れません（→ トランザクション分離レベル）。実務で押さえる点を整理します。

READ ONLY DEFERRABLE トランザクションは特別で、PostgreSQL が**安全なスナップショット（safe snapshot）**を取れるまで開始を待ち、取れた後は rw-依存の監視も中断もせずに走れます。読み取り専用なら出の rw を作らず pivot になり得ないため、危険構造に関与しないことを保証できるからです。レポート系の長い読み取りに有効です。

なお SSI は二相ロック（2PL）と違い、書き込み同士の衝突は MVCC の First-Committer-Wins に任せ、rw-依存だけを別建てで監視します（→ 二相ロック）。ロックで待たせて直列化する 2PL に対し、SSI は待たせず検出して中断する点が根本的に異なります。MVCC のバージョン可視性そのものは MVCC の内部実装 を参照してください。

まとめ

• SSI は「SI 由来の閉路には必ず連続2本の rw-依存（危険構造）があり、Tout が最初にコミットする」という定理を使い、pivot に入り・出の rw が揃った瞬間を定数時間で検出する。
• SIREAD ロックはデータを止めない述語ロックで、読んだ行・ページ・関係・範囲に印を付け、後続の書き込みと rw-依存の辺を張る。粒度は行→ページ→関係へ昇格する。
• 検出は閉路の必要条件による近似なので偽陽性が出る。40001 を捕捉して自動再試行するのが使う側の前提。
• PostgreSQL は SERIALIZABLE でこれを実装し、READ ONLY DEFERRABLE の安全スナップショットで監視を省く最適化を持つ。読み範囲を絞る（適切なインデックス）ほど印が小さく偽陽性が減る。