數(shù)據(jù)庫保護PPT課件

1、事務(wù)概念 事務(wù)定義 事務(wù)是由一系列操作序列構(gòu)成的程序執(zhí)行單元，這些操作要么都做，要么都不做，是一個不可分割的工作單位。例如銀行轉(zhuǎn)帳。 SQL中事務(wù)的定義事務(wù)以Begin transaction開始，以Commit work或 Rollback work結(jié)束。Commit work表示提交，事務(wù)正常結(jié)束。Rollback work表示事務(wù)非正常結(jié)束，撤消事務(wù)已做的操作，回滾到事務(wù)開始時狀態(tài)。第1頁/共58頁事務(wù)概念 示例銀行轉(zhuǎn)帳：事務(wù)T從A帳戶過戶50￥到B帳戶。T：read(A);A := A 50;write(A);read(B);B := B + 50;write(B);read(X)：從

2、數(shù)據(jù)庫傳送數(shù)據(jù)項X到事務(wù)的工作區(qū)中。write(X)：從事務(wù)的工作區(qū)中將數(shù)據(jù)項X寫回數(shù)據(jù)庫。第2頁/共58頁事務(wù)概念 事務(wù)特性(ACID) 原子性(Atomicity)事務(wù)中包含的所有操作要么全做，要么全不做。原子性由恢復(fù)機制實現(xiàn)。 一致性(Consistency)事務(wù)的隔離執(zhí)行必須保證數(shù)據(jù)庫的一致性。事務(wù)開始前，數(shù)據(jù)庫處于一致性的狀態(tài)；事務(wù)結(jié)束后，數(shù)據(jù)庫必須仍處于一致性狀態(tài)。數(shù)據(jù)庫的一致性狀態(tài)由用戶來負責。如銀行轉(zhuǎn)帳，轉(zhuǎn)帳前后兩個帳戶金額之和應(yīng)保持不變（意大利香腸）。第3頁/共58頁事務(wù)概念 隔離性(Isolation)系統(tǒng)必須保證事務(wù)不受其它并發(fā)執(zhí)行事務(wù)的影響。對任何一對事務(wù)T1，T2，在

3、T1看來，T2要么在T1開始之前已經(jīng)結(jié)束，要么在T1完成之后再開始執(zhí)行。隔離性通過并發(fā)控制機制實現(xiàn)。 持久性(Durability)一個事務(wù)一旦提交之后，它對數(shù)據(jù)庫的影響必須是永久的。系統(tǒng)發(fā)生故障不能改變事務(wù)的持久性。持久性通過恢復(fù)機制實現(xiàn)。第4頁/共58頁事務(wù)狀態(tài)活動狀態(tài)活動狀態(tài)失敗狀態(tài)失敗狀態(tài)部分部分提交狀態(tài)提交狀態(tài)提交狀態(tài)提交狀態(tài)中止狀態(tài)中止狀態(tài)初始狀態(tài)初始狀態(tài)事務(wù)無法繼事務(wù)無法繼續(xù)正常執(zhí)行續(xù)正常執(zhí)行事務(wù)回滾，數(shù)據(jù)庫恢事務(wù)回滾，數(shù)據(jù)庫恢復(fù)到事務(wù)開始前狀態(tài)復(fù)到事務(wù)開始前狀態(tài)最后一條語最后一條語句被執(zhí)行后句被執(zhí)行后成功完成，永成功完成，永久寫入數(shù)據(jù)庫久寫入數(shù)據(jù)庫第5頁/共58頁并發(fā)執(zhí)行 并行

4、 Vs 串行 基本比較 并行事務(wù)會破壞數(shù)據(jù)庫的一致性。 串行事務(wù)效率低。 并行的優(yōu)點 一個事務(wù)由不同的步驟組成，所涉及的系統(tǒng)資源也不同。這些步驟可以并發(fā)執(zhí)行，以提高系統(tǒng)的吞吐量。 系統(tǒng)中存在著周期不等的各種事務(wù)，串行會導致難于預(yù)測的時延。如果各個事務(wù)所涉及的是數(shù)據(jù)庫的不同部分，采用并發(fā)會減少平均響應(yīng)時間。第6頁/共58頁并發(fā)執(zhí)行 核心問題在保證一致性的前提下最大限度地提高并發(fā)度。 事務(wù)執(zhí)行示例T1: read(A); A := A 50; write(A); read(B); B := B + 50; write(B);T2: read(A); temp := A0.1 A := A temp

