デッドロック検出と待機グラフ・タイムアウト

デッドロックはなぜ自然解消しないのか

ロックベースの同時実行制御では、各トランザクションが必要なロックを取得し、取れなければ相手の解放を待ちます。問題は、この「待ち」が循環したときです。T1 が項目 A の X ロックを持って B を要求し、T2 が B の X ロックを持って A を要求すると、両者は互いの解放を永遠に待ち続けます。これがデッドロックで、外から介入しない限り自然には解けません。

2相ロック（2PL）は直列化可能性を保証しますが、デッドロックは防ぎません（→ 2相ロックと直列化可能性）。したがってロック方式の DB は、デッドロックを「起きてから解く（検出）」か「起こさせない（予防）」かのどちらかの仕組みを必ず持ちます。

待機-for グラフによる能動的検出

能動的検出（detection）は、循環待ちそのものを探します。使うのは**待機-for グラフ（wait-for graph、WFG）**です。作り方は単純です。

1. 実行中のトランザクションごとに頂点を1つ作る。
2. Ti が、Tj の保有するロックの解放を待っているなら、有向辺 Ti → Tj を引く。

待機-for グラフは、直列化可能性の判定に使う**先行グラフ（precedence graph）**とは別物です。先行グラフは「正しさ」を、待機-for グラフは「膠着」を判定します。混同しないでください。

T1: lock-X(A) 取得済み → lock-X(B) を要求して待ち  ⇒ 辺 T1 → T2（B は T2 が保有）
T2: lock-X(B) 取得済み → lock-X(A) を要求して待ち  ⇒ 辺 T2 → T1（A は T1 が保有）
待機-for グラフ: T1 ⇄ T2 （閉路あり）⇒ デッドロック確定

実装上の検出タイミングには2系統あります。1つは継続検出で、辺を追加するたびに閉路ができたか確かめる方式。もう1つは周期検出で、一定間隔または「あるロック要求が一定時間ブロックした」契機でグラフ全体をスキャンする方式です。PostgreSQL は後者寄りで、ロック待ちが deadlock_timeout（既定 1 秒）を超えたときに限って初めてグラフを点検します。閉路検出は深さ優先探索（DFS）で back edge を探せば線形時間で済むため、検出自体は軽い処理です。頻繁に走らせないのは、デッドロックがまれな前提で「待ちが長引いたときだけ調べる」方が平均コストが低いからです。

予防：wait-die と wound-wait

予防（prevention）は、待ちの循環そのものを構造的に作らせません。代表がwait-die と wound-wait で、どちらもトランザクションに開始時刻のタイムスタンプ TS を割り当て、これを「年齢」として扱います。TS が小さいほど古い（年長）トランザクションです。考え方はタイムスタンプ順序制御に近く、循環を一意な順序で禁じる発想です（→ オプティミスティック並行性制御とタイムスタンプ順序）。

Ti が、Tj の保有するロックを要求してぶつかった状況を考えます。両方式の規則は次の通りです。

両者に共通する原理は「待ちの向きをタイムスタンプ順に一方向へ揃える」ことです。wait-die では「古い→若い」の向きにしか待たない（若い者は待たずに死ぬ）。wound-wait では「若い→古い」の向きにしか待たない（古い者は待たずに奪う）。待ち辺の向きが TS の単調な大小に固定されるので、T1 → T2 → … → T1 のような循環は数の大小として矛盾し、原理的に作れません。これが予防が成立する理由です。

両方式の性質の差を押さえておきます。wait-die は非横取り型で、待つのは古い者だけ。若い者はロックをまだあまり持っていないことが多く、その時点で die させても巻き戻しが軽い傾向があります。wound-wait は横取り型で、古い（＝すでに多くの作業を終えた）者を優先して生かすため、無駄になる作業量が小さくなりやすく、アボート総数も wait-die より少ない傾向があります。どちらも「古い者ほど生き残りやすい」点は共通で、長時間走るトランザクションが何度も犠牲になって完了できなくなる事態を避けています。

犠牲者選定とアボートコスト

検出方式では、閉路を見つけた後に「閉路上のどの1件を殺すか」を決めねばなりません。閉路上のトランザクションを1つアボートしてロックを解放すれば、その辺が消えて閉路がほどけ、残りが進めます。問題はどれを選べば損が最小かで、これが**犠牲者選定（victim selection）**です。

犠牲者選定で同時に効くのがロールバック量の判断です。閉路を解くのに必要なのは「対象のロックを解放させる」ことだけなので、トランザクション全体を巻き戻す全ロールバックではなく、競合するロックを取得した地点まで戻す部分ロールバック（セーブポイントまで戻す）で足りる場合があります。戻す量が少ないほど再実行コストが下がります。ただし戻した先から再び同じ相手とぶつかれば、同じデッドロックが再発します。これを避けるため、犠牲者は短いランダム遅延を入れてから再試行する、取得順序を揃えるなどの工夫が併用されます。

最後に、これらの選定は MVCC とロックの併用環境でも本質は変わりません。読み取りがスナップショットを見てロックを取らない MVCC でも、行更新や明示ロック（SELECT ... FOR UPDATE）はロックを取るため、書き込み同士のデッドロックは依然として起こり、待機-for グラフで検出されます（→ ロックと MVCC）。

タイムアウト：検出を持たない簡易代替

待機-for グラフを維持せず、「一定時間待っても取れなければ自分をアボートする」だけの方式がタイムアウトです。実装が極めて軽く、分散環境でも大域グラフを構成せずに済む利点があります。多くの DB は、明示的な検出を行う前段としてロック待ちタイムアウト（例: lock_timeout）も提供します。

タイムアウトの本質的な弱点は、「デッドロックなのか、単に遅いだけなのか」を区別できないことです。閾値を短くすれば混雑時に正常なトランザクションまで巻き込んで殺し、長くすればデッドロックの膠着が閾値ぶんそのまま残ります。このトレードオフを避けたいからこそ、単一ノードの RDB は安価な閉路検出を実装します。PostgreSQL の deadlock_timeout は「タイムアウトでアボートする時間」ではなく「待機-for グラフを点検し始めるまでの猶予」である点に注意してください――タイムアウトと検出を組み合わせ、まれな検出コストを必要なときだけ払う設計です。

まとめ

• デッドロックは Coffman の4条件が揃うと成立し、ロックの循環待ちが核心。2PL では防げないため、検出か予防の仕組みが必須（→ トランザクション分離レベル）。
• 能動的検出は待機-for グラフの閉路 = デッドロックを DFS で見つけ、閉路上の1件をアボートして解く。点検は「待ちが長引いたときだけ」走らせると平均コストが低い。
• 予防の wait-die / wound-wait は TS（年齢）で待ちの向きを一方向に固定し、循環を最初から禁じる。再起動で元の TS を引き継ぐことが飢餓回避の鉄則。
• 犠牲者選定はアボートコスト最小化が原則で、作業量・ロック数・カスケード・過去のアボート回数を見て選ぶ。部分ロールバックで再実行コストを抑えつつ、再発を遅延・順序統一で防ぐ。タイムアウトは検出を持たない軽量代替で、誤検知と応答性のトレードオフを抱える。