1、第七章事務(wù)管理,1.恢復(fù)引論 2.運(yùn)行記錄的結(jié)構(gòu) 3.更新事務(wù)的執(zhí)行與恢復(fù) 4.易地更新恢復(fù)技術(shù) 5.消息的處理 6.失效的類型及恢復(fù)的對策 7.并發(fā)控制引論 8.加鎖協(xié)議 9.死鎖的檢測處理和防止 10.多粒度封鎖 11.索引的并發(fā)控制 12.幽靈及其防止 13.事務(wù)的隔離等級 14.基于時(shí)間標(biāo)記的并發(fā)控制技術(shù) 15.樂觀并發(fā)控制技術(shù),1.恢復(fù)引論,1.單純以后備復(fù)本為基礎(chǔ)的恢復(fù)技術(shù) 2.以后備復(fù)本和運(yùn)行記錄(log或journal)為基礎(chǔ)的恢復(fù)技術(shù) 3.基于多復(fù)本的恢復(fù)技術(shù),1.單純以后備復(fù)本為基礎(chǔ)的恢復(fù)技術(shù) 從文件系統(tǒng)借鑒過來的恢復(fù)技術(shù),定期轉(zhuǎn)儲(dump)數(shù)據(jù)庫到磁帶上. 磁帶上的數(shù)據(jù)

2、庫復(fù)本稱為后備復(fù)本. 具體有兩種方式:(也稱為靜態(tài)恢復(fù)技術(shù)) 1)利用后備復(fù)本恢復(fù)數(shù)據(jù)庫 2)利用后備復(fù)本加增量轉(zhuǎn)儲(incremental dumping,ID)恢復(fù)數(shù)據(jù)庫 更新丟失 取后備復(fù)本 取后備復(fù)本 取后備復(fù)本 取后備復(fù)本 利用后備復(fù)本恢復(fù)數(shù)據(jù)庫 取后備復(fù)本 ID ID 利用后備復(fù)本加增量轉(zhuǎn)儲,上述方式的缺點(diǎn): 1)取后備復(fù)本時(shí)間開銷太大. 2)備份時(shí),數(shù)據(jù)庫系統(tǒng)必須凍結(jié),影響數(shù)據(jù)庫的正常工作. 3)恢復(fù)時(shí),不能恢復(fù)到最近的數(shù)據(jù)庫一致狀態(tài).,2.以后備復(fù)本和運(yùn)行記錄(log或journal)為基礎(chǔ)的恢復(fù)技術(shù)(動態(tài)恢復(fù)技術(shù)) 運(yùn)行記錄是數(shù)據(jù)庫運(yùn)行情況的記錄,是數(shù)據(jù)庫恢復(fù)的依據(jù),它的主要

3、內(nèi)容: 1)前像(before image,BI): 當(dāng)數(shù)據(jù)庫被一個事務(wù)更新時(shí),所涉及的物理塊更新前的影像(image),稱 為該事務(wù)的前像BI,是撤消事務(wù)的手段,是undo操作的保證. 2)后像(after image,AI): 當(dāng)數(shù)據(jù)庫被一個事務(wù)更新時(shí),所涉及的物理塊更新后的影像(image),稱 為該事務(wù)的后像BI,是事務(wù)恢復(fù)的手段,是redo操作的保證. 3)事務(wù)狀態(tài): 記錄每個事務(wù)的狀態(tài)(提交或滾回,commit or rollback),以便在恢復(fù)時(shí)做不同的處理.,1.圖示:BI和AI() BI (T) AI(T) 2.ER圖說明:,事務(wù)T,物理塊,物理塊,物理塊,物理塊,物理塊,

