PostgreSQL的全域性死鎖檢測原理

5月26日,一年一度的PG開發者大會PGCon2020如約而至。與往年不同的是,受疫情的影響,今年的PGCon採取了線上會議的方式,雖然沒有了面對面的交流,但在組織者Dan Langille等的精心安排下,會議有了更廣泛的受眾,乾貨滿滿。來自Greenplum原廠的Greenplum核心工程師 Hubert Zhang與Asim Praveen合作發表了演講《Distributed Snapshot and Global Deadlock Detector》。在演講中Hubert透過理論結合例項的方式講解了Postgres單節點死鎖和Postgres Foreign Server Cluster中實現分散式死鎖檢測的技術路線。

現在讓我們透過本文來回顧一下精彩的演講內容吧!

在大資料時代,隨著資料量的爆發式增長,對於分散式資料庫的需求亦是水漲船高。作為最出色的開源資料庫之一,Postgres也在大力探索和發展分散式解決方案。其中,Postgres Foreign Server Cluster是目前Postgres開發者郵件列表Pghacker中非常活躍的關於分散式Postgres的話題,該方案透過Foreign Data Wrapper和分割槽表的技術,支援將邏輯分割槽表,物理的儲存在多個不同的Postgres節點上。為了保證分散式環境中事務的ACID,Postgres社群正在積極開發基於Foreign Server Cluster的分散式事務相關patch(https://commitfest.postgresql...。

但對於分散式系統來講,除了支援分散式事務,還需要考慮全域性快照,全域性死鎖檢測等問題。Greenplum作為分散式Postgres的先驅者和成功代表,在Postgres分散式執行的諸多領域都擁有成熟、穩定的解決方案。因此,本次演講的作者Hubert借鑑Greenplum中全域性死鎖檢測的原理和實現,探討了在Postgres Foreign Server Cluster中如何實現一個高效的分散式死鎖檢測系統。

單節點死鎖原理

首先,讓我們先來看一看單節點死鎖。下圖是一個單節點死鎖的示例。假設有兩個併發的Postgres會話,對應兩個Postgres的後端程序。最初,程序1持有鎖A,程序2持有鎖B。接著,程序1要獲取鎖B,而程序2要獲取鎖A。由於鎖通常在事務結束時才被釋放,因此,本地發生死鎖。

Postgresql 死鎖檢測器

Postgres使用死鎖檢測器來處理死鎖問題。死鎖檢測器負責檢測死鎖並打破死鎖。檢測器使用等待圖來為不同後端程序之間的等待關係建模。圖的節點由程序識別符號pid標識。節點A到節點B的邊表示節點A正在等待由節點B持有的鎖。

Postgresql死鎖檢測器的基本思想如下:

如果獲取鎖失敗,程序將進入睡眠模式。

SIGALARM訊號用於在超時後喚醒程序。

SIGALARM處理程式將檢查PROCLOCK共享記憶體以構建等待圖。以當前程序為起點,檢查是否存在環。環意味著發生死鎖。當前程序會主動退出以打破死鎖。Postgres死鎖檢測器可以處理本地死鎖問題。

分散式叢集中的死鎖

那麼分散式叢集中的死鎖又是怎麼樣的?叢集和單節點有什麼區別?

讓我們從一個例子開始進行講解。下圖中,我們有包含一個主節點和兩個從節點的叢集。假設我們有兩個併發的分散式事務。首先,分散式事務1在節點A上執行,然後事務2在節點B上執行。接著,事務1要在由事務2阻塞的節點B上執行,因此分散式事務1將被掛起。同時,假設事務2也嘗試在被本地事務1阻塞的節點A上執行,則分散式事務2也將掛起。這種情況下就會發生死鎖。

請注意,節點A或節點B上都沒有死鎖,但是死鎖確實出現了。從主節點的角度來看,這就是所謂的全域性死鎖。

現在,讓我們看一個更具體的 Postgres Foreign Server Cluster示例。在下圖中,我們有兩個外部伺服器,它們充當了在上一張圖中的從節點的角色。在主Postgres伺服器上,我們建立一個分割槽表,在外部伺服器A上部署一個分割槽,在外部伺服器B上也部署一個分割槽。接著我們插入一些行,其中某些行在外部伺服器A上,而其他行在外部伺服器B上。

分散式系統中的全域性死鎖檢測器

接著,我們在兩個併發會話上執行以下更新查詢,我們可以看到兩個會話都由於死鎖而掛起。但是每個外部伺服器上的本地Postgres死鎖檢測器卻無法檢測到它們。

那麼我們應該如何解決這種死鎖問題呢?答案就是——在分散式系統中引入全域性死鎖檢測器。

在本演講中,我們將提出一個關於如何在Postgres fdw叢集中實現全域性死鎖檢測器的想法。但是這個概念很普遍,可以作為對其他Postgres叢集實現的參考。實際上,我們參考了Greenplum全域性死鎖檢測器的實現。首先,將全域性死鎖檢測器實現為Postgres的Background Worker,使其更相容Postgres,高可用等需求都可以透過Postgres的Background Worker來實現。其次,我們提出使用集中式檢測演算法,這意味著我們只需要在主節點上啟動一個工作程序來收集事務等待關係並定期檢測死鎖。請注意,在Postgres的本地死鎖檢測器中,Postgres後端程序以自己為起點檢測死鎖。由於我們使用全域性檢測器,因此必須執行完整的等待圖搜尋以檢測死鎖。這需要一種更好的演算法來檢測死鎖,因為Postgres的基於每個頂點的查詢環演算法並不高效。

全域性死鎖檢測器模組

1. 等待圖

全域性死鎖檢測器仍會使用等待圖來為鎖等待關係進行建模。但與Postgres本地死鎖檢測有所不同的是,首先,等待圖是基於整個叢集,因此我們需要將每個外部伺服器上的本地等待圖進行合併,生成全域性圖。此外,該等待圖中的節點並不再是單個Postgres程序ID,而是一個程序組,我們使用分散式事務ID來表示一個等待圖中節點。

等待圖中的節點具有四個主要屬性:

分散式事務ID。

出度邊列表

入度邊列表

鎖等待者或持有者的pid和sessionid資訊。

從節點出發的是等待鎖的,指向節點的是持鎖者。

2. 等待圖邊

等待圖中的邊表示任何節點上的鎖等待關係。邊同樣具有四個主要屬性:

出度節點,持有鎖。

入度節點,等待鎖。

邊型別:並非所有鎖在事務結束時都被釋放,例如,xidlock可以提前釋放,而無需等待分散式事務提交。我們將這種提前結束的等待關係使用虛邊表示。與之對應的是實邊,事務結束使才釋放的鎖等待關係。稍後,我們將展示全域性死鎖檢測演算法中對這兩種邊的不同處理。

鎖等待關係中的鎖模式和鎖型別。

全域性死鎖檢測器工作原理

下面,透過全域性等待圖,讓我們看看叢集是如何處理全域性死鎖的。

基本思路如下:主節點上的Background Worker程序透過查詢叢集來定期建立全域性等待圖。接著,刪除與死鎖無關的節點和邊。重複此過程,直到無法刪除任何節點或邊。如果仍然存在邊,則也存在全域性死鎖,我們需要選擇一個會話來取消。

接下來,讓我們詳細介紹上述步驟。

要構建等待圖,我們需要在每個Segment上收集鎖資訊。這是一個兩階段過程。

1. 構建全域性圖

首先,它使用Postgres內部函式GetLockStatusData從PROCLOCK共享記憶體中獲取鎖等待關係。我們需要擴充套件lockInstanceData結構,以涵蓋分散式事務ID和holdTillEndXact標誌。之後,Background Worker程序需要從每個Foreign Server收集本地鎖資訊,並形成一個全域性鎖等待圖。

每個本地鎖等待圖包括以下屬性:Segment ID,鎖等待者和鎖持有者的分散式事務ID,標註其為實邊或虛邊,以及其他屬性,例如pid,sessionid,鎖型別和鎖模式,涵蓋了之前介紹的節點和邊的四個主要屬性。

2. 消除節點和邊

下一步是消除不相關的節點和邊。我們使用啟發式貪婪演算法。

有兩種策略。一種是對全域性圖的貪婪,這意味著刪除所有出節點度為零的節點,並刪除其相應邊。這是一個示例,在全域性圖上,節點D沒有出度,因此將其刪除。然後,節點C的出站度也更改為零,因此也刪除了節點C。

另一種策略是在區域性圖上貪婪,這意味著找到每個區域性圖上的所有虛邊。如果虛邊指向節點的出度為零,則該虛線邊表示的阻塞關係可能在事務結束之前消失,因此我們也可以消除這種虛邊。

下圖的示例中,節點C在全域性圖上的出度為1,但是在Server0的區域性圖上,出度為0,因此我們可以將從節點A到C的虛邊刪除。

全域性死鎖檢測器的最後一步是打破死鎖。集中式檢測器不同於Postgres本地死鎖檢測器,後者只能退出當前程序,前者可以根據策略選擇取消任何會話。通用策略包括取消最新的會話或基於CPU、記憶體等資源佔用量的策略等等。

例項分析

至此,我們已經介紹了全域性死鎖檢測器的概述和演算法。最後,讓我們看看另外兩種例項,以便更好地瞭解全域性死鎖檢測器的工作原理。

首先是資料準備工作,如下圖所示。

案例一

第一種例子中,有三個併發會話。會話C首先更新ID=2的元組,這將使server1上持有xid鎖。會話A更新val=3的元組,它將在server2上持有xid鎖。接著,會話B要更新val=3或id=2的元組,它將分別被server1和server2上的會話A和會話C阻塞。最後,會話A要更新server1上val=2的元組。

請注意,當會話B無法獲取server1上的xid鎖時,它將持有元組鎖,以確保在會話C釋放xid鎖之後可以拿到鎖。會話A將在元組鎖上被會話B阻塞。請注意,元組鎖在分散式事務結束之前就會被釋放,因此這是一個虛邊。原始的全域性等待圖在左上角,可以看到全域性等待圖存在迴圈。

現在,讓我們看看如何消除不相關的節點。首先,節點C的出度為零,我們可以刪除該節點和相應的邊。現在在Server1的本地等待圖上,指向B點的虛邊沒有出度,因此也可以刪除該虛邊。刪除虛邊後,節點A的出度變為零,可以刪除,最後也可以刪除節點B。沒有邊,因此在這種情況下沒有全域性死鎖。

案例二

下圖的第二個例子中,包括三個併發會話。會話C首先將更新ID=2的元組,這將在server1上持有xid鎖。然後,會話A將更新val=3的元組,它將在server2上持有xid鎖。會話B要更新val=2的元組,它將被server1上的會話C阻止。

接著,會話A想要更新server1上val=2的元組。像上圖的案例1一樣,會話A在元組鎖上被會話B阻塞,並形成虛邊。最後,會話C要更新ID=3的元組,它將被Server2上持有xid鎖的會話A阻止。原始全域性等待圖在左上角,全域性等待圖同樣包含迴圈。

回想上一張圖,案例1的全域性等待圖與案例2相同,唯一的不同是區域性圖。

從以上情況可以得出結論,即使全域性等待圖相同,它們的全域性死鎖檢測結果也會有所不同。

總結

以上就是本次PGCon演講的主要內容。回顧一下,本次演講首先討論Postgres本地死鎖檢測器的實現,並透過例項說明本地死鎖檢測器無法解決全域性死鎖問題,並進一步提出了在Postgres Foreign Server Cluster中實現全域性死鎖檢測的思路和需要注意的問題。

轉自:

新鮮出爐的PGCon2020演講回顧 ①--全域性死鎖檢測器

版權宣告:本文源自 網路, 於,由 楠木軒 整理釋出,共 4574 字。

轉載請註明: PostgreSQL的全域性死鎖檢測原理 - 楠木軒