數(shù)據(jù)庫原理DatabasePrincipl1.ppt

An Introduction to Database System,數(shù)據(jù)庫原理 Database Principle,仲愷農(nóng)業(yè)技術(shù)學(xué)院計算機科學(xué)與工程學(xué)院,An Introduction to Database System,問題的產(chǎn)生,多用戶數(shù)據(jù)庫系統(tǒng)的存在 允許多個用戶同時使用的數(shù)據(jù)庫系統(tǒng) 飛機定票數(shù)據(jù)庫系統(tǒng) 銀行數(shù)據(jù)庫系統(tǒng) 特點：在同一時刻并發(fā)運行的事務(wù)數(shù)可達數(shù)百個,An Introduction to Database System,問題的產(chǎn)生（續(xù)）,不同的多事務(wù)執(zhí)行方式 (1)事務(wù)串行執(zhí)行 每個時刻只有一個事務(wù)運行，其他事務(wù)必須等到這個事務(wù)結(jié)束以后方能運行 不能充分利用系統(tǒng)資源，發(fā)揮數(shù)據(jù)庫共享資源的特點,T1,T2,T3,事務(wù)的串行執(zhí)行方式,An Introduction to Database System,問題的產(chǎn)生（續(xù)）,(2)交叉并發(fā)方式（Interleaved Concurrency） 在單處理機系統(tǒng)中，事務(wù)的并行執(zhí)行是這些并行事務(wù)的并行操作輪流交叉運行 單處理機系統(tǒng)中的并行事務(wù)并沒有真正地并行運行，但能夠減少處理機的空閑時間，提高系統(tǒng)的效率,An Introduction to Database System,問題的產(chǎn)生（續(xù)）,事務(wù)的交叉并發(fā)執(zhí)行方式,An Introduction to Database System,問題的產(chǎn)生（續(xù)）,(3)同時并發(fā)方式（simultaneous concurrency） 多處理機系統(tǒng)中，每個處理機可以運行一個事務(wù)，多個處理機可以同時運行多個事務(wù)，實現(xiàn)多個事務(wù)真正的并行運行,An Introduction to Database System,問題的產(chǎn)生（續(xù)）,事務(wù)并發(fā)執(zhí)行帶來的問題 會產(chǎn)生多個事務(wù)同時存取同一數(shù)據(jù)的情況 可能會存取和存儲不正確的數(shù)據(jù)，破壞事務(wù)一致性和數(shù)據(jù)庫的一致性,An Introduction to Database System,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議 11.6 小結(jié),An Introduction to Database System,11.1 并發(fā)控制概述,并發(fā)控制機制的任務(wù) 對并發(fā)操作進行正確調(diào)度 保證事務(wù)的隔離性 保證數(shù)據(jù)庫的一致性,An Introduction to Database System,并發(fā)操作帶來數(shù)據(jù)的不一致性實例 例1飛機訂票系統(tǒng)中的一個活動序列 甲售票點(甲事務(wù))讀出某航班的機票余額A，設(shè)A=16； 乙售票點(乙事務(wù))讀出同一航班的機票余額A，也為16； 甲售票點賣出一張機票，修改余額AA-1，所以A為15，把A寫回數(shù)據(jù)庫； 乙售票點也賣出一張機票，修改余額AA-1，所以A為15，把A寫回數(shù)據(jù)庫 結(jié)果明明賣出兩張機票，數(shù)據(jù)庫中機票余額只減少1,T1的修改被T2覆蓋了！,并發(fā)控制概述（續(xù)）,并發(fā)控制概述（續(xù)）,An Introduction to Database System,并發(fā)控制概述（續(xù)）,這種情況稱為數(shù)據(jù)庫的不一致性，是由并發(fā)操作引起的。 在并發(fā)操作情況下，對甲、乙兩個事務(wù)的操作序列的調(diào)度是隨機的。 若按上面的調(diào)度序列執(zhí)行，甲事務(wù)的修改就被丟失。 原因：第4步中乙事務(wù)修改A并寫回后覆蓋了甲事務(wù)的修改,An Introduction to Database System,并發(fā)控制概述（續(xù)）,并發(fā)操作帶來的數(shù)據(jù)不一致性 丟失修改（Lost Update） 不可重復(fù)讀（Non-repeatable Read） 讀“臟”數(shù)據(jù)（Dirty Read） 記號 R(x):讀數(shù)據(jù)x W(x):寫數(shù)據(jù)x,An Introduction to Database System,1. 丟失修改,兩個事務(wù)T1和T2讀入同一數(shù)據(jù)并修改，T2的提交結(jié)果破壞了T1提交的結(jié)果，導(dǎo)致T1的修改被丟失。 上面飛機訂票例子就屬此類,An Introduction to Database System,丟失修改（續(xù)）,丟失修改,實例演示,An Introduction to Database System,2. 不可重復(fù)讀,不可重復(fù)讀是指事務(wù)T1讀取數(shù)據(jù)后，事務(wù)T2執(zhí)行更新操作，使T1無法再現(xiàn)前一次讀取結(jié)果。,An Introduction to Database System,不可重復(fù)讀（續(xù)）,不可重復(fù)讀包括三種情況： (1)事務(wù)T1讀取某一數(shù)據(jù)后，事務(wù)T2對其做了修改，當(dāng)事務(wù)T1再次讀該數(shù)據(jù)時，得到與前一次不同的值,An Introduction to Database System,不可重復(fù)讀（續(xù)）,T1讀取B=100進行運算 T2讀取同一數(shù)據(jù)B，對其進行修改后將B=200寫回數(shù)據(jù)庫。 T1為了對讀取值校對重讀B，B已為200，與第一次讀取值不一致,不可重復(fù)讀,例如：,實例演示,An Introduction to Database System,不可重復(fù)讀（續(xù)）,(2)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取了某些數(shù)據(jù)記錄后，事務(wù)T2刪除了其中部分記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)某些記錄消失了 (3)事務(wù)T1按一定條件從數(shù)據(jù)庫中讀取某些數(shù)據(jù)記錄后，事務(wù)T2插入了一些記錄，當(dāng)T1再次按相同條件讀取數(shù)據(jù)時，發(fā)現(xiàn)多了一些記錄。 后兩種不可重復(fù)讀有時也稱為幻影現(xiàn)象（Phantom Row）,An Introduction to Database System,3. 讀“臟”數(shù)據(jù),讀“臟”數(shù)據(jù)是指： 事務(wù)T1修改某一數(shù)據(jù)，并將其寫回磁盤 事務(wù)T2讀取同一數(shù)據(jù)后，T1由于某種原因被撤銷 這時T1已修改過的數(shù)據(jù)恢復(fù)原值，T2讀到的數(shù)據(jù)就與數(shù)據(jù)庫中的數(shù)據(jù)不一致 T2讀到的數(shù)據(jù)就為“臟”數(shù)據(jù)，即不正確的數(shù)據(jù),An Introduction to Database System,讀“臟”數(shù)據(jù)（續(xù)）,例如,T1將C值修改為200，T2讀到C為200 T1由于某種原因撤銷，其修改作廢，C恢復(fù)原值100 這時T2讀到的C為200，與數(shù)據(jù)庫內(nèi)容不一致，就是“臟”數(shù)據(jù),An Introduction to Database System,并發(fā)控制概述（續(xù)）,數(shù)據(jù)不一致性：由于并發(fā)操作破壞了事務(wù)的隔離性 并發(fā)控制就是要用正確的方式調(diào)度并發(fā)操作，使一個用戶事務(wù)的執(zhí)行不受其他事務(wù)的干擾，從而避免造成數(shù)據(jù)的不一致性,An Introduction to Database System,并發(fā)控制概述（續(xù)）,并發(fā)控制的主要技術(shù) 有封鎖(Locking) 時間戳(Timestamp) 樂觀控制法 商用的DBMS一般都采用封鎖方法,An Introduction to Database System,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議 11.6 小結(jié),An Introduction to Database System,11.2 封鎖,什么是封鎖 基本封鎖類型 鎖的相容矩陣,An Introduction to Database System,什么是封鎖,封鎖就是事務(wù)T在對某個數(shù)據(jù)對象（例如表、記錄等）操作之前，先向系統(tǒng)發(fā)出請求，對其加鎖 加鎖后事務(wù)T就對該數(shù)據(jù)對象有了一定的控制，在事務(wù)T釋放它的鎖之前，其它的事務(wù)不能更新此數(shù)據(jù)對象。,An Introduction to Database System,在 SQL Server中如何查看鎖？,An Introduction to Database System,在 SQL Server中如何查看鎖？（續(xù)）,實例演示,An Introduction to Database System,基本封鎖類型,一個事務(wù)對某個數(shù)據(jù)對象加鎖后究竟擁有什么樣的控制由封鎖的類型決定。 基本封鎖類型 排它鎖（Exclusive Locks，簡記為X鎖） 共享鎖（Share Locks，簡記為S鎖）,An Introduction to Database System,排它鎖,排它鎖又稱為寫鎖 若事務(wù)T對數(shù)據(jù)對象A加上X鎖，則只允許T讀取和修改A，其它任何事務(wù)都不能再對A加任何類型的鎖，直到T釋放A上的鎖 保證其他事務(wù)在T釋放A上的鎖之前不能再讀取和修改A,An Introduction to Database System,共享鎖,共享鎖又稱為讀鎖 若事務(wù)T對數(shù)據(jù)對象A加上S鎖，則其它事務(wù)只能再對A加S鎖，而不能加X鎖，直到T釋放A上的S鎖 保證其他事務(wù)可以讀A，但在T釋放A上的S鎖之前不能對A做任何修改,An Introduction to Database System,鎖的相容矩陣,An Introduction to Database System,鎖的相容矩陣（續(xù)）,在鎖的相容矩陣中： 最左邊一列表示事務(wù)T1已經(jīng)獲得的數(shù)據(jù)對象上的鎖的類型，其中橫線表示沒有加鎖。 最上面一行表示另一事務(wù)T2對同一數(shù)據(jù)對象發(fā)出的封鎖請求。 T2的封鎖請求能否被滿足用矩陣中的Y和N表示 Y表示事務(wù)T2的封鎖要求與T1已持有的鎖相容，封鎖請求可以滿足 N表示T2的封鎖請求與T1已持有的鎖沖突，T2的請求被拒絕,An Introduction to Database System,使用封鎖機制解決丟失修改問題,例：,事務(wù)T1在讀A進行修改之前先對A加X鎖 當(dāng)T2再請求對A加X鎖時被拒絕 T2只能等待T1釋放A上的鎖后T2獲得對A的X鎖 這時T2讀到的A已經(jīng)是T1更新過的值15 T2按此新的A值進行運算，并將結(jié)果值A(chǔ)=14送回到磁盤。避免了丟失T1的更新。,沒有丟失修改,An Introduction to Database System,使用封鎖機制解決不可重復(fù)讀問題,事務(wù)T1在讀A，B之前，先對A，B加S鎖 其他事務(wù)只能再對A，B加S鎖，而不能加X鎖，即其他事務(wù)只能讀A，B，而不能修改 當(dāng)T2為修改B而申請對B的X鎖時被拒絕只能等待T1釋放B上的鎖 T1為驗算再讀A，B，這時讀出的B仍是100，求和結(jié)果仍為150，即可重復(fù)讀 T1結(jié)束才釋放A，B上的S鎖。T2才獲得對B的X鎖,可重復(fù)讀,An Introduction to Database System,使用封鎖機制解決讀“臟”數(shù)據(jù)問題,例,事務(wù)T1在對C進行修改之前，先對C加X鎖，修改其值后寫回磁盤 T2請求在C上加S鎖，因T1已在C上加了X鎖，T2只能等待 T1因某種原因被撤銷，C恢復(fù)為原值100 T1釋放C上的X鎖后T2獲得C上的S鎖，讀C=100。避免了T2讀“臟”數(shù)據(jù),不讀“臟”數(shù)據(jù),An Introduction to Database System,11.2 封鎖(續(xù)),An Introduction to Database System,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議 11.6 小結(jié),An Introduction to Database System,11.3 活鎖和死鎖,封鎖技術(shù)可以有效地解決并行操作的一致性問題，但也帶來一些新的問題 死鎖 活鎖,An Introduction to Database System,活鎖（續(xù)）,活 鎖,An Introduction to Database System,活鎖（續(xù)）,避免活鎖：采用先來先服務(wù)的策略 當(dāng)多個事務(wù)請求封鎖同一數(shù)據(jù)對象時 按請求封鎖的先后次序?qū)@些事務(wù)排隊 該數(shù)據(jù)對象上的鎖一旦釋放，首先批準申請隊列中第一個事務(wù)獲得鎖,An Introduction to Database System,11.3.2 死鎖,事務(wù)T1封鎖了數(shù)據(jù)R1 T2封鎖了數(shù)據(jù)R2 T1又請求封鎖R2，因T2已封鎖了R2，于是T1等待T2釋放R2上的鎖 接著T2又申請封鎖R1，因T1已封鎖了R1，T2也只能等待T1釋放R1上的鎖 這樣T1在等待T2，而T2又在等待T1，T1和T2兩個事務(wù)永遠不能結(jié)束，即:T1和T2互相封鎖形成死鎖,An Introduction to Database System,死鎖（續(xù)）,死 鎖,An Introduction to Database System,解決死鎖的方法,兩類方法 1. 預(yù)防死鎖 2. 死鎖的診斷與解除,An Introduction to Database System,1. 死鎖的預(yù)防,產(chǎn)生死鎖的原因是兩個或多個事務(wù)都已封鎖了一些數(shù)據(jù)對象，然后又都請求對已為其他事務(wù)封鎖的數(shù)據(jù)對象加鎖，從而出現(xiàn)死等待。 預(yù)防死鎖的發(fā)生就是要破壞產(chǎn)生死鎖的條件,An Introduction to Database System,死鎖的預(yù)防（續(xù)）,預(yù)防死鎖的方法 一次封鎖法 順序封鎖法,An Introduction to Database System,(1)一次封鎖法,要求每個事務(wù)必須一次將所有要使用的數(shù)據(jù)全部加鎖，否則就不能繼續(xù)執(zhí)行 缺點 造成封鎖范圍時間擴大,降低系統(tǒng)并發(fā)度 難于事先精確確定封鎖對象,An Introduction to Database System,(2)順序封鎖法,順序封鎖法是預(yù)先對數(shù)據(jù)對象規(guī)定一個封鎖順序，所有事務(wù)都按這個順序?qū)嵭蟹怄i。 順序封鎖法存在的問題 維護成本 數(shù)據(jù)庫系統(tǒng)中封鎖的數(shù)據(jù)對象極多，并且在不斷地變化。 難以實現(xiàn)：很難事先確定每一個事務(wù)要封鎖哪些對象,An Introduction to Database System,死鎖的預(yù)防（續(xù)）,結(jié)論 在操作系統(tǒng)中廣為采用的預(yù)防死鎖的策略并不很適合數(shù)據(jù)庫的特點 DBMS在解決死鎖的問題上更普遍采用的是診斷并解除死鎖的方法,An Introduction to Database System,2. 死鎖的診斷與解除,死鎖的診斷 超時法 事務(wù)等待圖法,An Introduction to Database System,(1) 超時法,如果一個事務(wù)的等待時間超過了規(guī)定的時限，就認為發(fā)生了死鎖 優(yōu)點：實現(xiàn)簡單 缺點 有可能誤判死鎖 時限若設(shè)置得太長，死鎖發(fā)生后不能及時發(fā)現(xiàn),An Introduction to Database System,(2)等待圖法,用事務(wù)等待圖動態(tài)反映所有事務(wù)的等待情況 事務(wù)等待圖是一個有向圖G=(T，U) T為結(jié)點的集合，每個結(jié)點表示正運行的事務(wù) U為邊的集合，每條邊表示事務(wù)等待的情況 若T1等待T2，則T1，T2之間劃一條有向邊，從T1指向T2,An Introduction to Database System,等待圖法（續(xù)）,事務(wù)等待圖,圖(a)中，事務(wù)T1等待T2，T2等待T1，產(chǎn)生了死鎖 圖(b)中，事務(wù)T1等待T2，T2等待T3，T3等待T4，T4又等待T1，產(chǎn)生了死鎖 圖(b)中，事務(wù)T3可能還等待T2，在大回路中又有小的回路,An Introduction to Database System,等待圖法（續(xù)）,并發(fā)控制子系統(tǒng)周期性地（比如每隔數(shù)秒）生成事務(wù)等待圖，檢測事務(wù)。如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。,An Introduction to Database System,死鎖的診斷與解除（續(xù)）,解除死鎖 選擇一個處理死鎖代價最小的事務(wù)，將其撤消 釋放此事務(wù)持有的所有的鎖，使其它事務(wù)能繼續(xù)運行下去,An Introduction to Database System,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議 11.6 小結(jié),An Introduction to Database System,11.4 并發(fā)調(diào)度的可串行性,DBMS對并發(fā)事務(wù)不同的調(diào)度可能會產(chǎn)生不同的結(jié)果 什么樣的調(diào)度是正確的？,An Introduction to Database System,11.4 并發(fā)調(diào)度的可串行性（續(xù)）,可串行化(Serializable)調(diào)度 多個事務(wù)的并發(fā)執(zhí)行是正確的，當(dāng)且僅當(dāng)其結(jié)果與按某一次序串行地執(zhí)行這些事務(wù)時的結(jié)果相同 可串行性(Serializability) 是并發(fā)事務(wù)正確調(diào)度的準則 一個給定的并發(fā)調(diào)度，當(dāng)且僅當(dāng)它是可串行化的，才認為是正確調(diào)度,An Introduction to Database System,11.4 并發(fā)調(diào)度的可串行性（續(xù)）,例現(xiàn)在有兩個事務(wù)，分別包含下列操作： 事務(wù)T1：讀B；A=B+1；寫回A 事務(wù)T2：讀A；B=A+1；寫回B 現(xiàn)給出對這兩個事務(wù)不同的調(diào)度策略,An Introduction to Database System,串行調(diào)度,不可串行化調(diào)度,An Introduction to Database System,串行調(diào)度,可串行化調(diào)度,An Introduction to Database System,思考是否存在其他調(diào)度策略,？,串行調(diào)度,總結(jié)：如果有n個事務(wù)串行調(diào)度，那么不同的有效調(diào)度有n！個。,An Introduction to Database System,第十一章 并發(fā)控制,11.1 并發(fā)控制概述 11.2 封鎖 11.3 活鎖和死鎖 11.4 并發(fā)調(diào)度的可串行性 11.5 兩段鎖協(xié)議 11.6 小結(jié),An Introduction to Database System,11.5 兩段鎖協(xié)議,封鎖協(xié)議（Locking Protocol） 運用封鎖方法時，對數(shù)據(jù)對象加鎖時需要約定一些規(guī)則 何時申請封鎖 持鎖時間 何時釋放封鎖等 兩段封鎖協(xié)議(Two-Phase Locking，簡稱2PL)是最常用的一種封鎖協(xié)議，理論上證明使用兩段封鎖協(xié)議產(chǎn)生的是可串行化調(diào)度,An Introduction to Database System,兩段鎖協(xié)議（續(xù)）,兩段鎖協(xié)議 指所有事務(wù)必須分兩個階段對數(shù)據(jù)項加鎖和解鎖 在對任何數(shù)據(jù)進行讀、寫操作之前，事務(wù)首先要獲得對該數(shù)據(jù)的封鎖 在釋放一個封鎖之后，事務(wù)不再申請和獲得任何其他封鎖,An Introduction to Database System,兩段鎖協(xié)議（續(xù)）,“兩段”鎖的含義 事務(wù)分為兩個階段 第一階段是獲得封鎖，也稱為擴展階段 事務(wù)可以申請獲得任何數(shù)據(jù)項上的任何類型的鎖，但是不能釋放任何鎖 第二階段是釋放封鎖，也稱為收縮階段 事務(wù)可以釋放任何數(shù)據(jù)項上的任何類型的鎖，但是不能再申請任何鎖,An Introduction to Database System,兩段鎖協(xié)議（續(xù)）,例 ：事務(wù)Ti 遵守兩段鎖協(xié)議，其封鎖序列是 ： Slock A Slock B Xlock C Unlock B Unlock A UnlockC； | 擴展階段 | | 收縮階段 | 事務(wù)Tj 不遵守兩段鎖協(xié)議，其封鎖序列是： Slock A Unlock A Slock B Xlock C Unlock C UnlockB；,An Introduction to Database System,左圖的調(diào)度是遵守兩段鎖協(xié)議的，因此一定是一個可串行化調(diào)度。,An Introduction to Database System,兩段鎖協(xié)議 &可串行化調(diào)度,事務(wù)遵守兩段鎖協(xié)議是可串行化調(diào)度的充分條件，而不是必要條件。 兩段鎖協(xié)議 可串行化調(diào)度 可串行化調(diào)度 兩段鎖協(xié)議,？