5、; write(A); read(B); B := B + temp; write(B);從A過戶50￥到B從A過戶存款的10%到B開始狀態(tài)：A=1000￥B=2000￥A+B=3000￥第7頁/共58頁并發(fā)執(zhí)行 read(A); A := A 50; write(A); read(B); B := B + 50; write(B); read(A); temp := A0.1 A := A temp; write(A); read(B); B := B + temp; write(B);T1T2A=950￥B=2050￥結(jié)束狀態(tài)：A=855￥B=2145￥A+B=3000￥串串行行調(diào)調(diào)度度1

6、 1第8頁/共58頁并發(fā)執(zhí)行 read(A); A := A 50; write(A); read(B); B := B + 50; write(B); read(A); temp := A0.1 A := A temp; write(A); read(B); B := B + temp; write(B);T1T2A=900￥B=2100￥結(jié)束狀態(tài)：A=850￥B=2150￥A+B=3000￥串串行行調(diào)調(diào)度度2 2第9頁/共58頁并發(fā)執(zhí)行 事務(wù)的調(diào)度 事務(wù)的執(zhí)行順序稱為一個調(diào)度，表示事務(wù)的指令在系統(tǒng)中執(zhí)行的時間順序。 一組事務(wù)的調(diào)度必須保證 包含了所有事務(wù)的操作指令 一個事務(wù)中指令的順序必須

7、保持不變。 串行調(diào)度 在串行調(diào)度中，屬于同一事務(wù)的指令緊挨在一起。 對于有n個事務(wù)的事務(wù)組，可以有n！個有效調(diào)度。 并行調(diào)度 在并行調(diào)度中，來自不同事務(wù)的指令可以交叉執(zhí)行。 當并行調(diào)度等價于某個串行調(diào)度時，則稱它是正確的。第10頁/共58頁并發(fā)執(zhí)行 read(A); A := A 50; write(A); read(B); B := B + temp; write(B);T1T2A=950￥B=2000￥結(jié)束狀態(tài)：A=855￥B=2145￥A+B=3000￥ read(B); B := B + 50; write(B); read(A); temp := A0.1 A := A temp;

8、write(A); A=855￥B=2000￥A=855￥B=2050￥并并行行調(diào)調(diào)度度3第11頁/共58頁并發(fā)執(zhí)行 read(A); A := A 50; B := B + temp; write(B);T1T2A=1000￥B=2000￥結(jié)束狀態(tài)：A=950￥B=2100￥A+B=3050￥ write(A); read(B); B := B + 50; write(B); read(A); temp := A0.1 A := A temp; write(A); read(B); A=900￥B=2000￥A=950￥B=2000￥A=950￥B=2050￥并并行行調(diào)調(diào)度度4第12頁/共5

9、8頁并發(fā)執(zhí)行 SQL中一致性級別的定義 serializable：一個調(diào)度的執(zhí)行必須等價于一個串行調(diào)度的結(jié)果。 repeatable read：只允許讀取已提交的記錄，并要求一個事務(wù)對同一記錄的兩次讀取之間，其它事務(wù)不能對該記錄進行更新。 read committed：只允許讀取已提交的記錄，但不要求可重復(fù)讀。 read uncommitted：允許讀取未提交的記錄。第13頁/共58頁并發(fā)執(zhí)行read(A);A1 := A;read(B);B1 := B;A1 + B1 = 2950;read(B);B := B + 50;write(B);T1T2A=1000￥B=2000￥read(A);

10、A := A 50;write(A); 讀讀臟臟數(shù)數(shù)據(jù)據(jù)第14頁/共58頁并發(fā)執(zhí)行 read(A); A1 := AT1T2A=1000￥B=2000￥read(A);A := A 50;write(A); read(B);B := B + 50;write(B); 不不能能重重復(fù)復(fù)讀讀read(B);B1 := BA1+B1=3050A=950￥B=2050￥第15頁/共58頁并發(fā)執(zhí)行select *from SCwhere CNO = C01 and SNO = S01T1T2發(fā)生幻象insert into SC values(S01, C01, null)第16頁/共58頁可恢復(fù)性事務(wù)的

