PolarDB-X 如何檢測和分析分散式死鎖
背景
一般而言，在資料庫中，死鎖指的是事務間因互相持有了對方需要的鎖而導致事務無法繼續進行下去的現象。在 PolarDB-X 中，死鎖可以分成三種類型：單機死鎖（即單 DN 上的死鎖），分散式死鎖，以及分散式 MDL 死鎖（即分散式元資料鎖的死鎖）。本文將主要介紹 PolarDB-X 如何檢測分散式死鎖，以及當死鎖出現後，使用者可以怎樣分析死鎖。
分散式事務和分支事務
首先，我們簡要介紹一下 PolarDB-X 的事務系統。在 PolarDB-X 中，一張邏輯表可能被劃分到不同的物理分片上。PolarDB-X 的儲存節點（DN）是基於 MySQL 開發的 XDB，因此，每個物理分片可以簡單理解為 MySQL 中的一個物理庫。在執行分散式事務時，PolarDB-X 會在每個物理分片上開啟一個分支事務。分支事務則可以簡單理解為 MySQL 中的事務。對於 DN 上的死鎖，MySQL 已經具備了檢測的能力，基本原理是構造鎖等待的有向圖，然後檢測其中是否存在環，在檢測出環後自動回滾某個事務，以打破環而解決死鎖。
但是，對於分散式死鎖，由於觸發死鎖的分支事務位於不同的分片上，MySQL 無法檢測出這種型別的死鎖。以下圖為例，分散式事務 A 的分支事務 A1 正在等待分散式事務 B 的分支事務 B1 所持有的鎖；而 B 的分支事務 B2 正在等待 A 的分支事務 A2 所持有的鎖。這是一個典型的死鎖場景，事務 A 和 B 在互相等待對方持有的鎖。但對於 MySQL 來說，這裡只存在兩個鎖等待關係（A1->B1， B2->A2），並不形成鎖等待的環。更常見的是，A1 和 B1 所在的分片 1，與 A2 和 B2 所在的分片 2，位於不同的 DN 上，因此在每個 DN 上只能看到一個鎖等待關係。
PolarDB-X 如何檢測分散式死鎖
在出現死鎖時，如果沒有人工干預，參與死鎖的事務將永遠無法繼續進行下去，直至鎖超時等錯誤發生。因此，死鎖檢測是一個分散式資料庫必須具備的能力。對於 CockroachDB，其每個節點都會維護一個記憶體中的 lock table，用於記錄鎖的分配情況，其中也會維護鎖的等待關係資訊。同時，該鎖等待關係會定時地推送到每個 Range 的raft leader 節點，由該 leader 節點維護並更新事務的等待關係資訊，並檢測其中是否存在相互等待的環，檢測出環就意味著存在死鎖。對於 TiDB，其在特定 region leader 所在的 TiKV 例項上維護了一個全域性的鎖等待關係圖。在事務需要加鎖但被阻塞時，會在圖中增加一條邊，如果新增邊後會形成環，就意味著會產生死鎖。
對於 PolarDB-X，其死鎖檢測的實現原理與 CockroachDB 的做法類似。首先，鎖的分配情況分佈在每個 DN 上，而分散式事務的執行狀態則儲存在 CN 上。因此，CN 的 leader 節點會定時地從每個 DN 收集鎖等待關係，並從每個 CN 收集事務的資訊。最後根據這些資訊構造出事務的等待關係圖，並檢測圖中是否存在環，在檢測出環後 kill 掉環中的某個事務，以此來解決死鎖問題。
在具體實現上，在單個 DN 上的 information_schema 中提供了 innodb_trx 和 innodb_locks 等檢視，用於檢視實時的鎖資訊和（分支）事務資訊，透過 PolarDB-X 的 CN 節點可以方便地從中收集每個 DN 上鎖的資訊並構建出事務等待關係圖。
使用“鎖分析”功能
在出現死鎖後，PolarDB-X 會 kill 掉某個事務，來解除死鎖，此時客戶端會收到相應的死鎖報錯。除了報錯資訊，我們還有什麼途徑能獲取更多死鎖相關的資訊呢？
為了方便使用者分析死鎖的場景，PolarDB-X 控制檯增加了“鎖分析”的功能，具體入口可以在控制檯左側導航欄處找到。如下圖所示，我們可以點選“發起診斷”來分析在 PolarDB-X 中最近發生的一次單機死鎖/分散式死鎖/分散式 MDL 死鎖，可以點選“檢視詳情”看到死鎖的分析結果。
分散式死鎖
以分散式死鎖為例，點開詳情頁後，如下圖所示，顯示死鎖型別為 GLOBAL。注意，圖中的事務 SQL 是觸發死鎖時的邏輯 SQL，即使用者真正輸入的 SQL；而分支事務 SQL 則是在物理分片上實際執行的物理 SQL。值得一提的是，這裡事務的編號體現了事務間的等待關係，即事務 i 正在等待事務 i+1 所持有的鎖；最後一個事務正在等待第一個事務持有的鎖。
根據詳情頁資訊，檢視等待鎖和事務 SQL 的資訊，發現事務 1 的分支事務 1 正在等待物理分片 db1_000000 上物理表 tb0_giuu 的 id=0 的行鎖，而這個鎖正在被事務 2 的分支事務 1 所持有；同時，事務 2 的分支事務 2 正在等待物理分片 db1_000001 上物理表 tb0_giuu 的 id=1 的行鎖，而這個鎖正在被事務 1 的分支事務 2 所持有。因此，從總體上看，事務 1 和 事務 2 構成了迴圈的鎖等待，從而導致了死鎖，最終回滾了事務 1 來解決這個死鎖。
對於單機死鎖，詳情頁呈現的內容和分散式死鎖類似，這裡不再舉例贅述。
分散式 MDL 死鎖
對於分散式 MDL 死鎖，除了事務，還會涉及 DDL 語句。如下圖所示，點開詳情頁後顯示死鎖型別為 MDL，圖中事務和 DDL 的編號體現了事務/DDL 間對於 MDL 的等待關係。
由於 MDL 死鎖涉及資訊更繁雜，我們可以根據圖中的資訊，來還原出當初的死鎖場景，更直觀地分析死鎖原因：
DDL 語句想要獲取 EXCLUSIVE （X） 鎖時，需要等待該表上所有 SHARED_WRITE （SW） 鎖被釋放，同時，會阻塞後續所有 SW 鎖的獲取。透過上圖中可以看到，在每個分片上（灰色和橙色分別表示分片 0 和分片 1），都沒有形成鎖等待的環。但總體上看，形成了“事務 1 -> DDL 2 -> 事務 3 -> DDL 4 -> 事務 1”這樣迴圈的鎖等待，從而導致了 MDL 死鎖。結合詳情頁資訊可知，最終回滾了事務 1 來解決這個死鎖。
關於 MDL 之間的阻塞關係，由於內容比較長，不便在此處給出，感興趣的可以進一步參考文末的附錄。
SHOW
［LOCAL | GLOBAL］ DEADLOCKS
其實，上述鎖分析的功能，是對 PolarDB-X 的 SHOW ［LOCAL | GLOBAL］ DEADLOCKS 指令的解析。當出現死鎖時，我們也可以直接使用該指令看到最近的一次死鎖日誌。此外，我們也把該死鎖日誌保留在了“鎖分析”的結果中，點選死鎖詳情頁的“檢視死鎖日誌”就能看到了。因此，我們可以使用控制檯的“鎖分析”來看到死鎖的主要資訊，也可以進一步檢視完整的死鎖日誌來獲取更多的額外死鎖資訊。
總結
死鎖會使得資源利用率降低，事務併發效能受損。更嚴重的是，MDL 死鎖得不到解決，被鎖的表上的事務甚至會被阻塞一年。在本文中，我們介紹了 PolarDB-X 如何檢測和分析死鎖。在檢測出死鎖後，PolarDB-X 會 kill 掉參與死鎖的某個事務，從而解決死鎖。這之後，使用者可以使用“鎖分析”功能自主分析死鎖形成原因，以便在業務上排查和避免死鎖。
References
PolarDB-X 分散式MDL死鎖檢測 cockroachDB 的事務系統與死鎖檢測 TiDB 的悲觀鎖實現原理與死鎖檢測 MySQL 8。0。26 原始碼
附錄
可能出現在“鎖分析”詳情頁的 MDL 鎖型別有以下幾種：
INTENTION_EXCLUSIVE （IX） ：一種範圍意向鎖，獲取某個物件的 EXCLUSIVE （X） 鎖前，都會獲取某個 IX 鎖。例如，要想獲取某個表的 X 鎖，會首先獲取這個表所在庫的 IX 鎖，再嘗試獲取這個表的 X 鎖。
SHARED （S）：當我們只對讀取某個物件的元資料感興趣，而不會讀寫這個物件本身的資料時，我們會獲取這個物件的 S 鎖。例如，在給某個使用者授權某個表時，會獲取一下這個表的 S 鎖，以確定這個表是存在的。
SHARED_HIGH_PRIO （SH）：S 鎖的加強版，當要獲取這種鎖時，可以無視等待佇列直接獲取。絕大部分的 SHOW 指令都會獲取要 SHOW 的物件的 SH 鎖。例如，當某個 ALTER TABLE 正在執行時，SHOW TABLES 是不會被阻塞的。
SHARED_READ （SR）： 在 S 鎖的基礎上，不僅允許讀寫物件的元資料，還允許去讀這個物件的資料。例如，普通的 SELECT 語句會獲取表的 S 鎖。
SHARED_WRITE （SW）： 在 SR 鎖的基礎上，還允許去修改這個物件的資料。例如，幾乎所有的 DML 語句都會獲取表的 SW 鎖；SELECT 。。。 FOR UPDATE 也會獲取表的 SW 鎖。
MDL_SHARED_WRITE_LOW_PRIO （SWLP）： 低優先順序的 SW 鎖。一些低優先順序的 DML 語句會獲取這個鎖，例如 UPDATE LOW_PRIORITY 語句。
SHARED_UPGRADABLE （SU）： 當獲取了某個物件的 SU 鎖時，仍然允許其他執行緒對這個物件進行讀寫；持有 SU 的執行緒則只可以讀該物件的元資料和其本身的資料，不可以修改。例如，幾乎所有的 ALTER TABLE 都會首先獲取 TABLE 的 SU 鎖。SU 鎖會升級為 SHARED_NO_WRITE （SNW），SHARED_NO_READ_WRITE （SNRW），或是 X 鎖，當升級為 XNRW 和 X 鎖時，就可以修改這個物件的元資料和資料了。
SHARED_READ_ONLY （SRO）： 當獲取了某個物件的 SRO 鎖時，仍然允許其他執行緒對這個物件進行讀，但不允許寫；持有 SRO 的執行緒則只可以讀該物件的元資料和其本身的資料。使用 LOCK TABLES READ 時會獲取 SRO 鎖。
SHARED_NO_WRITE （SNW）： 當獲取了某個物件的 SNW 鎖時，仍然允許其他執行緒對這個物件進行讀，但不允許寫；持有 SNW 的執行緒則只可以讀該物件的元資料和其本身的資料，不可以修改。例如，ALTER TABLE 涉及從一個表複製資料到另一個表時，當獲取了這些表的 SNW 時，就可以開始 SELECT 這些表，但還不可以 UPDATE。SNW 鎖可以升級為 X 鎖。
SHARED_NO_READ_WRITE （SNRW）： 當獲取了某個物件的 SNRW 鎖時，只允許其他執行緒讀這個物件的元資料，不允許寫，也不允許讀寫物件的資料；持有 SNRW 的執行緒則可以讀該物件的元資料，以及修改物件本身的資料。例如，使用 LOCK TABLES WRITE 時會獲取表的 SNRW 鎖。SNRW 鎖可以升級為 X 鎖。
EXCLUSIVE （X）： 互斥鎖，一旦獲取某個物件的 X 鎖，不允許其他執行緒讀寫該物件的元資料和資料。同時，獲取 X 鎖的執行緒可以修改物件的元資料和資料。例如，CREATE/DROP/RENAME TABLE 時會獲取表的 X 鎖。一些 DDL 的特定階段也會獲取 X 鎖。
最後，結合下面的鎖的等待-阻塞關係表，我們就能透過 MDL 鎖型別來推斷出具體死鎖的根本原因了。
首先是範圍鎖，下表表示對於某個範圍，已經持有了某種 MDL 時，獲取另一種 MDL 會不會被阻塞，每一行表示請求的鎖型別，每一列表示已持有的鎖型別。其中，“-” 表示會被阻塞。可以看到，當想獲取 X 鎖時，需要等待所有鎖被釋放；在獲取之後，其他語句就不能獲取任何鎖。
IX
S
X
IX
+
-
-
S
-
+
-
X
-
-
-
而下表則表示，當 MDL 的等待佇列中已存在某種 MDL 時，獲取另一種 MDL 會不會被阻塞，每一行表示請求的鎖型別，每一列表示佇列中正在等待的鎖型別。其中，“-” 表示會被阻塞。可以看到，當佇列中已有 X 鎖在等待時，獲取其他非 X 鎖型別的鎖都會被阻塞，即會被排在 X 鎖的後面。
IX
S
X
IX
+
-
-
S
+
+
-
X
+
+
+
從圖中也能看出，這三種範圍鎖的優先順序順序為：X > S > IX。
其次是物件上的 MDL 鎖等待-阻塞關係表，下表表示對於某個物件，已經持有了某種 MDL 時，獲取另一種 MDL 會不會被阻塞。
S
SH
SR
SW
SWLP
SU
SRO
SNW
SNRW
X
S
+
+
+
+
+
+
+
+
+
-
SH
+
+
+
+
+
+
+
+
+
-
SR
+
+
+
+
+
+
+
+
-
-
SW
+
+
+
+
+
+
-
-
-
-
SWLP
+
+
+
+
+
+
-
-
-
-
SU
+
+
+
+
+
-
+
-
-
-
SRO
+
+
+
-
-
+
+
+
-
-
SNW
+
+
+
-
-
-
+
-
-
-
SNRW
+
+
-
-
-
-
-
-
-
-
X
-
-
-
-
-
-
-
-
-
-
而下表表示對於某個物件，其 MDL 等待佇列已存在某種 MDL 時，獲取另一種 MDL 會不會被阻塞。
S
SH
SR
SW
SWLP
SU
SRO
SNW
SNRW
X
S
+
+
+
+
+
+
+
+
+
-
SH
+
+
+
+
+
+
+
+
+
+
SR
+
+
+
+
+
+
+
+
-
-
SW
+
+
+
+
+
+
+
-
-
-
SWLP
+
+
+
+
+
+
-
-
-
-
SU
+
+
+
+
+
+
+
+
+
-
SRO
+
+
+
-
+
+
+
+
-
-
SNW
+
+
+
+
+
+
+
+
+
-
SNRW
+
+
+
+
+
+
+
+
+
-
X
-
-
-
-
-
-
-
-
-
-
舉個例子：當某物件上已經上了 X 鎖，則此時獲取任何鎖都會阻塞，都需要等待這個已經被授予的 X 鎖。當某物件的 MDL 等待佇列中已經有一個 X 鎖，則此時獲取任何除了 SH 鎖和 X 鎖的請求都會被阻塞，且該阻塞的請求需要等待這個 X 鎖（換句話說，被阻塞的請求都排在這個 X 鎖的後面，直到這個 X 鎖被授予且被釋放，才可能獲取對應的鎖）。
