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

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

一、The Deadlock Detection Algorithm

The Deadlock Detection Algorithm
--------------------------------
死鎖檢測(cè)算法
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允許事務(wù)以亂序的方式申請(qǐng)鎖,因此會(huì)出現(xiàn)死鎖的可能.PG使用的檢測(cè)算法相當(dāng)標(biāo)準(zhǔn),
但為了適配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.
一個(gè)設(shè)計(jì)上考慮的關(guān)鍵點(diǎn)是在沒有死鎖的情況下可以讓鎖授予和釋放可以執(zhí)行得更快.
通過使用一種"樂觀等待"機(jī)制來實(shí)現(xiàn):如果進(jìn)程不能馬上獲取請(qǐng)求的鎖,則馬上休眠而不執(zhí)行任何死鎖檢測(cè).
但同時(shí)設(shè)置了延遲時(shí)鐘,延遲時(shí)長為DeadlockTimeout毫秒(典型值是1s).
如果在進(jìn)程被授予鎖前延遲過期,則執(zhí)行死鎖檢測(cè)和中斷代碼.通常來說,這些代碼會(huì)確定
是否存在死鎖條件,然后進(jìn)程會(huì)重新休眠并等待直至可以獲取鎖.
但如果死鎖條件確實(shí)存在,那需解決此問題,通過來說會(huì)回滾執(zhí)行檢測(cè)的事務(wù).
通過這種方法,避免鎖等待時(shí)間小于DeadlockTimeout時(shí)的死鎖處理開銷,
而在出現(xiàn)錯(cuò)誤時(shí)則不執(zhí)行不合理的延遲檢測(cè).
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.對(duì)于如無沖突或者進(jìn)程已持有相同類型的鎖的鎖請(qǐng)求(如獲取兩次讀鎖),則馬上授予鎖.
注意進(jìn)程永遠(yuǎn)不會(huì)與自己沖突,比如已獲取獨(dú)占鎖的情況下可以獲取讀鎖.
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.否則,進(jìn)程會(huì)加入到鎖等待隊(duì)列.通常來說,會(huì)加入到隊(duì)列的末尾,但存在例外情況:
如果進(jìn)程已在對(duì)象上持有鎖但與其他等待者的請(qǐng)求存在沖突,進(jìn)程會(huì)插入到隊(duì)列中這些waiter的前面.
(如果不執(zhí)行該檢查,死鎖檢測(cè)代碼會(huì)調(diào)整隊(duì)列順序以解決沖突,
但在ProcSleep中執(zhí)行該檢查成本相對(duì)會(huì)低一點(diǎn),同時(shí)在這種情況下可以避免一次死鎖檢測(cè)超時(shí)延遲)
注意插入時(shí)在隊(duì)列末尾的特殊情況:如果進(jìn)程在插入點(diǎn)前的請(qǐng)求與現(xiàn)存鎖或其他請(qǐng)求不存在沖突,
則放在隊(duì)列的最前面同時(shí)無需等待馬上授予鎖.
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.
鎖釋放時(shí),ProcLockWakeup會(huì)掃描鎖定對(duì)象的等待隊(duì)列.喚醒滿足(a)鎖請(qǐng)求與現(xiàn)存鎖不存在沖突
(b)請(qǐng)求與先前未喚醒的waiter不存在沖突 這兩個(gè)條件的waiter.
規(guī)則(b)確保存在沖突的請(qǐng)求必須按到達(dá)的先后順序授予.
避免在允許后來者可在出現(xiàn)沖突的waiter前可能出現(xiàn)的死鎖,但這不是ProcLockWakeup的職責(zé),
相反,死鎖檢測(cè)代碼會(huì)在需要時(shí)重組等待隊(duì)列.
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:
為了執(zhí)行死鎖檢測(cè),使用標(biāo)準(zhǔn)方法將各個(gè)進(jìn)程視為有向圖(WFG)中的節(jié)點(diǎn).
圖中,如果A進(jìn)程等待B,那么會(huì)有存在一條從A指向B的邊.當(dāng)且僅當(dāng)如出現(xiàn)循環(huán)時(shí),則會(huì)出現(xiàn)死鎖.
沿著等待的邊進(jìn)行檢索看看是否會(huì)回到出發(fā)點(diǎn)來判斷是否出現(xiàn)循環(huán),這里有3種可能的情況:
1. All outgoing paths terminate at a running process (which has no
outgoing edge).
1. 所有出發(fā)的路徑都終止于一個(gè)正在運(yùn)行的進(jìn)程(而沒有從該進(jìn)程出發(fā)的邊).
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. 通過判斷是否回到開始點(diǎn)來進(jìn)行死鎖檢測(cè).
通過取消開始點(diǎn)的鎖請(qǐng)求并在該事務(wù)反饋一個(gè)錯(cuò)誤來解決死鎖,該事務(wù)會(huì)取消并釋放持有的鎖.
注意:取消一個(gè)鎖就可以消除循環(huán)了,而不需要?dú)⒌羲邢嚓P(guān)的事務(wù).
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. 某些路徑回到某些節(jié)點(diǎn)而不是開始點(diǎn).這意味著死鎖,但不涉及到開始進(jìn)程.
基于由相關(guān)進(jìn)程來解決死鎖這一原則,PG會(huì)忽略此條件(殺掉開始點(diǎn)進(jìn)程無助于解決死鎖).
因此,第1種和第3種情況會(huì)反饋"no deadlock".
Postgres' situation is a little more complex than the standard discussion
of deadlock detection, for two reasons:
PG的情況比起標(biāo)準(zhǔn)的死鎖檢查有一點(diǎn)點(diǎn)的復(fù)雜,有2點(diǎn)原因:
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. 進(jìn)程可等待超過1個(gè)其他進(jìn)程,因?yàn)榇嬖诙鄠€(gè)與等待請(qǐng)求相沖突的鎖類型相應(yīng)的PROCLOCKs.
這不會(huì)造成實(shí)際的困難,僅需要跟蹤多個(gè)出發(fā)的邊即可.
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. 如果進(jìn)程A在等待隊(duì)列中在B進(jìn)程之后,而它們的請(qǐng)求鎖沖突,這時(shí)候我們會(huì)認(rèn)為A等待B,
因?yàn)镻rocLockWakeup在B之前不會(huì)喚醒A.這會(huì)在WFG中產(chǎn)生額外的我們稱之為soft(相對(duì)于實(shí)際已持有的鎖而言)的邊.
注意如果B已持有所有與A請(qǐng)求沖突的鎖,那么它們的關(guān)系是硬邊而不是軟邊.
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"阻塞或者等待優(yōu)先級(jí)阻塞,與硬阻塞的處理一樣.
但是,我們可以不需要取消事務(wù)而解決軟阻塞:重新排列等待隊(duì)列的順序即可.
重排會(huì)調(diào)轉(zhuǎn)相關(guān)進(jìn)程的優(yōu)先順序.如果能夠重排而解決循環(huán),那么可以避免取消事務(wù).
檢查是否存在這樣的重排是算法中最棘手的部分.
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.
死鎖檢測(cè)器主要有例程FindLockCycle實(shí)現(xiàn),該例程輸入為起始點(diǎn)過程(正在等待的進(jìn)程).
如上所述,遞歸掃描指向到其他進(jìn)程的邊.如果從開始點(diǎn)沒有發(fā)現(xiàn)循環(huán),返回"false".
(正如上述所討論的,忽略與開始點(diǎn)無關(guān)的循環(huán)).
如果發(fā)現(xiàn)了存在循環(huán),FindLockCycle例程會(huì)返回"true",在展開(unwinds)時(shí),
它還構(gòu)建了一個(gè)包含涉及所有軟邊的鏈表.如果結(jié)果鏈表為空,那么只存在硬死鎖,重排不會(huì)成功.
但是,如果鏈表非空,遞歸重排鏈表中的邊檢查是否可以消除循環(huán).
由于這樣的重排可能會(huì)在其他地方產(chǎn)生新的循環(huán),因此需要嘗試各種可能.
因此,我們需要具備在假設(shè)配置和實(shí)際順序調(diào)用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.
看起來最簡單的方法是使用一個(gè)后備表,該表顯示了我們正在考慮隊(duì)列重排的每個(gè)建議的新順序.
該表通過FindLockCycle檢測(cè),并且該例程相信建議的隊(duì)列順序而不是實(shí)際順序.
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.
對(duì)每一存在的條目使用"topological sort"創(chuàng)建可能的新隊(duì)列順序.
我們目前考慮反轉(zhuǎn)的每個(gè)軟邊都創(chuàng)建了拓?fù)渑判虮仨殢?qiáng)制執(zhí)行的偏序?qū)傩?
我們必須使用一種盡可能保留輸入順序的排序方法,這樣就不會(huì)無緣無故破壞不涉及死鎖進(jìn)程的到達(dá)順序.
注意拓?fù)渑判蛉绻t意味著存在沖突排序約束,因此最好添加的軟邊反轉(zhuǎn)與先前的反轉(zhuǎn)存在沖突.
需要檢測(cè)這種情況以避免出現(xiàn)死循環(huán).可以試著反轉(zhuǎn),如果發(fā)現(xiàn)它仍然會(huì)導(dǎo)致循環(huán),
那么再反轉(zhuǎn),試圖擺脫那個(gè)循環(huán),等等.拓?fù)渑判蚴∫馕吨谶@種情況下反向操作是不合法的.
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.
因此,重排方法的基礎(chǔ)步驟是獲取循環(huán)中的軟邊鏈表(FindLockCycle返回),依次嘗試
將每個(gè)約束的反轉(zhuǎn)作為拓?fù)渑判蚣s束添加到已經(jīng)考慮的其他約束中.
遞歸檢索所有這樣的約束集合來看看是否存在可以消除循環(huán)的可能.
雖然這看來不太可能很有效,但在實(shí)踐中也沒有什么問題,因?yàn)樗梨i循環(huán)的數(shù)量通常很小.
因此這樣的組合并不會(huì)有什么問題.話又說回來,最好花點(diǎn)時(shí)間來保證已檢測(cè)所有可能的路徑
而不是什么都不做就取消事務(wù).
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.
每個(gè)邊的反轉(zhuǎn)約束都可以看做是請(qǐng)求等待進(jìn)程A移到等待隊(duì)列的阻塞進(jìn)程B的前面.
這樣的做法會(huì)反轉(zhuǎn)有向軟邊,現(xiàn)對(duì)于在A和其他進(jìn)程之間的其他軟邊,它是advanced over的.
沒有其他邊受影響,因此可以確保不會(huì)出現(xiàn)新的死鎖循環(huán).根據(jù)以上定義的FindLockCycle行為,
這些搜索都是必要的,也是充分的,因?yàn)閺钠鹗键c(diǎn)開始的FindLockCycle不會(huì)認(rèn)為包含A或B但不包含
初始起始點(diǎn)的循環(huán)有問題.
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.
簡短的來說,等待隊(duì)列的重排通過打破一個(gè)或多個(gè)A->B這樣的軟邊來確定,
由所涉及的每個(gè)等待隊(duì)列的拓?fù)渑判虻妮敵鐾耆付?然后通過調(diào)用FindLockCycle進(jìn)行測(cè)試,
該函數(shù)從原始的起始點(diǎn)以及上面提到的每個(gè)進(jìn)程(A&B)開始.
如果沒有一個(gè)測(cè)試檢測(cè)到循環(huán),那么我們有了一個(gè)有效的配置,通過重排每個(gè)重新排序的隊(duì)列來實(shí)現(xiàn)這一點(diǎn).
如果測(cè)試發(fā)現(xiàn)了軟循環(huán),可以嘗試通過將該循環(huán)中的每個(gè)軟鏈接依次添加到建議的重排鏈表中來解決.
遞歸處理直至找到了可用的重排或者確定重排不存在.在后續(xù)的情況中,外層通過取消開始點(diǎn)事務(wù)來解決死鎖.
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碰巧掃描進(jìn)來的順序,因此如果存在多個(gè)等待隊(duì)列上的重排,
那么選擇哪一個(gè)就不確定.更重要的是我們確保嘗試每個(gè)隊(duì)列重排可能會(huì)成功.
(比如,如果A在B和C的前面,B在C的前面,排序約束是C在A之前和B在C之前,首先會(huì)發(fā)現(xiàn)A在C之前是不行的,
這時(shí)候會(huì)重排C在A和B之前.這會(huì)導(dǎo)致額外的約束B在C之前)

感謝各位的閱讀，以上就是“怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)怎么理解PostgreSQL Locks中的The Deadlock Detection Algorithm這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！