Microsoft PowerPoint - EMDBCh14.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - EMDBCh14.ppt"

庙朱
5 years ago
Views:

1 第 14 章並行控制與回復技術學習重點二元鎖定共享 / 互斥鎖定鎖定的轉換兩階段鎖定協定的演算法 2PL 協定的類型死結與飢餓現象的處理時間戳記排序演算法樂觀的並行控制技術 2

2 學習重點資料項目的鎖定範圍大小多層範圍鎖定回復技術的概念回復策略回復技術寫前記錄以延遲更新為基礎的回復技術投影分頁功能 3 二元鎖定簡單但使用上限制較多二元鎖定 (binary lock) 有兩種狀態 : 鎖定與非鎖定 ( 簡單說就是 1 與 0) 每個資料庫的項目 X 都有一個自己的鎖定資料, 如果 X 的鎖定值等於 1 則代表 X 不能被其他資料庫動作所存取 ;X 的鎖定值等於 0 則代表則可被存取以 LOCK(X) 來表示資料項 X 的鎖定值二元鎖定是使用兩個指令 lock_item 和 unlock_item 4

3 二元鎖定運作方式 : 當交易要求存取 X, 首先發出 lock_item(x) 如果 LOCK(X) = 1, 此時交易將被迫進行等待 ; 如果 LOCK(X) = 0, 交易將 LOCK(X) 值設定為 1 ( 代表交易鎖定此項目 ), 並且被允許存取 X 當交易使用過此項目後, 它會發出 unlock_item(x) 的指令, 將 LOCK(X) 設為 0 ( 解除鎖定 ), 如此一來 X 就可被其他交易存取 5 二元鎖定 lock_item 與 unlock_item 指令是不可分解的單位每筆交易都必須遵守下列規則 : 在交易 T 中任何的 read_item(x) 或 write_item(x) 執行之前, 必須先執行 lock_item(x) 動作在交易 T 中所有的 read_item(x) 或 write_item(x) 完成之後, 必須執行 unlock_item(x) 動作假如交易 T 已鎖定項目 X, 則不能再執行 lock_item(x) 動作除非交易 T 已鎖定項目 X, 否則 T 不能執行 unlock_item(x) 動作 6

4 二元鎖定的指令以下的程式碼是執行鎖定動作 : B: if LOCK (X) = 0 (*item is unlocked*) then LOCK (X) 1 (*lock the item*) else begin goto B end; wait (until lock (X) = 0) and the lock manager wakes up the transaction); 7 二元鎖定的指令以下的程式碼是執行解除鎖定動作 : LOCK (X) 0 (*unlock the item*) if any transactions are waiting then wake up one of the waiting the transactions; 8

5 共享 / 互斥鎖定共享 / 互斥鎖定 (shared/exclusive) 也稱作讀 / 寫鎖定 (read/write) 有 3 種鎖定指令 : read_lock(x): 讀取鎖定也稱為共享鎖定 (sharelocked), 因為此時其他交易也被允許能讀取這個被鎖定的項目 write_lock(x): 寫入鎖定也稱為互斥鎖定 (exclusivelocked), 因為只有單一交易能獨自擁有此項目的鎖定 unlock(x) 9 讀取鎖定的指令以下的程式碼是執行讀取鎖定動作 : B: if LOCK (X) = unlocked then begin LOCK (X) read-locked ; no_of_reads (X) 1; end else if LOCK (X) read-locked then no_of_reads (X) no_of_reads (X) +1 else begin wait (until LOCK (X) = unlocked and the lock manager wakes up the transaction); go to B end; 10

6 寫入鎖定的指令以下的程式碼是執行寫入鎖定動作 : B: if LOCK (X) = unlocked then begin LOCK (X) read-locked ; no_of_reads (X) 1; end else if LOCK (X) read-locked then no_of_reads (X) no_of_reads (X) +1 else begin wait (until LOCK (X) = unlocked and the lock manager wakes up the transaction); go to B end; 11 解除鎖定的指令以下的程式碼是執行解除鎖定動作 : if LOCK (X) = write-locked then begin LOCK (X) unlocked ; wakes up one of the transactions, if any end else if LOCK (X) read-locked then begin no_of_reads (X) no_of_reads (X) -1 if no_of_reads (X) = 0 then begin LOCK (X) = unlocked ; wake up one of the transactions, if any end end; 12

