【數據庫】并發控制

并發控制

在數據庫系統，經常需要多個用戶同時使用。同一時間并發的事務可達數百個，這就是并發引入的必要性。

常見的并發系統有三種：

串行事務執行（X），每個時刻只有一個事務運行，不能充分利用系統資源
交叉并發（V），并行事務并行操作輪流交叉運行，適應于單處理機系統，能夠減少處理機的空閑時間，提高系統的效率。
同時并發，多個處理機同時運行多個事務，理想的并發方式，但是受限于硬件環境。

但是并發控制可能導致一些問題，所以主要有三個任務：

對并發操作的正確調度
保證事務隔離性
保證數據庫的一致性

并發操作的后果

并發控制可能導致的數據不一致性有三類：

丟失修改
不可重復讀
讀臟數據

為了說明這三種情況，我們用 $R (x)$ 表示讀數據 $x$ ， $W (x)$ 表示寫數據 $x$ .

一、丟失修改

考慮下面的情況：

$T_1$	$T_2$
$R (A) = 16$
	$R (A) = 16$
$A = A ? 1, W (A) = 15$
	$A = A ? 1$ , $W (A) = 15$

那么 $T_1$ 對 $A$ 的修改丟失了。

二、不可重復讀

不可重復讀是在 $T_1$ 讀取數據后， $T_2$ 更新，導致 $T_1$ 無法再現讀取結果。

（1）RUR(Read, Update, Read)

$T_1$	$T_2$
$R (A) = 50, R (B) = 100, S = 150$
	$R (B) = 100, W (B) = 200$
$R (A) = 50, R (B) = 200, S = 250$

（2）RDR(Read, Delete, Read)

$T_1$	$T_2$
$R (A) = 50, R (B) = 100, S = 150$
	將B記錄從數據庫中刪除
無法讀取到B的記錄

（3）RAR(Read, Add, Read)

$T_1$	$T_2$
A中有兩條記錄， $\sum A_i = 100$
	將記錄50插入到集合A中
A中有三條記錄， $\sum A_i = 150$

三、讀臟數據

事務 $T_1$ 修改某一數據，并寫回磁盤，然后 $T_2$ 讀取之后， $T_1$ 因為某種原因被撤銷，這個時候 $T_2$ 的數據可能不一致。

$T_1$	$T_2$
$R (C) = 100, W (C) = 200$
	$R (C) = 200$
ROLLBACK C，C恢復為100

封鎖

一、封鎖的概念

封鎖是指事務在某個數據對象操作前先對系統請求進行加鎖。加鎖之后，事務就有了數據對象控制權。

基本封鎖類型有兩種：排它鎖（Exclusive Locks, X鎖）和共享鎖（Share Locks, S鎖）

排它鎖又稱寫鎖，如果 $T$ 對 $A$ 加X鎖，那么其它事務不能加任何其他鎖。這個時候，其它事務不能讀取和修改。

共享鎖又稱讀鎖，如果 $T$ 對 $A$ 加S鎖，那么其它事務只能對 $A$ 加 $S$ 鎖。這個時候，其它事務可以讀 $A$ ，但是在 $T$ 釋放鎖之前不能進行修改。

換言之，存在鎖的相容矩陣：

二、封鎖協議

申請鎖、持有鎖、釋放鎖的規則，叫做封鎖協議。

一級封鎖協議是事務中隊數據修改之前必須對其加排它鎖直到事務結束。

一級封鎖協議可以有效防止丟失更新。

二級封鎖協議是在一級協議的基礎上，要求讀取數據之前必須加共享鎖，讀完再釋放。這樣可以防止讀臟數據。

二級封鎖協議可以有效防止讀臟數據。

三級封鎖協議是在二級基礎上，增加某事務施加的共享鎖，保持到事務結束再釋放。

三級封鎖協議可以解決不可重復得問題。

活鎖和死鎖

一、活鎖

考慮有四個事務T1,T2,T3,T4

