第092事務(wù)管理并行

1、數(shù)據(jù)庫系統(tǒng)概論An Introduction to Database System第九章 事務(wù)管理-并發(fā)控制1并發(fā)控制概述多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行每個時刻只有一個事務(wù)運行，其他事務(wù)必須等到這個事務(wù)結(jié)束以后方能運行不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫共享資源的特點2并發(fā)控制(2)交叉并發(fā)方式（interleaved concurrency）事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作輪流交叉運行是單處理機(jī)系統(tǒng)中的并發(fā)方式，能夠減少處理機(jī)的空閑時間，提高系統(tǒng)的效率3并發(fā)控制(3)同時并發(fā)方式（simultaneous concurrency）多處理機(jī)系統(tǒng)中，每個處理機(jī)可以運行一個事務(wù)，多個處理機(jī)可

2、以同時運行多個事務(wù)，實現(xiàn)多個事務(wù)真正的并行運行最理想的并發(fā)方式，但受制于硬件環(huán)境更復(fù)雜的并發(fā)方式機(jī)制4事務(wù)并發(fā)執(zhí)行概述可能會存取和存儲不正確的數(shù)據(jù)，破壞事務(wù)的隔離性和數(shù)據(jù)庫的一致性DBMS必須提供并發(fā)控制機(jī)制并發(fā)控制機(jī)制是衡量一個DBMS性能的重要標(biāo)志之一5并發(fā)控制概述并發(fā)控制機(jī)制的任務(wù)對并發(fā)操作進(jìn)行正確調(diào)度保證事務(wù)的隔離性保證數(shù)據(jù)庫的一致性6并發(fā)操作帶來的數(shù)據(jù)不一致性丟失修改（lost update）不可重復(fù)讀（non-repeatable read）讀“臟”數(shù)據(jù)（dirty read）71. 丟失修改丟失修改是指事務(wù)1與事務(wù)2從數(shù)據(jù)庫中讀入同一數(shù)據(jù)并修改事務(wù)2的提交結(jié)果破壞了事務(wù)1提交的結(jié)

3、果，導(dǎo)致事務(wù)1的修改被丟失。82. 不可重復(fù)讀不可重復(fù)讀是指事務(wù)1讀取數(shù)據(jù)后，事務(wù)2執(zhí)行更新操作，使事務(wù)1無法再現(xiàn)前一次讀取結(jié)果。9三類不可重復(fù)讀事務(wù)1讀取某一數(shù)據(jù)后：1。事務(wù)2對其做了修改，當(dāng)事務(wù)1再次讀該數(shù)據(jù)時，得到與前一次不同的值。2. 事務(wù)2刪除了其中部分記錄，當(dāng)事務(wù)1再次讀取數(shù)據(jù)時，發(fā)現(xiàn)某些記錄神密地消失了。3. 事務(wù)2插入了一些記錄，當(dāng)事務(wù)1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時也稱為幻影現(xiàn)象103. 讀“臟”數(shù)據(jù)事務(wù)1修改某一數(shù)據(jù)，并將其寫回磁盤事務(wù)2讀取同一數(shù)據(jù)后事務(wù)1由于某種原因被撤消，這時事務(wù)1已修改過的數(shù)據(jù)恢復(fù)原值事務(wù)2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的

4、數(shù)據(jù)不一致，是不正確的數(shù)據(jù)，又稱為“臟”數(shù)據(jù)。11三種數(shù)據(jù)不一致性 T1T2 讀A=16 AA-1 寫回A=15讀A=16AA-1寫回A=15(a) 丟失修改12三種數(shù)據(jù)不一致性讀B=100 BB*2寫回B=200 讀A=50 讀B=100 求和=150 讀A=50 讀B=200 求和=250 (驗算不對) T2T1(b) 不可重復(fù)讀13三種數(shù)據(jù)不一致性讀C=200 讀C=100 CC*2 寫回C ROLLBACK C恢復(fù)為100T2T1(c) 讀“臟”數(shù)據(jù)14封鎖一、什么是封鎖二、基本封鎖類型三、基本鎖的相容矩陣15一、什么是封鎖封鎖就是事務(wù)T在對某個數(shù)據(jù)對象（例如表、記錄等）操作之前，先向