7 鎖定的轉換升級 (upgrade): 將目前的讀取鎖定變成寫入鎖定 if Ti has a read-lock (X) and Tj has no read-lock (X) (i j) then convert read-lock (X) to write-lock (X) else force Ti to wait until Tj unlocks X 降級 (downgrade): 將目前的寫入鎖定變成讀取鎖定 Ti has a write-lock (X) (*no transaction can have any lock on X*) convert write-lock (X) to read-lock (X) 13 兩階段鎖定協定的演算法遵守兩階段鎖定協定 (two-phase locking protocol, 簡稱 2PL) 的交易可分為兩個階段 : 擴展階段 (expanding phase): 或稱成長 (growing) 階段, 這是第一階段, 此階段中可鎖定新的資料項目, 但不能解除已存在的鎖定縮減階段 (shrinking phase) 階段 : 這是第二階段, 在此階段中可解除已存在的鎖定, 但無法鎖定新的項目這兩個階段必須互斥進行 14

8 T1 T2 結果 read_lock (Y); read_lock (X); 初值 :X=20; Y=30 read_item (Y); read_item (X); 循序排程先 T1 unlock (Y); unlock (X); 再 T2 的結果 : write_lock (X); Write_lock (Y); X=50, Y=80 read_item (X); read_item (Y); 循序排程先 T2 X:=X+Y; Y:=X+Y; 再 T1 的結果 : write_item (X); write_item (Y); X=70, Y=50 unlock (X); unlock (Y); 15 16

9 T 1 T 2 read_lock (Y); read_lock (X); 它們有遵守兩階段 read_item (Y); read_item (X); 鎖定協定請注意 write_lock (X); Write_lock (Y); 它們可能會導致死結 unlock (Y); unlock (X); read_item (X); read_item (Y); X:=X+Y; Y:=X+Y; write_item (X); write_item (Y); unlock (X); unlock (Y); 17 2PL 協定的類型基本型 (basic) 2PL: 交易會逐漸鎖定資料項目, 可能會造成死結保守型 (conservative)2pl: 在交易執行前先鎖定所有需要的資料項目嚴格型 (strict)2pl: 這是最常用的, 它的方式是交易 T 不會解除任何持有的互斥 ( 寫入 ) 鎖定, 直到交易 T 完成或中止為止所以在 T 完成之前, 其他交易都不能存取被 T 所寫入的項目精確型 (rigorous) 2PL 18

10 死結與飢餓現象的處理死結 T 1 T 2 read_lock (Y); (Y); 但是卻發生死結 read_lock (X); read_item (Y); write_lock (X); ( 等待 X) write_lock (Y); ( 等待 Y) 產生死結 (T 1 與 T 2) T1 和 T2 的確有遵循協定,read_item 19 死結預防死結預防協定的原則是每個交易事先將所有需要用的資料項加以鎖定交易時間戳記 (transaction timestamp,ts(t)) 的概念時間戳記是依據交易開始執行的順序來排序的, 因此如果交易 T1 在交易 T2 之前開始執行, 則 TS(T1) < TS(T2) 以這個觀念為基礎, 發展出兩種預防死結的方法稱為 wait-die 與 wound-wait 20

11 死結偵測它的做法是檢查系統是否處於死結的狀態, 因此適用在事先知道交易彼此間的干擾很小的時候, 也就是很少有不同的交易同時存取相同的資料項目時有種偵測系統死結狀態的簡單方法是建構等待圖 (wait-for graph) 當交易 Ti 嘗試鎖定的資料項目 X 目前正被交易 Tj 鎖定時, 就會在等待圖中建立一條邊 (Ti Tj) 如果等待圖中的邊會形成圓圈時, 就代表有死結狀況發生 21 飢餓現象使用鎖定機制另一個可能發生的問題是飢餓現象 (Starvation) 這種情況發生在當某個交易無止盡的一直在等待執行, 但系統裡的其他交易卻能正常進行時假如等待機制的設計會讓某些交易優先權高於其他交易時, 就可能會發生飢餓現象解決飢餓現象的方法之一就是使用公平的等待機制 ( 例如 FCFS ), 或者是讓等待越久的交易有越高的優先權 22

