分散式資料庫管理系統 - 併發控制

併發控制技術確保多個事務可以同時執行，同時保持事務的ACID特性和排程中的可序列化。

在本章中，我們將學習併發控制的各種方法。

基於鎖的併發控制協議

基於鎖的併發控制協議使用資料項鎖定概念。鎖是與資料項關聯的變數，它決定是否可以對該資料項執行讀/寫操作。通常，使用鎖相容性矩陣來確定兩個事務是否可以同時鎖定一個數據項。

基於鎖的併發控制系統可以使用單相或兩相鎖定協議。

在這種方法中，每個事務在使用資料項之前對其進行鎖定，並在使用完後立即釋放鎖。這種鎖定方法提供了最大併發性，但並不總是強制執行可序列化。

在這種方法中，所有鎖定操作都先於第一個鎖釋放或解鎖操作。事務包括兩個階段。在第一階段，事務僅獲取它所需的所有鎖，並且不釋放任何鎖。這稱為擴充套件或增長階段。在第二階段，事務釋放鎖，並且不能請求任何新鎖。這稱為收縮階段。

遵循兩階段鎖定協議的每個事務都保證是可序列化的。但是，這種方法在兩個衝突事務之間提供了較低的並行性。

基於時間戳的併發控制演算法使用事務的時間戳來協調對資料項的併發訪問，以確保可序列化。時間戳是由DBMS賦予事務的唯一識別符號，表示事務的開始時間。

這些演算法確保事務按照其時間戳指定的順序提交。較舊的事務應該在較新的事務之前提交，因為較舊的事務比較新的事務先進入系統。

基於時間戳的併發控制技術生成可序列化的排程，使得等效的序列排程按照參與事務的年齡排序。

一些基於時間戳的併發控制演算法包括：

基於時間戳的排序遵循三個規則來強制執行可序列化：

在衝突率較低的系統中，驗證每個事務的可序列性的任務可能會降低效能。在這些情況下，可序列性測試被推遲到提交之前。由於衝突率較低，因此中止不可序列化事務的機率也較低。這種方法稱為樂觀併發控制技術。

在這種方法中，事務的生命週期分為以下三個階段：

該演算法使用三個規則在驗證階段強制執行可序列化：

規則1 - 給定兩個事務T_i和T_j，如果T_i正在讀取T_j正在寫入的資料項，則T_i的執行階段不能與T_j的提交階段重疊。T_j只有在T_i完成執行後才能提交。

規則2 - 給定兩個事務T_i和T_j，如果T_i正在寫入T_j正在讀取的資料項，則T_i的提交階段不能與T_j的執行階段重疊。T_j只有在T_i已提交後才能開始執行。

規則3 - 給定兩個事務T_i和T_j，如果T_i正在寫入T_j也正在寫入的資料項，則T_i的提交階段不能與T_j的提交階段重疊。T_j只有在T_i已提交後才能開始提交。

在本節中，我們將瞭解如何在分散式資料庫系統中實現上述技術。

分散式兩階段鎖定的基本原理與基本兩階段鎖定協議相同。但是，在分散式系統中，有一些站點被指定為鎖管理器。鎖管理器控制來自事務監視器的鎖獲取請求。為了在各個站點的鎖管理器之間強制協調，至少有一個站點被授權檢視所有事務並檢測鎖衝突。

根據可以檢測鎖衝突的站點數量，分散式兩階段鎖定方法可以分為三種類型：

集中式兩階段鎖定 - 在這種方法中，一個站點被指定為中央鎖管理器。環境中的所有站點都知道中央鎖管理器的地址，並在事務期間從其獲取鎖。
主副本兩階段鎖定 - 在這種方法中，一些站點被指定為鎖控制中心。每個站點負責管理一組定義的鎖。所有站點都知道哪個鎖控制中心負責管理哪個資料表/片段項的鎖。
分散式兩階段鎖定 - 在這種方法中，有多個鎖管理器，其中每個鎖管理器控制儲存在其本地站點的數據項的鎖。鎖管理器的地址基於資料分佈和複製。

在集中式系統中，任何事務的時間戳由物理時鐘讀數確定。但是，在分散式系統中，任何站點的本地物理/邏輯時鐘讀數都不能用作全域性時間戳，因為它們不是全域性唯一的。因此，時間戳由站點ID和該站點的時鐘讀數組合而成。

為了實現時間戳排序演算法，每個站點都有一個排程程式，該排程程式為每個事務管理器維護一個單獨的佇列。在事務期間，事務管理器向站點的排程程式傳送鎖請求。排程程式將請求按時間戳遞增的順序放入相應的佇列。請求按佇列順序從佇列的前面處理，即最舊的請求優先。

另一種方法是建立衝突圖。為此，定義了事務類。事務類包含兩個資料項集，稱為讀取集和寫入集。如果事務的讀取集是類讀取集的子集，並且事務的寫入集是類寫入集的子集，則事務屬於特定類。在讀取階段，每個事務都會發出其讀取集中的資料項的讀取請求。在寫入階段，每個事務都會發出其寫入請求。

為活動事務所屬的類建立衝突圖。它包含一組垂直、水平和對角線邊。垂直邊連線類內的兩個節點，表示類內的衝突。水平邊連線兩個類的兩個節點，表示不同類之間的寫寫衝突。對角線邊連線兩個類的兩個節點，表示兩個類之間的寫讀或讀寫衝突。

分析衝突圖以確定同一類或兩個不同類中的兩個事務是否可以並行執行。

分散式樂觀併發控制演算法擴充套件了樂觀併發控制演算法。對於此擴充套件，應用了兩個規則：

規則1 - 根據此規則，事務必須在執行時在所有站點本地進行驗證。如果發現任何站點上的事務無效，則將其中止。本地驗證保證事務在已執行的站點上保持可序列化。在事務透過本地驗證測試後，將進行全域性驗證。

規則2 - 根據此規則，在事務透過本地驗證測試後，應進行全域性驗證。全域性驗證確保如果兩個衝突事務在多個站點一起執行，則它們應在所有一起執行的站點的相同相對順序中提交。這可能需要事務在驗證後等待另一個衝突事務，然後才能提交。此要求使演算法不太樂觀，因為事務可能無法在某個站點驗證後立即提交。

列印頁面