本节是PostgreSQL Locks中的The Deadlock Detection Algorithm(死锁检测算法)部分,翻译自README文件.

### 一、The Deadlock Detection Algorithm
```
The Deadlock Detection Algorithm
--------------------------------
死锁检测算法

Since we allow user transactions to request locks in any order, deadlock
is possible.  We use a deadlock detection/breaking algorithm that is
fairly standard in essence, but there are many special considerations
needed to deal with Postgres' generalized locking model.
PG允许事务以乱序的方式申请锁,因此会出现死锁的可能.PG使用的检测算法相当标准,
但为了适配PG的锁模型因此有不少特别的考虑.

A key design consideration is that we want to make routine operations
(lock grant and release) run quickly when there is no deadlock, and
avoid the overhead of deadlock handling as much as possible.  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.  But if a deadlock condition
does exist, it will be resolved, usually by aborting the detecting
process' transaction.  In this way, we avoid deadlock handling overhead
whenever the wait time for a lock is less than DeadlockTimeout, while
not imposing an unreasonable delay of detection when there is an error.
一个设计上考虑的关键点是在没有死锁的情况下可以让锁授予和释放可以执行得更快.
通过使用一种"乐观等待"机制来实现:如果进程不能马上获取请求的锁,则马上休眠而不执行任何死锁检测.
但同时设置了延迟时钟,延迟时长为DeadlockTimeout毫秒(典型值是1s).
如果在进程被授予锁前延迟过期,则执行死锁检测和中断代码.通常来说,这些代码会确定
是否存在死锁条件,然后进程会重新休眠并等待直至可以获取锁.
但如果死锁条件确实存在,那需解决此问题,通过来说会回滚执行检测的事务.
通过这种方法,避免锁等待时间小于DeadlockTimeout时的死锁处理开销,
而在出现错误时则不执行不合理的延迟检测.

Lock acquisition (routines LockAcquire and ProcSleep) follows these rules:
锁获取(LockAcquire和ProcSleep子过程)遵循以下原则:

1. A lock request is granted immediately if it does not conflict with
any existing or waiting lock request, or if the process already holds an
instance of the same lock type (eg, there's no penalty to acquire a read
lock twice).  Note that a process never conflicts with itself, eg one
can obtain read lock when one already holds exclusive lock.
1.对于如无冲突或者进程已持有相同类型的锁的锁请求(如获取两次读锁),则马上授予锁.
注意进程永远不会与自己冲突,比如已获取独占锁的情况下可以获取读锁.

2. Otherwise the process joins the lock's wait queue.  Normally it will
be added to the end of the queue, but there is an exception: if the
process already holds locks on this same lockable object that conflict
with the request of any pending waiter, then the process will be
inserted in the wait queue just ahead of the first such waiter.  (If we
did not make this check, the deadlock detection code would adjust the
queue order to resolve the conflict, but it's relatively cheap to make
the check in ProcSleep and avoid a deadlock timeout delay in this case.)
Note special case when inserting before the end of the queue: if the
process's request does not conflict with any existing lock nor any
waiting request before its insertion point, then go ahead and grant the
lock without waiting.
2.否则,进程会加入到锁等待队列.通常来说,会加入到队列的末尾,但存在例外情况:
如果进程已在对象上持有锁但与其他等待者的请求存在冲突,进程会插入到队列中这些waiter的前面.
(如果不执行该检查,死锁检测代码会调整队列顺序以解决冲突,
但在ProcSleep中执行该检查成本相对会低一点,同时在这种情况下可以避免一次死锁检测超时延迟)
注意插入时在队列末尾的特殊情况:如果进程在插入点前的请求与现存锁或其他请求不存在冲突,
则放在队列的最前面同时无需等待马上授予锁.

When a lock is released, the lock release routine (ProcLockWakeup) scans
the lock object's wait queue.  Each waiter is awoken if (a) its request
does not conflict with already-granted locks, and (b) its request does
not conflict with the requests of prior un-wakable waiters.  Rule (b)
ensures that conflicting requests are granted in order of arrival. There
are cases where a later waiter must be allowed to go in front of
conflicting earlier waiters to avoid deadlock, but it is not
ProcLockWakeup's responsibility to recognize these cases; instead, the
deadlock detection code will re-order the wait queue when necessary.
锁释放时,ProcLockWakeup会扫描锁定对象的等待队列.唤醒满足(a)锁请求与现存锁不存在冲突
(b)请求与先前未唤醒的waiter不存在冲突 这两个条件的waiter.
规则(b)确保存在冲突的请求必须按到达的先后顺序授予.
避免在允许后来者可在出现冲突的waiter前可能出现的死锁,但这不是ProcLockWakeup的职责,
相反,死锁检测代码会在需要时重组等待队列.

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.  There are three possible
outcomes:
为了执行死锁检测,使用标准方法将各个进程视为有向图(WFG)中的节点.
图中,如果A进程等待B,那么会有存在一条从A指向B的边.当且仅当如出现循环时,则会出现死锁.
沿着等待的边进行检索看看是否会回到出发点来判断是否出现循环,这里有3种可能的情况:

1. All outgoing paths terminate at a running process (which has no
outgoing edge).
1. 所有出发的路径都终止于一个正在运行的进程(而没有从该进程出发的边).

2. A deadlock is detected by looping back to the start point.  We
resolve such a deadlock by canceling the start point's lock request and
reporting an error in that transaction, which normally leads to
transaction abort and release of that transaction's held locks.  Note
that it's sufficient to cancel one request to remove the cycle; we don't
need to kill all the transactions involved.
2. 通过判断是否回到开始点来进行死锁检测.
通过取消开始点的锁请求并在该事务反馈一个错误来解决死锁,该事务会取消并释放持有的锁.
注意:取消一个锁就可以消除循环了,而不需要杀掉所有相关的事务.

3. Some path(s) loop back to a node other than the start point.  This
indicates a deadlock, but one that does not involve our starting
process. We ignore this condition on the grounds that resolving such a
deadlock is the responsibility of the processes involved --- killing our
start-point process would not resolve the deadlock.  So, cases 1 and 3
both report "no deadlock".
3. 某些路径回到某些节点而不是开始点.这意味着死锁,但不涉及到开始进程.
基于由相关进程来解决死锁这一原则,PG会忽略此条件(杀掉开始点进程无助于解决死锁).
因此,第1种和第3种情况会反馈"no deadlock".

Postgres' situation is a little more complex than the standard discussion
of deadlock detection, for two reasons:
PG的情况比起标准的死锁检查有一点点的复杂,有2点原因:

1. A process can be waiting for more than one other process, since there
might be multiple PROCLOCKs of (non-conflicting) lock types that all
conflict with the waiter's request.  This creates no real difficulty
however; we simply need to be prepared to trace more than one outgoing
edge.
1. 进程可等待超过1个其他进程,因为存在多个与等待请求相冲突的锁类型相应的PROCLOCKs.
这不会造成实际的困难,仅需要跟踪多个出发的边即可.

2. If a process A is behind a process B in some lock's wait queue, and
their requested locks conflict, then we must say that A waits for B, since
ProcLockWakeup will never awaken A before B.  This creates additional
edges in the WFG.  We call these "soft" edges, as opposed to the "hard"
edges induced by locks already held.  Note that if B already holds any
locks conflicting with A's request, then their relationship is a hard edge
not a soft edge.
2. 如果进程A在等待队列中在B进程之后,而它们的请求锁冲突,这时候我们会认为A等待B,
因为ProcLockWakeup在B之前不会唤醒A.这会在WFG中产生额外的我们称之为soft(相对于实际已持有的锁而言)的边.
注意如果B已持有所有与A请求冲突的锁,那么它们的关系是硬边而不是软边.

A "soft" block, or wait-priority block, has the same potential for
inducing deadlock as a hard block.  However, we may be able to resolve
a soft block without aborting the transactions involved: we can instead
rearrange the order of the wait queue.  This rearrangement reverses the
direction of the soft edge between two processes with conflicting requests
whose queue order is reversed.  If we can find a rearrangement that
eliminates a cycle without creating new ones, then we can avoid an abort.
Checking for such possible rearrangements is the trickiest part of the
algorithm.
"soft"阻塞或者等待优先级阻塞,与硬阻塞的处理一样.
但是,我们可以不需要取消事务而解决软阻塞:重新排列等待队列的顺序即可.
重排会调转相关进程的优先顺序.如果能够重排而解决循环,那么可以避免取消事务.
检查是否存在这样的重排是算法中最棘手的部分.

The workhorse of the deadlock detector is a routine FindLockCycle() which
is given a starting point process (which must be a waiting process).
It recursively scans outward across waits-for edges as discussed above.
If it finds no cycle involving the start point, it returns "false".
(As discussed above, we can ignore cycles not involving the start point.)
When such a cycle is found, FindLockCycle() returns "true", and as it
unwinds it also builds a list of any "soft" edges involved in the cycle.
If the resulting list is empty then there is a hard deadlock and the
configuration cannot succeed.  However, if the list is not empty, then
reversing any one of the listed edges through wait-queue rearrangement
will eliminate that cycle.  Since such a reversal might create cycles
elsewhere, we may need to try every possibility.  Therefore, we need to
be able to invoke FindLockCycle() on hypothetical configurations (wait
orders) as well as the current real order.
死锁检测器主要有例程FindLockCycle实现,该例程输入为起始点过程(正在等待的进程).
如上所述,递归扫描指向到其他进程的边.如果从开始点没有发现循环,返回"false".
(正如上述所讨论的,忽略与开始点无关的循环).
如果发现了存在循环,FindLockCycle例程会返回"true",在展开(unwinds)时,
它还构建了一个包含涉及所有软边的链表.如果结果链表为空,那么只存在硬死锁,重排不会成功.
但是,如果链表非空,递归重排链表中的边检查是否可以消除循环.
由于这样的重排可能会在其他地方产生新的循环,因此需要尝试各种可能.
因此,我们需要具备在假设配置和实际顺序调用FindLockCycle的能力.

The easiest way to handle this seems to be to have a lookaside table that
shows the proposed new queue order for each wait queue that we are
considering rearranging.  This table is checked by FindLockCycle, and it
believes the proposed queue order rather than the real order for each lock
that has an entry in the lookaside table.
看起来最简单的方法是使用一个后备表,该表显示了我们正在考虑队列重排的每个建议的新顺序.
该表通过FindLockCycle检测,并且该例程相信建议的队列顺序而不是实际顺序.

We build a proposed new queue order by doing a "topological sort" of the
existing entries.  Each soft edge that we are currently considering
reversing creates a property of the partial order that the topological sort
has to enforce.  We must use a sort method that preserves the input
ordering as much as possible, so as not to gratuitously break arrival
order for processes not involved in a deadlock.  (This is not true of the
tsort method shown in Knuth, for example, but it's easily done by a simple
doubly-nested-loop method that emits the first legal candidate at each
step.  Fortunately, we don't need a highly efficient sort algorithm, since
the number of partial order constraints is not likely to be large.)  Note
that failure of the topological sort tells us we have conflicting ordering
constraints, and therefore that the last-added soft edge reversal
conflicts with a prior edge reversal.  We need to detect this case to
avoid an infinite loop in the case where no possible rearrangement will
work: otherwise, we might try a reversal, find that it still leads to
a cycle, then try to un-reverse the reversal while trying to get rid of
that cycle, etc etc.  Topological sort failure tells us the un-reversal
is not a legitimate move in this context.
对每一存在的条目使用"topological sort"创建可能的新队列顺序.
我们目前考虑反转的每个软边都创建了拓扑排序必须强制执行的偏序属性.
我们必须使用一种尽可能保留输入顺序的排序方法,这样就不会无缘无故破坏不涉及死锁进程的到达顺序.
注意拓扑排序如果失败则意味着存在冲突排序约束,因此最好添加的软边反转与先前的反转存在冲突.
需要检测这种情况以避免出现死循环.可以试着反转,如果发现它仍然会导致循环,
那么再反转,试图摆脱那个循环,等等.拓扑排序失败意味着在这种情况下反向操作是不合法的.

So, the basic step in our rearrangement method is to take a list of
soft edges in a cycle (as returned by FindLockCycle()) and successively
try the reversal of each one as a topological-sort constraint added to
whatever constraints we are already considering.  We recursively search
through all such sets of constraints to see if any one eliminates all
the deadlock cycles at once.  Although this might seem impossibly
inefficient, it shouldn't be a big problem in practice, because there
will normally be very few, and not very large, deadlock cycles --- if
any at all.  So the combinatorial inefficiency isn't going to hurt us.
Besides, it's better to spend some time to guarantee that we've checked
all possible escape routes than to abort a transaction when we didn't
really have to.
因此,重排方法的基础步骤是获取循环中的软边链表(FindLockCycle返回),依次尝试
将每个约束的反转作为拓扑排序约束添加到已经考虑的其他约束中.
递归检索所有这样的约束集合来看看是否存在可以消除循环的可能.
虽然这看来不太可能很有效,但在实践中也没有什么问题,因为死锁循环的数量通常很小.
因此这样的组合并不会有什么问题.话又说回来,最好花点时间来保证已检测所有可能的路径
而不是什么都不做就取消事务.

Each edge reversal constraint can be viewed as requesting that the waiting
process A be moved to before the blocking process B in the wait queue they
are both in.  This action will reverse the desired soft edge, as well as
any other soft edges between A and other processes it is advanced over.
No other edges will be affected (note this is actually a constraint on our
topological sort method to not re-order the queue more than necessary.)
Therefore, we can be sure we have not created any new deadlock cycles if
neither FindLockCycle(A) nor FindLockCycle(B) discovers any cycle.  Given
the above-defined behavior of FindLockCycle, each of these searches is
necessary as well as sufficient, since FindLockCycle starting at the
original start point will not complain about cycles that include A or B
but not the original start point.
每个边的反转约束都可以看做是请求等待进程A移到等待队列的阻塞进程B的前面.
这样的做法会反转有向软边,现对于在A和其他进程之间的其他软边,它是advanced over的.
没有其他边受影响,因此可以确保不会出现新的死锁循环.根据以上定义的FindLockCycle行为,
这些搜索都是必要的,也是充分的,因为从起始点开始的FindLockCycle不会认为包含A或B但不包含
初始起始点的循环有问题.

In short then, a proposed rearrangement of the wait queue(s) is determined
by one or more broken soft edges A->B, fully specified by the output of
topological sorts of each wait queue involved, and then tested by invoking
FindLockCycle() starting at the original start point as well as each of
the mentioned processes (A's and B's).  If none of the tests detect a
cycle, then we have a valid configuration and can implement it by
reordering the wait queues per the sort outputs (and then applying
ProcLockWakeup on each reordered queue, in case a waiter has become wakable).
If any test detects a soft cycle, we can try to resolve it by adding each
soft link in that cycle, in turn, to the proposed rearrangement list.
This is repeated recursively until we either find a workable rearrangement
or determine that none exists.  In the latter case, the outer level
resolves the deadlock by aborting the original start-point transaction.
简短的来说,等待队列的重排通过打破一个或多个A->B这样的软边来确定,
由所涉及的每个等待队列的拓扑排序的输出完全指定,然后通过调用FindLockCycle进行测试,
该函数从原始的起始点以及上面提到的每个进程(A&B)开始.
如果没有一个测试检测到循环,那么我们有了一个有效的配置,通过重排每个重新排序的队列来实现这一点.
如果测试发现了软循环,可以尝试通过将该循环中的每个软链接依次添加到建议的重排链表中来解决.
递归处理直至找到了可用的重排或者确定重排不存在.在后续的情况中,外层通过取消开始点事务来解决死锁.

The particular order in which rearrangements are tried depends on the
order FindLockCycle() happens to scan in, so if there are multiple
workable rearrangements of the wait queues, then it is unspecified which
one will be chosen.  What's more important is that we guarantee to try
every queue rearrangement that could lead to success.  (For example,
if we have A before B before C and the needed order constraints are
C before A and B before C, we would first discover that A before C
doesn't work and try the rearrangement C before A before B.  This would
eventually lead to the discovery of the additional constraint B before C.)
尝试重排的特定顺序取决于FindLockCycle碰巧扫描进来的顺序,因此如果存在多个等待队列上的重排,
那么选择哪一个就不确定.更重要的是我们确保尝试每个队列重排可能会成功.
(比如,如果A在B和C的前面,B在C的前面,排序约束是C在A之前和B在C之前,首先会发现A在C之前是不行的,
这时候会重排C在A和B之前.这会导致额外的约束B在C之前)

```

### 二、参考资料
[README](https://github.com/postgres/postgres/blob/master/src/backend/storage/lmgr/README)

ITPub博客

PostgreSQL 源码解读（224）- Locks(The Deadlock Detection Algorithm)

最新文章