數(shù) 據(jù) 庫(kù) 概 論 與 技 術(shù) 數(shù)據(jù)恢復(fù)技術(shù)

1、數(shù) 據(jù) 庫(kù) 概 論 與 技 術(shù)數(shù)據(jù)恢復(fù)技術(shù),湯 娜中山大學(xué)計(jì)算機(jī)科學(xué)系isstn@mail.sysu.edu.cn,1 數(shù)據(jù)庫(kù)恢復(fù)概述2 故障的種類3 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)4 恢復(fù)的實(shí)現(xiàn)技術(shù)5 恢復(fù)策略6 具有檢查點(diǎn)的恢復(fù)技術(shù)7 數(shù)據(jù)庫(kù)鏡像8 小結(jié),數(shù)據(jù)庫(kù)恢復(fù)技術(shù),數(shù)據(jù)庫(kù)恢復(fù)概述,事務(wù),事務(wù)(Transaction)是用戶定義的一個(gè)數(shù)據(jù)庫(kù)操作序列，這些操作要么全做，要么全不做，是一個(gè)不可分割的工作單位事務(wù)

2、的ACID特性：原子性（Atomicity）一致性（Consistency）隔離性（Isolation）持續(xù)性（Durability ）,數(shù)據(jù)庫(kù)恢復(fù)概述,故障是不可避免的計(jì)算機(jī)硬件故障系統(tǒng)軟件和應(yīng)用軟件的錯(cuò)誤操作員的失誤惡意的破壞故障的影響運(yùn)行事務(wù)非正常中斷，但不會(huì)破壞數(shù)據(jù)庫(kù)破壞數(shù)據(jù)庫(kù),數(shù)據(jù)庫(kù)恢復(fù)概述（續(xù)）,數(shù)據(jù)庫(kù)管理系統(tǒng)對(duì)故障的對(duì)策保證故障發(fā)生后，能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)從錯(cuò)誤狀態(tài)恢復(fù)到某種邏輯一致的狀態(tài)保證事務(wù)A

3、CID DBMS提供恢復(fù)子系統(tǒng)恢復(fù)技術(shù)是衡量系統(tǒng)優(yōu)劣的重要指標(biāo)恢復(fù)算法正常事務(wù)處理時(shí)，采取措施保證有足夠的數(shù)據(jù)用于故障恢復(fù)故障發(fā)生后，將數(shù)據(jù)庫(kù)內(nèi)容恢復(fù)到某個(gè)保證數(shù)據(jù)庫(kù)一致性、原子性及持久性的狀態(tài),故障的種類,3 故障的種類,事務(wù)故障系統(tǒng)故障介質(zhì)故障,一、事務(wù)故障,什么是事務(wù)故障某個(gè)事務(wù)在運(yùn)行過(guò)程中由于種種原因未運(yùn)行至正常終止點(diǎn)就夭折了事務(wù)故障的常見(jiàn)原因輸入數(shù)據(jù)有誤運(yùn)算溢出違反了某些完整性限制某些應(yīng)用程序出錯(cuò)

4、并行事務(wù)發(fā)生死鎖。。。。,事務(wù)故障的恢復(fù),發(fā)生事務(wù)故障時(shí)，夭折的事務(wù)可能已把對(duì)數(shù)據(jù)庫(kù)的部分修改寫(xiě)回磁盤(pán)處理方法預(yù)期故障： 通過(guò)在程序中加判斷條件來(lái)實(shí)現(xiàn)。執(zhí)行回滾（ROLLBACK）語(yǔ)句來(lái)撤銷事務(wù)。非預(yù)期的故障： 如由于死鎖、運(yùn)算溢出而被迫撤銷的事務(wù)等，由系統(tǒng)來(lái)撤銷事務(wù)事務(wù)故障的恢復(fù)的本質(zhì)：撤消事務(wù)（UNDO）,3 故障的種類,事務(wù)故障系統(tǒng)故障介質(zhì)故障,二、系統(tǒng)故障,什么是系統(tǒng)故障整個(gè)系統(tǒng)的正常運(yùn)行突然被破

5、壞所有正在運(yùn)行的事務(wù)都非正常終止內(nèi)存中數(shù)據(jù)庫(kù)緩沖區(qū)的信息全部丟失外部存儲(chǔ)設(shè)備上的數(shù)據(jù)未受影響,系統(tǒng)故障的常見(jiàn)原因,操作系統(tǒng)或DBMS代碼錯(cuò)誤操作員操作失誤特定類型的硬件錯(cuò)誤（如CPU故障）突然停電,系統(tǒng)故障的恢復(fù),清除尚未完成的事務(wù)對(duì)數(shù)據(jù)庫(kù)的所有修改系統(tǒng)重新啟動(dòng)時(shí)，恢復(fù)程序要強(qiáng)行撤消（UNDO）所有未完成事務(wù)將緩沖區(qū)中已完成事務(wù)提交的結(jié)果寫(xiě)入數(shù)據(jù)庫(kù)系統(tǒng)重新啟動(dòng)時(shí)，恢復(fù)程序需要重做（REDO）所有已提交的事務(wù),3 故障

