リビン・テクノロジーズでは、エンジニアの希望者に対してデータベーススペシャリスト試験に向けた講座を開催しています。先日の講義では、デッドロックについての話をしたので、その辺りを深掘って解説したいと思います。
デッドロックが発生する仕組み
データベースを取り扱う上で避けて通れない問題の一つが、デッドロックです。
デッドロック (Deadlock) とは、複数のトランザクションが、互いに相手が保持しているリソース（テーブルロックや行ロックなど）の解放を待ち続け、結果としてどの処理も先に進めなくなる状態を指します。
循環待機によるデッドロックの例
デッドロックは、複数のトランザクションがリソースの獲得に関して、閉じた円環状の待機関係を形成する「 循環待機 (Circular Wait) 」によって発生します。
最も単純な循環待機の例として、二つのリソース $R_1, R_2$ をロックする二つのトランザクション $T_1, T_2$ を想定します。
begin
Lock(R1)
Lock(R2)
end
begin
Lock(R2)
Lock(R1)
end
これらのトランザクションが同時に実行されたとき、以下のようなタイミングで処理が停止します。
| ステップ | トランザクション $T_1$ | トランザクション $T_2$ | 状況 |
|---|---|---|---|
| 1 |
Lock(R1) を獲得 |
− | $T_1$ が $R_1$ を排他ロック |
| 2 | − |
Lock(R2) を獲得 |
$T_2$ が $R_2$ を排他ロック |
| 3 |
Lock(R2) を要求 |
− | $T_1$ は $T_2$ が持つ $R_2$ の解放待ち |
| 4 | − |
Lock(R1) を要求 |
$T_2$ は $T_1$ が持つ $R_1$ の解放待ち |
ステップ4 の時点で、 $T_1$ は $R_2$ を待ち、$T_2$ は $R_1$ を待つという相互の待機状態（循環待機）が発生し、デッドロックに陥ります。
これを 待ちグラフ (Wait-For Graph) として表現すると、閉路 (サイクル) が確認できます。
デッドロック検出の仕組みを持つデータベースシステムは、この待ちグラフを監視し、閉路が検出された場合にデッドロックと判定します。そして、デッドロックを解消するために、いずれかのトランザクションを強制的に ロールバック (アボート) し、ロックを解放させます。
2相ロックプロトコルとデッドロック対策
2相ロックプロトコルとは、トランザクションにおけるロック操作 (Lock）とアンロック操作（Unlock）のフェーズを以下の2つに分けるルールです。
-
成長相 (Growing Phase):
トランザクションはロックを獲得することのみが許されます。
アンロック操作は一切行えません。 -
収縮相 (Shrinking Phase):
トランザクションはアンロック操作のみが許されます。
新たなロック獲得は一切行えません。
この 2PL を適用することで、トランザクションの「 直列化可能性 (Serializability) 」が保証され、同時実行の結果が、あたかもトランザクションが一つずつ順番に実行されたかのような結果と同じになります。
厳密な 2PL (Strict 2PL)
実用的なデータベースのほとんどは、2PLをさらに強化したプロトコルを採用しています。
特に、トランザクションがコミットまたはアボートするまで、排他ロックを解放しないという制限を加えたプロトコルを 厳密な 2PL (Strict 2PL) と呼びます。
Strict 2PL の主な利点は、 カスケードロールバック（連鎖的な取り消し） を防止できる点にあります。これにより、大規模なシステムにおけるトランザクション処理の堅牢性が高まります。
Strict 2PLでもデッドロックは発生する
重要な点として、2相ロックプロトコル（厳密な2PLを含む）は 直列化可能性を保証する ためのプロトコルであり、デッドロックを回避するものではありません。
デッドロックの主要因は「異なるリソースのロック獲得順序」にあるため、2PLを基礎とした上で、システム全体でロック順序の統一を行う必要があります。
ロック順序の統一によるデッドロックの回避
デッドロックの直接的な原因である「循環待機」を防ぐため、リソース (テーブル、行など) に対してロックを獲得する順序をシステム全体で統一するルールを設けます。
例:
-
テーブル名をアルファベット順（A $\to$ B $\to$ C...）にロックする。
-
同じテーブル内で複数の行をロックする場合、主キー (Primary Key) の昇順または降順にロックする。
ロック獲得の順序が統一されていれば、トランザクション $T_1$ が $R_1$ と $R_2$ をロックする場合も、$T_2$ が $R_2$ と $R_1$ をロックする場合も、 常に同じ順序（例：$R_1 \to R_2$） でロックを試みるため、原理的に循環待機が発生しなくなります。
この「ロック順序の統一」こそが、アプリケーションレベルでデッドロックを回避するための最も強力な手段となります。