デッドロックの検出
gpt-5.icon
データベースがデッドロックを検出する仕組みは、基本的に 「トランザクション同士の待ち関係をグラフとして分析し、循環（サイクル）があるかどうかを調べる」 ことで成立します。
🔍 デッドロックの検出方法（基本原理）
1. Wait-for Graph（待ちグラフ）の構築）
DB は、トランザクション間での「待ち」をグラフとして管理します。
ノード：トランザクション（T1, T2, …）
エッジ：
「T1 → T2」 = T1 が T2 のロック解放を待っている
例（デッドロック状況）：
code:_
T1 → T2
T2 → T1
これが サイクル（循環） です。
循環が見つかったら、それはデッドロック。
2. サイクル検出アルゴリズム
DB はこのグラフに対し、サイクルがあるか を調べます。
DFS（深さ優先探索）
Tarjanの強連結成分アルゴリズム
たーぽん
Union-Find
など、DBにより実装は異なるがグラフの循環検出が基本原理。
3. サイクルがあれば、デッドロック確定
循環があると、これは誰も先に進まない状況なので、
DBが一方のトランザクションを自動的にロールバック
他方は処理を続行できる
という「犠牲者選択」（Victim Selection）を行う。
🔧 MySQL / PostgreSQL の挙動（主要DBの違い）
🐬 MySQL (InnoDB)
ロック待ちのたびに Wait-for graph を更新しチェック
デッドロックを見つけたら、
ロールバックコストが小さい方（更新行が少ない等）を victim にする
🐘 PostgreSQL
同じく Wait-for graph を構築して循環検出
victim は待ち時間が最も短いトランザクション
（PostgreSQL は比較的公平性に寄せる）