T1封鎖數據R，T2請求R，所以T2等待。T3也請求R，然后T1釋放R的鎖之后系統調度給T3，T4請求R，T3釋放R的鎖之后系統調度給T4，導致T2永遠等待。這就是活鎖。

避免活鎖比較簡單，只需要采取先來先服務的策略，在多個事務請求封鎖同一個數據對象的時候按照請求封鎖的先后次序對事務排序。

二、死鎖

考慮兩個事務T1、T2。T1封鎖R1，T2封鎖R2。T1此時請求封鎖R2，而T2封鎖R2，所以T1等待T2釋放R2的鎖。此時T2又申請R1，T1已經封鎖R1，T2只能等待T1釋放R1的鎖。此時，T1、T2形成死鎖。

如果希望預防死鎖，一般有兩個思路：

一次封鎖法。要求每個事務必須一次將所有要使用的數據全部加鎖，否則就不能繼續執行。但是這樣比較難確定封鎖對象，也會導致并發度降低。
順序封鎖法。對數據對象規定封鎖順序，按照順序進行封鎖。但是這樣難以確定事務要封鎖哪些對象。

因此，死鎖的預防比較難，多采用診斷解決的思路。

最簡單的診斷方法就是使用超時法，如果事務等待時間超過規定時限，就說明發生死鎖。這樣實現簡單，但是可能誤判，并且如果時限過長，可能會讓死鎖無法及時發現。

等待圖法是一個比較好的方式。設 $G=\langle V,E\rangle$ ， $V$ 是正運行的事務， $E$ 是事務等待情況，如果 $T_1$ 等待 $T_2$ ，就連接 $T_1T_2$ 。如果圖中存在回路，說明系統出現死鎖。

檢測到死鎖后，選擇一個處理死鎖代價最小的事務，將其撤銷。釋放事務持有的所有鎖，讓其他事務能運行下去。

可串行性

多個事務的并發執行想要保證正確性，需要結果和某一次序串行執行結果相同。

一、可串行化的判定

可串行性是并發事務正確調度的準則，只有并發調度是可串行化的才能認為是正確調度。

考慮下面的兩個事務：

T1：讀B，A=B+1，寫回A
T2：讀A，B=A+1，寫回B

對于下面的這些策略：

這兩種策略相當于串行執行，因此并行執行的結果應當和二者之一相同。而對于下面的例子：

不可串行化。

二、沖突可串行化

沖突可串行化給出了一個可串行化的充分條件：

一個調度Sc在保證沖突操作次序不變的情況下，通過交換兩個事務不沖突操作的次序得到另一個調度Sc’。如果Sc’是串行的，稱調度Sc為沖突可串行化的調度。

這里需要先引入沖突操作的概念。所謂沖突操作是指如下操作：

事務Ti讀x，Tj寫x
事務Ti寫x，Tj寫x

下面舉一個例子。

證明：調度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)可串行化。

r1(A)、w1(A)、w2(A)不可交換，r1(B)、w1(B)、w2(B)不可交換。

這樣，可以交換為r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(N)

這是一個串行調度T1T2，所以Sc1是沖突可串行化調度。

需要注意的是，這個條件并不是必要的。下面舉一個反例。

T1=W1(Y)W1(X), T2=W2(Y)W2(X), T3=W3(X)

調度W1(Y)W2(Y)W2(X)W1(X)W3(X)結果與T1T2T3相同，可串行化，但并非沖突可串行化。

兩段鎖

在封鎖的時候，對數據對象加鎖需要遵守約定，比如何時申請加鎖、鎖持續時間和何時釋放。兩段封鎖協議（2PL）是最常用的封鎖協議，并且能產生可串行化調度。

兩段鎖協議是指所有事務需要分兩個階段對數據項加鎖和解鎖：

在數據讀寫之前，事務需要先取得封鎖
釋放封鎖之后，事務不再申請和獲得其它封鎖