11、恢復(fù)：一個事務(wù)失敗了，應(yīng)該能夠撤消該事務(wù)對數(shù)據(jù)庫的影響。如果有其它事務(wù)讀取了失敗事務(wù)寫入的數(shù)據(jù)，則該事務(wù)也應(yīng)該撤消。 可恢復(fù)調(diào)度read(A);write(A);T1T2read(B);commit;read(A);commit不可恢復(fù)的調(diào)度不可恢復(fù)的調(diào)度可恢復(fù)調(diào)度：可恢復(fù)調(diào)度：對于每對事務(wù)對于每對事務(wù)T1T1與與T2T2，如果如果T2T2讀取了讀取了T1T1所寫的數(shù)所寫的數(shù)據(jù)，則據(jù)，則T1T1必須先于必須先于T2T2提交提交第17頁/共58頁可恢復(fù)性 無級聯(lián)調(diào)度read(A);read(B);write(A);T1T2read(A)write(A);級聯(lián)調(diào)度：級聯(lián)調(diào)度：由于一個事務(wù)故障而由于

12、一個事務(wù)故障而導致一系列事務(wù)回滾導致一系列事務(wù)回滾無級聯(lián)調(diào)度：無級聯(lián)調(diào)度：對于每對事務(wù)對于每對事務(wù)T1T1與與T2T2，如果如果T2T2讀取了讀取了T1T1所寫的所寫的數(shù)據(jù)，則數(shù)據(jù)，則T1T1必須在必須在T2T2讀讀取之前提交取之前提交T2read(A)無級聯(lián)調(diào)度必是可恢復(fù)調(diào)度無級聯(lián)調(diào)度必是可恢復(fù)調(diào)度第18頁/共58頁可串行化如何判定并行調(diào)度與一個串行調(diào)度等價？ 沖突指令 指令的順序考慮一個調(diào)度S中的兩條連續(xù)指令（僅限于read與 write操作）Ii與Ij，分別屬于事務(wù)Ti與Tj，Ii = read(Q), Ij = read(Q)Ii = read(Q), Ij = write(Q)Ii

13、= write(Q), Ij = read(Q);Ii = write(Q), Ij = write(Q);在 情況下，Ii與Ij的次序無關(guān)緊要。其余情況下，Ii與Ij的次序不同，其執(zhí)行結(jié)果也不同，數(shù)據(jù)庫最終狀態(tài)也不同。第19頁/共58頁可串行化 沖突指令當兩條指令是不同事務(wù)在相同數(shù)據(jù)項上的操作，并且其中至少有一個是write指令時，則稱這兩條指令是沖突的。如在、情況下，Ii與Ij 是沖突的。非沖突指令交換次序不會影響調(diào)度的最終結(jié)果。 沖突等價如果調(diào)度S可以經(jīng)過一系列非沖突指令交換轉(zhuǎn)換成調(diào)度S，則稱調(diào)度S與S是沖突等價的。第20頁/共58頁可串行化read(A);write(A);read(B

14、);write(B);T1T2read(B); write(B);并并行行調(diào)調(diào)度度3read(A);write(A);read(A);write(A);read(B);write(B);T1T2write(B);read(A);write(A);read(B);read(A);write(A);read(B);write(B);write(B);read(A);write(A);read(B);read(A);write(A);read(B);write(B);write(B);read(A);write(A);read(B);第21頁/共58頁可串行化 沖突可串行化當一個調(diào)度S與一個串行調(diào)度

15、沖突等價時，則稱該調(diào)度是沖突可串行化的。如并行調(diào)度3是沖突可串行化的。read(A);T1T2write(A);write(A);非沖突串行化的例子：存在結(jié)果相同，但非沖突等價的調(diào)度。第22頁/共58頁可串行化read(A);A := A - 50write(A);T1T2沖突指令沖突指令T1T2read(B);B := B - 10write(B);read(B);B := B + 50write(B);read(A);A := A + 10write(A);read(A);A := A - 50write(A);read(B);B := B + 50write(B);read(B);B :