6、的種類,事務(wù)故障系統(tǒng)故障介質(zhì)故障,三、介質(zhì)故障,硬件故障使存儲(chǔ)在外存中的數(shù)據(jù)部分丟失或全部丟失介質(zhì)故障比前兩類故障的可能性小得多，但破壞性大得多,介質(zhì)故障的常見(jiàn)原因,硬件故障磁盤(pán)損壞磁頭碰撞操作系統(tǒng)的某種潛在錯(cuò)誤瞬時(shí)強(qiáng)磁場(chǎng)干擾,介質(zhì)故障的恢復(fù),裝入數(shù)據(jù)庫(kù)發(fā)生介質(zhì)故障前某個(gè)時(shí)刻的數(shù)據(jù)副本重做自此時(shí)始的所有成功事務(wù)，將這些事務(wù)已提交的結(jié)果重新記入數(shù)據(jù)庫(kù),,,數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),Storage Structure,Volatile

7、storage:does not survive system crashesexamples: main memory, cache memoryNonvolatile storage:survives system crashesexamples: disk, tape, flash memory, non-volatile (battery backed up) RAM Stabl

8、e storage:a mythical form of storage that survives all failuresapproximated by maintaining multiple copies on distinct nonvolatile media,Stable-Storage Implementation,Maintain multiple copies of each block on separate

9、disksraid遠(yuǎn)程災(zāi)備copies can be at remote sites to protect against disasters such as fire or flooding.Failure during data transfer can still result in inconsistent copies: Block transfer can result inSuccessful completion

10、Partial failure: destination block has incorrect informationTotal failure: destination block was never updated,Stable-Storage Implementation,Protecting storage media from failure during data transfer (one solution):Ex

11、ecute output operation as follows (assuming two copies of each block):Write the information onto the first physical block.When the first write successfully completes, write the same information onto the second physical

12、 block.The output is completed only after the second write successfully completes.,Stable-Storage Implementation (Cont.),Protecting storage media from failure during data transfer (cont.):Copies of a block may differ d

13、ue to failure during output operation. To recover from failure:First find inconsistent blocks:Expensive solution: Compare the two copies of every disk block.Better solution: Record in-progress disk writes on non-vola

14、tile storage (Non-volatile RAM or special area of disk). Use this information during recovery to find blocks that may be inconsistent, and only compare copies of these. Used in hardware RAID systemsIf either copy of

15、 an inconsistent block is detected to have an error (bad checksum), overwrite it by the other copy. If both have no error, but are different, overwrite the second block by the first block.,Data Access,Physical blocks ar

16、e those blocks residing on the disk. Buffer blocks are the blocks residing temporarily in main memory.Block movements between disk and main memory are initiated through the following two operations:input(B) transfers

17、 the physical block B to main memory.output(B) transfers the buffer block B to the disk, and replaces the appropriate physical block there.,Data Access,Each transaction Ti has its private work-area in which local copie

18、s of all data items accessed and updated by it are kept. Ti's local copy of a data item X is called xi.We assume, for simplicity, that each data item fits in, and is stored inside, a single block.,Data Access (Cont

19、.),Transaction transfers data items between system buffer blocks and its private work-area using the following operations :read(X) assigns the value of data item X to the local variable xi.write(X) assigns the value of

20、 local variable xi to data item {X} in the buffer block.both these commands may necessitate the issue of an input(BX) instruction before the assignment, if the block BX in which X resides is not already in memory.Trans

21、actions Perform read(X) while accessing X for the first time; All subsequent accesses are to the local copy. After last access, transaction executes write(X).output(BX) need not immediately follow write(X). System ca

22、n perform the output operation when it deems fit.,Example of Data Access,,x,Y,,,,,,,A,B,,,,,,,x1,y1,buffer,Buffer Block A,Buffer Block B,,,,,input(A),output(B),,,read(X),write(Y),disk,,,,,,,,,,,,,,,work areaof T1,work a

23、reaof T2,memory,x2,恢復(fù)的實(shí)現(xiàn)技術(shù),恢復(fù)操作的基本原理,恢復(fù)操作的基本原理：冗余利用存儲(chǔ)在系統(tǒng)其它地方的冗余數(shù)據(jù)來(lái)重建數(shù)據(jù)庫(kù)中已被破壞或不正確的那部分?jǐn)?shù)據(jù)恢復(fù)的實(shí)現(xiàn)技術(shù)：復(fù)雜一個(gè)大型數(shù)據(jù)庫(kù)產(chǎn)品，恢復(fù)子系統(tǒng)的代碼要占全部代碼的10%以上,4 恢復(fù)的實(shí)現(xiàn)技術(shù),恢復(fù)機(jī)制涉及的關(guān)鍵問(wèn)題1. 如何建立冗余數(shù)據(jù)數(shù)據(jù)轉(zhuǎn)儲(chǔ)（backup）登錄日志文件（logging）2. 如何利用這些冗余數(shù)據(jù)實(shí)施數(shù)據(jù)庫(kù)恢復(fù),4.1