4、物理塊,圖示事務(wù)狀態(tài)變遷: 運(yùn)行記錄 最近后備復(fù)本 段點(diǎn) 以后備復(fù)本和運(yùn)行記錄為基礎(chǔ)的恢復(fù),活動狀態(tài),操作結(jié)束,事務(wù)提交,事務(wù)失敗,滾回,事務(wù)結(jié)束,3.基于多復(fù)本的恢復(fù)技術(shù) 獨(dú)立失效模式(independent failure mode): 各個數(shù)據(jù)復(fù)本不會因同一故障而一起失效. 磁盤鏡像(disk mirror or mirrored disks)技術(shù):,磁盤1,控制器1,CPU1,磁盤2,控制器2,CPU2,2.運(yùn)行記錄(日志)的結(jié)構(gòu),1.活動事務(wù)表(active transaction list, ATL): 記錄所有正在執(zhí)行,尚未提交的事務(wù)(TID) 2.提交事務(wù)表(committed

5、 transaction list, CTL): 記錄所有已提交的事務(wù)(TID) 3.前像文件(BI file): 所有前像的集合. undo操作: undo(undo(undo(x)=undo(x) 等冪性 4.后像文件(AI file): 所有后像的集合. redo操作: redo(redo(redo(x)=redo(x) 等冪性 減少存儲冗余的措施: 1)不保留已提交事務(wù)的前像 2)有選擇性地保留后像 3)合并后像,3.更新事務(wù)的執(zhí)行與恢復(fù),1.提交規(guī)則(commit rule): 后像必須在事務(wù)提交前寫入非易失存儲器中,即寫入數(shù)據(jù)庫或運(yùn)行記錄中(日志). 2.先記后寫規(guī)則(log ah

6、ead rule): 如果后像在事務(wù)提交前寫入數(shù)據(jù)庫,則必須將前像先寫入運(yùn)行記錄(日志). 具體實(shí)施的不同方案與分析: 1)后像在事務(wù)提交前完全寫入數(shù)據(jù)庫: 步驟如下: (1) TIDATL (2) BILOG (3) AIDB (4) TIDCTL (5) 從ATL刪除TID,2)后像在事務(wù)提交后才寫入數(shù)據(jù)庫: 步驟如下: (1) TIDATL (2) AILOG (3) TIDCTL (4) AIDB (5) 從ATL刪除TID 3)后像在事務(wù)提交前后寫入數(shù)據(jù)庫: 步驟如下: (1) TIDATL (2) AI,BILOG (3) AIDB(部分寫入) (4) TIDCTL (5) AID

7、B(繼續(xù)完成) (5) 從ATL刪除TID,6.失效的類型及恢復(fù)的對策,失效的類型: 1.事務(wù)失效 1)事務(wù)因無法執(zhí)行而自行夭折 2)操作員因錯誤或改變主意而要求撤消事務(wù) 3)由于系統(tǒng)調(diào)度原因而終止某些事務(wù)的執(zhí)行 2.系統(tǒng)失效 1)掉電 2)除數(shù)據(jù)庫存儲介質(zhì)故障以外的軟 3.介質(zhì)失效 主要指磁盤故障 恢復(fù)的對策: 1.事務(wù)失效的恢復(fù)的對策: 1)MM丟棄該事務(wù)的消息隊(duì)列 2)如果需要,進(jìn)行undo操作 3)從ATL刪除該事務(wù)的TID,釋放該事務(wù)所占的資源 2.系統(tǒng)失效的恢復(fù)的對策: 1)restart OS and DBMS 2)恢復(fù)數(shù)據(jù)庫到一致狀態(tài) 3.介質(zhì)失效的恢復(fù)的對策: 1)修復(fù)系統(tǒng),