5、系統(tǒng)發(fā)出請求，對其加鎖加鎖后事務(wù)T就對該數(shù)據(jù)對象有了一定的控制，在事務(wù)T釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對象。封鎖是實現(xiàn)并發(fā)控制的一個非常重要的技術(shù)16二、基本封鎖類型DBMS通常提供了多種類型的封鎖。一個事務(wù)對某個數(shù)據(jù)對象加鎖后究竟擁有什么樣的控制是由封鎖的類型決定的?；痉怄i類型排它鎖（eXclusive lock，簡記為X鎖）共享鎖（Share lock，簡記為S鎖）17排它鎖排它鎖又稱為寫鎖若事務(wù)T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對A加任何類型的鎖，直到T釋放A上的鎖.X鎖排斥其他事物對數(shù)據(jù)加任何類型的鎖。18共享鎖共享鎖又稱為讀鎖若事務(wù)T對數(shù)

6、據(jù)對象A加上S鎖，則其它事務(wù)只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖可讀但是不能寫19三、鎖的相容矩陣Y=Yes，相容的請求N=No，不相容的請求 T1 T2XS-XNNYSNYY-YYY20封鎖協(xié)議在運用X鎖和S鎖對數(shù)據(jù)對象加鎖時，需要約定一些規(guī)則：封鎖協(xié)議（Locking Protocol） 何時申請X鎖或S鎖持鎖時間、何時釋放 不同的封鎖協(xié)議，在不同的程度上為并發(fā)操 作的正確調(diào)度提供一定的保證常用的封鎖協(xié)議：三級封鎖協(xié)議211級封鎖協(xié)議事務(wù)T在修改數(shù)據(jù)R之前必須先對其加X鎖非正常結(jié)束（ROLLBACK）1級封鎖協(xié)議可防止丟失修改在1級封鎖協(xié)議中，沒有規(guī)定事物讀數(shù)據(jù)需要加鎖，所

7、以它不能保證可重復(fù)讀和不讀“臟”數(shù)據(jù)。221級封鎖協(xié)議T1T2 Xlock A 獲得 讀A=16AA-1 寫回A=15 Commit Unlock AXlock A等待等待等待等待獲得Xlock A讀A=15AA-1寫回A=14CommitUnlock A沒有丟失修改 231級封鎖協(xié)議讀A=15 Xlock A 獲得 讀A=16 AA-1 寫回A=15 RollbackUnlock AT2T1讀“臟”數(shù)據(jù)這里的漏洞是T2沒有對數(shù)據(jù)加鎖241級封鎖協(xié)議 Xlock B 獲得 讀B=100 BB*2 寫回B=200 Commit Unlock B讀A=50 讀B=100 求和=150讀A=50 讀

8、B=200 求和=250 (驗算不對) T2T1不可重復(fù)讀25 2級封鎖協(xié)議1級封鎖協(xié)議+事務(wù)T在讀取數(shù)據(jù)R前必須先加S鎖，讀完后即可釋放S鎖2級封鎖協(xié)議可以防止丟失修改和讀“臟”數(shù)據(jù)。在2級封鎖協(xié)議中，由于讀完數(shù)據(jù)后即可釋放S鎖，所以它不能保證可重復(fù)讀。262級封鎖協(xié)議不可重復(fù)讀Sclock A 獲得 讀A=50 Unlock A Sclock B 獲得 讀B=100 Unlock B 求和=150 Xlock B等待等待獲得Xlock B讀B=100BB*2寫回B=200CommitUnlock BT2T1Sclock A 獲得 讀A=50 Unlock A Sclock B 獲得 讀B=

9、200 Unlock B 求和=250 (驗算不對)T2T1 (續(xù))27 3級封鎖協(xié)議1級封鎖協(xié)議 + 事務(wù)T在讀取數(shù)據(jù)R之前必須先對其加S鎖，直到事務(wù)結(jié)束才釋放3級封鎖協(xié)議可防止丟失修改、讀臟數(shù)據(jù)和不可重復(fù)讀。283級封鎖協(xié)議T1T2 Slock A 讀A=50 Slock B 讀B=100 求和=150 讀A=50 讀B=100 求和=150 Commit Unlock A Unlock B Xlock B等待等待等待 等待等待等待等待等待獲得Xlock B讀B=100BB*2寫回B=200CommitUnlock B 可重復(fù)讀 293級封鎖協(xié)議T1T2 Xlock C 讀C= 100 C