12 時間戳記排序演算法基本時間戳記排序法 (Basic TO) 1. 交易 T 執行一個 write_item(x) 動作 : a. 假如 read_ts(x) > TS(T) 或 write_ts(x) > TS(T), 則將 T 中止並撤回, 而且拒絕此動作 b. 若沒有發生 (a) 的狀況, 則執行 T 的 write_item(x) 動作, 並設定 write_ts(x) 等於 TS(T) 2. 交易 T 執行一個 read_item(x) 動作 : a. 假如 write_ts(x) > TS(T), 則將 T 中止並撤回, 而且拒絕此動作 b. 若 write_ts(x) TS(T), 則執行 T 的 read_item(x) 動作, 並設定 read_ts(x) 的值為 TS(T) 與 read_ts(x) 目前值較大者 23 樂觀的並行控制技術樂觀的 (optimistic) 並行控制技術, 在交易執行當中不需要作任何的檢查動作它的基本觀念是交易的更新動作並非直接對資料庫項目進行修改, 而是對項目的複製版本 (copy) 進行修改, 等到交易結束時再去檢查這些更新動作是否符合可循序性確認符合時再從副本更新到資料庫中, 否則交易將中止 24

13 樂觀的並行控制協定這種並行控制協定有 3 個階段 : 1. 讀取階段 (Read phase): 交易可以從資料庫中讀取資料項但是更新資料項的動作只會更新到交易工作區的副本上 2. 確認階段 (Validation phase): 執行檢查, 確保交易更新至資料庫的動作沒有違反可循序性 3. 寫入階段 (Write phase): 如果確認階段成功, 交易的更新資料會被存入資料庫 ; 否則將取消更新動作, 且交易將重新開始 25 資料項目的鎖定範圍大小所有並行控制技術都是控制資料庫中的資料項目, 例如一筆記錄記錄中的一個欄位值一個磁碟區塊一整個檔案, 甚至於整個資料庫資料項目的大小通常稱為資料項目範圍大小 (data item granularity) 最佳的資料項目範圍大小是根據交易型態的需求來決定如果交易經常存取小量的記錄, 則鎖定範圍以記錄為單位會比較好相反的, 如果交易經常存取同檔案中的多筆記錄, 則以區塊或檔案為鎖定範圍, 會比以記錄為鎖定範圍來得好 26

14 多層範圍鎖定下圖展示鎖定範圍大小的階層架構, 從最大 ( 資料庫 ) 到最小 ( 記錄 ) DB f1 p11 p12... p1n f2 p11 p12... p1n r r11j r r11j r r11j r r11j r r11j r r11j 27 回復技術的概念將資料庫回復到最接近交易失敗發生之前的狀態交易進行時所有資料項修改的資訊, 而這些資訊通常是保存在上一章講過的系統日誌 (system log) 中 28

15 回復策略典型的回復策略如下 1. 如果資料庫錯誤是由毀壞性的故障引起的嚴重損毀, 如磁碟毀損, 則回復方法是將資料庫系統之前在不同儲存裝置 ( 通常是磁帶 ) 的備份檔, 重新回存到資料庫系統中, 並根據系統記錄重做 (redo) 已交付交易的動作 29 回復策略 2. 假如資料庫不是實體上的損壞, 而是資料不一致, 此時的回復策略是取消 (undo) 某些動作來消除不一致的現象, 有時也會需要重做 (redo) 這時候並不需要完整的資料庫檔案備份, 而是需要系統記錄中所儲存的項目 30

16 回復技術資料不一致這類交易故障所採用的資料庫回復技術可分為兩種 : 延遲更新 : 在交易達到交付點之前並不需要更新資料, 而是將所有的更新保留在資料庫中等交付時將更新資料先記錄在系統記錄中, 然後再將實際的資料變更寫入資料庫如果交易在交付點之前發生錯誤, 此時不需要做 UNDO 的動作, 而是需要利用 REDO 將系統記錄中所記錄的更新動作重新執行因此, 延遲更新也被稱為 NO- UNDO/REDO 演算法 31 回復技術立即更新 : 在交易到達交付點之前, 交易動作可能已經更動資料庫因此在回復過程中, 取消和重做都是必要的, 所以它也被稱為 UNDO/REDO 演算法此種演算法還有一種變型, 就是在交易交付之前, 所有的更新會先被記錄在資料庫中, 由於它只需要復原 (UNDO), 因此被稱為 UNDO/NO-REDO 演算法 32

