2相ロックと直列化可能性

直列化可能性とは「何と同じ結果か」

並行実行の正しさの基準は、直列スケジュール（serial schedule）と同じ結果になることです。直列スケジュールとは、トランザクションを途中で混ぜず、1件ずつ最後まで流したスケジュールを指します。直列なら相互干渉が原理的に起きないので「正しい」とみなせる――これを基準点にします。

並行スケジュールが、ある直列スケジュールと等価なら、それは直列化可能（serializable）です。注意したいのは「元の到着順と同じ」である必要はない点で、T1→T2 でも T2→T1 でも、どれか1つの直列順と等価でありさえすればよい、という緩い条件です。

実務で扱う等価性はほぼ常に競合等価（conflict equivalence）です。2つの操作が「同じデータ項目を対象とし、少なくとも一方が書き込み」のとき、その2操作は競合します。2つのスケジュールが競合等価とは、すべての競合ペアの相対順序が両者で一致することを指します。そして並行スケジュールがある直列スケジュールと競合等価なら、それを**競合直列化可能（conflict serializable）**と呼びます。読み×読みは競合しないので順序を入れ替えても結果は変わりません。

先行グラフ：閉路の有無で判定する

競合直列化可能かどうかは、**先行グラフ（precedence graph、別名 serializability graph）**で機械的に判定できます。作り方は単純です。

1. トランザクションごとに頂点を1つ作る。
2. Ti の操作と Tj の操作が競合し、スケジュール上で Ti の操作が先なら、辺 Ti → Tj を引く。

そして次の定理が成り立ちます。

なぜ閉路が「不可能」を意味するのか。辺 Ti → Tj は「等価な直列順では Ti が Tj より前でなければならない」という制約です。閉路 T1 → T2 → T1 があれば「T1 は T2 より前、かつ T2 は T1 より前」という矛盾した要求になり、それを満たす直列順は存在しません。だから閉路の有無がそのまま判定基準になります。

スケジュール S: r1(A) w2(A) w2(B) r1(B)
  r1(A)→w2(A): A で read-write 競合、T1 が先 ⇒ 辺 T1→T2
  w2(B)→r1(B): B で write-read 競合、T2 が先 ⇒ 辺 T2→T1
先行グラフ: T1 ⇄ T2 （閉路あり）⇒ 直列化不可能

上の S は、どちらの直列順（T1→T2 でも T2→T1）とも結果が一致しません。だから「速いが正しくない」スケジュールです。隔離レベルの議論（→ トランザクション分離レベル）で出てくる各種アノマリーは、この先行グラフに閉路を生む並びを許してしまうことに対応します。

2相ロック（2PL）が閉路を作らせない理由

先行グラフは「正しさの判定器」ですが、DB は実行前に閉路を防ぎたい。そこで使うのが2相ロックです。ルールは2つだけです。

• 取得（growing）フェーズ：必要なロックを取得していく。この間は解放しない。
• 解放（shrinking）フェーズ：いったんどれか1つでもロックを解放したら、以後は新たなロックを取得してはいけない。

つまり各トランザクションのロック保有数は「単調に増えてから単調に減る」山型になります。基本ロックは共有ロック（S、読み取り用）と排他ロック（X、書き込み用）で、S は互いに両立し、X は誰とも両立しません（→ ロックと MVCC）。

言い換えると、2PL は「ロックポイントの順序」という1本の直列順を暗黙に決めており、全トランザクションをその順に並べたものが等価な直列スケジュールになります。

T1: lock-X(A) ... lock-S(B) ... | unlock(A) ... unlock(B)   ← | がロックポイント
T2: ......... lock-X(A) を待つ（T1 が unlock するまでブロック）

基本 2PL の弱点と Strict 2PL

2PL は直列化可能性を保証しますが、それだけでは実務に足りません。2つの問題が残ります。

そこで実装の定番が **Strict 2PL（厳格2相ロック）**です。追加ルールはひとつ、「すべての排他（X）ロックは、コミットまたはアボートの瞬間まで保持する」。S ロックは早めに解放する変種が一般的です。さらに S ロックも含めて全ロックをコミットまで持つ方式を **Rigorous 2PL（強2相ロック）**と呼びます。

ロック方式と MVCC の関係

近年の RDB は読み取りを止めない MVCC を併用するため、「読み取りは S ロックを取らずスナップショットを見る」のが標準です（→ MVCC の内部実装）。この場合、純粋な2PL とは正しさの保証経路が変わります。スナップショット分離（SI）は直列化可能性より弱く、**書き込みスキュー（write skew）**という、先行グラフに閉路を作るアノマリーを許します。

そこで PostgreSQL の SERIALIZABLE などは、MVCC の上に SSI（Serializable Snapshot Isolation）を載せ、実行時に危険な競合パターン（先行グラフの閉路につながる依存）を検出して、片方を直列化失敗でアボートします。考え方は先行グラフそのもので、「閉路ができそうなら未然に1つ落とす」楽観的な手法です。基本 2PL がロックで事前に閉路を防ぐのに対し、SSI は事後検出で防ぐ、という対比で押さえると見通しが良くなります。

まとめ

• 正しさの基準は競合直列化可能性で、その判定は先行グラフの閉路の有無に帰着する。
• 2PL は取得→解放の山型ルールにより、ロックポイントの時間順という1本の直列順を作り、先行グラフに閉路を作らせない。これが直列化可能性の理論的根拠。
• 実務は Strict 2PL（X ロックをコミットまで保持）で、ダーティリードとカスケードアボートまで封じ、回復可能性を担保する。
• 2PL はデッドロックを防がないので、検出・アボートとリトライが前提。MVCC 系では SSI が先行グラフの閉路を事後検出して同じ正しさを実現する。分散環境のコミット調整は別レイヤの話（→ 2相コミット（2PC））。