這里的兩段，具體來說就是事務的兩個階段：

擴展階段，獲得封鎖，可以申請獲得數據項上任何類型的鎖，但是不能釋放任何鎖
收縮階段，釋放封鎖，可以釋放任何數據線上的任何類型的鎖，但是不能申請任何鎖。

比如事務A按照兩段鎖協議的封鎖序列是：

Slock A, Slock B, Xlock C, Unlock B, Unlock A, Unlock C

如果多個調度都符合兩段鎖協議，一定是一個可串行化調度。

但是兩段鎖可能會出現死鎖，所以還需要引入一次封鎖法。也就是事務必須一次將所有使用數據全部加鎖，否則就不能繼續執行，這樣可以回避死鎖。

封鎖粒度

封鎖對象的大小稱為封鎖粒度。封鎖對象分成邏輯單元和物理單元。

在關系數據庫中，邏輯單元包括屬性值、屬性值集合、元組、關系、索引項、整個索引、整個數據庫；物理單元包括頁和物理記錄。

封鎖粒度和系統并發度與并發控制的開銷密切相關。

粒度大，封鎖數據單元少，并發度低，開銷小
粒度小，并發度高，開銷大

下面舉兩個例子。

（1）若封鎖粒度是數據頁，事務T1需要修改元組L1，則T1必須對包含L1的整個數據頁A加鎖。如果T1對A加鎖后事務T2要修改A中元組L2，則T2被迫等待，直到T1釋放A。如果封鎖粒度是元組，則T1和T2可以同時對L1和L2加鎖，不需要互相等待，提高了系統的并行度。

（2）事務T需要讀取整個表，若封鎖粒度是元組，T必須對表中的每一個元組加鎖，開銷極大。

因此，在一個系統中需要同時支持多種封鎖粒度供不同事務選擇，也就是 多粒度封鎖。在選擇粒度的時候，要同時考慮封鎖開銷和并發度：

對處理多個關系大量元組的事務，以數據庫為封鎖單位
對處理大量元組的事務，以關系為封鎖單位
對少量元組的用戶事務，以元組為封鎖單位。

可以用一顆樹來表示粒度，稱作多粒度樹：

在這個樹中，對一個結點加鎖相當于節點所有子孫加同類型的鎖。這里就引入了顯式封鎖和隱式封鎖：顯式封鎖是直接加到數據對象上的封鎖，隱式封鎖是由于上級結點加鎖導致的子節點加鎖。

因此，系統在檢查封鎖沖突的收，需要檢查顯式封鎖和隱式封鎖。具體來說就是：

數據對象有沒有顯式封鎖與之沖突
本事務顯式封鎖是否與上級節點隱式封鎖沖突
上面的顯式封鎖是否與本事務隱式封鎖沖突

意向鎖

在此基礎上，引入意向鎖，來提高對某個數據對象加鎖時系統的檢查效率。

如果對一個結點加意向鎖，說明其下層節點正在被加鎖；對任意結點加基本鎖，必須對上層節點加意向鎖。

常用的意向鎖有三種：

意向共享鎖（IS鎖），表示后裔節點擬（意向）加S鎖
意向排它鎖（IX鎖），表示后裔節點擬（意向）加X鎖
共享意向排它鎖（SIX鎖），表示對它加S鎖，再加IX鎖。

對于這些鎖，相容矩陣如下：

鎖強度的哈斯圖如下：

這里鎖強度是對其他所的排斥程度，強鎖對弱鎖是安全的。

在引入意向鎖之后，執行封鎖操作：

申請時按照從上到下的次序
釋放時按照從下到上的次序

例如，T1對R1加S鎖，需要下面的操作

對數據庫加IS鎖
檢查數據庫和R1是否加了不相容鎖，也就是X或IX鎖
無需搜索R1中元組是否加了X鎖。

這樣，意向鎖提高了系統并發度，減少了加減鎖的開銷，得到廣泛應用。