數據庫系統原理與實踐 筆記 #12

事務管理和并發控制與恢復(續)

并發控制

• 數據庫必須提供一種機制來保證所有調度(目標)是：
  • 沖突可串行化
  • 可恢復性，最好是無級聯
• 一個策略是一個時間只允許一個事務，即產生一個串行調度，但是并發性能差
• 目標：建立一個能夠保證串行化的并發控制協議

SQL-92中的并發級別

• 可串行化(serializable)—通常保證可串行化的執行
• 可重復讀(repeatable read)—只允許讀取已提交數據，一個事務對相同數據的重復讀取要返回相同的值(其他事務不得更改該數據)
• 已提交讀(read committed)—（默認）只允許讀取已提交的數據，但不要求可重復讀
• 未提交讀(read uncommitted)—允許讀取未提交數據
• 以上所有隔離性級別都不允許臟寫：即如果一個數據項已經被另外一個尚未提交或中止的事務寫入，則不允許對該數據項執行寫操作
• 通過命令顯式設置隔離性級別：

set transaction isolation level serializable

基于鎖的協議

• 鎖是用來控制對數據項的并發訪問的一種機制
• 給數據加鎖有兩種方式：
  • 排他鎖(X)：對數據項即可寫又可讀，使用lock-X指令
  • 共享鎖(S)：對數據項只能讀，使用lock-S指令
• unlock指令釋放鎖
• 申請鎖請求發送給并發控制管理器，只有在并發控制管理器授予所需鎖之后，事務才能繼續其操作
• 鎖相容性矩陣
  ? 表示為comp(A, B)

	S	X
S	true	false
X	false	false

• 指令之間的沖突對應于鎖類型之間的不相容性

• 如果被請求所與數據項上已有的鎖相容，那么事務可以被授予該鎖：

  • 一個數據項可以同時有多個共享鎖
  • 如果一個事務在某個數據項上擁有排他鎖，那么其他事物不能再在這個數據項上加任何鎖

• 如果一個鎖不能被授予，那么請求該鎖的事務必須等待，直到該數據項上的其他不相容鎖全部釋放，然后再授予鎖

• 事務執行鎖的例子：
  $$\begin{gathered} T_2:lock?S(A); \\ read(A); \\ unlock(A); \\ lock?S(B); \\ read(B); \\ unlock(B); \\ display(A+B); \end{gathered}$$

• 上述鎖無法有效地保證可串行化—如果A在read B的時候被其他事務更新了，那么最后的和將會是錯誤的答案

• 需指定合理的封鎖協議：一組規定事務何時對數據項進行加鎖、解鎖的規則。封鎖協議限制了可能的調度數目

基于鎖的協議的隱患

• 考慮下面的調度：
  

• $T_3$和$T_4$都無法被處理—排他鎖lock-S(B)導致$T_4$等待$T_3$釋放其在B上的鎖，而排他鎖lock-X(A)導致$T_3$等待$T_4$釋放其在A上的鎖

• 這樣的情況稱為死鎖(deadlock)：要處理$T_3$或$T_4$其中一個死鎖，必須回滾并釋放鎖

• 大多數封鎖協議都會產生死鎖

• 如果并發控制管理器設計得差也有可能導致餓死(starved)

• 并發控制協議可以通過良好的設計，能夠避免事務餓死

鎖的授予

• 避免事務餓死的授權加鎖方式：當事務$T_i$申請對數據項Q加M型鎖時，并發控制管理器授權加鎖的條件需滿足：
  • 1.不存在在數據項Q上持有與M型鎖沖突的鎖的其他事務
  • 2.不存在等待對數據項Q加鎖且**先于$T_i$申請加鎖的事務
• 這樣，一個加鎖申請就不會被其后的加鎖申請阻塞

封鎖協議

• 令 { T 0 , T 1 , . . . , T n } \{T_0, T_1, ..., T_n\} {T0?,T1?,...,Tn?}是參與調度S的一個事務集，如果存在數據項Q，使得$T_i$在Q上持有A型鎖。后來，$T_j$在Q上持有B型鎖，且comp(A,B)=false，則我們稱$T_i$先于$T_j$，記為$T_i\to T_j$
  • 如果$T_i\to T_j$，這一優先意味著在任何等價的串行調度中，$T_i$必須出現在$T_j$之前
• 如果調度S是那些遵從封鎖協議規則的事務集的可能調度之一，我們稱調度S在規定的封鎖協議下是合法的
• 一個封鎖協議當且僅當其所有合法的調度為沖突可串行化時，我們稱它保證沖突可串行性
• 換句話說，對于任何合法的調度，其關聯的事務優先關系是無循環的

兩階段封鎖協議