10、C*2 寫回C=200 ROLLBACK (C恢復(fù)為100) Unlock C Slock C等待等待等待等待獲得Slock C讀C=100Commit CUnlock C不讀“臟”數(shù)據(jù) 304封鎖協(xié)議小結(jié)三級協(xié)議的主要區(qū)別什么操作需要申請封鎖何時釋放鎖（即持鎖時間）31封鎖協(xié)議小結(jié)32活鎖和死鎖封鎖技術(shù)可以有效地解決并行操作的一致性問題，但也帶來一些新的問題死鎖活鎖33 活鎖34如何避免活鎖采用先來先服務(wù)的策略：當(dāng)多個事務(wù)請求封鎖同一數(shù)據(jù)對象時按請求封鎖的先后次序?qū)@些事務(wù)排隊該數(shù)據(jù)對象上的鎖一旦釋放，首先批準(zhǔn)申請隊列中第一個事務(wù)獲得鎖。352 死鎖T1 T2 Xlock R1.Xlock

11、R2等待等待等待.Xlock R2.Xlock R1等待等待.36解決死鎖的方法兩類方法1. 預(yù)防死鎖2. 死鎖的診斷與解除371. 死鎖的預(yù)防產(chǎn)生死鎖的原因是兩個或多個事務(wù)都已封鎖了一些數(shù)據(jù)對象，然后又都請求對已為其他事務(wù)封鎖的數(shù)據(jù)對象加鎖，從而出現(xiàn)死等待。預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件38死鎖的預(yù)防預(yù)防死鎖的方法 一次封鎖法 順序封鎖法39（1）一次封鎖法要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行一次封鎖法存在的問題：降低并發(fā)度 擴(kuò)大封鎖范圍將以后要用到的全部數(shù)據(jù)加鎖，勢必擴(kuò)大了封鎖的范圍，從而降低了系統(tǒng)的并發(fā)度40一次封鎖法難于事先精確確定封鎖對象數(shù)據(jù)庫中

12、數(shù)據(jù)是不斷變化的，原來不要求封鎖的數(shù)據(jù)，在執(zhí)行過程中可能會變成封鎖對象，所以很難事先精確地確定每個事務(wù)所要封鎖的數(shù)據(jù)對象41（2）順序封鎖法順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務(wù)都按這個順序?qū)嵭蟹怄i。順序封鎖法存在的問題 維護(hù)成本高數(shù)據(jù)庫系統(tǒng)中可封鎖的數(shù)據(jù)對象極其眾多，并且隨數(shù)據(jù)的插入、刪除等操作而不斷地變化，要維護(hù)這樣極多而且變化的資源的封鎖順序非常困難，成本很高42順序封鎖法難于實現(xiàn)事務(wù)的封鎖請求可以隨著事務(wù)的執(zhí)行而動態(tài)地決定，很難事先確定每一個事務(wù)要封鎖哪些對象，因此也就很難按規(guī)定的順序去施加封鎖。43死鎖的預(yù)防結(jié)論在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫的特點

13、DBMS在解決死鎖的問題上更普遍采用的是診斷并解除死鎖的方法442. 死鎖的診斷與解除允許死鎖發(fā)生解除死鎖由DBMS的并發(fā)控制子系統(tǒng)定期檢測系統(tǒng)中是否存在死鎖一旦檢測到死鎖，就要設(shè)法解除45檢測死鎖如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認(rèn)為發(fā)生了死鎖優(yōu)點：實現(xiàn)簡單缺點時限太短，有可能誤判死鎖時限若設(shè)置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn)46等待圖法用事務(wù)等待圖動態(tài)反映所有事務(wù)的等待情況事務(wù)等待圖是一個有向圖G=(T，U)T為結(jié)點的集合，每個結(jié)點表示正運行的事務(wù)U為邊的集合，每條邊表示事務(wù)等待的情況若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T2并發(fā)控制子系統(tǒng)周期性地（比如每隔1 mi

14、n）檢測事務(wù)等待圖，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。47死鎖的診斷與解除解除死鎖選擇一個處理死鎖代價最小的事務(wù)，將其撤消，釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運行下去。4811.4 并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的49一、什么樣的并發(fā)操作調(diào)度是正確的計算機(jī)系統(tǒng)對并行事務(wù)中并行操作的調(diào)度是的隨機(jī)的，而不同的調(diào)度可能會產(chǎn)生不同的結(jié)果。將所有事務(wù)串行起來的調(diào)度策略一定是正確的調(diào)度策略。如果一個事務(wù)運行過程中沒有其他事務(wù)在同時運行，也就是說它沒有受到其他事務(wù)干擾，那么就可以認(rèn)為該事務(wù)的運行結(jié)果是正常的或者預(yù)想的。50什么樣的并發(fā)操