16、= B - 10write(B);read(A);A := A + 10write(A);A=950￥B=2000￥A=950￥B=1990￥A=950￥B=2040￥A=960￥B=2040￥A=960￥B=2040￥A=950￥B=2050￥第23頁/共58頁可串行化 視圖可串行化考慮關(guān)于某個事務(wù)集的兩個調(diào)度S，S，若調(diào)度S，S滿足以下條件，則稱它們是視圖等價的：對于每個數(shù)據(jù)項Q，若事務(wù)Ti在調(diào)度S中讀取了Q的初始值，那么Ti在調(diào)度S中也必須讀取Q的初始值。對于每個數(shù)據(jù)項Q，若事務(wù)Ti在調(diào)度S中執(zhí)行了read(Q)，并且讀取的值是由Tj產(chǎn)生的，那么Ti在調(diào)度S中讀取的Q值也必須是由Tj產(chǎn)生

17、的。對于每個數(shù)據(jù)項Q，若在調(diào)度S中有事務(wù)執(zhí)行了最后的write(Q)，則在調(diào)度S中該事務(wù)也必須執(zhí)行最后的write(Q)。第24頁/共58頁可串行化注：條件、保證兩個調(diào)度中的每個事務(wù)都讀取相同的值，從而進行相同的計算；條件、保證兩個調(diào)度得到最終相同的系統(tǒng)狀態(tài)。 read(A);write(A); read(B);write(B);read(A);write(A); read(B);write(B);T1T2 read(A);write(A); read(B);write(B);read(A);write(A); read(B);write(B);T1T2由由T1T1產(chǎn)生的產(chǎn)生的A A值值調(diào)度執(zhí)

18、行前的調(diào)度執(zhí)行前的A A值值非視圖等價非視圖等價第25頁/共58頁可串行化 read(A);write(A); read(B);write(B);read(A);write(A); read(B);write(B);T1T2read(B);write(B);read(A);write(A); T1T2由由T1T1產(chǎn)生的產(chǎn)生的A A值值 read(A);write(A);read(B);write(B);由由T1T1產(chǎn)生的產(chǎn)生的A A值值視圖等價視圖等價第26頁/共58頁可串行化 視圖可串行化 如果某個調(diào)度視圖等價于一個串行調(diào)度，則稱該調(diào)度是視圖可串行化的。 沖突可串行化調(diào)度一定是視圖可串行化的

19、。存在視圖可串行化但非沖突可串行化的調(diào)度。read(Q);T1T2write(Q);write(Q);write(Q);T3視圖等價視圖等價盲目寫操作盲目寫操作第27頁/共58頁可串行化 沖突可串行化判定 優(yōu)先圖(precedence graph)一個調(diào)度S的優(yōu)先圖是這樣構(gòu)造的：它是一個有向圖G =（V，E），V是頂點集，E是邊集。頂點集由所有參與調(diào)度的事務(wù)組成，邊集由滿足下述條件之一的邊Ti Tj組成：在Tj執(zhí)行read(Q)之前，Ti執(zhí)行write(Q)。在Tj執(zhí)行write(Q)之前，Ti執(zhí)行read(Q)。在Tj執(zhí)行write(Q)之前，Ti執(zhí)行write(Q)。第28頁/共58頁可串

20、行化T1T2并并行行調(diào)調(diào)度度3 3T1T2read(A);write(B);T1T2write(A);read(B); write(B);并并行行調(diào)調(diào)度度4read(A);write(A);read(B);T1T2read(A);write(A);read(B);write(B);read(B); write(B);read(A);write(A);第29頁/共58頁可串行化如果優(yōu)先圖中存在邊TiTj ，則在任何等價于S的串行調(diào)度S中，Ti都必須出現(xiàn)在Tj之前。 沖突可串行化判定準則如果調(diào)度S的優(yōu)先圖中有環(huán)，則調(diào)度S是非沖突可串行化的。如果圖中無環(huán)，則調(diào)度S是沖突可串行化的。T1T2T1T2并