• 這是一個能夠保證沖突可串行化調度的協議
• 階段1：增長階段
  • 事務可以獲得鎖
  • 事務不能釋放鎖
• 階段2：縮減階段
  • 事務可以釋放鎖
  • 事務不能獲得新鎖
• 封鎖點：在調度中該事務獲得其最后加鎖的位置（增長階段結束點）
• 兩階段封鎖協議保證可串行化：可以證明事務可以按照封鎖點來排序（一種可串行化次序）
• 兩階段封鎖不能保證不發生死鎖
• 兩階段封鎖下很有可能發生級聯回滾
  • 為了避免這個問題，將該協議修改為嚴格兩階段封鎖協議
• 嚴格兩階段封鎖協議要求未提交事務所寫的熱河數據在該事務提交之前均以排他方式加鎖，防止其他事務讀取這些數據
• 強兩階段封鎖協議更加嚴格：要求是提交之前不得釋放任何鎖（在這個協議下，事務可以按其提交順序串行化

多粒度

• 將多個數據聚成一組，作為同步單元，無需單獨對單個數據項進行加鎖
• 多粒度：允許各種大小的數據項，并定義數據粒度的層次結構，可以圖形化的表示為樹
• 如果一個事務顯式地對樹中的某個節點加了鎖，那么它也給所有統一模式下的該節點的子節點隱式地加了鎖
• 鎖的力度：
  • 細粒度（樹的低層）：高并發性，鎖開銷多
  • 粗粒度（樹的高層）：低并發性，鎖開銷少

粒度層次的例子

• 如事務$T_i$需判定某個節點（如$r_{b_1}$）是否可以加鎖，必須從根結點進行遍歷至該節點（開銷大）

意向鎖類型

• 除了排他鎖及共享鎖類型，多粒度下還有其他三種鎖類型：
  • 共享型意向鎖(IS)：將在樹的較低層進行顯式封鎖，但只能加共享鎖
  • 排他型意向鎖(IX)：將在樹的較低層進行顯式封鎖，可以加排他鎖或共享鎖
  • 共享排他型意向鎖(SIX)：以該節點為根的子樹顯式地加了共享鎖，并且在樹的更底層顯式地加排他鎖
• 意義：意向鎖允許較高層的節點被加上共享鎖或排他鎖，而無需從樹根遍歷到子孫節點來檢驗鎖的相容性，提升鎖相容檢驗的效率

相容性矩陣

• 所有所類型的相容性矩陣
  

多粒度封鎖模式

• 事務$T_i$按如下規則對數據項Q加鎖：
  • 1.必須遵從鎖類型相容函數
  • 2.必須首先是封鎖樹的根節點，并且可以加任意類型的鎖
  • 3.僅當事務$T_i$當前對Q的父節點具有IX或IS時，對結點Q可加S或IS鎖
  • 4.僅當事務$T_i$當前對Q的父節點具有IX時，對節點Q可加X、SIX或IX鎖
  • 5.僅當$T_i$未曾對任何節點解鎖時，$T_i$可對節點加鎖(滿足兩階段封鎖)
  • 6.僅當$T_i$當前不持有Q的子節點的鎖時，$T_i$可對節點Q解鎖
• 加鎖按自頂向下的順序，鎖的釋放按自底向上的順序

基于時間戳的協議

• 對于系統中每個事務$T_i$，我們把一個唯一的固定時間戳和它聯系起來，此時間戳記為$TS(T_i)$；該時間戳是在事務$T_i$開始執行前由數據庫系統賦予的。若事務$T_i$已被賦予時間戳$TS(T_i)$，并且有一新事務$T_j$進入系統，則$TS(T_i)<TS(T_j)$
• 事務的時間戳決定了串行化順序
• 每個數據項Q需要與兩個時間戳值相關聯：
  • W-timestamp(Q)表示成功執行write(Q) 的所有事務的最大時間戳
  • R-timestamp(Q)表示成功執行read(Q) 的所有事務的最大時間戳
• 時間戳排序協議保證任何有沖突的read或write操作按照時間戳順序執行
• 假設事務$T_i$發出指令read(Q)：
  • 1.若$TS(T_i)$ < W-timestamp(Q)，則$T_i$需要讀入的Q值已被覆蓋：read操作被拒絕，$T_i$回滾
  • 2.若$TS(T_i)\ge$W-timestamp(Q)：執行read操作，R-timestamp(Q)被設置為max(R-timestamp(Q), $TS(T_i)$)
