PostgreSQL的全局死鎖檢測(cè)原理

5月26日，一年一度的PG開(kāi)發(fā)者大會(huì)PGCon2020如約而至。與往年不同的是，受疫情的影響，今年的PGCon采取了線上會(huì)議的方式，雖然沒(méi)有了面對(duì)面的交流，但在組織者Dan Langille等的精心安排下，會(huì)議有了更廣泛的受眾，干貨滿(mǎn)滿(mǎn)。來(lái)自Greenplum原廠的Greenplum內(nèi)核工程師 Hubert Zhang（張桓）與Asim Praveen合作發(fā)表了演講《Distributed Snapshot and Global Deadlock Detector》。在演講中Hubert通過(guò)理論結(jié)合實(shí)例的方式講解了Postgres單節(jié)點(diǎn)死鎖和Postgres Foreign Server Cluster中實(shí)現(xiàn)分布式死鎖檢測(cè)的技術(shù)路線。

現(xiàn)在讓我們通過(guò)本文來(lái)回顧一下精彩的演講內(nèi)容吧！

在大數(shù)據(jù)時(shí)代，隨著數(shù)據(jù)量的爆發(fā)式增長(zhǎng)，對(duì)于分布式數(shù)據(jù)庫(kù)的需求亦是水漲船高。作為最出色的開(kāi)源數(shù)據(jù)庫(kù)之一，Postgres也在大力探索和發(fā)展分布式解決方案。其中，Postgres Foreign Server Cluster是目前Postgres開(kāi)發(fā)者郵件列表Pghacker中非?；钴S的關(guān)于分布式Postgres的話(huà)題，該方案通過(guò)Foreign Data Wrapper和分區(qū)表的技術(shù)，支持將邏輯分區(qū)表，物理的存儲(chǔ)在多個(gè)不同的Postgres節(jié)點(diǎn)上。為了保證分布式環(huán)境中事務(wù)的ACID，Postgres社區(qū)正在積極開(kāi)發(fā)基于Foreign Server Cluster的分布式事務(wù)相關(guān)patch（https://commitfest.postgresql.。.。

但對(duì)于分布式系統(tǒng)來(lái)講，除了支持分布式事務(wù)，還需要考慮全局快照，全局死鎖檢測(cè)等問(wèn)題。Greenplum作為分布式Postgres的先驅(qū)者和成功代表，在Postgres分布式執(zhí)行的諸多領(lǐng)域都擁有成熟、穩(wěn)定的解決方案。因此，本次演講的作者Hubert借鑒Greenplum中全局死鎖檢測(cè)的原理和實(shí)現(xiàn)，探討了在Postgres Foreign Server Cluster中如何實(shí)現(xiàn)一個(gè)高效的分布式死鎖檢測(cè)系統(tǒng)。

單節(jié)點(diǎn)死鎖原理

首先，讓我們先來(lái)看一看單節(jié)點(diǎn)死鎖。下圖是一個(gè)單節(jié)點(diǎn)死鎖的示例。假設(shè)有兩個(gè)并發(fā)的Postgres會(huì)話(huà)，對(duì)應(yīng)兩個(gè)Postgres的后端進(jìn)程。最初，進(jìn)程1持有鎖A，進(jìn)程2持有鎖B。接著，進(jìn)程1要獲取鎖B，而進(jìn)程2要獲取鎖A。由于鎖通常在事務(wù)結(jié)束時(shí)才被釋放，因此，本地發(fā)生死鎖。

Postgresql 死鎖檢測(cè)器

Postgres使用死鎖檢測(cè)器來(lái)處理死鎖問(wèn)題。死鎖檢測(cè)器負(fù)責(zé)檢測(cè)死鎖并打破死鎖。檢測(cè)器使用等待圖（wait-for graph）來(lái)為不同后端進(jìn)程之間的等待關(guān)系建模。圖的節(jié)點(diǎn)由進(jìn)程標(biāo)識(shí)符pid標(biāo)識(shí)。節(jié)點(diǎn)A到節(jié)點(diǎn)B的邊表示節(jié)點(diǎn)A正在等待由節(jié)點(diǎn)B持有的鎖。

Postgresql死鎖檢測(cè)器的基本思想如下：

如果獲取鎖失敗，進(jìn)程將進(jìn)入睡眠模式。

SIGALARM信號(hào)用于在超時(shí)后喚醒進(jìn)程。