8、必要時(shí)更換磁盤 2)如果系統(tǒng)崩潰,restart OS or DBMS 3)加載最近后備復(fù)本 4)用運(yùn)行記錄中的后像,重做最近后備復(fù)本以后提交的所有事務(wù),7.并發(fā)控制引論,主要問題: 1.為什么要并發(fā)? 2.不加控制的并發(fā)會產(chǎn)生什么問題? 3.什么樣的并發(fā)是正確的? 4.如何產(chǎn)生正確的并發(fā)? 1.數(shù)據(jù)庫系統(tǒng)中的并發(fā) 2.并發(fā)的目的 3.并發(fā)所引起的問題 4.并發(fā)控制的正確性,1.數(shù)據(jù)庫系統(tǒng)中的并發(fā) 串行訪問(serial access): 如果事務(wù)執(zhí)行順序,嚴(yán)格按照一個完全結(jié)束后,才開始另一個事務(wù)的 執(zhí)行. 并發(fā)訪問(concurrent access): 如果事務(wù)執(zhí)行順序,可以同時(shí)進(jìn)行,也就

9、是說,事務(wù)在時(shí)間上可以重疊進(jìn)行. 根據(jù)CPU的多少,分為兩種方式: 1)單CPU:交叉并發(fā)(interleaved concurrency) 2)多CPU:同時(shí)并發(fā)(simultaneous concurrency) T3 T2 T1 T1 T2 T3,DBMS,DBMS,2.并發(fā)的目的: 目的: 1)改善系統(tǒng)的資源利用率和吞吐率(throughput,單位時(shí)間內(nèi)處理的事 務(wù)數(shù)) 2)改善短事務(wù)的響應(yīng)時(shí)間 并發(fā)控制的特點(diǎn): (1) 共享對象多: 操作系統(tǒng)中并發(fā)事務(wù)的共享對象是軟、硬件部件和設(shè)備，它的數(shù)量少。在 數(shù)據(jù)庫系統(tǒng)中并發(fā)事務(wù)的共享對象是數(shù)據(jù)庫中的數(shù)據(jù)，它的數(shù)量大。 (2) 共享對象是動態(tài)

10、變化的: 數(shù)據(jù)庫中數(shù)據(jù)是隨時(shí)間變化，而操作系統(tǒng)的軟、硬件部件和設(shè)備一般是不 變的或變化很小。 (3) 共享對象不能命名: 數(shù)據(jù)庫系統(tǒng)中并發(fā)事務(wù)的共享對象的確定是根據(jù)“值”數(shù)據(jù)庫的內(nèi)容確 定，而操作系統(tǒng)的對象是根據(jù)名字確定的。 上述特點(diǎn)使數(shù)據(jù)庫系統(tǒng)的并發(fā)控制比操作系統(tǒng)更復(fù)雜、更困難。,3.并發(fā)所引起的問題 例:飛機(jī)定票系統(tǒng) 說明 事務(wù)如果不加控制地并發(fā)執(zhí)行,會產(chǎn)生如下的三個問題: 1)丟失更新(lost update) 2)讀臟數(shù)據(jù)(dirty read) 3)讀值不可復(fù)現(xiàn)(unrepeatable read) 丟失更新 讀臟數(shù)據(jù),讀值不可復(fù)現(xiàn),4.并發(fā)控制的正確性 設(shè):事務(wù)集TT1,T1,TN

11、,調(diào)度( schedule ) S 用W表示write ,R表示read ,則調(diào)度S可表示如下: S=R1(X)W2(Y)W1(X) S1,S2,SN 表示N個不同的調(diào)度,對同一個事務(wù)集T,可能有很多種調(diào)度 概念: 1)等價(jià)調(diào)度: 如果兩個調(diào)度S1,S2,在數(shù)據(jù)庫的任何初始狀態(tài)下,所讀出的數(shù)據(jù)都是一樣的, 留給數(shù)據(jù)庫的最終狀態(tài)也是一樣的.則稱S1和S2是等價(jià)的. 2)目標(biāo)等價(jià)(result equivalence):上述等價(jià)也稱為目標(biāo)等價(jià). 3)沖突等價(jià)(conflict equivalence): 沖突操作:不同事務(wù)的一對操作,有些是沖突的,有些是不沖突的. 沖突操作的分類: 讀-寫沖突:

12、Ri(x)Wj(x) 寫-寫沖突: Wi(x)Wj(x) 不沖突操作的分類: 讀-讀: Ri(x)Rj(x) 寫-寫: Wi(x)Wj(y) 通過調(diào)換S中不沖突操作所得的新調(diào)度S,稱為S的沖突等價(jià)調(diào)度 推論: 如果兩個調(diào)度是沖突等價(jià)的,一定是目標(biāo)等價(jià)的.反之不一定成立. 4)串行調(diào)度:事務(wù)按照某種順序一個事務(wù)一個事務(wù)依次執(zhí)行的調(diào)度 5)調(diào)度的可串行化: 對于事務(wù)集T,如果一個調(diào)度與另一個串行調(diào)度等價(jià),則稱此調(diào)度是可串行化(serializable)的調(diào)度 6)并發(fā)控制的正確性準(zhǔn)則: 對于事務(wù)集T,如果一個調(diào)度S與另一個串行調(diào)度S等價(jià),則稱此調(diào)度是正確的,也稱為并發(fā)控制的正確性準(zhǔn)則.,說明: 1

13、.如果兩個調(diào)度是沖突等價(jià)的,一定是目標(biāo)等價(jià)的 T=T1,T2,T3 S=R2(X)W3(X)R1(Y)W2(Y) 因?yàn)?S-R2(X)R1(Y)W3(X)W2(Y)- R1(Y)R2(X)W3(X)W2(Y) - R1(Y)R2(X)W2(Y)W3(X)=S S是串行調(diào)度,S是沖突可串行化的 另外S和S也是目標(biāo)等價(jià)的,S也是目標(biāo)可串行化的. 2.反之不一定成立(目標(biāo)可串行化的調(diào)度不一定是沖突可串行化的) 如: S=R1(X)W2(X)W1(X)W3(X) S不是沖突可串行化的,但S是目標(biāo)可串行化的 S= R1(X)W1(X)W2(X)W3(X),調(diào)度的可串行化的判斷: 前趨圖判定法: 前趨圖是

14、個有向圖G=,其中V是結(jié)點(diǎn)的集合,E是邊的集合 V包含所有參與調(diào)度的事務(wù),E可以通過分析沖突操作來決定,具體確定邊TiTj的方法如下: 1)Ri(x)在 Wj(x) 之前 2)Wi(x)在 Rj(x) 之前 3)Wi(x)在Wj(x)之前 判定方法: 如果調(diào)度S所構(gòu)成的圖G有回路,則S不等價(jià)于任何串行調(diào)度,也就是說 S不是可串行化的調(diào)度.如果圖G無回路,則可找到一個等價(jià)的串行化 調(diào)度,例:設(shè)有事務(wù)集T=T1,T2,T3,T4的一個調(diào)度 S=W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) 試檢驗(yàn)S是否可串行化,若是可串行化的,找出其等價(jià)的串行調(diào)度. 解: T2

15、T1 T4 T3 圖G無回路,所以S是可串行化的,其等價(jià)的串行調(diào)度是T1,T3,T2,T4,8.加鎖協(xié)議,概述: 鎖的基本概念 (1) 鎖:所謂鎖是指當(dāng)一個事務(wù)對某些對象進(jìn)行操作時(shí)，對其它事務(wù)在該對象上的操作的某些 限制（封鎖）。不同類型的鎖限制的程度不一樣。一般的數(shù)據(jù)庫有三類基本鎖：排它鎖、共享鎖、共享修改鎖。 (2) 封鎖過程 申請鎖：一個事務(wù)為了獲得對一個對象操作的權(quán)力，它必須首先向系統(tǒng)的鎖管理部件申請獲得對對象進(jìn)行封鎖的權(quán)力。 上鎖：一個事務(wù)獲得封鎖的權(quán)力后，具體執(zhí)行相應(yīng)的封鎖。 解鎖：撤消一個事務(wù)對一個對象的封鎖。 (3) 鎖的粒度 所謂鎖的粒度是指一把鎖封鎖的范圍大小。如前所述數(shù)據(jù)