• 假設事務$T_i$發出指令write(Q)：
  • 1.若$TS(T_i)$ < R-timestamp(Q)，則$T_i$所需更新Q的值已過時：write操作被拒絕，$T_i$回滾
  • 2.若$TS(T_i)$ <W-timestamp(Q)，則$T_i$試圖寫入的Q值已過時：write操作被拒絕，$T_i$被餓死
  • 3.其他情況：執行write操作，將W-timestamp(Q)設置為$TS(T_i)$

基于時間戳協議的正確性

• 時間戳排序協議保證沖突可串行化：沖突操作按時間戳的順序來處理
• 保證無死鎖：不存在等待，可能有長事務餓死
• 可能產生不可恢復的調度：事務可恢復性與事務提交順序有關

基于有效性檢查的協議

• 有效性檢查協議（適用于大部分只讀事務的情況） 要求每個事務$T_i$在其生命周期中按兩個或三個階段執行：
  • 1.讀階段：事務$T_i$的所有write操作都是對局部臨時變量進行的
  • 2.有效性檢查階段：事務$T_i$進行有效性檢查，判斷是否可以write操作而不違反可串行性
  • 3.寫階段：如果$T_i$已通過有效性檢查，則保存任何寫操作結果的臨時局部變量值被復制到數據庫中。只讀事務不進入此階段
• 每個事務必須按照以上順序經歷這些過程。然而，并發執行的事務三個階段可以是交叉執行的
• 每個事務$T_i$都有三個不同的時間戳：
  • Start($T_i$)：事務$T_i$開始執行的時間
  • Validation($T_i$)：事務$T_i$完成讀階段
• 利用時間戳Validation($T_i$)的值，通過時間戳排序技術決定可串行化順序，以增加并發性：即$TS(T_i)=Validation(T_i)$

事務Ti的有效性檢測

• 對于任何滿足$TS(T_k)<TS(T_i)$的事務$T_k$必須滿足下面兩條件之一：
  • $Finish(T_k)<Start(T_i)$
  • $Start(T_i)<Finish(T_k)<Validation(T_i)$，并且需保證$T_k$鎖寫的數據項集與$T_i$所讀數據項集不想交；即$T_k$的寫操作不會影響到$T_i$的讀操作
• 則有效性檢測通過，$T_i$可以進入寫階段并提交，否則測試失敗$T_i$中止
• 有效性檢查協議能夠自頂預防級聯回滾，保證無死鎖

恢復系統

故障分類

• 事務故障：
  • 邏輯錯誤：由于某些內部條件而無法繼續正常執行
  • 系統錯誤：系統進入一種不良狀態（如死鎖），結果事務無法繼續正常執行
• 系統崩潰：硬件故障，或者是數據庫軟件或操作系統的漏洞，導致易失性存儲器內容丟失，并使得事務處理停止
• 磁盤故障：由于磁頭損壞或故障造成磁盤塊上的內容丟失：
  • 毀壞是可探測的：磁盤驅動器用校驗和來檢測故障

恢復機制

• 保證數據庫一致性以及事務的原子性的算法稱為回復算法：
  • 在正常事務處理時采取措施，保證有足夠的信息可用于故障恢復
  • 故障發生后采取措施，將數據庫內容恢復到某個保證數據庫一致性、事件原子性及持久性的狀態
• 存儲器類型：
  • 易失性存儲器(volatile storage)：易失性存儲器中的信息在系統崩潰時通常無法保存下來
  • 非易失性存儲器(nonvolatile storage)：非易失性存儲器中的信息在系統崩潰時可以保存下來
  • 穩定存儲器(stable storage)：穩定存儲器中的信息永不丟失

數據訪問

• 物理塊是位于磁盤上的塊

• 緩沖塊是臨時位于主存的塊

• 磁盤和主存間的塊移動是由下面兩個操作引發的：**input(B)**傳送物理塊B到主存，**output(B)**傳送緩沖塊B至硬盤，并替換磁盤上相應的物理塊

• 例子
  

• 每個事務$T_i$有一個私有工作區，用于保存$T_i$所訪問及更新的所有數據項的拷貝：$T_i$的工作區中保存的每一個數據項X記為$x_i$

• 使用下面兩個操作里完成數據在工作區和系統緩沖區之間的傳遞：

  • read(X) 將數據項X的值賦予局部變量$x_i$
  • write(X) 將局部變量$x_i$的值賦予緩沖塊中的數據項X
  • 注意: output($B_x$) 不需要立刻在write(X)后執行。系統會在它認為合適的時候執行output操作

• 事務：必須在第一次訪問X之前執行read(X)；**write(X)**可以在事務被提交前的任意時刻執行

恢復和原子性

• 為保證原子性，我們必須在修改數據庫本身之前，首先向穩定存儲器輸出信息，描述要做的修改
• 目的：確保由中止事務所做的修改不會持久保存與數據庫中，即回滾該中止事務
• 基于日志的恢復系統