21、行調(diào)度并行調(diào)度3 3是沖是沖突可串行化的突可串行化的并行調(diào)度并行調(diào)度4 4是非是非沖突可串行化的沖突可串行化的第30頁/共58頁可串行化 與沖突可串行化等價的串行順序串行順序可由拓撲排序得到，求出與優(yōu)先圖的偏序相一致的線序。T1T3T2T4T1T2T3T4T1T3T2T4第31頁/共58頁可串行化 視圖可串行化判定read(Q);T1T2write(Q);write(Q);write(Q);T3T1T2T3無用的寫操作無用的寫操作第32頁/共58頁可串行化 帶標記的優(yōu)先圖的構(gòu)造設(shè)調(diào)度S包含了事務(wù)T1, T2, , Tn，設(shè)Tb, Tf是兩個虛事務(wù)，其中Tb為S中所有write(Q)操作， Tf

22、為S中所有read(Q)操作。在調(diào)度S的開頭插入Tb ，在調(diào)度S的末尾插入Tf，得到一個新的調(diào)度S。如果Tj讀取Ti寫入的數(shù)據(jù)項的值，則加入邊Ti Tj。刪除所有關(guān)聯(lián)無用事務(wù)的邊。如果在優(yōu)先圖中不存在從Ti到Tf的通路，則Ti是無用事務(wù)。對于每個數(shù)據(jù)項Q，如果Tj讀取Ti讀取寫入的Q值， Tk執(zhí)行write (Q)操作且TkTb ，則： 0第33頁/共58頁可串行化如果Ti = Tb且TjTf，則在帶標記的優(yōu)先圖中插入邊Tj Tk 。如果TiTb且Tj = Tf，則在帶標記的優(yōu)先圖中插入邊Tk Ti 。如果TiTb且TjTf，則在帶標記的優(yōu)先圖中插入邊Tk Ti與Tj Tk 。其中p是一個唯一

23、的，在前面邊的標記中未曾用過的大于0的整數(shù)。 0 0 p p第34頁/共58頁可串行化read(A);T1T2write(A);write(A);T1TfTbT20000第35頁/共58頁可串行化read(Q);T1T2write(Q);write(Q);write(Q);T3T1T2T3Tb0Tf0000第36頁/共58頁可串行化read(Q);T1T2write(Q);write(Q);write(Q);T3T1T2T3Tb0Tf0000read(Q);11第37頁/共58頁可串行化T1T2T3Tb0Tf00001T1T2T3Tb0Tf00001第38頁/共58頁并發(fā)控制 封鎖的定義 封鎖

24、就是一個事務(wù)對某個數(shù)據(jù)對象加鎖，取得對它一定的控制，限制其它事務(wù)對該數(shù)據(jù)對象使用。 并發(fā)控制的基本方法就是封鎖。 封鎖的類型 排它鎖（X鎖，eXclusive lock）：事務(wù)T對數(shù)據(jù)對象R加上X鎖，則其它事務(wù)對R的任何封鎖請求都不能成功，直至T釋放R上的X鎖。 共享鎖（S鎖，Share lock）：事務(wù)T對數(shù)據(jù)對象R加上S鎖，則其它事務(wù)對R的X鎖請求不能成功，而對R的S鎖請求可以成功。第39頁/共58頁并發(fā)控制相容矩陣相容矩陣相容請求相容請求不相容請求不相容請求T1 T2XSXNNSNY第40頁/共58頁并發(fā)控制 封鎖粒度 封鎖對象：屬性值、屬性值幾何、元組、關(guān)系、某索引項、整個索引、整個數(shù)