24、 數(shù)據(jù)轉(zhuǎn)儲(chǔ)（備份）,一、什么是轉(zhuǎn)儲(chǔ)二、轉(zhuǎn)儲(chǔ)的用途三、轉(zhuǎn)儲(chǔ)方法,一、什么是轉(zhuǎn)儲(chǔ),轉(zhuǎn)儲(chǔ)是指DBA將整個(gè)數(shù)據(jù)庫(kù)復(fù)制到磁帶或另一個(gè)磁盤(pán)上保存起來(lái)的過(guò)程。這些備用的數(shù)據(jù)文本稱為后備副本或后援副本。,二、轉(zhuǎn)儲(chǔ)方法,1．靜態(tài)轉(zhuǎn)儲(chǔ)與動(dòng)態(tài)轉(zhuǎn)儲(chǔ)2．海量轉(zhuǎn)儲(chǔ)與增量轉(zhuǎn)儲(chǔ)3．轉(zhuǎn)儲(chǔ)方法小結(jié),1．靜態(tài)轉(zhuǎn)儲(chǔ),在系統(tǒng)中無(wú)運(yùn)行事務(wù)時(shí)進(jìn)行轉(zhuǎn)儲(chǔ)轉(zhuǎn)儲(chǔ)開(kāi)始時(shí)數(shù)據(jù)庫(kù)處于一致性狀態(tài)。轉(zhuǎn)儲(chǔ)期間不允許對(duì)數(shù)據(jù)庫(kù)的任何存取、修改活動(dòng)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：降低了數(shù)據(jù)庫(kù)的可用性

25、轉(zhuǎn)儲(chǔ)必須等用戶事務(wù)結(jié)束新的事務(wù)必須等轉(zhuǎn)儲(chǔ)結(jié)束,動(dòng)態(tài)轉(zhuǎn)儲(chǔ),轉(zhuǎn)儲(chǔ)操作與用戶事務(wù)并發(fā)進(jìn)行轉(zhuǎn)儲(chǔ)期間允許對(duì)數(shù)據(jù)庫(kù)進(jìn)行存取或修改優(yōu)點(diǎn)不用等待正在運(yùn)行的用戶事務(wù)結(jié)束不會(huì)影響新事務(wù)的運(yùn)行動(dòng)態(tài)轉(zhuǎn)儲(chǔ)的缺點(diǎn)不能保證副本中的數(shù)據(jù)正確有效,動(dòng)態(tài)轉(zhuǎn)儲(chǔ),利用動(dòng)態(tài)轉(zhuǎn)儲(chǔ)得到的副本進(jìn)行故障恢復(fù)需要把動(dòng)態(tài)轉(zhuǎn)儲(chǔ)期間各事務(wù)對(duì)數(shù)據(jù)庫(kù)的修改活動(dòng)登記下來(lái)，建立日志文件后備副本加上日志文件才能把數(shù)據(jù)庫(kù)恢復(fù)到某一時(shí)刻的正確狀態(tài),2．海量轉(zhuǎn)儲(chǔ)與增量轉(zhuǎn)儲(chǔ),海量轉(zhuǎn)儲(chǔ): 每次轉(zhuǎn)

26、儲(chǔ)全部數(shù)據(jù)庫(kù)增量轉(zhuǎn)儲(chǔ): 只轉(zhuǎn)儲(chǔ)上次轉(zhuǎn)儲(chǔ)后更新過(guò)的數(shù)據(jù)海量轉(zhuǎn)儲(chǔ)與增量轉(zhuǎn)儲(chǔ)比較,3．轉(zhuǎn)儲(chǔ)方法小結(jié),轉(zhuǎn)儲(chǔ)方法分類,3 恢復(fù)的實(shí)現(xiàn)技術(shù),3.1 數(shù)據(jù)轉(zhuǎn)儲(chǔ)3.2 登記日志文件,3.2 登記日志文件,一、日志文件的內(nèi)容三、登記日志文件的原則,一、日志文件的內(nèi)容,1. 什么是日志文件日志文件(log)是用來(lái)記錄事務(wù)對(duì)數(shù)據(jù)庫(kù)的更新操作的文件2. 日志文件的格式以記錄為單位的日志文件以數(shù)據(jù)塊為單位的日志文件,日志文件的內(nèi)容

27、（續(xù)）,3. 日志文件內(nèi)容各個(gè)事務(wù)的開(kāi)始標(biāo)記(BEGIN TRANSACTION)各個(gè)事務(wù)的結(jié)束標(biāo)記(COMMIT或ROLLBACK)各個(gè)事務(wù)的所有更新操作日志文件中的一個(gè)日志記錄 (log record),4. 基于記錄的日志文件,更新操作日志記錄的內(nèi)容事務(wù)標(biāo)識(shí)操作類型（插入、刪除或修改）操作對(duì)象（記錄ID、Block NO.）更新前數(shù)據(jù)的舊值（對(duì)插入操作而言，此項(xiàng)為空值）更新后數(shù)據(jù)的新值（對(duì)刪除操作而言, 此項(xiàng)

28、為空值）,二、登記日志文件的原則（WAL）,為保證數(shù)據(jù)庫(kù)是可恢復(fù)的，登記日志文件時(shí)必須遵循兩條原則登記的次序嚴(yán)格按并行事務(wù)執(zhí)行的時(shí)間次序必須先寫(xiě)日志文件，后寫(xiě)數(shù)據(jù)庫(kù)寫(xiě)日志文件操作：把表示這個(gè)修改的日志記錄 寫(xiě)到日志文件（在磁盤(pán)上）寫(xiě)數(shù)據(jù)庫(kù)操作：把對(duì)數(shù)據(jù)的修改寫(xiě)到數(shù)據(jù)庫(kù)中,,,?,登記日志文件的原則（續(xù)）,為什么要先寫(xiě)日志文件寫(xiě)數(shù)據(jù)庫(kù)和寫(xiě)日志文件是兩個(gè)不同的操作在這兩個(gè)操作之間可能發(fā)生故障如果先寫(xiě)了數(shù)據(jù)庫(kù)修改，而在日志

29、文件中沒(méi)有登記下這個(gè)修改，則以后就無(wú)法恢復(fù)這個(gè)修改了如果先寫(xiě)日志，但沒(méi)有修改數(shù)據(jù)庫(kù)，按日志文件恢復(fù)時(shí)只不過(guò)是多執(zhí)行一次不必要的UNDO操作，并不會(huì)影響數(shù)據(jù)庫(kù)的正確性,先寫(xiě)日志的原則（WAL）,日志緩沖區(qū),數(shù)據(jù)庫(kù)緩沖區(qū),日志,數(shù)據(jù)庫(kù),,,WAL,調(diào)入B2輸出B1,輸出所有與B1有關(guān)的日志記錄(flush log)輸出B1調(diào)入B2,同步(synchronous)寫(xiě)日志：只有事務(wù)的相關(guān)日志已經(jīng)完全在磁盤(pán)上了，才會(huì)向進(jìn)程發(fā)送該事務(wù)已提

30、交的確認(rèn)消息異步(asynchronous)寫(xiě)緩沖區(qū)：只需要將數(shù)據(jù)頁(yè)的寫(xiě)入操作投遞給操作系統(tǒng)即可，不需要等待其完成,利用靜態(tài)轉(zhuǎn)儲(chǔ)副本進(jìn)行恢復(fù),,,恢復(fù)策略,5 恢復(fù)策略,5.1 事務(wù)故障的恢復(fù)5.2 系統(tǒng)故障的恢復(fù)5.3 介質(zhì)故障的恢復(fù),5.1 事務(wù)故障的恢復(fù),事務(wù)故障：事務(wù)在運(yùn)行至正常終止點(diǎn)前被中止恢復(fù)方法由恢復(fù)子系統(tǒng)應(yīng)利用日志文件撤消（UNDO）此事務(wù)已對(duì)數(shù)據(jù)庫(kù)進(jìn)行的修改事務(wù)故障的恢復(fù)由系統(tǒng)自動(dòng)完成，不需要用戶

31、干預(yù),事務(wù)故障的恢復(fù)步驟,1. 反向掃描文件日志（即從最后向前掃描日志文件），查找該事務(wù)的更新操作。2. 對(duì)該事務(wù)的更新操作執(zhí)行逆操作。即將日志記錄中“更新前的值”（Befor Image, BI）寫(xiě)入數(shù)據(jù)庫(kù)。插入操作， “更新前的值”為空，則相當(dāng)于做刪除操作刪除操作，“更新后的值”為空，則相當(dāng)于做插入操作若是修改操作，則用BI 代替 AI（After Image）3. 繼續(xù)反向掃描日志文件，查找該事務(wù)的其他更新操作，并做同樣

32、處理。4. 如此處理下去，直至讀到此事務(wù)的開(kāi)始標(biāo)記，事務(wù)故障恢復(fù)就完成了。,事務(wù)故障恢復(fù),反向撤銷事務(wù)操作,正向撤銷事務(wù)操作,5.2 系統(tǒng)故障的恢復(fù),系統(tǒng)故障造成數(shù)據(jù)庫(kù)不一致?tīng)顟B(tài)的原因一些未完成事務(wù)對(duì)數(shù)據(jù)庫(kù)的更新已寫(xiě)入數(shù)據(jù)庫(kù)一些已提交事務(wù)對(duì)數(shù)據(jù)庫(kù)的更新還留在緩沖區(qū)沒(méi)來(lái)得及寫(xiě)入數(shù)據(jù)庫(kù)恢復(fù)方法1. Undo 故障發(fā)生時(shí)未完成的事務(wù)2. Redo 已完成的事務(wù)系統(tǒng)故障的恢復(fù)由系統(tǒng)在重新啟動(dòng)時(shí)自動(dòng)完成，不需要用戶干預(yù),系統(tǒng)故障的

33、恢復(fù)步驟,1.正向掃描日志文件（即從頭掃描日志文件）Redo隊(duì)列: 在故障發(fā)生前已經(jīng)提交的事務(wù) T1, T3, T8…..Undo隊(duì)列:故障發(fā)生時(shí)尚未完成的事務(wù) T2, T4, T5, T6, T7, T9 …...,系統(tǒng)故障的恢復(fù)步驟,2. 對(duì)Undo隊(duì)列事務(wù)進(jìn)行UNDO處理 反向掃描日志文件，對(duì)每個(gè)UNDO事務(wù)的更 新操作執(zhí)行逆操作 T2, T4, T5, T6,

34、T7, T9 …… 3. 對(duì)Redo隊(duì)列事務(wù)進(jìn)行REDO處理 正向掃描日志文件，對(duì)每個(gè)REDO事務(wù)重新 執(zhí)行登記的操作 T1, T3, T8…..,系統(tǒng)故障恢復(fù),,T0圓滿事務(wù)，T1夭折事務(wù),undo,A=950,B=2050,C=700,redoredo,A=950,B=2000,C=700,5.3 介質(zhì)故障的恢復(fù),1. 重裝數(shù)據(jù)庫(kù)， 使數(shù)據(jù)庫(kù)恢復(fù)到一致性狀態(tài)

35、2. 重做已完成的事務(wù),5.3 介質(zhì)故障的恢復(fù),恢復(fù)步驟1. 裝入最新的后備數(shù)據(jù)庫(kù)副本，使數(shù)據(jù)庫(kù)恢復(fù)到最近一次轉(zhuǎn)儲(chǔ)時(shí)的一致性狀態(tài)。對(duì)于靜態(tài)轉(zhuǎn)儲(chǔ)的數(shù)據(jù)庫(kù)副本，裝入后數(shù)據(jù)庫(kù)即處于一致性狀態(tài)對(duì)于動(dòng)態(tài)轉(zhuǎn)儲(chǔ)的數(shù)據(jù)庫(kù)副本，還須同時(shí)裝入轉(zhuǎn)儲(chǔ)時(shí)刻的日志文件副本，才能將數(shù)據(jù)庫(kù)恢復(fù)到一致性狀態(tài)。,介質(zhì)故障的恢復(fù)（續(xù)）,2. 裝入有關(guān)的日志文件副本，重做已完成的事務(wù)。首先掃描日志文件，找出故障發(fā)生時(shí)已提交的事務(wù)的標(biāo)識(shí)，將其記入重做隊(duì)列。然后正向

36、掃描日志文件，對(duì)重做隊(duì)列中的所有事務(wù)進(jìn)行重做處理。即將日志記錄中“更新后的值”寫(xiě)入數(shù)據(jù)庫(kù)。,介質(zhì)故障的恢復(fù)（續(xù)）,介質(zhì)故障的恢復(fù)需要DBA介入DBA的工作重裝最近轉(zhuǎn)儲(chǔ)的數(shù)據(jù)庫(kù)副本和有關(guān)的各日志文件副本執(zhí)行系統(tǒng)提供的恢復(fù)命令具體的恢復(fù)操作仍由DBMS完成,具有檢查點(diǎn)的恢復(fù)技術(shù),6 具有檢查點(diǎn)的恢復(fù)技術(shù),一、問(wèn)題的提出二、檢查點(diǎn)技術(shù)三、利用檢查點(diǎn)的恢復(fù)策略,一、問(wèn)題的提出,兩個(gè)問(wèn)題搜索整個(gè)日志將耗費(fèi)大量的時(shí)間REDO處理：

37、重新執(zhí)行，浪費(fèi)了大量時(shí)間,解決方案,具有檢查點(diǎn)（checkpoint）的恢復(fù)技術(shù)在日志文件中增加檢查點(diǎn)記錄（checkpoint）增加重新開(kāi)始文件恢復(fù)子系統(tǒng)在登錄日志文件期間動(dòng)態(tài)地維護(hù)日志,,二、檢查點(diǎn)技術(shù),檢查點(diǎn)記錄的內(nèi)容1. 建立檢查點(diǎn)時(shí)刻所有正在執(zhí)行的事務(wù)清單2. 這些事務(wù)最近一個(gè)日志記錄的地址重新開(kāi)始文件的內(nèi)容記錄各個(gè)檢查點(diǎn)記錄在日志文件中的地址,在檢查點(diǎn) 維護(hù)日志文件,1.將當(dāng)前日志緩沖區(qū)中的所有日志記錄寫(xiě)入

38、磁盤(pán)的日志文件上。2.在日志文件中寫(xiě)入一個(gè)檢查點(diǎn)記錄。3. 將當(dāng)前數(shù)據(jù)緩沖區(qū)的所有數(shù)據(jù)記錄寫(xiě)入磁盤(pán)的數(shù)據(jù)庫(kù)中。4. 把檢查點(diǎn)記錄在日志文件中的地址寫(xiě)入一個(gè)重新開(kāi)始文件。,,建立檢查點(diǎn),定期按照預(yù)定的一個(gè)時(shí)間間隔不定期按照某種規(guī)則，如日志文件已寫(xiě)滿一半建立一個(gè)檢查點(diǎn),三、利用檢查點(diǎn)的恢復(fù)策略,當(dāng)事務(wù)T在一個(gè)檢查點(diǎn)之前提交 T對(duì)數(shù)據(jù)庫(kù)所做的修改已寫(xiě)入數(shù)據(jù)庫(kù)在進(jìn)行恢復(fù)處理時(shí)，沒(méi)有必要對(duì)事務(wù)T執(zhí)行REDO操作,利用檢查點(diǎn)的

39、恢復(fù)策略（續(xù)）,利用檢查點(diǎn)的恢復(fù)步驟,1. 從重新開(kāi)始文件中找到最后一個(gè)檢查點(diǎn)記錄在日志文件中的地址2 由該地址在日志文件中找到最后一個(gè)檢查點(diǎn)記錄,利用檢查點(diǎn)的恢復(fù)策略（續(xù)）,2.由該檢查點(diǎn)記錄得到檢查點(diǎn)建立時(shí)刻所有正在執(zhí)行的事務(wù)清單ACTIVE-LIST建立兩個(gè)事務(wù)隊(duì)列UNDO-LIST REDO-LIST 把ACTIVE-LIST暫時(shí)放入U(xiǎn)NDO-LIST隊(duì)列，REDO隊(duì)列暫為空。,利用檢查點(diǎn)的恢復(fù)策略（續(xù)）,3.從檢查點(diǎn)

40、開(kāi)始正向掃描日志文件，直到日志文件結(jié)束如有新開(kāi)始的事務(wù)Ti，把Ti暫時(shí)放入U(xiǎn)NDO-LIST隊(duì)列如有提交的事務(wù)Tj，把Tj從UNDO-LIST隊(duì)列移到REDO-LIST隊(duì)列4.對(duì)UNDO-LIST中的每個(gè)事務(wù)執(zhí)行UNDO操作, 對(duì)REDO-LIST中的每個(gè)事務(wù)執(zhí)行REDO操作,,思考題,一條update語(yǔ)句只修改一條記錄，如果在前圖第3步完成后down機(jī)系統(tǒng)重啟后，是如何處理？一條update語(yǔ)句修改一萬(wàn)條記錄，如果在修改了5

41、000條記錄后down機(jī)系統(tǒng)重啟后，是如何處理？,數(shù)據(jù)庫(kù)鏡像,7 數(shù)據(jù)庫(kù)鏡像,介質(zhì)故障是對(duì)系統(tǒng)影響最為嚴(yán)重的一種故障，嚴(yán)重影響數(shù)據(jù)庫(kù)的可用性介質(zhì)故障恢復(fù)比較費(fèi)時(shí)為預(yù)防介質(zhì)故障，DBA必須周期性地轉(zhuǎn)儲(chǔ)數(shù)據(jù)庫(kù)提高數(shù)據(jù)庫(kù)可用性的解決方案數(shù)據(jù)庫(kù)鏡像（Mirror）,數(shù)據(jù)庫(kù)鏡像（續(xù)）,數(shù)據(jù)庫(kù)鏡像DBMS自動(dòng)把整個(gè)數(shù)據(jù)庫(kù)或其中的關(guān)鍵數(shù)據(jù)復(fù)制到另一個(gè)磁盤(pán)上DBMS自動(dòng)保證鏡像數(shù)據(jù)與主數(shù)據(jù)的一致性(圖5a),數(shù)據(jù)庫(kù)鏡像的用途,出現(xiàn)介質(zhì)故

42、障時(shí)DBMS自動(dòng)利用鏡像磁盤(pán)數(shù)據(jù)進(jìn)行數(shù)據(jù)庫(kù)的恢復(fù)，不需要關(guān)閉系統(tǒng)和重裝數(shù)據(jù)庫(kù)副本(圖5b)沒(méi)有出現(xiàn)故障時(shí)可用于并發(fā)操作(圖5a)一個(gè)用戶對(duì)數(shù)據(jù)加排他鎖修改數(shù)據(jù)其他用戶可以讀鏡像數(shù)據(jù)庫(kù)上的數(shù)據(jù),數(shù)據(jù)庫(kù)鏡像（續(xù)）,,數(shù)據(jù)庫(kù)鏡像（續(xù)）,由于采用復(fù)制數(shù)據(jù)實(shí)現(xiàn)鏡像，而頻繁復(fù)制會(huì)導(dǎo)致較低系統(tǒng)運(yùn)行效率。因此實(shí)際應(yīng)用只針對(duì)關(guān)鍵數(shù)據(jù)和日志文件進(jìn)行鏡像，而不是整個(gè)數(shù)據(jù)庫(kù),Advanced Recovery Algorithm,邏輯Undo日志,一

43、般恢復(fù)技術(shù)要求一旦事務(wù)更新了一個(gè)數(shù)據(jù)項(xiàng)，其它事務(wù)都不能更新該數(shù)據(jù)項(xiàng)，直至第一個(gè)事務(wù)提交或回滾嚴(yán)格兩階段封鎖協(xié)議實(shí)施到某些特殊結(jié)構(gòu)如B+樹(shù)索引頁(yè)時(shí)，并發(fā)性極度下降。為提高并發(fā)性，可以使用非兩段方式使鎖較早釋放如果事務(wù)T向B+樹(shù)插入了一項(xiàng)，在插入操作結(jié)束后但在事務(wù)提交前釋放了某些鎖。在鎖釋放后，其它事務(wù)可執(zhí)行插入或刪除操作，于是造成對(duì)B+樹(shù)結(jié)點(diǎn)的進(jìn)一步改變?nèi)绻褂梦锢韚ndo執(zhí)行事務(wù)回滾，即事務(wù)回滾時(shí)我們將B+樹(shù)內(nèi)部結(jié)點(diǎn)（執(zhí)行插入操作

44、前）的舊值寫(xiě)回，那么其它事務(wù)在其后執(zhí)行的插入或刪除操作所做的某些更新可能會(huì)丟失插入操作必須通過(guò)一個(gè)邏輯undo來(lái)完成，即通過(guò)執(zhí)行一次刪除操作撤消,,For such operations, undo log records should contain the undo operation to be executed called logical undo logging, in contrast to physical undo

45、 logging.Redo information is logged physically (that is, new value for each write) even for such operationsLogical redo is very complicated since database state on disk may not be “operation consistent”,Advanced Recove

46、ry Techniques (Cont.),Operation logging is done as follows:When operation starts, log . Here Oj is a unique identifier of the operation instance.While operation is executing, normal log records with physical redo and p

47、hysical undo information are logged. When operation completes, is logged, where U contains information needed to perform a logical undo information.,Advanced Recovery Techniques (Cont.),If crash/rollback occurs before

48、 operation completes:the operation-end log record is not found, and the physical undo information is used to undo operation.If crash/rollback occurs after the operation completes:the operation-end log record is found

49、, and in this caselogical undo is performed using U; the physical undo information for the operation is ignored.,Advanced Recovery Techniques (Cont.),Rollback of transaction Ti is done as follows: Scan the log backwar

50、ds If a log record is found, perform the undo and log a special redo-only log record .If a record is foundRollback the operation logically using the undo information U. Log Updates performed during roll back are

51、logged just like during normal operation execution. At the end of the operation rollback, instead of logging an operation-end record, generate a record .Skip all preceding log records for Ti until the recor

52、d is found,日志類型的對(duì)比,物理日志Ti,Xi,V1,V2回滾時(shí)登記的日志Ti,Xi,V1,undonextLSN,邏輯日志Ti,Qi,operation-begin……（物理日志）Ti,Qi, operation-end,U回滾時(shí)登記的日志……（物理日志）Ti,Qi,operation-abort,Advanced Recovery Techniques (Cont.),Scan the log

53、 backwards (cont.):If a redo-only record is found ignore itIf a record is found:skip all preceding log records for Ti until the record is found.Stop the scan when the record is foundAdd a record to the logSom

54、e points to note:Cases 3 and 4 above can occur only if the database crashes while a transaction is being rolled back.Skipping of log records as in case 4 is important to prevent multiple rollback of the same operation

55、.,Advanced Recovery Techniques(Cont,),The following actions are taken when recovering from system crashScan log forward from last recordRepeat history by physically redoing all updates of all transactions, Create a

56、n undo-list during the scan as followsundo-list is set to L initiallyWhenever is found Ti is added to undo-listWhenever or is found, Ti is deleted from undo-listThis brings database to state as of crash, with com

57、mitted as well as uncommitted transactions having been redone.Now undo-list contains transactions that are incomplete, that is, have neither committed nor been fully rolled back.,Advanced Recovery Techniques (Cont.),R

58、ecovery from system crash (cont.)Scan log backwards, performing undo on log records of transactions found in undo-list. Transactions are rolled back as described earlier.When is found for a transaction Ti in undo-l

59、ist, write a log record.Stop scan when records have been found for all Ti in undo-listThis undoes the effects of incomplete transactions (those with neither commit nor abort log records). Recovery is now complete.,A

60、dvanced Recovery Techniques (Cont.),Fuzzy checkpointing allows transactions to progress while the most time consuming parts of checkpointing are in progress正在輸出到磁盤(pán)的緩沖塊也不能更新，雖然其他緩沖塊可以并發(fā)更新，但必須遵守先寫(xiě)日志協(xié)議。,ARIES算法,ARIES算法：數(shù)據(jù)結(jié)

61、構(gòu),日志記錄的基本格式LSN在增長(zhǎng)的日志記錄空間中的日志記錄的第一個(gè)字節(jié)的地址。這是一個(gè)單調(diào)遞增的數(shù)值，記錄越晚產(chǎn)生，lsn值越大Type表示一個(gè)記錄是補(bǔ)償日志（'compensation'），正常更新記錄('update')，一個(gè)提交協(xié)議相關(guān)記錄（例如'prepare'）TransID事務(wù)的標(biāo)記，如有，則寫(xiě)入到日志記錄中PrevLSN本事務(wù)的前一條日志記錄的LSN。對(duì)該事

62、務(wù)的第一條日志記錄而言是0，因此，不需要用一條日志記錄顯式地表示一條事務(wù)的開(kāi)始PageID只在Update和compensation類型的記錄中出現(xiàn)，它記錄本記錄所所做更新的頁(yè)面的標(biāo)記,ARIES算法：數(shù)據(jù)結(jié)構(gòu),Data這是描述欲更新的redo和/或undo數(shù)據(jù)。CLR只包含redo信息，因?yàn)樗鼈儾荒躸ndoUndoNxtLSN只在CLR中出現(xiàn)，它指的是回滾階段要處理的下一個(gè)本事務(wù)的日志記錄，也即UndoNxtLSN是當(dāng)前日志

63、正在彌補(bǔ)的日志記錄的PrevLSN的數(shù)值。如果已經(jīng)沒(méi)有日志記錄需要undo，該數(shù)據(jù)域就會(huì)是0頁(yè)面結(jié)構(gòu)數(shù)據(jù)庫(kù)的每個(gè)頁(yè)都有page_LSN域。它包含描述對(duì)該頁(yè)面所做的最近更新日志記錄的LSN。在恢復(fù)的Redo階段，LSN值小于等于page_LSN值的記錄將不在這頁(yè)上redo,ARIES算法：數(shù)據(jù)結(jié)構(gòu),事務(wù)表事務(wù)表記錄事務(wù)的狀態(tài)TransID：事務(wù)的IDState：事務(wù)的提交狀態(tài)LastLSN：事務(wù)所寫(xiě)的最后一條LSNUndoN

64、xtLSN：在回滾階段下一個(gè)記錄的LSN。如果本事務(wù)的最近日志記錄是一個(gè)可undo的非CLR記錄，這個(gè)字段的值就會(huì)被設(shè)為L(zhǎng)astLSN。如果最近日志記錄是CLR，此字段的值就設(shè)為此CLR的UndoNxtLSN的值,ARIES算法：數(shù)據(jù)結(jié)構(gòu),臟頁(yè)表包含一個(gè)在數(shù)據(jù)庫(kù)緩沖區(qū)中已更新的列表，PageID+pageLSN+ RecLSNRecLSN用于標(biāo)識(shí)日志記錄，這些日志記錄的磁盤(pán)頁(yè)版本沒(méi)有實(shí)施更新當(dāng)一頁(yè)被插入到臟頁(yè)表時(shí)(當(dāng)他首次在緩沖

65、池中被修改時(shí))，RecLSN的值被設(shè)置成日志的當(dāng)前末尾只要頁(yè)被寫(xiě)入磁盤(pán)，該頁(yè)就被從臟頁(yè)表中移除。檢查點(diǎn)日志記錄包含檢查點(diǎn)發(fā)生時(shí)臟頁(yè)和活動(dòng)事務(wù)的列表，同時(shí)記錄每個(gè)事務(wù)的LastLSN,ARIES算法：三個(gè)原理,先寫(xiě)日志在將更新的數(shù)據(jù)庫(kù)對(duì)象的修改寫(xiě)入磁盤(pán)之前，先將對(duì)應(yīng)的日志記錄寫(xiě)入穩(wěn)存恢復(fù)修改的記錄數(shù)據(jù)在回滾某些事務(wù)時(shí)，如果出現(xiàn)對(duì)數(shù)據(jù)庫(kù)的改變，則需要在日志中記錄這些改變，保證在重復(fù)進(jìn)行重新啟動(dòng)時(shí)不需要重復(fù)這些操作重做時(shí)重復(fù)

66、歷史在崩潰后進(jìn)行重新啟動(dòng)時(shí)，重做崩潰前的所有操作，使系統(tǒng)恢復(fù)到崩潰時(shí)的狀態(tài)，然后回滾崩潰時(shí)還在執(zhí)行的事務(wù)已完成的操作,ARIES算法：三個(gè)過(guò)程,分析過(guò)程決定哪些事務(wù)要undo，哪些頁(yè)在崩潰時(shí)是臟的，以及redo應(yīng)從哪個(gè)LSN開(kāi)始Redo過(guò)程從分析過(guò)程決定的位置開(kāi)始，執(zhí)行一個(gè)redo，重復(fù)歷史，將數(shù)據(jù)庫(kù)恢復(fù)到發(fā)生崩潰前的狀態(tài)Undo過(guò)程回滾在發(fā)生崩潰時(shí)那些不完整的事務(wù),ARIES算法：系統(tǒng)故障恢復(fù),ARIES算法：分析

67、過(guò)程,找到最后完整檢查點(diǎn)日志記錄，并從該記錄開(kāi)始讀入臟頁(yè)表將RedoLSN設(shè)置為臟頁(yè)表中頁(yè)的RecLSN的最小值，如果沒(méi)有臟頁(yè)，就將其設(shè)置為檢查點(diǎn)日志記錄的LSN將要被undo的事務(wù)列表undo-list設(shè)置為檢查點(diǎn)日志記錄中的事務(wù)列表及這些事務(wù)的LastLSN從檢查點(diǎn)繼續(xù)向前掃描，每找到一個(gè)不在undo-list中的事務(wù)日志記錄，就將其添加到undo-list，每找到一個(gè)事務(wù)的end日志記錄，就將其從undo-list中刪除,A

68、RIES算法：Redo過(guò)程,Redo過(guò)程通過(guò)重演所有沒(méi)有在磁盤(pán)頁(yè)上反映的動(dòng)作來(lái)重復(fù)歷史Redo過(guò)程從RedoLSN開(kāi)始向前掃描日志，該點(diǎn)之前的日志記錄已經(jīng)反映在磁盤(pán)數(shù)據(jù)庫(kù)頁(yè)上只要Redo過(guò)程找到一個(gè)update日志記錄，它就執(zhí)行如下動(dòng)作：如果該頁(yè)不在臟頁(yè)表中(更新已經(jīng)實(shí)施)，或者該update日志記錄的LSN小于臟頁(yè)表中該頁(yè)的RecLSN（沒(méi)有實(shí)施，但之后還有更新），Redo過(guò)程就跳過(guò)該日志記錄否則Redo過(guò)程就從磁盤(pán)調(diào)出該頁(yè)，

69、如果其PageLSN小于該日志記錄的LSN，重做該日志記錄,ARIES算法：Undo過(guò)程,Undo過(guò)程反向掃描日志，取消所有undo-list中的事務(wù)如果找到一個(gè)CLR，它用UndoNextLSN字段跳過(guò)一個(gè)已經(jīng)回滾了的事務(wù)日志。否則，它用事務(wù)日志的PrevLSN字段查找下一個(gè)要被撤消的事務(wù)日志每當(dāng)一個(gè)update日志記錄被用于撤消，Undo過(guò)程產(chǎn)生一個(gè)包含undo執(zhí)行動(dòng)作（必須是物理邏輯的）的CLR，并將CLR的UndoNextL