15、作調(diào)度是正確的以不同的順序串行執(zhí)行事務(wù)也有可能會產(chǎn)生不同的結(jié)果，但由于不會將數(shù)據(jù)庫置于不一致狀態(tài)，所以都可以認(rèn)為是正確的。 幾個事務(wù)的并行執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行它們時的結(jié)果相同。這種并行調(diào)度策略稱為可串行化（Serializable）的調(diào)度。51(a) 串行調(diào)度策略，正確的調(diào)度Slock BY=B=2Unlock BXlock AA=Y+1寫回A(=3)Unlock A Slock AX=A=3Unlock AXlock BB=X+1寫回B(=4)Unlock B T1T252(b) 串行調(diào)度策略，正確的調(diào)度 Slock BY=B=3Unlock BXlock AA

16、=Y+1寫回A(=4)Unlock A SlockA X=A=2Unlock AXlock BB=X+1寫回B(=3)Unlock BT1T253(c) 不可串行化的調(diào)度Slock BY=B=2Unlock BXlock AA=Y+1寫回A(=3)Unlock A Slock AX=A=2Unlock AXlock BB=X+1寫回B(=3)Unlock B T1T254(c) 不可串行化的調(diào)度由于其執(zhí)行結(jié)果與(a)、(b)的結(jié)果都不同，所以是錯誤的調(diào)度。55(d) 可串行化的調(diào)度Slock BY=B=2Unlock BXlock AA=Y+1寫回A(=3)Unlock ASlock A 等待

17、 等待 等待X=A=3Unlock AXlock BB=X+1寫回B(=4)Unlock B T1T256(d) 可串行化的調(diào)度由于其執(zhí)行結(jié)果與串行調(diào)度（a）的執(zhí)行結(jié)果相同，所以是正確的調(diào)度。5711.5 并發(fā)調(diào)度的可串行性一、什么樣的并發(fā)操作調(diào)度是正確的二、如何保證并發(fā)操作的調(diào)度是正確的58二、如何保證并發(fā)操作的調(diào)度是正確的為了保證并行操作的正確性，DBMS的并行控制機(jī)制必須提供一定的手段來保證調(diào)度是可串行化的。從理論上講，在某一事務(wù)執(zhí)行時禁止其他事務(wù)執(zhí)行的調(diào)度策略一定是可串行化的調(diào)度，這也是最簡單的調(diào)度策略，但這種方法實際上是不可行的，因為它使用戶不能充分共享數(shù)據(jù)庫資源。59如何保證并發(fā)操

18、作的調(diào)度是正確的（續(xù)）保證并發(fā)操作調(diào)度正確性的方法封鎖方法：兩段鎖（Two-Phase Locking，簡稱2PL）協(xié)議時標(biāo)方法樂觀方法60兩段鎖協(xié)議兩段鎖協(xié)議的內(nèi)容1. 在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，事務(wù)首先要獲得對該數(shù)據(jù)的封鎖2. 在釋放一個封鎖之后，事務(wù)不再獲得任何其他封鎖。61兩段鎖協(xié)議“兩段”鎖的含義事務(wù)分為兩個階段 第一階段是獲得封鎖，也稱為擴(kuò)展階段； 第二階段是釋放封鎖，也稱為收縮階段。62兩段鎖協(xié)議例：事務(wù)1的封鎖序列：Slock A . Slock B . Xlock C . Unlock B . Unlock A . Unlock C；事務(wù)2的封鎖序列：Slock A .

19、 Unlock A . Slock B . Xlock C . Unlock C . Unlock B；事務(wù)1遵守兩段鎖協(xié)議，而事務(wù)2不遵守兩段協(xié)議。63兩段鎖協(xié)議并行執(zhí)行的所有事務(wù)均遵守兩段鎖協(xié)議，則對這些事務(wù)的所有并行調(diào)度策略都是可串行化的。所有遵守兩段鎖協(xié)議的事務(wù)，其并行執(zhí)行的結(jié)果一定是正確的事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件可串行化的調(diào)度中，不一定所有事務(wù)都必須符合兩段鎖協(xié)議。64兩段鎖協(xié)議T1Slock B讀B=2Y=BXlock AA=Y+1寫回A=3Unlock BUnlock AT2Slock A 等待 等待 等待 等待 等待Slock A讀A=3Y=A