17 回存磁碟的策略修改過的資料要存回磁碟時, 有兩個主要策略 : 就地更新 (in-place updating): 將項目寫入到相同的磁碟位置, 因此磁碟上的舊值會被新值覆寫 (overwrite) 所以在磁碟中每個項目只會保留一份副本投影 (shadowing): 將項目的新值寫入到不同的磁碟位置, 所以同一項目可以保留多份副本通常更新前的舊值被稱為前像 (before image,bfim), 而在更新後的新值被稱為後像 (after image,afim) 33 寫前記錄回復機制必須確定資料項的 BFIM 有被記錄在適當的日誌記錄中, 而且此記錄在 BFIM 被 AFIM 覆寫之前, 會被先寫入磁碟中這個過程通常被稱為寫前記錄 (writeahead logging,wal) 每個寫入動作必須記錄兩種資料,UNDO 所需的記錄資料以及 REDO 所需的記錄資料 : REDO 類型的記錄資料是指對應到某個含有項目新值 (AFIM) 的記錄 UNDO 類型的記錄包括此項目的舊值 (BFIM) 34

18 以延遲更新為基礎的回復技術典型的延遲更新協定 : 1. 在交易到達交付點之前, 此交易不能改變資料庫的記錄 2. 在交易中所有的更新動作都被記錄到日誌記錄, 而且日誌記錄被強制寫入磁碟之前, 交易不會到達交付點因為直到交易被交付之前, 資料庫都不會被更新, 所以沒有必要做 UNDO 的動作, 因此這種技術被稱為 NO-UNDO/REDO 演算法 35 RDU_S 程序 RDU_S (Recovery using Deferred Update in a Singleuser environment) 是使用 REDO 程序, 也就是重做某些 write_item 的動作 REDO 程序的定義如下 : REDO(WRITE_OP): 重做 write_item 動作 WRITE_OP, 其中包括檢查日誌記錄項目 [write_item,t,x,new_value], 並將資料庫中項目 X 的值設定為 new_value, 也就是後像 (AFIM) 36

19 37 RDU_M 程序 RDU_M (Recovery using Deferred Update in a Multiuser environment) 針對多使用者資料庫系統此程序採用 REDO 程序使用兩個交易清單, 一個是從上一個檢查點之後已交付的交易 T, 另一個是執行中的交易 T 針對在日誌記錄中已交付交易的所有 WRITE 動作, 依照動作被寫入日誌記錄的順序, 執行 REDO 動作正在執行中而且尚未交付的交易將被取消, 並且必須重新被傳送 38

20 39 40

21 投影分頁功能投影分頁功能是將資料庫視為由一些固定大小的磁碟分頁 ( 或磁碟區塊 ) 所組成建構一個具有 n 個項目的目錄, 其中第 i 個項目是指向磁碟的第 i 個資料庫分頁執行 write_item 動作時, 會建立被修改分頁的一份新副本, 但是該分頁的舊副本不會被覆寫目前的分頁表格項目會被修改成指向新的磁碟區塊, 但投影目錄不會被修改, 繼續指向原來未修改過的磁碟區塊 41 42

22 學習評量何謂兩階段鎖定 (2PL) 協定? 它如何保證可循序性? 請說明死結 (deadlock) 與飢餓現象 (starvation), 以及處理這些問題的方法何謂時間戳記? 系統如何產生時間戳記? 樂觀的並行控制技術在做法上與其他並行控制技術的差別為何? 為何它被稱為樂觀或認證技術? 請列出樂觀並行控制方法的基本階段何謂意圖鎖定? 請描述投影分頁回復技術 43

PowerPoint Presentation

PowerPoint Presentation 第十三章交易管理和並行控制資料庫系統設計理論李紹綸著交易管理 (Transaction Management) 交易的 ACID 四大特性交易狀態 (Transaction States) 錯誤回復 (Failure Recovery) 錯誤的種類 (Types of Failures) 錯誤回復的處理 (Process of Failure Recovery) 為何需要並行控制排程的循序性