一、三類并發問題及四種事務隔離級別

首先介紹三類并發問題：

1.臟讀：一個事務讀到另一個事務未提交的更新數據（A和B事務并發執行，B事務執行更新后，A事務查詢B事務沒有提交的數據，B事務回滾，則A事務得到的數據不是數據庫中的真實數據。也就是臟數據，即和數據庫中不一致的數據）。 2.不可重復讀：一個事務讀到另一個事務已提交的更新數據（A和B事務并發執行，A事務查詢數據，然后B事務更新該數據，A再次查詢該數據時，發現該數據變化了）。 3.虛讀（幻讀）：一個事務讀到另一個事務已提交的新插入的數據（A和B事務并發執行，A事務查詢數據，B事務插入或者刪除數據，A事務再次查詢發現結果集中有以前沒有的數據或者以前有的數據消失了）。

相應的有四種事務隔離級別供用戶選用：

二、兩階段封鎖協議（2PL）及解決死鎖的方法

下面介紹兩階段封鎖協議（2PL）。2PL可以使事務的隔離級別達到可串行化。2PL要求每個事務分兩個階段提出加鎖和解鎖申請：

1.增長階段：事務可以獲得鎖，但是不能釋放鎖 2.縮減階段：事務可以釋放鎖，但是不能獲得鎖

一開始，事務處于增長階段，事務根據需要獲得鎖。一旦該事務釋放鎖，就進入縮減階段，不能再發出加鎖請求。我們可以證明2PL協議保證沖突可串行化。對于任何事務，在調度中該事務獲得其最后的加鎖位置（增長階段結束點）稱為事務的封鎖點。這樣，多個事務可以根據它們的封鎖點進行排序，實際上，這個順序就是事務的一個可串行化順序。但是，2PL不保證不發生死鎖，例如：

*其中lock-X表示排它鎖，lock-S表示共享鎖此時，事務T₃等待T₄釋放A上的共享鎖，T₄等待T₃釋放B上的排他鎖,發生死鎖。死鎖的解決方法有兩種，一種是預防，一種是檢測與恢復。這里采用第二種方法，鎖的等待關系可以用有向圖來表示，如T₃->T₄表示T₃等待T₄釋放鎖。轉化為圖后，如果有向圖中有環，則有死鎖。這里使用NyaDB的死鎖檢測與恢復方法：

1.設置一個時間戳stamp = 0; 2.為每個點設置一個”訪問戳”, visStamp, 初始化為-1; 3.任意選擇一個visStamp為-1的點, 設它為s; 4.stamp++; 5.從s開始遍歷, 對每個遍歷到的點u進行下面的判斷: 6.===> 如果visStamp[u] == -1, 則visStamp[u] = stamp, 繼續遍歷; 7.===> 如果visStamp[u] != -1 and visStamp[u] < stamp, 跳過點u, 即不以它為節點繼續向下遍歷; 8.===> 如果visStamp[u] == stamp, 則有環, 結束算法; 9.當從s開始遍歷完且并沒發行環, 重復3), 直到沒有visStamp為-1的點. 10.當整個算法結束時, 都沒發現環, 則無環.

將等待圖維護在內存中, 每當出現等待時, 則向圖中加入一條邊。 每向圖中加入一條邊, 便進行一次死鎖檢測。 如果加入某條邊后檢測到了死鎖, 則撤銷加入這條邊的事務。

三、新的問題—級聯回滾

考慮如下圖的事務調度：

如果在事務T₇的read(A)步驟之后事務T₅發生故障需要回滾，此時雖然T₆和T₇并沒有發生故障，但是因為這兩個事務中有一部分命令是在事務T₅開始到故障點之間執行的，所以也需要回滾，這就導致了級聯回滾。級聯回滾需要撤銷大量的工作，這是數據庫系統不希望見到的。可以通過將2PL協議變為嚴格2PL協議來避免級聯回滾。嚴格2PL協議不僅要求封鎖是兩階段的，還要求事務持有的所有排他鎖必須在事務提交之后才能釋放。這個要求保證了未提交事務所寫的任何數據在該事務提交之前均以排他鎖方式加鎖，防止了其他事務讀取這些數據。應用嚴格2PL協議的級聯回滾事務調度變成了下圖的樣子,防止了級聯回滾的出現：

參考文獻：

1.NyaDB的技術文檔：https://qw4990.gitbooks.io/nyadb/content/chapter4.html2.數據庫系統概念（原書第5版） 第16章 并發控制