SIGALARM處理程序?qū)z查PROCLOCK共享內(nèi)存以構(gòu)建等待圖。以當(dāng)前進(jìn)程為起點(diǎn)，檢查是否存在環(huán)。環(huán)意味著發(fā)生死鎖。當(dāng)前進(jìn)程會(huì)主動(dòng)退出以打破死鎖。Postgres死鎖檢測(cè)器可以處理本地死鎖問(wèn)題。

分布式集群中的死鎖

那么分布式集群中的死鎖又是怎么樣的？集群和單節(jié)點(diǎn)有什么區(qū)別？

讓我們從一個(gè)例子開(kāi)始進(jìn)行講解。下圖中，我們有包含一個(gè)主節(jié)點(diǎn)和兩個(gè)從節(jié)點(diǎn)的集群。假設(shè)我們有兩個(gè)并發(fā)的分布式事務(wù)。首先，分布式事務(wù)1在節(jié)點(diǎn)A上運(yùn)行，然后事務(wù)2在節(jié)點(diǎn)B上運(yùn)行。接著，事務(wù)1要在由事務(wù)2阻塞的節(jié)點(diǎn)B上運(yùn)行，因此分布式事務(wù)1將被掛起。同時(shí)，假設(shè)事務(wù)2也嘗試在被本地事務(wù)1阻塞的節(jié)點(diǎn)A上運(yùn)行，則分布式事務(wù)2也將掛起。這種情況下就會(huì)發(fā)生死鎖。

請(qǐng)注意，節(jié)點(diǎn)A或節(jié)點(diǎn)B上都沒(méi)有死鎖，但是死鎖確實(shí)出現(xiàn)了。從主節(jié)點(diǎn)的角度來(lái)看，這就是所謂的全局死鎖。

現(xiàn)在，讓我們看一個(gè)更具體的 Postgres Foreign Server Cluster示例。在下圖中，我們有兩個(gè)外部服務(wù)器，它們充當(dāng)了在上一張圖中的從節(jié)點(diǎn)的角色。在主Postgres服務(wù)器上，我們創(chuàng)建一個(gè)分區(qū)表，在外部服務(wù)器A上部署一個(gè)分區(qū)，在外部服務(wù)器B上也部署一個(gè)分區(qū)。接著我們插入一些行，其中某些行在外部服務(wù)器A上，而其他行在外部服務(wù)器B上。

分布式系統(tǒng)中的全局死鎖檢測(cè)器

接著，我們?cè)趦蓚€(gè)并發(fā)會(huì)話(huà)上運(yùn)行以下更新查詢(xún)，我們可以看到兩個(gè)會(huì)話(huà)都由于死鎖而掛起。但是每個(gè)外部服務(wù)器上的本地Postgres死鎖檢測(cè)器卻無(wú)法檢測(cè)到它們。

那么我們應(yīng)該如何解決這種死鎖問(wèn)題呢？答案就是——在分布式系統(tǒng)中引入全局死鎖檢測(cè)器。

在本演講中，我們將提出一個(gè)關(guān)于如何在Postgres fdw集群中實(shí)現(xiàn)全局死鎖檢測(cè)器的想法。但是這個(gè)概念很普遍，可以作為對(duì)其他Postgres集群實(shí)現(xiàn)的參考。實(shí)際上，我們參考了Greenplum全局死鎖檢測(cè)器的實(shí)現(xiàn)。首先，將全局死鎖檢測(cè)器實(shí)現(xiàn)為Postgres的Background Worker，使其更兼容Postgres，高可用等需求都可以通過(guò)Postgres的Background Worker來(lái)實(shí)現(xiàn)。其次，我們提出使用集中式檢測(cè)算法，這意味著我們只需要在主節(jié)點(diǎn)上啟動(dòng)一個(gè)工作進(jìn)程來(lái)收集事務(wù)等待關(guān)系并定期檢測(cè)死鎖。請(qǐng)注意，在Postgres的本地死鎖檢測(cè)器中，Postgres后端進(jìn)程以自己為起點(diǎn)檢測(cè)死鎖。由于我們使用全局檢測(cè)器，因此必須執(zhí)行完整的等待圖搜索以檢測(cè)死鎖。這需要一種更好的算法來(lái)檢測(cè)死鎖，因?yàn)镻ostgres的基于每個(gè)頂點(diǎn)的查找環(huán)算法并不高效。

全局死鎖檢測(cè)器模塊

1. 等待圖

全局死鎖檢測(cè)器仍會(huì)使用等待圖（wait for graph）來(lái)為鎖等待關(guān)系進(jìn)行建模。但與Postgres本地死鎖檢測(cè)有所不同的是，首先，等待圖是基于整個(gè)集群，因此我們需要將每個(gè)外部服務(wù)器上的本地等待圖進(jìn)行合并，生成全局圖。此外，該等待圖中的節(jié)點(diǎn)并不再是單個(gè)Postgres進(jìn)程ID，而是一個(gè)進(jìn)程組，我們使用分布式事務(wù)ID來(lái)表示一個(gè)等待圖中節(jié)點(diǎn)。