16、庫對象根據(jù)范圍大小有如下的層次： * 數(shù)據(jù)庫（Database） * 表（Table、View） * 數(shù)據(jù)頁（Data Page） * 列（Column） * 行（Tuple） * 數(shù)據(jù)項(xiàng)（Data Item） 鎖粒度對并發(fā)性有一定的影響，同時(shí)也影響性能。鎖的粒度由整個數(shù)據(jù)庫到關(guān)系變量，最后到最小單元-數(shù)據(jù)項(xiàng)。 鎖粒度越小并發(fā)程度越高，可以提高整個系統(tǒng)性能，但粒度小鎖數(shù)量增加，管理負(fù)載（內(nèi)務(wù)操作）越重，也會降低系統(tǒng)性能。所粒度越大鎖數(shù)量減少，管理負(fù)載（內(nèi)務(wù)操作）越低，也會提高系統(tǒng)性能，但鎖粒度大并發(fā)程度越低，對性能有不利的影響。,可串行性和兩階段封鎖協(xié)議與兩階段事務(wù) 串行性原理有的文獻(xiàn)將其稱為

17、事務(wù)的可串行性特征。它通常是作為并發(fā)事務(wù)執(zhí)行的正確性原則，即當(dāng)且僅當(dāng)多個事務(wù)并發(fā)執(zhí)行時(shí)是可串行化時(shí)，它的執(zhí)行過程才是正確的。所謂可串行化是指多個事務(wù)并發(fā)執(zhí)行結(jié)果與同樣事務(wù)的某個串行執(zhí)行過程的結(jié)果相同。 為了保證多個事務(wù)并發(fā)并發(fā)執(zhí)行是可串性化數(shù)據(jù)庫并發(fā)控制中有一個重要的理論：兩階段鎖協(xié)議。 (1) 兩階段封鎖協(xié)議(two-phase locking protocol) 兩階段封鎖協(xié)議為： * 在對任何一個對象進(jìn)行操作之前，事務(wù)必須獲得對該對象上的相應(yīng)鎖。 * 在釋放之后，事務(wù)不再獲得任何類型的鎖 遵守兩個階段鎖協(xié)議的事務(wù)分為兩個階段 * 上鎖（獲得）階段，也稱為擴(kuò)張階段 * 釋放鎖階段，也稱為收

18、縮階段 一般系統(tǒng)實(shí)現(xiàn)鎖的釋放（收縮階段）都是在事務(wù)結(jié)束時(shí)的單個操作：Commit或Rollback。 兩階段鎖協(xié)議是可串行化的充分條件，但不是必要條件。 (2) 兩階段事務(wù) 如果一個事務(wù)遵守兩階段鎖協(xié)議，稱其為兩階段事務(wù)。,1.X鎖(eXclusive,排他鎖): X鎖:用于讀和寫的封鎖 X鎖的相容矩陣(語義): X鎖的問題: 連鎖卷回 解決的方法:將讀寫操作的鎖保持到事務(wù)結(jié)束(EOT)時(shí),X鎖相容矩陣,2.兩階段封鎖協(xié)議 定義1:在一個事務(wù)中,如果加鎖動作都在所有釋放鎖動作之前,則稱此 事務(wù)為兩段事務(wù)(two-phase transaction),上述加鎖限制,也稱為 兩段封鎖協(xié)議. 定義2

