PostgreSQL のマニュアルでは、デッドロックの検出が比較的重たい処理であると記載されています。また、これを理由にデッドロック検出待機時間の見直しを提案しています。
deadlock_timeout (integer)
20.12. ロック管理
これは、デッドロック状態があるかどうかを調べる前にロックを待つ時間です。デッドロックの検査は比較的高価なので、サーバはロックを待つ度にこれを実行するわけではありません。（中略）理想としてはこの設定は通常のトランザクションにかかる時間を超えているべきです。そうすればロック待ちトランザクションがデッドロックの検査をする前にロックが解除される可能性が改善されます。
デッドロック検出待機時間のパラメータである deadlock_timeout の見直しに、どれほどの優先度で取組むべきなのかを、デッドロック検出処理の仕組みの観点から調査しました。
調査方法として、実装を追ったりパフォーマンスを適切に計測することは難しそうだったので、理論面から追うことにしました。
まず、マニュアルやソースコード中のコメントから情報収集・整理を行います。今回は PostgreSQL 14 を基準としました。
デッドロックはテーブルレベルロック・行レベルロックで発生しうることがマニュアルに記載されています。下記の節を参照してください。
https://www.postgresql.jp/document/14/html/explicit-locking.html
13.3.4. デッドロック
ソースコードの README の記述を確認します。
src/backend/storage/lmgr/README
To perform deadlock checking, we use the standard method of viewing the various processes as nodes in a directed graph (the waits-for graph or WFG). There is a graph edge leading from process A to process B if A waits for B, ie, A is waiting for some lock and B holds a conflicting lock. There is a deadlock condition if and only if the WFG contains a cycle. We detect cycles by searching outward along waits-for edges to see if we return to our starting point.
プロセスを有向グラフのノードとして表現します。プロセス A がプロセス B のロック解放を待つとき、A から B へのエッジが存在します。このグラフが循環する時にデッドロック状態となっています。
グラフが循環するかはトポロジカルソートできるかで検証できます。トポロジカルソートの時間計算量は O(N+E)（Nはノード数、Eはエッジ数）です。
トポロジカルソート - Thoth Children
トポロジカルソートにどれだけ時間がかかるかを検証しました。1→2, 2→3, 3→4, ... 100000→100001 のように依存関係が続きかつ閉路は無い順序を tsort コマンドに与えました。
# time tsort sortnode_100k.txt > /dev/null real 0m0.060s user 0m0.055s sys 0m0.005s
これだけ多くても 60 ミリ秒程度で済んでいます。
デッドロック検出では他にもオーバーヘッドがあると思われます。また、テーブルレベルロックだけでなく行レベルロックも対象であることを考えると、検出対象の規模も状況に応じて様々でしょう。それでも、処理時間の一つの目安として考えることはできます。
引き続き README を確認します。
src/backend/storage/lmgr/README
We do this using an "optimistic waiting" approach: if a process cannot acquire the lock it wants immediately, it goes to sleep without any deadlock check. But it also sets a delay timer, with a delay of DeadlockTimeout milliseconds (typically set to one second). If the delay expires before the process is granted the lock it wants, it runs the deadlock detection/breaking code. Normally this code will determine that there is no deadlock condition, and then the process will go back to sleep and wait quietly until it is granted the lock.
プロセスがロックを即座に獲得できなければ、デッドロック検出無しにスリープします。ですが、deadlock_timeout（通常は1秒）を超過してもロックを獲得できなければ、デッドロック検出を行います。デッドロック状態になければプロセスは再びスリープし、ロックを獲得できるまで待ちます。
この記述からは以下のことが推測できます。
まず、デッドロック検出はプロセス単位で行われるということです。データベース全体で定期的にデッドロックを検出しているわけではないようです。
また、プロセスはロック獲得待ちの間にデッドロック検出を1回しか行いません。デッドロック検出でデッドロックが見つからなければプロセスはロック獲得まで待ちます。デッドロック検出を繰り返す必要がない理由として、グラフの循環は最後のエッジが追加されたときに形成され、その最後の待機プロセスがデッドロック検出を実行した時に見つかるためとしています。参考にした記述を README から引用します。
src/backend/storage/lmgr/README
It is easily proven that no deadlock will be missed due to our asynchronous invocation of deadlock checking. A deadlock cycle in the WFG is formed when the last edge in the cycle is added; therefore the last process in the cycle to wait (the one from which that edge is outgoing) is certain to detect and resolve the cycle when it later runs CheckDeadLock.
今回の調査をまとめます。
トランザクション単位で見れば、デッドロック検出処理時間よりロック獲得待ち時間のほうが長いと推測されます。よって、デッドロック検出処理がトランザクション単位の処理時間に影響する程度は少ないでしょう。ただ、デッドロック検出処理でCPUを使用することを考えると、全体のスループットに多少の影響はあるでしょう。
デッドロック検出はプロセス（トランザクション）がロック獲得待ちかつ deadlock_timeout を超過した場合に行われます。これが頻発するような状況であれば、deadlock_timeout の見直しだけでなく、アプリケーション設計を見直すべきなのかもしれません。
また、デッドロック検出の条件を言い換えると、ロック獲得待ちが deadlock_timeout を超過しなければ、デッドロック検出は発動しません。このような状況であれば、deadlock_timeout の設定値を見直したとしても、効力を発揮しないでしょう。
これらを踏まえると、deadlock_timeout の見直しを行う優先度は比較的低いといえそうです。