等待圖中的節(jié)點(diǎn)具有四個(gè)主要屬性：

分布式事務(wù)ID。

出度邊列表

入度邊列表

鎖等待者或持有者的pid和sessionid信息。

從節(jié)點(diǎn)出發(fā)的是等待鎖的，指向節(jié)點(diǎn)的是持鎖者。

2. 等待圖邊

等待圖中的邊表示任何節(jié)點(diǎn)上的鎖等待關(guān)系。邊同樣具有四個(gè)主要屬性：

出度節(jié)點(diǎn)，持有鎖。

入度節(jié)點(diǎn)，等待鎖。

邊類(lèi)型：并非所有鎖在事務(wù)結(jié)束時(shí)都被釋放，例如，xidlock可以提前釋放，而無(wú)需等待分布式事務(wù)提交。我們將這種提前結(jié)束的等待關(guān)系使用虛邊表示。與之對(duì)應(yīng)的是實(shí)邊，事務(wù)結(jié)束使才釋放的鎖等待關(guān)系。稍后，我們將展示全局死鎖檢測(cè)算法中對(duì)這兩種邊的不同處理。

鎖等待關(guān)系中的鎖模式和鎖類(lèi)型。

全局死鎖檢測(cè)器工作原理

下面，通過(guò)全局等待圖，讓我們看看集群是如何處理全局死鎖的。

基本思路如下：主節(jié)點(diǎn)上的Background Worker進(jìn)程通過(guò)查詢(xún)集群來(lái)定期建立全局等待圖。接著，刪除與死鎖無(wú)關(guān)的節(jié)點(diǎn)和邊。重復(fù)此過(guò)程，直到無(wú)法刪除任何節(jié)點(diǎn)或邊。如果仍然存在邊，則也存在全局死鎖，我們需要選擇一個(gè)會(huì)話(huà)來(lái)取消。

接下來(lái)，讓我們?cè)敿?xì)介紹上述步驟。

要構(gòu)建等待圖，我們需要在每個(gè)Segment上收集鎖信息。這是一個(gè)兩階段過(guò)程。

1. 構(gòu)建全局圖

首先，它使用Postgres內(nèi)部函數(shù)GetLockStatusData從PROCLOCK共享內(nèi)存中獲取鎖等待關(guān)系。我們需要擴(kuò)展lockInstanceData結(jié)構(gòu)，以涵蓋分布式事務(wù)ID和holdTillEndXact標(biāo)志。之后，Background Worker進(jìn)程需要從每個(gè)Foreign Server收集本地鎖信息，并形成一個(gè)全局鎖等待圖。

每個(gè)本地鎖等待圖包括以下屬性：Segment ID，鎖等待者和鎖持有者的分布式事務(wù)ID，標(biāo)注其為實(shí)邊或虛邊，以及其他屬性，例如pid，sessionid，鎖類(lèi)型和鎖模式，涵蓋了之前介紹的節(jié)點(diǎn)和邊的四個(gè)主要屬性。

2. 消除節(jié)點(diǎn)和邊

下一步是消除不相關(guān)的節(jié)點(diǎn)和邊。我們使用啟發(fā)式貪婪算法。

有兩種策略。一種是對(duì)全局圖的貪婪，這意味著刪除所有出節(jié)點(diǎn)度為零的節(jié)點(diǎn)，并刪除其相應(yīng)邊。這是一個(gè)示例，在全局圖上，節(jié)點(diǎn)D沒(méi)有出度，因此將其刪除。然后，節(jié)點(diǎn)C的出站度也更改為零，因此也刪除了節(jié)點(diǎn)C。

另一種策略是在局部圖上貪婪，這意味著找到每個(gè)局部圖上的所有虛邊。如果虛邊指向節(jié)點(diǎn)的出度為零，則該虛線邊表示的阻塞關(guān)系可能在事務(wù)結(jié)束之前消失，因此我們也可以消除這種虛邊。

下圖的示例中，節(jié)點(diǎn)C在全局圖上的出度為1，但是在Server0的局部圖上，出度為0，因此我們可以將從節(jié)點(diǎn)A到C的虛邊刪除。

