怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm

這篇文章主要講解了“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”吧！

一、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之前)

感謝各位的閱讀，以上就是“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”的內容了，經過本文的學習后，相信大家對怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！