20、 Xlock BB=Y+1寫回B=4Unlock BUnlock AT1Slock B讀B=2Y=BUnlock BXlock AA=Y+1寫回A=3Unlock AT2Slock A等待等待等待等待Slock A讀A=3X=AUnlock AXlock BB=X+1寫回B=4Unlock B (a) 遵守兩段鎖協(xié)議 (b) 不遵守兩段鎖協(xié)議 T1Slock B讀B=2Y=BUnlock BXlock AA=Y+1寫回A=3Unlock AT2Slock A讀A=2X=AUnlock AXlock B等待Xlock BB=X+1寫回B=3Unlock B(c) 不遵守兩段鎖協(xié)議 65兩段鎖協(xié)議

21、兩段鎖協(xié)議與防止死鎖的一次封鎖法一次封鎖法要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行，因此一次封鎖法遵守兩段鎖協(xié)議但是兩段鎖協(xié)議并不要求事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，因此遵守兩段鎖協(xié)議的事務(wù)可能發(fā)生死鎖66兩段鎖協(xié)議遵守兩段鎖協(xié)議的事務(wù)發(fā)生死鎖T1Slock B讀B=2Xlock A等待等待T2Slock A讀A=2Xlock A等待67兩段鎖協(xié)議兩段鎖協(xié)議與三級封鎖協(xié)議兩類不同目的的協(xié)議兩段鎖協(xié)議保證并發(fā)調(diào)度的串行性三級封鎖協(xié)議在不同程度上保證數(shù)據(jù)一致性6811.6 封鎖粒度一、什么是封鎖粒度二、選擇封鎖粒度的原則69一、什么是封鎖粒度X鎖和S鎖都是加在某一

22、個數(shù)據(jù)對象上的封鎖的對象:邏輯單元，物理單元 例：在關(guān)系數(shù)據(jù)庫中，封鎖對象：邏輯單元: 屬性值、屬性值集合、元組、關(guān)系、索引項、整個索引、整個數(shù)據(jù)庫等物理單元：頁（數(shù)據(jù)頁或索引頁）、物理記錄等70什么是封鎖粒度封鎖對象可以很大也可以很小 例： 對整個數(shù)據(jù)庫加鎖 對某個屬性值加鎖封鎖對象的大小稱為封鎖的粒度(Granularity)多粒度封鎖(multiple granularity locking)在一個系統(tǒng)中同時支持多種封鎖粒度供不同的事務(wù)選擇71二、選擇封鎖粒度的原則封鎖的粒度越 大，小，系統(tǒng)被封鎖的對象 少，多，并發(fā)度 小，高，系統(tǒng)開銷 小，大，選擇封鎖粒度：考慮封鎖機(jī)構(gòu)和并發(fā)度兩個因素

23、對系統(tǒng)開銷與并發(fā)度進(jìn)行權(quán)衡72選擇封鎖粒度的原則需要處理多個關(guān)系的大量元組的用戶事務(wù)：以數(shù)據(jù)庫為封鎖單位；需要處理大量元組的用戶事務(wù)：以關(guān)系為封鎖單元；只處理少量元組的用戶事務(wù)：以元組為封鎖單位7311.6 多粒度封鎖多粒度樹以樹形結(jié)構(gòu)來表示多級封鎖粒度根結(jié)點是整個數(shù)據(jù)庫，表示最大的數(shù)據(jù)粒度葉結(jié)點表示最小的數(shù)據(jù)粒度 74多粒度封鎖例：三級粒度樹。根結(jié)點為數(shù)據(jù)庫，數(shù)據(jù)庫的子結(jié)點為關(guān)系，關(guān)系的子結(jié)點為元組。數(shù)據(jù)庫關(guān)系Rn關(guān)系R1元組元組元組元組75多粒度封鎖協(xié)議 允許多粒度樹中的每個結(jié)點被獨立地加鎖對一個結(jié)點加鎖意味著這個結(jié)點的所有后裔結(jié)點也被加以同樣類型的鎖在多粒度封鎖中一個數(shù)據(jù)對象可能以兩種方式封鎖：顯式封鎖和隱式封鎖76顯式封鎖和隱式封鎖顯式封鎖: 直接加到數(shù)據(jù)對象上的封鎖隱式封鎖: 由于其上