19、:一個事務(wù)如果遵守先加鎖,后操作的原則,則此事務(wù)稱為合式事 務(wù). 定理:如果所有事務(wù)都是合式,兩段事務(wù),則它們的任何調(diào)度都是可串行 化的.,3.(S,X)鎖: S鎖(sharing locks):用于讀操作 X鎖:用于寫操作 相容矩陣(語義):(page 156圖7-19 ) 鎖的問題: 活鎖 解決的方法:先申請,先服務(wù),(S,X)鎖相容矩陣,4. (S,U,X)鎖 S鎖(sharing locks):用于讀操作 U鎖(updating locks):用于更新操作 X鎖:用于寫操作 相容矩陣:(page 159圖7-25 ),例:事務(wù)T1,T2如下:,事務(wù)T1,物理塊1,物理塊2,物理塊n,事

20、務(wù)T2,DBMS局部功能模擬實(shí)現(xiàn)的考慮,要求:根據(jù)描述,做一個系統(tǒng),模擬DBMS的局部功能 第一步:建立相關(guān)表:創(chuàng)建若干表,并給出數(shù)據(jù)字典 第二步:初始化 1.輸入可用的主存空間(可變),轉(zhuǎn)變?yōu)橹鞔嬷芯彌_區(qū)的塊 2.輸入磁盤空間(可變),轉(zhuǎn)變?yōu)榇疟P中的塊 3.分別給若干表輸入若干記錄(給表分配塊空間) 第三步:模擬緩沖區(qū)管理器的功能 1.給出一個無條件查詢,顯示主存緩沖區(qū)的情況 2.再給出另無條件一個查詢,采用緩沖區(qū)管理策略進(jìn)行換入換出 第四步:對各表進(jìn)行插入操作,如何申請塊,判斷塊空間,分配塊 第五步:功能延伸 1.各表均有索引(索引塊) 2.建立臨時(shí)表空間(或tempdb) 3.給出一個帶

21、條件的多表查詢,演示如何用索引進(jìn)行查詢 第六步:功能再延伸 1.事務(wù)機(jī)制的建立 2.在主存中建立鎖表空間 3.在磁盤中建立日志空間(AI,BI) 4.實(shí)現(xiàn)數(shù)據(jù)恢復(fù)機(jī)制,9.死鎖的檢測處理和防止,1.死鎖的檢測,處理 死鎖:事務(wù)間出現(xiàn)循環(huán)等待,如果不加干預(yù),則會一直等待,這種狀態(tài)稱為死鎖. 活鎖: 如果并發(fā)事務(wù)中存在大量的只讀事務(wù)，他們可能造成寫事務(wù)的長期等待，即 前一個只讀事務(wù)還未釋放S鎖后面的只讀事務(wù)又申請新的S鎖，這樣造成寫事 務(wù)長期不能申請到U（或X）鎖。這就是所謂的活鎖。解決活鎖的一個辦法是 寫事務(wù)在等待一定數(shù)量的讀事務(wù)后，系統(tǒng)不再允許新的只讀事務(wù)獲得S鎖。 死鎖的檢測: (1)超時(shí)法

22、:如果一個事務(wù)的等待時(shí)間超過某時(shí)間限制,則認(rèn)為發(fā)生死鎖. 問題:設(shè)定事務(wù)等待時(shí)間的閥值 2)等待圖法:通過維護(hù)一個有向圖,判定是否死鎖. 問題:維護(hù)和判斷的開銷太大.周期性地檢測,周期的大小. 死鎖的處理: DBMS對死鎖處理如下: 1)在循環(huán)等待的事務(wù)中,選一個事務(wù)作為犧牲(victim)者,kill 該事務(wù). 2)卷回犧牲的事務(wù),釋放其所獲得的鎖及其他資源. 3)將釋放的鎖分配給等待它的事務(wù). 犧牲事務(wù)的選擇依據(jù): 1)選擇最遲交付的事務(wù)作為犧牲者 2)選擇獲得鎖最少的事務(wù) 3)選擇卷回代價(jià)最小的事務(wù).,2.死鎖的防止: 時(shí)間標(biāo)記(time stamp ,ts ,也叫郵戳): DBMS給每個事務(wù)一個時(shí)間郵戳ts(T1), ts(T2), Ta:lock(x),lock(y), Tb: