第8章 并發(fā)控制

1、silberschatz, korth and sudarshan16.1database system concepts 3rd editionn本章內(nèi)容參考本章內(nèi)容參考:數(shù)據(jù)庫(kù)概念數(shù)據(jù)庫(kù)概念(第四版第四版) by a. silberschatzchapter 16 concurrency control補(bǔ)充內(nèi)容補(bǔ)充內(nèi)容n本章內(nèi)容特色本章內(nèi)容特色:若干協(xié)議，實(shí)現(xiàn)時(shí)編程較難若干協(xié)議，實(shí)現(xiàn)時(shí)編程較難理論上有難度，細(xì)致（如時(shí)間戳，等候圖等）理論上有難度，細(xì)致（如時(shí)間戳，等候圖等）有些協(xié)議至今沒(méi)有實(shí)現(xiàn)有些協(xié)議至今沒(méi)有實(shí)現(xiàn)n本章要解決的關(guān)鍵問(wèn)題：本章要解決的關(guān)鍵問(wèn)題：如何實(shí)現(xiàn)隔離性，保證一致性如何實(shí)現(xiàn)

2、隔離性，保證一致性silberschatz, korth and sudarshan16.2database system concepts 3rd editionnintroduction to isolationndependency model of isolationntransaction dependency relationsn基于鎖的協(xié)議基于鎖的協(xié)議n基于時(shí)間戳的協(xié)議基于時(shí)間戳的協(xié)議n基于驗(yàn)證的協(xié)議基于驗(yàn)證的協(xié)議n多粒度多粒度n多版本多版本n死鎖處理死鎖處理n插入與刪除操作插入與刪除操作n索引結(jié)構(gòu)中的并發(fā)索引結(jié)構(gòu)中的并發(fā)silberschatz, korth and sudar

3、shan16.3database system concepts 3rd editionintroduction to isolationn系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)vs. 不變式不變式(invariant) “如果向如果向emp 插入一個(gè)記錄，相應(yīng)地必須向插入一個(gè)記錄，相應(yīng)地必須向zip 插入一條記錄。插入一條記錄?！?“如果如果emp的一個(gè)副本被更新的一個(gè)副本被更新,其余副本也必須以同樣的方式被更新。其余副本也必須以同樣的方式被更新。” “如果一個(gè)程序改變了帳戶(hù)余額，有關(guān)的修改必須記錄在案。如果一個(gè)程序改變了帳戶(hù)余額，有關(guān)的修改必須記錄在案?！眓如果滿(mǎn)足所有這些不變式，則系統(tǒng)狀態(tài)被認(rèn)為是一致的如果滿(mǎn)

4、足所有這些不變式，則系統(tǒng)狀態(tài)被認(rèn)為是一致的n通常一個(gè)狀態(tài)在向另外一個(gè)新的且一致性狀態(tài)轉(zhuǎn)換時(shí)，通常一個(gè)狀態(tài)在向另外一個(gè)新的且一致性狀態(tài)轉(zhuǎn)換時(shí)，可能會(huì)出現(xiàn)短暫的不一致可能會(huì)出現(xiàn)短暫的不一致n例如，向例如，向emp 表插入一條記錄，不可能使表插入一條記錄，不可能使emp 以及以及zip 索引的插入完全同步索引的插入完全同步n幾乎任何一個(gè)涉及多個(gè)對(duì)象更新的變換，都會(huì)使它們之幾乎任何一個(gè)涉及多個(gè)對(duì)象更新的變換，都會(huì)使它們之間有短暫的不一致性間有短暫的不一致性silberschatz, korth and sudarshan16.4database system concepts 3rd editioni

5、ntroduction to isolationn為了應(yīng)付這些短暫的不一致性，將多個(gè)相關(guān)操作以組的方式形成事務(wù)，以為了應(yīng)付這些短暫的不一致性，將多個(gè)相關(guān)操作以組的方式形成事務(wù)，以保持一致性的約束保持一致性的約束.一個(gè)從一致性的系統(tǒng)狀態(tài)開(kāi)始的事務(wù)，其間會(huì)導(dǎo)致臨時(shí)一個(gè)從一致性的系統(tǒng)狀態(tài)開(kāi)始的事務(wù)，其間會(huì)導(dǎo)致臨時(shí)的不一致?tīng)顟B(tài)，但是在事務(wù)結(jié)束時(shí)系統(tǒng)會(huì)進(jìn)入一個(gè)新的一致?tīng)顟B(tài)的不一致?tīng)顟B(tài)，但是在事務(wù)結(jié)束時(shí)系統(tǒng)會(huì)進(jìn)入一個(gè)新的一致?tīng)顟B(tài)n事務(wù)是一致性的單位，這就是事務(wù)事務(wù)是一致性的單位，這就是事務(wù)acid特性中的特性中的c (一致性一致性)的含義的含義n如果事務(wù)是隔離地一一在運(yùn)行，那么每一個(gè)事務(wù)可以知道其上一個(gè)事

6、務(wù)所如果事務(wù)是隔離地一一在運(yùn)行，那么每一個(gè)事務(wù)可以知道其上一個(gè)事務(wù)所導(dǎo)致的一致性狀態(tài)導(dǎo)致的一致性狀態(tài)n但是，但是， 如果多個(gè)事務(wù)并發(fā)執(zhí)行，那么某些事務(wù)的輸入和后續(xù)行為或許會(huì)不如果多個(gè)事務(wù)并發(fā)執(zhí)行，那么某些事務(wù)的輸入和后續(xù)行為或許會(huì)不一致，即使每一個(gè)隔離執(zhí)行的事務(wù)都是正確的一致，即使每一個(gè)隔離執(zhí)行的事務(wù)都是正確的,并發(fā)事務(wù)的執(zhí)行必須加以控并發(fā)事務(wù)的執(zhí)行必須加以控制以便正確的程序不會(huì)失效制以便正確的程序不會(huì)失效n這就是事務(wù)這就是事務(wù)acid特性中的特性中的i(隔離性隔離性)的含義的含義silberschatz, korth and sudarshan16.5database system conc

7、epts 3rd editionintroduction to isolationn實(shí)現(xiàn)隔離最簡(jiǎn)單的方式就是一次只運(yùn)行一個(gè)程序?qū)崿F(xiàn)隔離最簡(jiǎn)單的方式就是一次只運(yùn)行一個(gè)程序 (事務(wù)事務(wù),前提是前提是:n如果所有的程序都很短小，如果所有數(shù)據(jù)可以集中存放如果所有的程序都很短小，如果所有數(shù)據(jù)可以集中存放在主存中，且如果所有的數(shù)據(jù)都由一個(gè)處理器來(lái)存取，在主存中，且如果所有的數(shù)據(jù)都由一個(gè)處理器來(lái)存取，這時(shí)沒(méi)必要考慮并發(fā)來(lái)存取這時(shí)沒(méi)必要考慮并發(fā)來(lái)存取這些程序可以簡(jiǎn)單地以這些程序可以簡(jiǎn)單地以順序方式執(zhí)行順序方式執(zhí)行n問(wèn)題是，這些情況中包含了太多的問(wèn)題是，這些情況中包含了太多的”如果如果”n因此，系統(tǒng)必須以某種方

8、式提供并發(fā)控制，保證隔離性因此，系統(tǒng)必須以某種方式提供并發(fā)控制，保證隔離性，使之滿(mǎn)足并發(fā)的第一法則，使之滿(mǎn)足并發(fā)的第一法則n人們已經(jīng)嘗試過(guò)許多種提供自動(dòng)隔離的方法人們已經(jīng)嘗試過(guò)許多種提供自動(dòng)隔離的方法n其中，一個(gè)公認(rèn)可行的解決方案就是封鎖其中，一個(gè)公認(rèn)可行的解決方案就是封鎖silberschatz, korth and sudarshan16.6database system concepts 3rd editionintroduction to isolationn對(duì)封鎖方法，仍有一系列費(fèi)解的問(wèn)題對(duì)封鎖方法，仍有一系列費(fèi)解的問(wèn)題n如果并發(fā)控制機(jī)制代價(jià)過(guò)高，會(huì)使得代價(jià)高于收益。通如果并發(fā)控制機(jī)

9、制代價(jià)過(guò)高，會(huì)使得代價(jià)高于收益。通常，復(fù)雜的算法實(shí)現(xiàn)起來(lái)和執(zhí)行起來(lái)也比較復(fù)雜常，復(fù)雜的算法實(shí)現(xiàn)起來(lái)和執(zhí)行起來(lái)也比較復(fù)雜n第二法則主張使用簡(jiǎn)單的算法第二法則主張使用簡(jiǎn)單的算法silberschatz, korth and sudarshan16.7database system concepts 3rd editionintroduction to isolationn最簡(jiǎn)單的封鎖協(xié)議是給每個(gè)對(duì)象加一個(gè)鎖。如果這個(gè)需要鎖同時(shí)授最簡(jiǎn)單的封鎖協(xié)議是給每個(gè)對(duì)象加一個(gè)鎖。如果這個(gè)需要鎖同時(shí)授于另外一個(gè)事務(wù)，該事務(wù)將等待這個(gè)鎖被釋放于另外一個(gè)事務(wù)，該事務(wù)將等待這個(gè)鎖被釋放n封鎖是一種實(shí)現(xiàn)串行化的機(jī)制，這樣

10、就確保任一時(shí)刻僅僅只有一個(gè)封鎖是一種實(shí)現(xiàn)串行化的機(jī)制，這樣就確保任一時(shí)刻僅僅只有一個(gè)事務(wù)在存取一個(gè)對(duì)象事務(wù)在存取一個(gè)對(duì)象n通過(guò)細(xì)化鎖的粒度（鎖覆蓋的數(shù)據(jù)多少），可以提高并發(fā)度通過(guò)細(xì)化鎖的粒度（鎖覆蓋的數(shù)據(jù)多少），可以提高并發(fā)度n鎖的概念可以追溯到幾千年以前，它是緊接著門(mén)之后的發(fā)明鎖的概念可以追溯到幾千年以前，它是緊接著門(mén)之后的發(fā)明n現(xiàn)在這個(gè)概念（思想）在操作系統(tǒng)領(lǐng)域里已經(jīng)很普遍了現(xiàn)在這個(gè)概念（思想）在操作系統(tǒng)領(lǐng)域里已經(jīng)很普遍了, 在該領(lǐng)域在該領(lǐng)域中，鎖又被稱(chēng)為中，鎖又被稱(chēng)為: 信號(hào)量（信號(hào)量（ semaphores），）， 管程（管程（ monitors） 臨界區(qū)（臨界區(qū)（ critical

11、sections ），）， 串行重用資源（串行重用資源（ serially reuseable reuseable resources ）silberschatz, korth and sudarshan16.8database system concepts 3rd editionintroduction to isolationn事務(wù)系統(tǒng)對(duì)并發(fā)控制的主要貢獻(xiàn)是，進(jìn)一步提煉了原有事務(wù)系統(tǒng)對(duì)并發(fā)控制的主要貢獻(xiàn)是，進(jìn)一步提煉了原有的這些思想，納入了自動(dòng)封鎖以及把事務(wù)的這些思想，納入了自動(dòng)封鎖以及把事務(wù)undo/redo 算算法同封鎖算法結(jié)合起來(lái)法同封鎖算法結(jié)合起來(lái)n這種方法給應(yīng)用程序開(kāi)發(fā)者一個(gè)極

12、簡(jiǎn)單的并發(fā)控制和異這種方法給應(yīng)用程序開(kāi)發(fā)者一個(gè)極簡(jiǎn)單的并發(fā)控制和異常處理的模型常處理的模型n事務(wù)處理系統(tǒng)自動(dòng)地申請(qǐng)加鎖并且登錄日志以維護(hù)事務(wù)處理系統(tǒng)自動(dòng)地申請(qǐng)加鎖并且登錄日志以維護(hù)acid 特性特性n應(yīng)用程序設(shè)計(jì)人員可能疏忽并發(fā)控制問(wèn)題，除非存在著應(yīng)用程序設(shè)計(jì)人員可能疏忽并發(fā)控制問(wèn)題，除非存在著許多事務(wù)存取同一個(gè)對(duì)象而引起的性能問(wèn)題許多事務(wù)存取同一個(gè)對(duì)象而引起的性能問(wèn)題,所謂的熱點(diǎn)所謂的熱點(diǎn)（hotspots hotspots）n隔離性理論是允許自動(dòng)封鎖而帶來(lái)的重要結(jié)果隔離性理論是允許自動(dòng)封鎖而帶來(lái)的重要結(jié)果silberschatz, korth and sudarshan16.9databa

13、se system concepts 3rd editiondependency model of isolationn理解隔離性結(jié)果最簡(jiǎn)單的方式，是根據(jù)事務(wù)的輸入和輸理解隔離性結(jié)果最簡(jiǎn)單的方式，是根據(jù)事務(wù)的輸入和輸出來(lái)理解出來(lái)理解n事務(wù)要么讀一個(gè)對(duì)象查看其狀態(tài)，要么寫(xiě)一個(gè)對(duì)象改變事務(wù)要么讀一個(gè)對(duì)象查看其狀態(tài)，要么寫(xiě)一個(gè)對(duì)象改變對(duì)象的狀態(tài)對(duì)象的狀態(tài)n設(shè)想創(chuàng)建和消除對(duì)象只不過(guò)是改寫(xiě)其狀態(tài)而已。以這種設(shè)想創(chuàng)建和消除對(duì)象只不過(guò)是改寫(xiě)其狀態(tài)而已。以這種粗略的方式來(lái)看，事務(wù)可以看作是一連串對(duì)象的讀寫(xiě)操粗略的方式來(lái)看，事務(wù)可以看作是一連串對(duì)象的讀寫(xiě)操作作n兩個(gè)不同事務(wù)對(duì)同一個(gè)對(duì)象的讀操作不會(huì)破壞一致性，兩

14、個(gè)不同事務(wù)對(duì)同一個(gè)對(duì)象的讀操作不會(huì)破壞一致性，因?yàn)樽x操作不會(huì)改變對(duì)象的狀態(tài)（假定其狀態(tài)初始是一因?yàn)樽x操作不會(huì)改變對(duì)象的狀態(tài)（假定其狀態(tài)初始是一致的）致的）n因此，只有寫(xiě)操作有可能帶來(lái)問(wèn)題因此，只有寫(xiě)操作有可能帶來(lái)問(wèn)題silberschatz, korth and sudarshan16.10database system concepts 3rd editiondependency model of isolationn同一事務(wù)對(duì)同一個(gè)對(duì)象的兩個(gè)寫(xiě)操作也不會(huì)違同一事務(wù)對(duì)同一個(gè)對(duì)象的兩個(gè)寫(xiě)操作也不會(huì)違反一致性，反一致性， acid特性假定事務(wù)知道它正在干什特性假定事務(wù)知道它正在干什么么nacid

15、特性假定：如果事務(wù)隔離地運(yùn)行，最終會(huì)特性假定：如果事務(wù)隔離地運(yùn)行，最終會(huì)正確地轉(zhuǎn)換系統(tǒng)狀態(tài)正確地轉(zhuǎn)換系統(tǒng)狀態(tài)n因此，只有兩個(gè)并發(fā)事務(wù)之間同寫(xiě)操作有關(guān)聯(lián)因此，只有兩個(gè)并發(fā)事務(wù)之間同寫(xiě)操作有關(guān)聯(lián)的的交叉操才可能造成不一致性或是違背隔離的的交叉操才可能造成不一致性或是違背隔離性性silberschatz, korth and sudarshan16.11database system concepts 3rd editiondependency model of isolationsilberschatz, korth and sudarshan16.12database system concep

16、ts 3rd editionstatic vs. dynamic allocationsilberschatz, korth and sudarshan16.13database system concepts 3rd editionstatic vs. dynamic allocationn動(dòng)態(tài)分配系統(tǒng)中，每一個(gè)事務(wù)都被看作是一系動(dòng)態(tài)分配系統(tǒng)中，每一個(gè)事務(wù)都被看作是一系列的行為動(dòng)作而不是輸入輸出集列的行為動(dòng)作而不是輸入輸出集n每個(gè)動(dòng)作的請(qǐng)求都在其出現(xiàn)時(shí)按需調(diào)度。當(dāng)一每個(gè)動(dòng)作的請(qǐng)求都在其出現(xiàn)時(shí)按需調(diào)度。當(dāng)一個(gè)動(dòng)作存取一個(gè)特定的對(duì)象時(shí)，對(duì)象被動(dòng)態(tài)地個(gè)動(dòng)作存取一個(gè)特定的對(duì)象時(shí)，對(duì)象被動(dòng)態(tài)地分配給事

17、務(wù)分配給事務(wù)n例如，只有銀行帳戶(hù)記錄和其它的一些特別的例如，只有銀行帳戶(hù)記錄和其它的一些特別的事務(wù)將要存取的記錄分配給該事務(wù)事務(wù)將要存取的記錄分配給該事務(wù), 出納員才能出納員才能運(yùn)行一個(gè)銀行事務(wù)運(yùn)行一個(gè)銀行事務(wù)n這樣針對(duì)不同帳戶(hù)的事務(wù)可以并發(fā)地且隔離地這樣針對(duì)不同帳戶(hù)的事務(wù)可以并發(fā)地且隔離地執(zhí)行執(zhí)行silberschatz, korth and sudarshan16.14database system concepts 3rd editiontransaction dependency relationsn圖中顯示了兩個(gè)在對(duì)象圖中顯示了兩個(gè)在對(duì)象e 上的事務(wù)上的事務(wù)t1 和和t2 ，所可能有

18、，所可能有的三種讀寫(xiě)執(zhí)行序列操作的三種讀寫(xiě)執(zhí)行序列操作read-write, write-read, write-writen沒(méi)有沒(méi)有read-read 依賴(lài)，因?yàn)樽x同一個(gè)版本的多個(gè)事依賴(lài)，因?yàn)樽x同一個(gè)版本的多個(gè)事務(wù)不會(huì)產(chǎn)生對(duì)另外一個(gè)版本的依賴(lài)務(wù)不會(huì)產(chǎn)生對(duì)另外一個(gè)版本的依賴(lài)silberschatz, korth and sudarshan16.15database system concepts 3rd editiontransaction dependency relationsn一個(gè)依賴(lài)圖可以看作一個(gè)時(shí)間序列一個(gè)依賴(lài)圖可以看作一個(gè)時(shí)間序列:如果事務(wù)如果事務(wù)t1 到事務(wù)到事務(wù)t2 有一條邊，

19、那么有一條邊，那么t1 訪(fǎng)問(wèn)的對(duì)象隨后會(huì)被訪(fǎng)問(wèn)的對(duì)象隨后會(huì)被t2 訪(fǎng)訪(fǎng)問(wèn)，并且這些訪(fǎng)問(wèn)中至少有一個(gè)產(chǎn)生一個(gè)新的版本問(wèn)，并且這些訪(fǎng)問(wèn)中至少有一個(gè)產(chǎn)生一個(gè)新的版本在這種意義上，在這種意義上， 在這種意義上，在這種意義上，t1 在在 t2之前運(yùn)行之前運(yùn)行在事務(wù)的純順序執(zhí)行之中，在事務(wù)的純順序執(zhí)行之中， t1運(yùn)行結(jié)束，再運(yùn)行運(yùn)行結(jié)束，再運(yùn)行t2 t結(jié)束，所有的結(jié)束，所有的依賴(lài)箭頭都是從依賴(lài)箭頭都是從t1 指向指向t2 n隔離定理的主要結(jié)論是：任何一個(gè)沒(méi)有環(huán)的依賴(lài)圖都暗示了隔離定理的主要結(jié)論是：任何一個(gè)沒(méi)有環(huán)的依賴(lài)圖都暗示了事務(wù)的一種隔離執(zhí)行方式事務(wù)的一種隔離執(zhí)行方式silberschatz, kort

20、h and sudarshan16.16database system concepts 3rd editionthe three badtransaction dependenciesn一個(gè)令人驚奇的結(jié)論是：這三種不一致的基本形式覆蓋了所一個(gè)令人驚奇的結(jié)論是：這三種不一致的基本形式覆蓋了所有的情況，如果他們可以被防止發(fā)生，那將不會(huì)有并發(fā)異常有的情況，如果他們可以被防止發(fā)生，那將不會(huì)有并發(fā)異常，事務(wù)將表現(xiàn)為隔離運(yùn)行的狀態(tài)，事務(wù)將表現(xiàn)為隔離運(yùn)行的狀態(tài)silberschatz, korth and sudarshan16.17database system concepts 3rd edition

21、formal model of isolationn為了更精確地描述并發(fā)和恢復(fù)的問(wèn)題，需要一個(gè)為了更精確地描述并發(fā)和恢復(fù)的問(wèn)題，需要一個(gè)形式化的模型。因?yàn)?，這些問(wèn)題是復(fù)雜而又微妙形式化的模型。因?yàn)?，這些問(wèn)題是復(fù)雜而又微妙的，而形式化有助于擺脫描述問(wèn)題的，而形式化有助于擺脫描述問(wèn)題n“隔離性隔離性”的幾種等價(jià)定義的幾種等價(jià)定義直觀(guān)定義直觀(guān)定義:依據(jù)用戶(hù)事務(wù)特性，直觀(guān)定義是為了方便應(yīng)用程序設(shè)依據(jù)用戶(hù)事務(wù)特性，直觀(guān)定義是為了方便應(yīng)用程序設(shè)計(jì)人員和用戶(hù)用來(lái)描述系統(tǒng)的行為計(jì)人員和用戶(hù)用來(lái)描述系統(tǒng)的行為形式化定義形式化定義:依據(jù)系統(tǒng)執(zhí)行的過(guò)程和依賴(lài)圖，形式化定義是為了依據(jù)系統(tǒng)執(zhí)行的過(guò)程和依賴(lài)圖，形式化定義

22、是為了陳述和證明隔離性的性質(zhì)。陳述和證明隔離性的性質(zhì)。操作上的定義操作上的定義:依據(jù)封鎖協(xié)議，操作上的定義是為了用來(lái)指導(dǎo)系依據(jù)封鎖協(xié)議，操作上的定義是為了用來(lái)指導(dǎo)系統(tǒng)的實(shí)現(xiàn)。統(tǒng)的實(shí)現(xiàn)。n下面將要對(duì)沖突可串行性作形式化描述，給出嚴(yán)下面將要對(duì)沖突可串行性作形式化描述，給出嚴(yán)格定義格定義silberschatz, korth and sudarshan16.18database system concepts 3rd edition插曲插曲:畫(huà)的圓沒(méi)有說(shuō)的圓圓畫(huà)的圓沒(méi)有說(shuō)的圓圓n把想明白的事情表達(dá)清楚是作科研的基本功把想明白的事情表達(dá)清楚是作科研的基本功,下面是從下面是從let開(kāi)始開(kāi)始的一種下定義的

23、方法。的一種下定義的方法。n例如例如:圓的定義圓的定義定義定義1:右邊的圖形稱(chēng)為圓右邊的圖形稱(chēng)為圓(通俗，但不及格通俗，但不及格)定義定義2:到一點(diǎn)的距離相等的軌跡稱(chēng)為圓到一點(diǎn)的距離相等的軌跡稱(chēng)為圓(及格及格)定義定義3:在一個(gè)平面上到一點(diǎn)的距離相等的軌跡稱(chēng)為圓在一個(gè)平面上到一點(diǎn)的距離相等的軌跡稱(chēng)為圓(良良)定義定義4:let o be a point over planet p, r = 0, and d(x, y) be the distance between points x and y.then the set c=x | x in p , d(x,o)=r is said to b

24、e the circle with center o and radius r. (信息完整信息完整,嚴(yán)格規(guī)范嚴(yán)格規(guī)范,所以所以:優(yōu)優(yōu))n嚴(yán)格定義好處嚴(yán)格定義好處:有了符號(hào)體系（模型），為后續(xù)研究奠定基礎(chǔ)有了符號(hào)體系（模型），為后續(xù)研究奠定基礎(chǔ)silberschatz, korth and sudarshan16.19database system concepts 3rd editionformal model of isolationn隔離性隔離性(用戶(hù)定義用戶(hù)定義1):n事務(wù)處理系統(tǒng)可以并發(fā)地執(zhí)行事務(wù)，但它的結(jié)果事務(wù)處理系統(tǒng)可以并發(fā)地執(zhí)行事務(wù)，但它的結(jié)果如同順序執(zhí)行一樣。就應(yīng)用程序而言，

25、事務(wù)好象如同順序執(zhí)行一樣。就應(yīng)用程序而言，事務(wù)好象是在沒(méi)有并發(fā)的情況下運(yùn)行；事務(wù)的確切執(zhí)行順是在沒(méi)有并發(fā)的情況下運(yùn)行；事務(wù)的確切執(zhí)行順序是由系統(tǒng)控制的，系統(tǒng)行為等價(jià)于事務(wù)的某種序是由系統(tǒng)控制的，系統(tǒng)行為等價(jià)于事務(wù)的某種順序執(zhí)行，其造成的表面現(xiàn)象是一個(gè)事務(wù)執(zhí)行完順序執(zhí)行，其造成的表面現(xiàn)象是一個(gè)事務(wù)執(zhí)行完畢后，下一個(gè)事務(wù)才開(kāi)始執(zhí)行畢后，下一個(gè)事務(wù)才開(kāi)始執(zhí)行silberschatz, korth and sudarshan16.20database system concepts 3rd editionformal model of isolationn隔離性隔離性(用戶(hù)定義用戶(hù)定義2)：這是更為程

26、序化的定義，稱(chēng)：這是更為程序化的定義，稱(chēng)事務(wù)事務(wù)t與其它事務(wù)是隔離的，如果：與其它事務(wù)是隔離的，如果：（0） t不會(huì)重寫(xiě)其它事務(wù)的臟數(shù)據(jù)不會(huì)重寫(xiě)其它事務(wù)的臟數(shù)據(jù)（1） t所寫(xiě)的數(shù)據(jù)，在所寫(xiě)的數(shù)據(jù)，在t提交（提交（commit work ）之前，不會(huì)被其它事）之前，不會(huì)被其它事務(wù)讀或者寫(xiě)務(wù)讀或者寫(xiě)（2） t不讀臟數(shù)據(jù)不讀臟數(shù)據(jù)（3）在）在t提交之前，其它事務(wù)不會(huì)寫(xiě)提交之前，其它事務(wù)不會(huì)寫(xiě)t所要讀的數(shù)據(jù)所要讀的數(shù)據(jù)條件條件(0) 和和 (1)排除了丟失修改排除了丟失修改, (2) 防止了讀臟數(shù)據(jù)防止了讀臟數(shù)據(jù) (3)防止了不可重復(fù)防止了不可重復(fù)讀讀n用用bernstein, hadzilacos,

27、 goodman1987,p.36 的記法，定義的記法，定義1是是sr ，定義，定義2是兩階段封鎖（是兩階段封鎖（ 2pl）n sr 2pl ：一些隔離性方法比這里描述的封鎖機(jī)制更具一般性一些隔離性方法比這里描述的封鎖機(jī)制更具一般性silberschatz, korth and sudarshan16.21database system concepts 3rd editionformal model: actions and transactionssilberschatz, korth and sudarshan16.22database system concepts 3rd editi

28、onformal model: simple transactionn系統(tǒng)支持系統(tǒng)支持對(duì)象上的動(dòng)作對(duì)象上的動(dòng)作read，write ，xlock ，slock ，unlock三個(gè)一般性的動(dòng)作三個(gè)一般性的動(dòng)作 begin ，commit，rollbackn一個(gè)簡(jiǎn)化事務(wù)是由一個(gè)簡(jiǎn)化事務(wù)是由read，write， xlock，slock，unlock 等動(dòng)作組成的等動(dòng)作組成的silberschatz, korth and sudarshan16.23database system concepts 3rd editionlocks cover actions(10/21)silberschatz,

29、korth and sudarshan16.24database system concepts 3rd editionwell formed and two-phasedtransactionssilberschatz, korth and sudarshan16.25database system concepts 3rd editionwell formed and two-phasedtransactionssilberschatz, korth and sudarshan16.26database system concepts 3rd editiontransaction hist

30、oryn一組事務(wù)的所有動(dòng)作序列，在保持各自順序的情況下，一組事務(wù)的所有動(dòng)作序列，在保持各自順序的情況下，歸并成的一個(gè)單一序列，我們稱(chēng)之為這組事務(wù)的一個(gè)歸并成的一個(gè)單一序列，我們稱(chēng)之為這組事務(wù)的一個(gè)調(diào)調(diào)度度n最簡(jiǎn)單的調(diào)度是首先運(yùn)行一個(gè)事務(wù)的所有動(dòng)作，然后再最簡(jiǎn)單的調(diào)度是首先運(yùn)行一個(gè)事務(wù)的所有動(dòng)作，然后再運(yùn)行另外一個(gè)事務(wù)的所有動(dòng)作，如此一直下去，這樣的運(yùn)行另外一個(gè)事務(wù)的所有動(dòng)作，如此一直下去，這樣的“一次一個(gè)事務(wù)一次一個(gè)事務(wù)”的調(diào)度稱(chēng)為的調(diào)度稱(chēng)為串行調(diào)度串行調(diào)度(serial history)n調(diào)度的定義暗指了每個(gè)動(dòng)作作為對(duì)象狀態(tài)的一個(gè)調(diào)度的定義暗指了每個(gè)動(dòng)作作為對(duì)象狀態(tài)的一個(gè)acid 轉(zhuǎn)轉(zhuǎn)換：即

31、每個(gè)動(dòng)作是當(dāng)作一個(gè)換：即每個(gè)動(dòng)作是當(dāng)作一個(gè)acid 步驟來(lái)執(zhí)行的步驟來(lái)執(zhí)行的n下面的問(wèn)題是，對(duì)給定的一組下面的問(wèn)題是，對(duì)給定的一組acid 動(dòng)作，如何既能并發(fā)動(dòng)作，如何既能并發(fā)執(zhí)行這些動(dòng)作，而又保持事務(wù)的隔離性執(zhí)行這些動(dòng)作，而又保持事務(wù)的隔離性silberschatz, korth and sudarshan16.27database system concepts 3rd editionsummary of definitionsn事務(wù)是在對(duì)象上的事務(wù)是在對(duì)象上的 read，write ，slock和和xlock 動(dòng)作的序列，它以動(dòng)作的序列，它以commit 或或 rollback動(dòng)作結(jié)尾動(dòng)

32、作結(jié)尾n含含commit或或rollback的一般事務(wù)可以轉(zhuǎn)化成為簡(jiǎn)化的一般事務(wù)可以轉(zhuǎn)化成為簡(jiǎn)化事務(wù)，它只含事務(wù)，它只含read, write,slock,xlock和和 unlock動(dòng)作動(dòng)作n如果事務(wù)的每個(gè)如果事務(wù)的每個(gè)read，write，unlock 都被相應(yīng)的都被相應(yīng)的鎖覆蓋，且所有的鎖都是在事務(wù)結(jié)束時(shí)釋放，那么我們鎖覆蓋，且所有的鎖都是在事務(wù)結(jié)束時(shí)釋放，那么我們稱(chēng)這樣的事務(wù)是稱(chēng)這樣的事務(wù)是規(guī)范的規(guī)范的n如果一個(gè)事務(wù)可以分成兩個(gè)階段，只請(qǐng)求封鎖的擴(kuò)展階如果一個(gè)事務(wù)可以分成兩個(gè)階段，只請(qǐng)求封鎖的擴(kuò)展階段，和只釋放封鎖的收縮階段，那么我們稱(chēng)之為段，和只釋放封鎖的收縮階段，那么我們稱(chēng)之為兩階

33、段兩階段的事務(wù)的事務(wù)silberschatz, korth and sudarshan16.28database system concepts 3rd editionsilberschatz, korth and sudarshan16.29database system concepts 3rd editionsilberschatz, korth and sudarshan16.30database system concepts 3rd editionn鎖兼容性矩陣鎖兼容性矩陣n如果事務(wù)對(duì)某數(shù)據(jù)項(xiàng)的鎖請(qǐng)求與其他事務(wù)在該數(shù)據(jù)項(xiàng)如果事務(wù)對(duì)某數(shù)據(jù)項(xiàng)的鎖請(qǐng)求與其他事務(wù)在該數(shù)據(jù)項(xiàng)上已有的鎖兼容上

34、已有的鎖兼容, 則請(qǐng)求被批準(zhǔn)則請(qǐng)求被批準(zhǔn)n任意數(shù)目的事務(wù)可對(duì)同一數(shù)據(jù)持有共享鎖任意數(shù)目的事務(wù)可對(duì)同一數(shù)據(jù)持有共享鎖; 但若一事務(wù)但若一事務(wù)對(duì)某數(shù)據(jù)持有排他鎖對(duì)某數(shù)據(jù)持有排他鎖, 則其他事務(wù)不得持有該數(shù)據(jù)上的則其他事務(wù)不得持有該數(shù)據(jù)上的任何鎖任何鎖n若不能授予鎖若不能授予鎖, 則使請(qǐng)求事務(wù)等待持有不兼容鎖的所有則使請(qǐng)求事務(wù)等待持有不兼容鎖的所有其他事務(wù)釋放鎖其他事務(wù)釋放鎖. 然后才可授予鎖然后才可授予鎖silberschatz, korth and sudarshan16.31database system concepts 3rd editionn執(zhí)行封鎖的事務(wù)例執(zhí)行封鎖的事務(wù)例: t2: l

35、ock-s(a); read (a); unlock(a); lock-s(b); read (b); unlock(b); display(a+b)n上例中的封鎖不足以保證可串行化上例中的封鎖不足以保證可串行化 若若a和和b 在讀操作之間被修改在讀操作之間被修改, 則顯示的總和是錯(cuò)誤的則顯示的總和是錯(cuò)誤的n鎖協(xié)議鎖協(xié)議是所有事務(wù)在請(qǐng)求與釋放鎖時(shí)遵守的規(guī)則集合是所有事務(wù)在請(qǐng)求與釋放鎖時(shí)遵守的規(guī)則集合n鎖協(xié)議對(duì)可能出現(xiàn)的調(diào)度集合加以限制鎖協(xié)議對(duì)可能出現(xiàn)的調(diào)度集合加以限制silberschatz, korth and sudarshan16.32database system concepts 3

36、rd editionn考慮下面的部分調(diào)度考慮下面的部分調(diào)度nt3 和和t4 都不能繼續(xù)都不能繼續(xù) 執(zhí)行執(zhí)行l(wèi)ock-s(b) 使使t4 等待等待t3 釋放它持有的釋放它持有的b上的上的鎖鎖, 而執(zhí)行而執(zhí)行 lock-x(a) 使使t3 等待等待t4 釋放它持有的釋放它持有的a上的鎖上的鎖n這種情形稱(chēng)為死鎖這種情形稱(chēng)為死鎖n為處理死鎖為處理死鎖, t3 或或t4 必須回滾并釋放它持有的鎖必須回滾并釋放它持有的鎖silberschatz, korth and sudarshan16.33database system concepts 3rd editionn多數(shù)鎖協(xié)議中都存在潛在的死鎖可能性多數(shù)

37、鎖協(xié)議中都存在潛在的死鎖可能性. 但為了鎖機(jī)制但為了鎖機(jī)制的好處的好處, 這個(gè)缺陷的引入是可以容忍的這個(gè)缺陷的引入是可以容忍的n如果并發(fā)控制管理器設(shè)計(jì)的不好還可能出現(xiàn)如果并發(fā)控制管理器設(shè)計(jì)的不好還可能出現(xiàn)餓死餓死n例如例如:一個(gè)事務(wù)可能在等待給數(shù)據(jù)項(xiàng)加一個(gè)事務(wù)可能在等待給數(shù)據(jù)項(xiàng)加x-鎖鎖, 同時(shí)一系列其他事務(wù)在同時(shí)一系列其他事務(wù)在請(qǐng)求并被授予同一數(shù)據(jù)項(xiàng)上的請(qǐng)求并被授予同一數(shù)據(jù)項(xiàng)上的s-鎖鎖同一事務(wù)因死鎖而被重復(fù)回滾同一事務(wù)因死鎖而被重復(fù)回滾n并發(fā)控制管理器可設(shè)計(jì)成能夠防止餓死并發(fā)控制管理器可設(shè)計(jì)成能夠防止餓死silberschatz, korth and sudarshan16.34datab

38、ase system concepts 3rd editionn兩階段封鎖協(xié)議預(yù)備兩階段封鎖協(xié)議預(yù)備: 封鎖資源與獲得服務(wù)的直觀(guān)解釋封鎖資源與獲得服務(wù)的直觀(guān)解釋silberschatz, korth and sudarshan16.35database system concepts 3rd editionn兩階段封鎖協(xié)議預(yù)備兩階段封鎖協(xié)議預(yù)備:封鎖資源與獲得服務(wù)的直觀(guān)解釋封鎖資源與獲得服務(wù)的直觀(guān)解釋silberschatz, korth and sudarshan16.36database system concepts 3rd editionn兩階段封鎖協(xié)議預(yù)備兩階段封鎖協(xié)議預(yù)備: 封鎖資

39、源與獲得服務(wù)的直觀(guān)解釋封鎖資源與獲得服務(wù)的直觀(guān)解釋silberschatz, korth and sudarshan16.37database system concepts 3rd editionn兩階段封鎖協(xié)議預(yù)備兩階段封鎖協(xié)議預(yù)備:封鎖資源與獲得服務(wù)的直觀(guān)解釋封鎖資源與獲得服務(wù)的直觀(guān)解釋silberschatz, korth and sudarshan16.38database system concepts 3rd editionn兩階段鎖不能避免死鎖兩階段鎖不能避免死鎖n兩階段鎖不能避免級(jí)聯(lián)回滾兩階段鎖不能避免級(jí)聯(lián)回滾n但用但用嚴(yán)格嚴(yán)格(strict)兩階段鎖兩階段鎖的改進(jìn)協(xié)議可避免

40、的改進(jìn)協(xié)議可避免: 事務(wù)必須保持它的所有排他鎖直至提交事務(wù)必須保持它的所有排他鎖直至提交/夭折夭折n嚴(yán)密?chē)?yán)密(rigorous)兩階段鎖兩階段鎖更加嚴(yán)格更加嚴(yán)格: 所有鎖都必所有鎖都必須保持到事務(wù)提交須保持到事務(wù)提交/夭折夭折,在這種協(xié)議中事務(wù)可在這種協(xié)議中事務(wù)可按它們提交的次序串行化按它們提交的次序串行化silberschatz, korth and sudarshan16.39database system concepts 3rd editionn存在用兩階段鎖不能得到的沖突可串行化調(diào)度存在用兩階段鎖不能得到的沖突可串行化調(diào)度n即即: 給定不遵守兩階段鎖的事務(wù)給定不遵守兩階段鎖的事務(wù)ti

41、, 可以找到使可以找到使用兩階段鎖的事務(wù)用兩階段鎖的事務(wù)tj 及及ti 與與tj 的一個(gè)不是沖突的一個(gè)不是沖突可串行化的調(diào)度可串行化的調(diào)度n然而然而, 在缺少額外信息在缺少額外信息(如數(shù)據(jù)存取次序如數(shù)據(jù)存取次序)的情況的情況下下, 兩階段鎖對(duì)沖突可串行化要求來(lái)說(shuō)是必要兩階段鎖對(duì)沖突可串行化要求來(lái)說(shuō)是必要的的silberschatz, korth and sudarshan16.40database system concepts 3rd editionn帶有鎖轉(zhuǎn)換的兩階段鎖帶有鎖轉(zhuǎn)換的兩階段鎖: 第一階段第一階段: （趨勢(shì)：擴(kuò)大封鎖，減少共享）（趨勢(shì)：擴(kuò)大封鎖，減少共享） 可獲得可獲得 loc

42、k-s可獲得可獲得 lock-x可轉(zhuǎn)換可轉(zhuǎn)換 lock-s 到到 lock-x (升級(jí)升級(jí)) 第二階段第二階段:（趨勢(shì)：擴(kuò)大共享，減少封鎖）（趨勢(shì)：擴(kuò)大共享，減少封鎖）可釋放可釋放 lock-s可釋放可釋放 lock-x可轉(zhuǎn)換可轉(zhuǎn)換 lock-x 到到 lock-s (降級(jí)降級(jí))n本協(xié)議確?？纱谢緟f(xié)議確?？纱谢? 但仍依靠程序員插入各種封鎖指令但仍依靠程序員插入各種封鎖指令silberschatz, korth and sudarshan16.41database system concepts 3rd editionn事務(wù)事務(wù)ti 發(fā)出標(biāo)準(zhǔn)的讀發(fā)出標(biāo)準(zhǔn)的讀/寫(xiě)指令寫(xiě)指令, 無(wú)需使用顯式

43、的封鎖調(diào)用無(wú)需使用顯式的封鎖調(diào)用n操作操作read(d) 的處理如下的處理如下:(把方便留給用戶(hù)，把困難留給系統(tǒng)） if ti 在d上有鎖 then read(d) else begin 如有必要?jiǎng)t等待直至沒(méi)有事務(wù)在如有必要?jiǎng)t等待直至沒(méi)有事務(wù)在d上有上有l(wèi)ock-x 授予授予ti 在在d上的上的lock-s; read(d) endsilberschatz, korth and sudarshan16.42database system concepts 3rd editionnwrite(d) 如下處理如下處理: if ti 在在d上有上有 lock-x then write(d) else

44、 begin 如有必要?jiǎng)t等待直至沒(méi)有事務(wù)在如有必要?jiǎng)t等待直至沒(méi)有事務(wù)在d上有任何鎖上有任何鎖, if ti 在在d上有上有l(wèi)ock-s then 將將d上的鎖升級(jí)到上的鎖升級(jí)到 lock-x else 授予授予ti 在在d上的上的 lock-x write(d) end;n所有鎖在提交所有鎖在提交/夭折之后釋放夭折之后釋放silberschatz, korth and sudarshan16.43database system concepts 3rd editionn鎖管理器鎖管理器可實(shí)現(xiàn)為單獨(dú)的進(jìn)程可實(shí)現(xiàn)為單獨(dú)的進(jìn)程, 事務(wù)向它發(fā)送加鎖與釋事務(wù)向它發(fā)送加鎖與釋放鎖請(qǐng)求放鎖請(qǐng)求n鎖管理器通過(guò)

45、發(fā)送鎖授予消息來(lái)回答鎖請(qǐng)求鎖管理器通過(guò)發(fā)送鎖授予消息來(lái)回答鎖請(qǐng)求(或死鎖時(shí)或死鎖時(shí)發(fā)送請(qǐng)事務(wù)回滾的消息發(fā)送請(qǐng)事務(wù)回滾的消息)n請(qǐng)求事務(wù)等待請(qǐng)求事務(wù)等待, 直至它的請(qǐng)求被回答直至它的請(qǐng)求被回答n鎖管理器維護(hù)一個(gè)稱(chēng)為鎖管理器維護(hù)一個(gè)稱(chēng)為鎖表鎖表的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄授予的的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄授予的鎖和掛起的請(qǐng)求鎖和掛起的請(qǐng)求n鎖表通常實(shí)現(xiàn)為以被鎖數(shù)據(jù)項(xiàng)的名字為索引的內(nèi)存散鎖表通常實(shí)現(xiàn)為以被鎖數(shù)據(jù)項(xiàng)的名字為索引的內(nèi)存散列表列表silberschatz, korth and sudarshan16.44database system concepts 3rd editionsilberschatz, korth

46、 and sudarshan16.45database system concepts 3rd editionn黑色矩形表示已授予的鎖黑色矩形表示已授予的鎖, 白色白色矩形表示等待的請(qǐng)求矩形表示等待的請(qǐng)求n鎖表記錄授予或請(qǐng)求的鎖的類(lèi)型鎖表記錄授予或請(qǐng)求的鎖的類(lèi)型n新請(qǐng)求加入到對(duì)某數(shù)據(jù)項(xiàng)的請(qǐng)求新請(qǐng)求加入到對(duì)某數(shù)據(jù)項(xiàng)的請(qǐng)求隊(duì)列的末尾隊(duì)列的末尾, 并且如果與所有以并且如果與所有以前的鎖兼容則被授予前的鎖兼容則被授予n釋放鎖請(qǐng)求導(dǎo)致請(qǐng)求被刪除釋放鎖請(qǐng)求導(dǎo)致請(qǐng)求被刪除, 并并且其后的請(qǐng)求被檢查看看現(xiàn)在是且其后的請(qǐng)求被檢查看看現(xiàn)在是否可以授予否可以授予n如果事務(wù)夭折如果事務(wù)夭折, 則該事務(wù)的所有則該事務(wù)的

47、所有等待或已批準(zhǔn)的請(qǐng)求都被刪除等待或已批準(zhǔn)的請(qǐng)求都被刪除n鎖管理器可能保存每個(gè)事務(wù)持有鎖管理器可能保存每個(gè)事務(wù)持有的鎖的列表的鎖的列表, 以便對(duì)此高效地實(shí)以便對(duì)此高效地實(shí)現(xiàn)現(xiàn)silberschatz, korth and sudarshan16.46database system concepts 3rd editionhash表實(shí)現(xiàn)表實(shí)現(xiàn), 高效高效)silberschatz, korth and sudarshan16.47database system concepts 3rd editionn基于圖的協(xié)議是相對(duì)于兩階段鎖協(xié)議的另一選基于圖的協(xié)議是相對(duì)于兩階段鎖協(xié)議的另一選擇擇n在所有數(shù)

48、據(jù)項(xiàng)集合在所有數(shù)據(jù)項(xiàng)集合d = d1, d2 ,., dh 上定義一上定義一個(gè)偏序個(gè)偏序(讀作goes to 或先于先于)如果如果di dj 則存取則存取di 和和dj 的任何事務(wù)都必須先存的任何事務(wù)都必須先存取取di 后存取后存取dj集合集合d可視為可視為有向無(wú)圈圖有向無(wú)圈圖(特例為樹(shù)特例為樹(shù)(有根的圖有根的圖),表示表示數(shù)據(jù)的加工流程數(shù)據(jù)的加工流程)稱(chēng)為數(shù)據(jù)庫(kù)圖稱(chēng)為數(shù)據(jù)庫(kù)圖n樹(shù)協(xié)議樹(shù)協(xié)議是圖協(xié)議的一種簡(jiǎn)單形式是圖協(xié)議的一種簡(jiǎn)單形式silberschatz, korth and sudarshan16.48database system concepts 3rd editionsilbers

49、chatz, korth and sudarshan16.49database system concepts 3rd editionn樹(shù)協(xié)議確保沖突可串行化且可避免死鎖樹(shù)協(xié)議確保沖突可串行化且可避免死鎖n樹(shù)協(xié)議中釋放鎖可比兩階段鎖協(xié)議更早發(fā)生樹(shù)協(xié)議中釋放鎖可比兩階段鎖協(xié)議更早發(fā)生較短等待時(shí)間較短等待時(shí)間, 增加并發(fā)度增加并發(fā)度協(xié)議無(wú)死鎖協(xié)議無(wú)死鎖, 不需回滾不需回滾事務(wù)的夭折仍然可能導(dǎo)致級(jí)聯(lián)回滾事務(wù)的夭折仍然可能導(dǎo)致級(jí)聯(lián)回滾 (教材中對(duì)此有改進(jìn)方法教材中對(duì)此有改進(jìn)方法)n然而然而, 在樹(shù)封鎖協(xié)議中在樹(shù)封鎖協(xié)議中, 事務(wù)可能對(duì)它不需要存取的數(shù)據(jù)項(xiàng)事務(wù)可能對(duì)它不需要存取的數(shù)據(jù)項(xiàng)加鎖加鎖(可能誅連

50、可能誅連(冤枉封鎖了冤枉封鎖了)太多子孫，誅九族太多子孫，誅九族)增加鎖開(kāi)銷(xiāo)以及額外的等待時(shí)間增加鎖開(kāi)銷(xiāo)以及額外的等待時(shí)間潛在的并發(fā)度降低潛在的并發(fā)度降低n樹(shù)協(xié)議可產(chǎn)生兩階段鎖協(xié)議不能產(chǎn)生的調(diào)度樹(shù)協(xié)議可產(chǎn)生兩階段鎖協(xié)議不能產(chǎn)生的調(diào)度, 反之亦然反之亦然.樹(shù)協(xié)議與樹(shù)協(xié)議與2pl沒(méi)絕對(duì)的強(qiáng)弱，各有用武之地沒(méi)絕對(duì)的強(qiáng)弱，各有用武之地silberschatz, korth and sudarshan16.50database system concepts 3rd editionn兩種時(shí)間戳，分別對(duì)事務(wù)，對(duì)數(shù)據(jù)兩種時(shí)間戳，分別對(duì)事務(wù)，對(duì)數(shù)據(jù)n每個(gè)事務(wù)進(jìn)入系統(tǒng)時(shí)被賦予一個(gè)時(shí)間戳，若一個(gè)老事務(wù)每個(gè)事務(wù)進(jìn)入

51、系統(tǒng)時(shí)被賦予一個(gè)時(shí)間戳，若一個(gè)老事務(wù)ti 具有時(shí)間戳具有時(shí)間戳ts(ti)，則一個(gè)新事務(wù)，則一個(gè)新事務(wù)tj 被賦予時(shí)間戳被賦予時(shí)間戳ts(tj) 使得使得ts(ti) ts(tj) n該協(xié)議管理并發(fā)執(zhí)行該協(xié)議管理并發(fā)執(zhí)行, 使得時(shí)間戳決定了串行化次序使得時(shí)間戳決定了串行化次序n為了保證這種行為為了保證這種行為, 該協(xié)議為每個(gè)數(shù)據(jù)該協(xié)議為每個(gè)數(shù)據(jù)q維護(hù)兩個(gè)時(shí)間戳值維護(hù)兩個(gè)時(shí)間戳值w-timestamp(q):成功執(zhí)行了成功執(zhí)行了write(q)的所有事務(wù)中的最大時(shí)間戳的所有事務(wù)中的最大時(shí)間戳r-timestamp(q):成功執(zhí)行了成功執(zhí)行了read(q)的所有事務(wù)中的最大時(shí)間戳的所有事務(wù)中的最大

52、時(shí)間戳n注注:學(xué)習(xí)時(shí)間戳協(xié)議的方法學(xué)習(xí)時(shí)間戳協(xié)議的方法聽(tīng)講課，有時(shí)不能立即反應(yīng)和理解聽(tīng)講課，有時(shí)不能立即反應(yīng)和理解需用例子，畫(huà)出時(shí)間軸，調(diào)度，需要細(xì)心體會(huì)需用例子，畫(huà)出時(shí)間軸，調(diào)度，需要細(xì)心體會(huì)silberschatz, korth and sudarshan16.51database system concepts 3rd editionn假設(shè)事務(wù)假設(shè)事務(wù)ti 發(fā)出了發(fā)出了read(q) 1. 若若ts(ti) w-timestamp(q)，則，則ti 需要讀需要讀q 的已經(jīng)的已經(jīng)被寫(xiě)覆蓋了的一個(gè)值，因此，被寫(xiě)覆蓋了的一個(gè)值，因此， read 操作被拒絕，操作被拒絕， ti 回滾回滾 2.

53、若若ts(ti) r-timestamp(q)，則，則read 操作執(zhí)行，并操作執(zhí)行，并且且r-timestamp(q) 置為置為r-timestamp(q) 與與ts(ti)的的最大值最大值n時(shí)戳讀法則：讀舊回卷（時(shí)戳讀法則：讀舊回卷（roll back原義，電影膠片卷原義，電影膠片卷回重放）回重放）silberschatz, korth and sudarshan16.52database system concepts 3rd editionn假設(shè)事務(wù)假設(shè)事務(wù)ti 發(fā)出發(fā)出write(q):若若ts(ti) r-timestamp(q), 則則ti 要產(chǎn)生的要產(chǎn)生的q 值是值是過(guò)去曾需要

54、的過(guò)去曾需要的, 而系統(tǒng)假設(shè)該值永遠(yuǎn)不會(huì)產(chǎn)生而系統(tǒng)假設(shè)該值永遠(yuǎn)不會(huì)產(chǎn)生. 于是于是, write 操作被拒絕操作被拒絕, ti 回滾回滾若若ts(ti) w-timestamp(q), 則則ti 試圖寫(xiě)一個(gè)過(guò)時(shí)試圖寫(xiě)一個(gè)過(guò)時(shí)的的q值值,因此因此, 這個(gè)這個(gè)write 操作被拒絕操作被拒絕, ti 回滾回滾否則否則,執(zhí)行執(zhí)行write 操作操作, 且且w-timestamp(q) 置為置為ts(ti)n時(shí)間戳寫(xiě)法則：寫(xiě)先于讀或以舊蓋新，否則回卷時(shí)間戳寫(xiě)法則：寫(xiě)先于讀或以舊蓋新，否則回卷n結(jié)論結(jié)論: 時(shí)間戳排序協(xié)議可確保任何沖突的時(shí)間戳排序協(xié)議可確保任何沖突的read 和和write 操作都能按照

55、時(shí)間戳序執(zhí)行操作都能按照時(shí)間戳序執(zhí)行silberschatz, korth and sudarshan16.53database system concepts 3rd editionn針對(duì)若干數(shù)據(jù)項(xiàng)的、時(shí)間戳為針對(duì)若干數(shù)據(jù)項(xiàng)的、時(shí)間戳為1, 2, 3, 4, 5的事務(wù)的一個(gè)部分調(diào)度的事務(wù)的一個(gè)部分調(diào)度silberschatz, korth and sudarshan16.54database system concepts 3rd editionn時(shí)間戳保證了可串行性，有絕對(duì)時(shí)間戳，等候圖不會(huì)有循環(huán)（時(shí)間戳保證了可串行性，有絕對(duì)時(shí)間戳，等候圖不會(huì)有循環(huán)（ 按按資歷分配資源）資歷分配資源） n

56、因此因此, 優(yōu)先圖中沒(méi)有圈優(yōu)先圖中沒(méi)有圈n時(shí)間戳協(xié)議確保沒(méi)有死鎖時(shí)間戳協(xié)議確保沒(méi)有死鎖, 因?yàn)闆](méi)有事務(wù)會(huì)等待因?yàn)闆](méi)有事務(wù)會(huì)等待n但是但是, 調(diào)度可能導(dǎo)致級(jí)聯(lián)回滾調(diào)度可能導(dǎo)致級(jí)聯(lián)回滾, 并且甚至可能不可恢復(fù)并且甚至可能不可恢復(fù)n先生沒(méi)有晉升成功，后生晉升后也要作廢先生沒(méi)有晉升成功，后生晉升后也要作廢較小時(shí)間戳事務(wù)較大時(shí)間戳事務(wù)silberschatz, korth and sudarshan16.55database system concepts 3rd editionn時(shí)間戳排序協(xié)議的問(wèn)題時(shí)間戳排序協(xié)議的問(wèn)題:假如假如ti 夭折，但夭折，但tj 已經(jīng)讀了已經(jīng)讀了ti 所寫(xiě)的一個(gè)數(shù)據(jù)項(xiàng)所寫(xiě)的一

57、個(gè)數(shù)據(jù)項(xiàng)則則tj 必須夭折，若必須夭折，若tj 已被允許較早提交，則該調(diào)度是不可恢已被允許較早提交，則該調(diào)度是不可恢復(fù)的復(fù)的進(jìn)一步，任何讀了進(jìn)一步，任何讀了tj 所寫(xiě)的數(shù)據(jù)項(xiàng)的事務(wù)必須夭折所寫(xiě)的數(shù)據(jù)項(xiàng)的事務(wù)必須夭折這可能導(dǎo)致級(jí)聯(lián)回滾：即一個(gè)回滾鏈這可能導(dǎo)致級(jí)聯(lián)回滾：即一個(gè)回滾鏈silberschatz, korth and sudarshan16.56database system concepts 3rd editionn解決方案解決方案:1.事務(wù)到最后才寫(xiě)事務(wù)到最后才寫(xiě)(at the end of its processing)2.所有寫(xiě)動(dòng)作作為一個(gè)原子（定先進(jìn)和發(fā)獎(jiǎng)金一起寫(xiě)盤(pán)）所有寫(xiě)動(dòng)作

58、作為一個(gè)原子（定先進(jìn)和發(fā)獎(jiǎng)金一起寫(xiě)盤(pán)）3.事務(wù)中止后重新開(kāi)始，且重新給時(shí)間戳事務(wù)中止后重新開(kāi)始，且重新給時(shí)間戳silberschatz, korth and sudarshan16.57database system concepts 3rd editionn是時(shí)間戳排序協(xié)議的修正版本，其中過(guò)時(shí)是時(shí)間戳排序協(xié)議的修正版本，其中過(guò)時(shí)write 操作在操作在某些情況下可以忽略某些情況下可以忽略n當(dāng)當(dāng)ti 試圖寫(xiě)數(shù)據(jù)項(xiàng)試圖寫(xiě)數(shù)據(jù)項(xiàng)q, 若若 ts(ti) w-timestamp(q), 則則ti 正試圖寫(xiě)一個(gè)過(guò)時(shí)的正試圖寫(xiě)一個(gè)過(guò)時(shí)的q值。因此，不是按時(shí)間戳排序值。因此，不是按時(shí)間戳排序協(xié)議要求的那樣

59、回滾協(xié)議要求的那樣回滾ti，這個(gè)，這個(gè)write 操作可以忽略（其操作可以忽略（其他情況下此協(xié)議與按時(shí)間戳排序協(xié)議相同）他情況下此協(xié)議與按時(shí)間戳排序協(xié)議相同）nthomas寫(xiě)規(guī)則允許更多的潛在并發(fā)性，但不同于前面寫(xiě)規(guī)則允許更多的潛在并發(fā)性，但不同于前面的協(xié)議，它允許做某些非沖突可串行化但是視圖可串的協(xié)議，它允許做某些非沖突可串行化但是視圖可串行化的調(diào)度（即最終結(jié)果等價(jià)于某個(gè)串行調(diào)度）行化的調(diào)度（即最終結(jié)果等價(jià)于某個(gè)串行調(diào)度）silberschatz, korth and sudarshan16.58database system concepts 3rd editionn思路思路:大膽先做，做

60、了再驗(yàn)證，即不要坐而論道，遲遲大膽先做，做了再驗(yàn)證，即不要坐而論道，遲遲不動(dòng)不動(dòng)n事務(wù)事務(wù)ti 的執(zhí)行分成三個(gè)階段的執(zhí)行分成三個(gè)階段: 1. 讀與執(zhí)行階段讀與執(zhí)行階段: 事務(wù)事務(wù)ti 的的write操作只寫(xiě)到臨時(shí)局部變操作只寫(xiě)到臨時(shí)局部變量量 2. 有效性檢查階段有效性檢查階段: 事務(wù)事務(wù)ti 執(zhí)行執(zhí)行“有效性檢查有效性檢查”來(lái)決定來(lái)決定局部變量的值是否可以寫(xiě)到數(shù)據(jù)庫(kù)而不違反可串行化局部變量的值是否可以寫(xiě)到數(shù)據(jù)庫(kù)而不違反可串行化 3. 寫(xiě)階段寫(xiě)階段: 若若ti 通過(guò)有效性檢查通過(guò)有效性檢查, 則更新數(shù)據(jù)庫(kù)則更新數(shù)據(jù)庫(kù); 否則否則ti 回滾回滾silberschatz, korth and su