#71 資料庫引擎 - Deadlock 偵測 (Wait-For graph)

前兩篇文章談完了 table join，接著這篇文章把主題拉回到資料庫的 Transaction．

之前文章曾提過 deadlock 的發生，這在關聯式資料庫裡算是件平常可見的事情．之前曾提過當 deadlock 發生時，資料庫引擎可利用 wait-for graph 來偵測 deadlock 的發生．這篇文章將說明什麼是 wait-for graph．

Wait-for graph 是一個簡單的圖形，是一個有方向的圖形 (directed graph)，也就是它圖形上的邊具有方向性，這裡的方向性用來代表是那一個交易等待那一個交易．如下圖:



上圖的 S(A) 代表某個交易要對 A 物件取得 shared lock，R(A) 代表某交易要對 A 物件進行 read 動作，X(B) 代表某交易要對 B 物件取得 exclusive lock，W(B) 代表某交易要對 B 物件進行 write 動作．在進行 read 動作之前必須取得 shared lock，在進行 write 動作之前必須取得 exclusive lock．

從上圖可得知，T1 等待 T2，因為 T2 正在寫入 B 物件．所以在 wait-for graph 上就會有一個邊從 T1 指向 T2，用來代表 T1 等待 T2．再來， T2 等待 T3 因為 T2 想要寫入 C 物件，但 T3 先對 C 物件進行 read 動作．T3 等待 T1，因為 T3 想對 A 物件進行寫入動作，但在這之前 T1 對 A 物件進行讀取動作．因此就變成了 T1 等待 T2, T2 等待 T3, T3 等待 T1 的情況．這個情況將使得 wait-for graph 會形成一個 cyclic graph ，意思就是圖形裡點的某個點走到其他點上後有可能再走回到原來出發的點，這便形成了一個 cycle．



資料庫引擎在這個 wait-for graph 上來辦別是否有 cycle．如果有，這表示 deadlock 發生了．此時資料庫引擎便得採用設計好的規則來決定該如何解決 deadlock．解決的方法就是讓 wait-for graph 不會有 cycle 的現象．理論上，只要在 cycle 的路徑上把某一個 transaction 刪除即可．通常來說，資料庫引擎會刪除 "年輕" 的 transaction，"年輕" 是用 transaction 啟動時間來決定，因為基本上來說年輕的 transaction 已做過的動作可能比較少，所以刪除他們再重新啟動後比較省點讀取和寫入資料成本．

Wait-for graph 的應用其實蠻廣泛，在資料庫系統或一般的作業系統都會用到它來描述物件之間的關係．甚至在程式開發工具裡，元件之間參考的關係也可以用 wait-for graph 來呈現．當 A 元件參考 B 元件，B 元件參考 C 元件，C 元件再參考 A 元件，這情況將不允許發生，因為在 wait-for graph 裡將會有一個 cycle．

Hope it helps,