オプティミスティック並行性制御とタイムスタンプ順序

楽観と悲観：そもそも何を賭けているか

同時実行制御は「複数トランザクションを並行に流しても、1件ずつ順番に流したのと同じ結果（直列化可能）になる」ことを保証する仕組みです。その実現方式は大きく2系統に分かれます。

2相ロック（2PL）に代表される**悲観的（pessimistic）方式は、「競合は起きるもの」と仮定し、データに触れる前にロックを取って他者をブロックします（→ 2相ロックと直列化可能性）。対して楽観的（optimistic）**方式は「競合はめったに起きない」と仮定し、まずロックなしで走らせ、コミットの直前に初めて競合の有無を確かめます。

この「賭け」が当たる、すなわち競合が実際に少ないワークロードでは、楽観的方式はロック取得・解放のコストもブロック待ちもデッドロックも避けられるため、悲観的方式より速くなります。賭けが外れて競合が多いと、せっかく実行した処理を捨ててやり直すアボートのコストが膨らみ、逆に遅くなります。

OCC：読み取り・検証・書き込みの3フェーズ

OCC（Optimistic Concurrency Control）は各トランザクションを3つのフェーズに分けて実行します。

肝は「共有データを触るのは検証通過後の書き込みフェーズだけ」という点です。実行中は誰もブロックしないので、読み取りの多い処理は互いに干渉せず並走できます。

検証は通常、各トランザクションにコミット順を表すトランザクション番号を割り当て、番号の若い側を「論理的に先」とみなして判定します。Ti が Tj より先（番号が小さい）なら、両者が並行していた場合に直列順 Ti → Tj と矛盾しない、すなわち次のいずれかが成り立てば検証成功です。

検証成功の条件（Ti の番号 < Tj の番号、両者が並行のとき）
  (a) Ti が write フェーズを終えてから Tj が read フェーズを始めた
  (b) Ti の write set と Tj の read set が交わらず、かつ
      Ti は Tj が read を終える前に write を完了している
  (c) Ti の write set が、Tj の read set とも write set とも交わらない

直感的には「Ti が書いた項目を Tj が読んでいなければ、Tj から見て Ti の更新は無かったのと同じか、きれいに前後できる」ということです。逆に Ti の write set と Tj の read set が交わる（Tj が Ti の書いた古い版を読んでしまった）場合、直列順と矛盾するので後発の Tj をアボートします。

タイムスタンプ順序（T/O）：直列順を先に決める

タイムスタンプ順序制御は、別のアプローチで同じ正しさを狙います。各トランザクション Ti に開始時に一意なタイムスタンプ TS(Ti) を与え、「タイムスタンプの小さい順がそのまま直列順である」と最初に固定してしまいます。あとは、実際の操作がこの順序と矛盾しないかをデータ項目ごとに監視するだけです。

そのために各データ項目 X に2つのタイムスタンプを持たせます。

RTS(X) : X を読んだトランザクションのうち最大の TS（最後に読んだ時刻）
WTS(X) : X を書いたトランザクションのうち最大の TS（最後に書いた時刻）

操作が来たら、規定の順序（TS の昇順）に反する「過去から来た遅れた操作」を検出してアボートします。

このルールにより、データ項目への read/write は常に TS の昇順で「整列」され、先行グラフ（serializability graph）に閉路が生じません。ロックを一切使わないためデッドロックは原理的に起きず、代わりに順序違反は即アボートで処理します。

書き込みについては、TS(Ti) が WTS(X) 未満のとき「すでにより新しい版が存在するのだから、古い Ti の書き込みはどうせ誰にも読まれない」として、アボートせずその書き込みだけ黙って無視する最適化があります。これを**トーマスの書き込み規則（Thomas Write Rule）**と呼びます。これは write-write の順序だけを緩めるもので、直列化可能性は保たれます。

T/O はカスケードアボート（未コミット値を他者が読み、後で巻き戻る連鎖）を起こしうるため、実装では書き込みをコミットまで他者に見せないコミットビットを併用するのが一般的です。

MVCC との接点：版を使って読みを止めない

タイムスタンプ順序の発想は、現代の RDB が使う**MVCC（多版同時実行制御）**の土台でもあります（→ MVCC の内部実装）。多版タイムスタンプ順序（MVTO）では、書き込みのたびに古い版を消さず、WTS 付きの版として残します。Ti の読みは「TS(Ti) 以下で最大の WTS を持つ版」を選ぶため、読みは決してアボートされず、古い版を読むことで常に成功します。書き込みだけが順序違反でアボートしうる、という非対称が生まれます。

PostgreSQL の SERIALIZABLE で使われる SSI（Serializable Snapshot Isolation）も、根は楽観的です。スナップショット分離（SI）は読みを止めない代わりに書き込みスキューなどのアノマリーを許しますが（→ スナップショット分離のアノマリー）、SSI は実行時に危険な依存の組み合わせを監視し、先行グラフに閉路ができそうなら片方を直列化失敗でアボートします。「まず走らせ、危なければ後で1つ落とす」という点で、思想は OCC の検証フェーズと同じです。

2PL との対比：どこで効くか

要点は「競合の確率に賭ける向きが逆」という一語に尽きます。読み取り中心・更新が広く分散するワークロード（競合がまれ）では、楽観的方式がロックのオーバーヘッドとデッドロックをまるごと回避して優位に立ちます。逆に少数のホットな行に書き込みが集中するワークロードでは、楽観的方式のアボート率が跳ね上がり、待ってでも確実に進む 2PL の方が安定します。トランザクションを短く保ち read/write set を小さくするほど、楽観的方式の検証は通りやすくなります（→ トランザクション分離レベル）。

まとめ

• OCC は読み取り・検証・書き込みの3フェーズで、実行中はロックを取らず、コミット直前の検証で read/write set の衝突を見て、ダメなら自分をアボートする。
• タイムスタンプ順序は開始時刻で直列順を先に固定し、各項目の RTS/WTS と矛盾する遅れた操作を即アボートする。デッドロックは原理的に起きない。
• どちらも競合がまれなほど無駄が消え、ロック取得・ブロック待ち・デッドロックを避けられるため 2PL より高スループットになりやすい。競合が多いとアボートが増え逆転する。
• 多版化（MVTO）や SSI のように、読みは版で逃がし書きだけ検証する形が、MVCC を持つ現代 RDB での楽観的制御の実装形である。