基于日志的恢復機制

• 日志保存于穩定存儲器中：日志是日志記錄的序列它記錄數據庫中的所有更新活動
• 當一個事務$T_i$開始時，它記錄$<T_{i}start>$
• 事務$T_i$執行write(X) 前，日志記錄：$<T_{i}X,V_1,V_2>$，$V_1$是在write之前X的值(舊值)，$V_2$是需要寫入X的值(新值)
• 當$T_i$結束了最后一條指令時，$<T_{i}commit>$寫入日志
• 當事$T_i$中止時，日志記錄$<T_{i}abort>$
• 使用日志的兩種方法：延遲的數據庫修改（事務提交后還未修改），立即的數據庫修改（事務提交前已修改）

數據庫修改

• 立即修改模式允許在事務提交前，將未提交的事務更新至緩沖區或磁盤
• 延遲修改模式直到事務提交時都沒有更新到緩沖區/磁盤：簡化了恢復，但是多了存儲本地副本的開銷
• 日志記錄的更新必須在數據項被write(數據庫修改)之前完成

事務提交

• 當事務將其關于提交的日志記錄輸出到穩定存儲器時，該事務被認為已提交：之前的所有日志記錄必須都已經輸出
• 事務提交時，由該事務執行的write操作結果可能仍在緩沖區，隨后被輸出

并發控制和恢復

• 在并發事務中，所有事務共享一個磁盤緩沖區和日志：一個緩沖塊中的數據項可以來自多個事務的更新
• 假設如果一個事務$T_i$習概了一個數據項，那么在$T_i$提交前，其他事務不能修改同一個數據項(即不允許臟寫)：
  • 未提交事務的更新不能被其他事務所見
  • 可以通過在被更新數據項上獲取排他鎖，并持有該鎖直到事務提交位置來保證（嚴格兩階段封鎖）
• 不同事務的日志記錄在日志中穿插(interspersed)存儲

Undo和Redo操作

• 對日志記錄$<T_i,X,V_i,V_2>$的Undo操作將舊值$V_1$寫入X
• 對日志記錄$<T_i,X,V_1,V_2>$的Redo操作將新值$V_2$寫入X

事務的Undo和Redo

• undo($T_i$) 將事務$T_i$所更新的所有數據項的值恢復成舊值，回到$T_i$的最后一條日志記錄：
  • 每次數據項X被恢復成舊值，日志記錄$<T_i,X,V>$會被寫入
  • 當事務的undo操作完成時，日志記錄$<T_{i}abort>$被寫入
• redo($T_i$) 將事務$T_i$所更新的所有數據項的值置為新值，從$T_i$的第一條日志記錄開始執行（這個情況下沒有任何日志記錄）

從故障中恢復的Undo和Redo

從故障中恢復時

• 當日志是以下狀態時，事務$T_i$需要undo操作：
  • 有日志$<T_{i}start>$
  • 沒有日志$<T_{i}commit>$和$<T_{i}abort>$
• 當日志是以下狀態時，事務$T_i$需要進行redo操作：
  • 有日志$<T_{i}start>$
  • 有日志$<T_{i}commit>$或$<T_{i}abort>$
• 如果事務$T_i$之前執行了undo操作，$<T_{i}abort>$被寫入到日志，接著故障發生。為了從故障中恢復，$T_i$要執行redo操作
• 這樣的redo操作重新執行了原先的所有操作，包括重新存儲舊值：稱為重復歷史，看起來很浪費，但是最大程度地簡化了恢復

檢查點

• 對于日志中的所有事務做Redo/Undo
  • 1.如果系統已經運行了很長一段時間，那么處理整個日志很浪費時間
  • 2.那些已經將輸出更新到數據庫的事務沒必要redo
• 流線型恢復過程周期性地執行檢查點：
  • 1.將當前位于主存的所有日志記錄輸出到穩定存儲器上
  • 2.將所有修改了的緩沖塊輸出到磁盤上
  • 3.將一個日志記錄$<checkpointL>$輸出到穩定存儲器
  • 執行檢查點時，所有數據更新都停止
• 恢復時，我們僅考慮在檢查點前最近開始的事務$T_i$，及在$T_i$后開始的事務：
  • 從日志末尾反向掃描，找到最近的$<checkpointL>$記錄
  • 只要在L未提交/中止的事務或者在檢查點后開始的事務需要redo或undo
  • 檢查點之前的已提交或者中止的事務已經將其更新輸出到了穩定存儲器
• undo操作可能需要一些早期的日志
  • 繼續從日志末尾反向掃描直到找到在L的每個事務$T_i$的記錄$<T_{i}start>$