全局死鎖檢測(cè)器的最后一步是打破死鎖。集中式檢測(cè)器不同于Postgres本地死鎖檢測(cè)器，后者只能退出當(dāng)前進(jìn)程，前者可以根據(jù)策略選擇取消任何會(huì)話(huà)。通用策略包括取消最新的會(huì)話(huà)或基于CPU、內(nèi)存等資源占用量的策略等等。

實(shí)例分析

至此，我們已經(jīng)介紹了全局死鎖檢測(cè)器的概述和算法。最后，讓我們看看另外兩種實(shí)例，以便更好地了解全局死鎖檢測(cè)器的工作原理。

首先是數(shù)據(jù)準(zhǔn)備工作，如下圖所示。

案例一

第一種例子中，有三個(gè)并發(fā)會(huì)話(huà)。會(huì)話(huà)C首先更新ID=2的元組，這將使server1上持有xid鎖。會(huì)話(huà)A更新val=3的元組，它將在server2上持有xid鎖。接著，會(huì)話(huà)B要更新val=3或id=2的元組，它將分別被server1和server2上的會(huì)話(huà)A和會(huì)話(huà)C阻塞。最后，會(huì)話(huà)A要更新server1上val=2的元組。

請(qǐng)注意，當(dāng)會(huì)話(huà)B無(wú)法獲取server1上的xid鎖時(shí)，它將持有元組鎖，以確保在會(huì)話(huà)C釋放xid鎖之后可以拿到鎖。會(huì)話(huà)A將在元組鎖上被會(huì)話(huà)B阻塞。請(qǐng)注意，元組鎖在分布式事務(wù)結(jié)束之前就會(huì)被釋放，因此這是一個(gè)虛邊。原始的全局等待圖在左上角，可以看到全局等待圖存在循環(huán)。

現(xiàn)在，讓我們看看如何消除不相關(guān)的節(jié)點(diǎn)。首先，節(jié)點(diǎn)C的出度為零，我們可以刪除該節(jié)點(diǎn)和相應(yīng)的邊。現(xiàn)在在Server1的本地等待圖上，指向B點(diǎn)的虛邊沒(méi)有出度，因此也可以刪除該虛邊。刪除虛邊后，節(jié)點(diǎn)A的出度變?yōu)榱?，可以刪除，最后也可以刪除節(jié)點(diǎn)B。沒(méi)有邊，因此在這種情況下沒(méi)有全局死鎖。

案例二

下圖的第二個(gè)例子中，包括三個(gè)并發(fā)會(huì)話(huà)。會(huì)話(huà)C首先將更新ID=2的元組，這將在server1上持有xid鎖。然后，會(huì)話(huà)A將更新val=3的元組，它將在server2上持有xid鎖。會(huì)話(huà)B要更新val=2的元組，它將被server1上的會(huì)話(huà)C阻止。

接著，會(huì)話(huà)A想要更新server1上val=2的元組。像上圖的案例1一樣，會(huì)話(huà)A在元組鎖上被會(huì)話(huà)B阻塞，并形成虛邊。最后，會(huì)話(huà)C要更新ID=3的元組，它將被Server2上持有xid鎖的會(huì)話(huà)A阻止。原始全局等待圖在左上角，全局等待圖同樣包含循環(huán)。

回想上一張圖，案例1的全局等待圖與案例2相同，唯一的不同是局部圖。

現(xiàn)在讓我們看看如何消除不相關(guān)的節(jié)點(diǎn)。首先，讓我們檢查全局圖：沒(méi)有出節(jié)點(diǎn)度數(shù)為零的節(jié)點(diǎn)，因此沒(méi)有可以刪除的節(jié)點(diǎn)。接下來(lái)，我們檢查局部圖上的虛邊。從節(jié)點(diǎn)A到節(jié)點(diǎn)B，我們有一條虛邊，但是節(jié)點(diǎn)B的出度不為零，因此無(wú)法刪除該虛邊。我們無(wú)法刪除任何節(jié)點(diǎn)或邊，因此在這種情況下消除失敗，全局死鎖存在。

從以上情況可以得出結(jié)論，即使全局等待圖相同，它們的全局死鎖檢測(cè)結(jié)果也會(huì)有所不同。

總結(jié)

以上就是本次PGCon演講的主要內(nèi)容。回顧一下，本次演講首先討論P(yáng)ostgres本地死鎖檢測(cè)器的實(shí)現(xiàn)，并通過(guò)實(shí)例說(shuō)明本地死鎖檢測(cè)器無(wú)法解決全局死鎖問(wèn)題，并進(jìn)一步提出了在Postgres Foreign Server Cluster中實(shí)現(xiàn)全局死鎖檢測(cè)的思路和需要注意的問(wèn)題。