25、據(jù)庫、物理頁、塊。 封鎖粒度大，則并發(fā)度低，封鎖機構(gòu)簡單，開銷小。封鎖粒度小，則并發(fā)度高，封鎖機構(gòu)復(fù)雜，開銷高。 理想的情況是只封鎖與規(guī)定的操作有關(guān)的的數(shù)據(jù)對象，這些數(shù)據(jù)對象稱作事務(wù)的完整性相關(guān)域。第41頁/共58頁并發(fā)控制 封鎖協(xié)議 保持到事務(wù)結(jié)束時才釋放的鎖稱作長鎖。在事務(wù)中途就可以釋放的鎖稱作短鎖。0級封鎖協(xié)議級封鎖協(xié)議BEGIN短X鎖EOTlock-X(A);read(A);A := A 50;write(A); rollback；read(A);A1 := A; T1 T2 不能保證不能保證孤立退出孤立退出第42頁/共58頁并發(fā)控制1級封鎖協(xié)議級封鎖協(xié)議BEGIN長X鎖EOTread

26、(A);A1 := A 1;lock-X(A);A := A1 1;write(A); commit；lock-X(A)read(A);A := A 1;write(A)；commit； T1 T2 不能保證不能保證丟失修改丟失修改第43頁/共58頁并發(fā)控制2級封鎖協(xié)議級封鎖協(xié)議BEGIN 短S鎖長X鎖EOTlock-S(A); read(A);A1 := A;unlock(A);lock-S(A); read(A);A1 := A;unlock(A);commit；lock-X(A)read(A);A := A 1;write(A)；commit； T1 T2 不能保證不能保證可重復(fù)讀可重復(fù)

27、讀第44頁/共58頁并發(fā)控制3級封鎖協(xié)議級封鎖協(xié)議BEGIN 長S鎖長X鎖EOT第45頁/共58頁并發(fā)控制 封鎖方法 直接封鎖事務(wù)對它要進行存取的數(shù)據(jù)對象直接申請加鎖。已有的封鎖方式NLSXNLNLSXSSS請求的封鎖方式XX第46頁/共58頁并發(fā)控制 分層封鎖數(shù)據(jù)對象從大到小有一種層次關(guān)系，當封鎖了外層數(shù)據(jù)對象時也就意味著同時封鎖了它的所有內(nèi)層數(shù)據(jù)對象。數(shù)據(jù)庫數(shù)據(jù)庫段段關(guān)系關(guān)系元組元組第47頁/共58頁并發(fā)控制 意向（預(yù)約）封鎖在分層封鎖中，封鎖了上層節(jié)點就意味著封鎖了所有內(nèi)層節(jié)點。如果有事務(wù)T1對某元組加了S鎖，而事務(wù)T2對該元組所在的關(guān)系加了X鎖，因而隱含地X封鎖了該元組，從而造成矛盾。

28、引入意向鎖I（Intend）：當為某節(jié)點加上I鎖，表明其某些內(nèi)層節(jié)點已發(fā)生事實上的封鎖，防止其它事務(wù)再去顯式封鎖該節(jié)點。I鎖的實施是從封鎖層次的根開始，依次占據(jù)路徑上的所有節(jié)點，直至要真正進行顯式封鎖的節(jié)點的父節(jié)點為止。第48頁/共58頁并發(fā)控制相容矩陣T1 T2ISXI+-S-+-X-第49頁/共58頁并發(fā)控制更精細的相容矩陣T1 T2ISIXSXIS+-IX+-S+-+-X-第50頁/共58頁并發(fā)控制 死鎖(Deadlock) 定義兩個事務(wù)都封鎖了一些數(shù)據(jù)對象，并相互等待對方釋放另一些數(shù)據(jù)對象以便對其封鎖，結(jié)果兩個事務(wù)都不能結(jié)束，則發(fā)生死鎖。 死鎖發(fā)生的條件互斥條件：事務(wù)請求對資源的獨占控制。等待條件：事務(wù)已持有一定資源，又去申請并等待其它資源。非搶占條件：直到資源被持有它的事務(wù)釋放之前，不可能將該資源強制從持有它的事務(wù)奪去。第51頁/共58頁并發(fā)控制循環(huán)等待條件：存在事務(wù)相互等待的等待圈。 定理：在條件成立的前提下，條件是死鎖存在的充分必要條件。事事務(wù)務(wù)號號占占有有資資源源號號請請求求資資源源號號T1R1R2T2R3R1，R2T3R2R3R2R1R3第52頁/共58頁并發(fā)控制 解決死鎖的方法預(yù)防死鎖 預(yù)先占據(jù)所需