主記憶體資料庫系統設計/併發
目錄 —
第 8 章：併發管理
併發是指多個程序和執行緒能夠同時訪問和更改資料記錄的能力。隨著更多使用者的參與，對訪問和修改資料的爭用降低，併發性越好，反之亦然。訪問資料的程序會阻止其他程序更改資料。這會降低併發性。修改資料的程序會阻止其他程序訪問或更改資料。這會降低併發性。
一般來說，資料庫系統使用兩種方法來管理併發資料訪問：悲觀和樂觀。這兩種模型都無法避免衝突，區別僅在於處理衝突的時間。
悲觀併發系統假設會發生衝突，並透過獲取正在讀取或修改的資料的鎖來避免衝突，這樣其他程序就無法修改該資料。在這個模型中，讀取器會阻塞寫入器，寫入器也會阻塞讀取器。
樂觀併發系統假設事務不太可能修改另一個事務正在修改的資料。這是透過使用版本控制技術實現的。這允許讀取器在修改發生之前看到資料的狀態，因為系統在實際嘗試更改資料記錄之前會維護資料記錄的先前版本。在這個模型中，讀取器不會阻塞寫入器，寫入器也不會阻塞讀取器。但是，寫入器會阻塞寫入，這會導致衝突。
任何併發控制機制都必須解決一些問題。有三種方式會導致錯誤。分別是丟失更新問題、未提交依賴和不一致分析。在這三種情況下，單個事務都是正確的，但當它們交錯時可能會產生錯誤的結果。
TODO- 定義這個
TODO- 繪製圖表
事務-1 在時間 t1 讀取元組 1 事務-2 在時間 t2 讀取元組 1 事務-1 在時間 t3 更新元組 1 事務-2 在時間 t4 更新元組 1
事務-1 在時間 t3 對元組 1 的更新丟失了，因為事務-2 在沒有檢查元組 1 是否已更改的情況下，覆蓋了事務-1 對元組 1 的更新。
當一個事務被允許訪問或更新另一個事務已更新但尚未提交的元組時，就會發生這種情況。
TODO- 繪製圖表
事務-1 在時間 t1 更新元組 1 事務-2 在時間 t2 讀取元組 1 事務-1 在時間 t3 回滾事務 在上面的序列中，事務-2 在時間 t2 看到一個未提交的更改，該更改在時間 t3 被撤銷。事務-2 使用在時間 t2 看到的值進行操作。結果，事務-2 可能會產生不正確的結果。
如果事務-2 在 t2 更新元組 t1 而不是讀取它，情況會更糟，它將失去對元組 t1 的更新，一旦事務-1 回滾。
如果一個事務正在計算對記錄的聚合彙總函式，而其他事務正在更新彙總中涉及的某些記錄，那麼聚合函式可能會使用更新之前的某些值和更新之後的某些值進行計算。
TODO- 繪製圖表
例如，假設事務-1 正在計算特定日期所有影院的預訂總數；與此同時，事務-2 正在預訂當天 5 個座位，那麼事務-1 的結果將減少 5 個，因為事務-1 在從 X 中減去 5 個座位之後讀取 X 的值。
以上所有三個問題都可以透過使用稱為鎖定的併發控制技術來解決。基本思想是在事務正在處理資料記錄時，拒絕所有事務訪問該資料記錄。
鎖是一個與資料項關聯的變數，它描述了資料項的狀態。通常，在 DBMS 中每個資料項（記錄）都有一個鎖。鎖用於透過併發事務同步訪問資料項。Unix 類作業系統支援兩種型別的鎖
- pthread 互斥體
- 訊號量
pthread 互斥鎖在多執行緒環境中執行良好，訊號量在多執行緒和多程序環境中也執行良好。pthread 互斥鎖被稱為二元鎖，因為它們只有兩種狀態（lockState）：鎖定和解鎖。訊號量可以用於二元鎖以及計數鎖。在我們的案例中，二元鎖將用於提供對資料項的同步併發訪問。使用二元鎖定有兩個操作：lockItem() 和 unlockItem()。一個事務透過首先發出 lockItem(X) 操作來請求訪問資料項 X。如果 lockState(X) 為 1，則事務將被迫等待，直到 lockState(X) 變為 0。如果它為零，則 lockState(X) 設定為 1，並且允許事務訪問資料項 X。當事務完成使用資料項時，它將發出 unlockItem(X) 操作，該操作將 lockState(X) 設定為零，以便其他事務可以訪問 X。
鎖定方法的資料訪問協議是
- 讀取事務將在讀取資料之前獲取對資料的鎖定。
- 寫入事務將在寫入資料之前獲取對資料的鎖定。
- 如果鎖定請求被拒絕，則事務進入等待狀態，並定期嘗試獲取鎖定，直到獲取鎖定的事務釋放鎖定。
在上述鎖定模型中，
- 讀取器阻塞讀取器和寫入器
- 寫入器阻塞讀取器和寫入器
透過使讀取器不阻塞其他讀取器來稍微提高上述模型的併發性，因為這不會導致任何不一致。這可以透過引入另一種型別的鎖來實現，這種鎖將由所有讀取器共享。這些鎖被稱為共享鎖。另一種型別的鎖，排他鎖，由寫入器獲取，以阻止所有讀取器和寫入器訪問資料。此鎖定方法的資料訪問協議是
- 讀取事務將在讀取資料之前獲取對資料的共享鎖。
- 寫入事務將在寫入資料之前獲取對資料的排他鎖。
- 如果另一個事務對資料項擁有排他鎖，則讀取操作的鎖定請求將被拒絕。
- 如果另一個事務對資料項擁有讀取鎖或排他鎖，則寫入操作的鎖定請求將被拒絕。
- 如果鎖定請求被拒絕，則事務進入等待狀態，並定期嘗試獲取鎖定，直到獲取鎖定的事務釋放鎖定。
在上述鎖定模型中，
- 讀取器阻塞寫入器並允許其他讀取器
- 寫入器阻塞讀取器和寫入器
上述規則應概括為鎖定相容性矩陣
共享 排他 無鎖 共享 是 否 是 排他 否 否 是 否 鎖 是 是 是 TODO::上述鎖定相容性矩陣以影像形式顯示
是 -> 相容，無衝突，鎖定請求將被授予。
否 -> 不相容，存在衝突，因此應拒絕鎖定請求。
鎖定協議的併發問題
- 丟失更新問題– 事務 1 從時間 t3 開始無限期地等待排他鎖，因為共享鎖由事務 1 和事務 2 獲取。事務 2 從時間 t4 開始無限期地等待排他鎖，因為共享鎖由事務 1 和事務 2 獲取。我們的丟失更新問題已解決，但出現了一個新問題。它被稱為“死鎖”。我們將在後面詳細介紹它。
- 未提交依賴- 事務 2 在時間 t2 嘗試讀取元組 1 時等待鎖定，因為它被事務 1 獨佔鎖定。它將等待，直到事務 1 提交或回滾。鎖定避免了未提交依賴問題。
- 不一致分析– 事務 1 等待，直到事務 2 釋放對資料記錄 X 的排他鎖，然後計算聚合，從而給出正確的結果。
8.3.1 可序列化事務
[edit | edit source]如果一組給定的事務產生與這些事務按順序逐個執行時相同的結果，則該組事務被認為是可序列化的。
- 單個事務是正確的，因為它們將資料庫的正確狀態轉換為另一個正確狀態
- 按任何順序一次執行一個事務也是正確的，因為單個事務彼此獨立。
- 如果交織執行等效於序列執行或可序列化，則它是正確的。
可序列化概念首先由 Eswaran 提出，Gray 證明了二階段鎖定協議，該協議簡要描述如下
If all transactions obey the “two-phase locking protocol”, then all possible interleaved schedules are serializable.
8.3.2 二階段鎖定協議
[edit | edit source]在釋放鎖定後，事務永遠不能繼續獲取更多鎖定。遵守此協議的事務因此有兩個階段，一個鎖定獲取或“增長”階段和一個鎖定釋放或“收縮”階段。
二階段鎖定可能會限制排程中可能發生的併發量。這是因為事務可能無法在完成資料項後釋放對該資料項的鎖定。這是為了保證所有排程的可序列化而不必檢查排程本身而付出的代價。
二階段鎖定 (2PL) 有許多變體。我們上面描述的技術被稱為 2 階段鎖定。
8.3.2.1 保守型 2PL
[edit | edit source]這要求事務在事務開始之前鎖定它訪問的所有專案，方法是宣告讀取集和寫入集。事務的讀取集是事務讀取的所有專案的集合，寫入集是它寫入的所有專案的集合。
如果讀取集或寫入集中的任何專案無法鎖定，它將等待其他事務釋放它，並在一次獲取所有鎖定後，它將啟動事務。保守型 2 階段鎖定是一種無死鎖協議。但是，由於需要宣告讀取集和寫入集，因此在實踐中很難使用，這在大多數情況下實際上是不可能的。
在保守型 2 階段鎖定的情況下，增長階段在事務開始之前，收縮階段在事務結束時開始。
8.3.2.2 嚴格型 2PL
[edit | edit source]2 階段鎖定的最流行變體是嚴格型 2 階段鎖定。事務在事務提交或回滾之前不會釋放任何排他鎖。這保證了嚴格的排程，因為在事務提交之前，沒有其他事務可以讀取或寫入該事務寫入的專案。增長階段在事務開始時開始，寫入鎖的收縮階段在事務提交或回滾時發生。
8.3.2.3 嚴格型 2PL
[edit | edit source]這是嚴格型 2 階段鎖定協議的更嚴格版本。事務在事務提交或回滾之前不會釋放任何共享鎖和排他鎖。這是最容易實現的 2 階段鎖定，但會降低讀取的併發性。
增長階段在事務開始時開始，收縮階段在事務提交或回滾時發生。
8.3.3 鎖定飢餓
[edit | edit source]當事務在無限期的時間內無法繼續進行，而系統中的其他事務繼續正常執行時，就會發生鎖定飢餓。這可能是由於不公平的鎖定排程演算法導致的，該演算法實現了基於優先順序的鎖定。解決飢餓問題的一個方法是採用公平的鎖定等待方案，例如先進先出 (FIFO) 佇列。
當死鎖演算法反覆選擇相同的事務進行中止時，也會發生飢餓，從而永遠不會允許它完成。應修改演算法以對已中止多次的事務使用更高優先順序，以避免此問題。
8.3.4 死鎖
[edit | edit source]當一組兩個或多個事務中的每個事務都等待由該組中的另一個事務鎖定的某個資源時，就會發生死鎖。
例如，事務 T1 獲取資源 R1，事務 T2 獲取資源 R2。在此之後，如果 T1 等待 R2，而 T2 等待 R1。兩者都永遠不會獲得鎖定，這種情況被稱為死鎖。
TODO 關於時間的圖表
8.3.4.1 死鎖預防
[edit | edit source]有許多預防協議，但大多數協議在 DBMS 的情況下實際上不可行。它們是保守型 2 階段鎖定、資料記錄鎖定排序、無等待、謹慎等待、等待-死亡和傷亡-等待。
保守型二階段鎖定協議是一種死鎖預防協議，其中所有鎖定都在事務對資料記錄進行操作之前獲取。
資料記錄鎖定排序也將防止死鎖。在多個數據記錄上進行操作的事務應始終按預定的順序獲取鎖定。這需要程式設計師或 DBMS 瞭解所選資料記錄鎖定的順序。這在資料庫系統中也不切實際。
無等待演算法如果事務無法獲得鎖，它將立即中止，並在經過一定時間延遲後重新啟動，而不會檢查是否實際發生了死鎖。這會導致事務不必要地中止和重啟。謹慎等待演算法
為了避免在沒有等待演算法的情況下不必要的重啟，如果事務 T1 試圖鎖定資料記錄 R1，但由於 R1 被另一個事務 T2 以衝突鎖鎖定而無法做到。如果 T2 沒有被其他鎖定資料記錄阻塞，那麼 T1 將被阻塞並允許等待；否則中止 T1。
等待-死亡和傷亡-等待演算法其他兩種技術，等待-死亡和傷亡-等待，使用事務時間戳作為基礎來確定在發生死鎖的情況下該做什麼。事務時間戳是分配給每個事務的唯一識別符號。這些時間戳通常是執行計數器，在每個開始的事務都會遞增。如果事務 T1 在事務 T2 之前開始，那麼 TS(T1) < TS(T2)
假設事務 T1 試圖鎖定資料記錄 R1，但由於 R1 被另一個事務 T2 以衝突鎖鎖定而無法鎖定。這些方案遵循的規則如下
等待-死亡 - 如果 TS (T1) < TS (T2)，則允許 T1 等待，否則中止 T1 並稍後以相同的時間戳重新啟動它。傷亡-等待 - 如果 TS (T1) < TS (T2)，則中止 T1 並稍後以相同的時間戳重新啟動它；否則允許 T1 等待
在等待-死亡中，允許較舊的事務等待較年輕的事務，而較年輕的事務請求鎖定被較舊的事務持有的記錄 R1 將被中止並重新啟動。傷亡-等待方法則相反；允許較年輕的事務等待較舊的事務，而較舊的事務請求鎖定被較年輕的事務持有的記錄 R1 會透過中止較年輕的事務來搶佔它。兩種方案最終都會中止可能參與死鎖的兩個事務中較年輕的那個。在等待-死亡中，事務只等待較年輕的事務。在傷亡-等待中，事務只等待較舊的事務。因此在這兩種方案中都不會產生迴圈，避免死鎖。
死鎖檢測比死鎖預防技術更實用。這首先檢查系統中是否實際存在死鎖狀態，然後再採取任何措施。
檢測死鎖狀態的一種簡單方法是讓系統構建和維護一個“等待-for”圖TODO-圖和說明
如果系統處於死鎖狀態，則必須中止導致死鎖的一些事務。應用程式或 DBMS 應該選擇參與死鎖的事務之一進行回滾以使系統擺脫死鎖情況。此選擇演算法應考慮避免執行時間過長的事務和執行過多次更新的事務。最適合中止的事務是 SELECT 或只讀事務。
處理死鎖的最簡單解決方案是超時。在這種方法中，等待時間超過系統定義的超時時間的事務被認為處於死鎖狀態，並被中止。
TODO
資料項的大小通常稱為資料項粒度。細粒度是指資料項大小小，而粗粒度是指資料項大小大。
資料項大小越大，併發度越低。例如，如果資料項大小是表示為 Table1 的“表”，則需要鎖定記錄 X 的事務 T1 必須鎖定包含記錄 X 的整個表 Table1，因為鎖與整個資料項 Table1 相關聯。如果另一個事務 T2 想要鎖定 Table1 的另一個記錄 Y，它將被迫等待 T1 釋放對 Table1 的鎖定。如果資料項大小是單個記錄，那麼事務 T2 就可以繼續執行，因為它會鎖定不同的資料項。
資料項大小越小，資料庫中專案數量越多。因為每個專案都與一個鎖相關聯，所以系統將擁有更多活動鎖。將執行更多鎖和解鎖操作，導致更高的開銷。此外，儲存這些鎖需要更多儲存空間。
對於訪問許多記錄的大型事務，應該使用粗粒度；對於訪問少量記錄的小型事務，應該使用細粒度。
粒度級別按從粗到細的順序列出如下
- 資料庫
- 表
- 磁碟塊或記憶體頁
- 記錄
- 記錄欄位
由於最佳粒度大小取決於給定的事務，因此 DBMS 應該支援多個級別，以便事務能夠選擇任何它想要的級別。
讓我們以一個包含一個表 Table1 的示例資料庫 DB1 為例，Table1 包含 2 個頁面 P1 和 P2。P1 有 10 個記錄 R1 到 R10，P2 有 10 個記錄 R11 到 R20。
TODO::繪製樹結構表示上述內容。
場景 1
事務 T1 想要更新 Table1 中的所有記錄。它將請求對 Table1 進行排他鎖定。這對 T1 來說比為每個資料記錄獲取 20 個鎖更有益。現在假設，另一個事務 T2 想要從頁面 P1 讀取記錄 R5，那麼 T2 將請求對 R5 進行共享記錄級鎖定。現在 DBMS 將檢查所請求的鎖與已持有的鎖的相容性。驗證此問題的一種方法是遍歷從葉子節點 R5 到根節點 DB1 的樹，並檢查衝突鎖。
場景 2
事務 T1 想要從頁面 P1 讀取記錄 R5，然後 T2 將請求對 R5 進行共享記錄級鎖定。現在假設，另一個事務 T2 想要更新 Table1 中的所有記錄，因此它將請求對 Table1 進行排他鎖定。現在 DBMS 將檢查所請求的鎖與已持有的鎖的相容性。為此，它需要檢查頁面級和記錄級的所有鎖，以確保沒有衝突鎖。
對於上述兩種場景，基於遍歷的鎖衝突檢測效率非常低，會破壞擁有多個粒度鎖定的目的。
引入了新型鎖以提高多個粒度鎖定的效率。意圖鎖背後的理念是讓事務沿從根節點到所需節點的路徑指示它將在其中一個節點的後代節點上需要哪種型別的鎖。
有三種類型的意圖鎖。
- 意圖共享 (IS)
- 意圖排他 (IX)
- 共享意圖排他 (SIX)
意圖-共享鎖
指示將對某個後代節點請求共享鎖
意圖-排他鎖
指示將對某個後代節點請求排他鎖
意圖-共享鎖
指示該節點處於共享模式鎖定，並且將對某個後代節點請求排他鎖
相容性表
模式 IS IX S SIX X IS 是 是 是 是 否 IX 是 是 否 否 否 S 是 否 是 否 否 SIX 是 否 否 否 否 X 否 否 否 否 否
TODO::上述鎖相容性表的圖表
鎖定協議
- 必須首先鎖定樹的根節點
- 只有當父節點已經被事務以 IS 或 IX 模式鎖定時，事務才能以 S 或 IS 模式鎖定節點
- 只有當節點的父節點已經被事務以 IX 或 SIX 模式鎖定時，事務才能以 X、IX 或 SIX 模式鎖定節點
- 只有當節點的任何子節點都沒有被事務當前鎖定時，事務才能解鎖節點。
- 應遵守鎖相容性和兩階段鎖定。
TODO::說明上述協議和相容性表的示例：參考 Elmasri 的 445
解決幻像記錄問題的一種解決方案是使用索引鎖定。
一種更通用的技術，稱為謂詞鎖定，將鎖定對滿足謂詞或條件的所有記錄的訪問。事實證明，謂詞鎖很難有效地實現。
還有另一種基於時間戳排序的併發控制技術，它避免了鎖的使用。由於它避免了鎖，因此在這種併發控制機制中不會發生死鎖。
時間戳是由DBMS建立的唯一識別符號，用於識別事務。通常，時間戳值是按照事務提交到系統的順序分配的。通常它是事務開始時間，稱為TS（T）。這些唯一的識別符號應該使用簡單的計數器來實現，當事務開始時計數器會遞增。由於它有有限的最大值，演算法應該注意在達到最大值時將其重置。
每個資料項X都有兩個時間戳
- ReadTS(X) – 資料項X的讀取時間戳；這是所有成功讀取資料項X的事務的時間戳中的最大值。
- WriteTS(X) – 資料項X的寫入時間戳；這是所有成功修改資料項X的事務的時間戳中的最大值。
當某個事務T嘗試發出readItem(X)或writeItem(X)時，演算法應該將T的時間戳與ReadTS(X)和WriteTS(X)進行比較，以確保事務執行的時間戳順序沒有被違反。如果該順序被違反，則事務T將被中止，並作為新事務重新提交到系統，並分配一個新的時間戳。如果T被中止，則任何可能使用T寫入的值的事務T1也必須中止。同樣，任何可能使用T1寫入的值的事務T2也必須中止，依此類推。這種效應被稱為級聯回滾，是與這種方案相關聯的最大問題之一。
基本時間戳排序演算法總結如下
事務T發出writeItem(X)操作如果readTS(X) > TS(T)或writeTS(T) > TS(T)，則中止T，否則執行T的writeItem(X)並將writeTS(X)設定為TS(T)
事務T發出readItem(X)操作如果writeTS(T) > TS(T)，則中止T，否則執行T的readItem(X)並將readTS(X)設定為TS(T)和當前readTS(X)中的最大值
每當基本時間戳排序演算法檢測到兩個衝突操作以不正確的順序發生時，它會透過中止發出該操作的事務來拒絕後面的操作。該演算法產生的排程保證是衝突可序列化的，就像兩階段鎖定協議一樣。
嚴格時間戳排序是基本時間戳排序的一種變體，它確保排程是可恢復的和衝突可序列化的。在這個變體中，一個發出readItem(X)或writeItem(X)的操作且TS(T) > writeTS(X)的事務T，它的讀或寫操作會被延遲，直到寫入X的值的事務T1提交或中止。為了實現這個演算法，需要鎖定。這個演算法不會導致死鎖，因為只有當TS(T) > TS(T1)時，T才會等待T1。
TODO::參考白皮書並新增更多內容
TODO
在鎖定和時間戳排序這兩種併發控制技術中，在事務對資料項進行操作之前都會進行一些檢查。在鎖定中，檢查是用來確定要訪問的項是否被鎖定的。在時間戳排序中，事務時間戳會與資料項的讀寫時間戳進行比較。這給事務執行帶來了開銷。在樂觀併發控制技術中，在事務執行過程中不會進行任何檢查。在這種方案中，事務中的更新不會直接應用於資料項，直到事務結束。在事務執行過程中，所有更新都會應用於資料項的本地副本，這些副本以每個事務為基礎儲存。在事務執行結束時，驗證階段會檢查事務的任何更新是否違反了可序列化。如果沒有違反，則事務提交，資料庫從本地副本更新，否則事務中止，然後稍後重新啟動。該協議有三個階段
- 讀取階段– 事務可以從資料庫中讀取已提交資料項的值。但是，更新只應用於儲存在事務工作區中的資料項的本地副本。
- 驗證階段- 執行檢查以確保如果事務更新被應用於資料庫，則不會違反可序列化。
- 寫入階段– 如果驗證階段表明它是可序列化的，則事務更新被應用於資料庫。否則，更新被丟棄，事務被重新啟動。
這種協議非常適合事務之間對資料項的干擾很少的情況。如果幹擾更多，則事務將經常被重新啟動。這種技術被稱為“樂觀”，因為它們假設干擾很少發生，因此在事務執行期間不需要進行檢查。
TODO::參考白皮書並新增更多內容
傳統資料庫系統中的併發控制旨在維護資料庫的一致性。MMDB中的併發控制由於滿足時間約束和維護資料一致性的衝突需求而變得困難。