DBMS UNIT 5 CHAPTER 3.ppt

DBMS and it's 5 th unit

1. UNIT -5
RECOVERY SYSTEM

2. •Failure Classification
•Storage Structure
•Recovery and Atomicity
•Log-Based Recovery
•Shadow Paging
•Recovery With Concurrent Transactions
•Buffer Management
•Failure with Loss of Nonvolatile Storage
•Advanced Recovery Techniques
•ARIES Recovery Algorithm
•Remote Backup Systems

3. 1. Failure Classification
•Transactionfailure:
–Logical errors:transactioncannot
completeduetosomeinternalerror
condition
–Systemerrors:thedatabasesystemmust
terminateanactivetransactionduetoan
errorcondition(e.g.,deadlock)

4. Failure Classification
•System crash:apowerfailureorother
hardwareorsoftwarefailurecausesthe
systemtocrash.
–Fail-stopassumption:non-volatilestorage
contentsareassumedtonotbecorruptedby
systemcrash
•Databasesystemshavenumerousintegritychecksto
preventcorruptionofdiskdata
•Diskfailure:aheadcrashorsimilardisk
failuredestroysallorpartofdiskstorage
–Destructionisassumedtobedetectable:disk
drivesusechecksumstodetectfailures

5. 2. Recovery and Atomicity
•Modifyingthedatabasewithoutensuringthat
thetransactionwillcommitmayleavethe
databaseinaninconsistentstate.
•ConsidertransactionT
ithattransfers$50
fromaccountAtoaccountB;goaliseitherto
performalldatabasemodificationsmadebyT
i
ornoneatall.
•Severaloutputoperationsmayberequired
forT
i(tooutputAandB).Afailuremay
occurafteroneofthesemodificationshave
beenmadebutbeforeallofthemaremade.

6. Recovery and Atomicity (cont..)
•Toensureatomicitydespitefailures,wefirst
output information describing the
modificationstostablestoragewithout
modifyingthedatabaseitself.
•Westudytwoapproaches:
–log-basedrecovery,and
–shadow-paging
•Weassume(initially)thattransactionsrun
serially,thatis,oneaftertheother.

7. 3. Log-Based Recovery
•Alogiskeptonstablestorage.
–Thelogisasequenceoflogrecords,and
maintainsarecordofupdateactivitiesonthe
database.
•WhentransactionT
istarts,itregistersitself
by writing a
<T
istart>logrecord
•BeforeT
iexecuteswrite(X),alogrecord<T
i,
X,V
1,V
2>iswritten,whereV
1isthevalue
ofXbeforethewrite,andV
2isthevalueto
bewrittentoX.
–LogrecordnotesthatT
ihasperformedawriteon
dataitemX
jX
jhadvalueV
1beforethewrite,and
willhavevalueV
2afterthewrite.

8. 3. Log-Based Recovery (Cont..)
•WhenT
ifinishesitlaststatement,thelog
record<T
icommit>iswritten.
•Weassumefornowthatlogrecordsare
writtendirectlytostablestorage(thatis,
theyarenotbuffered)
•Twoapproachesusinglogs
–Deferreddatabasemodification
–Immediatedatabasemodification

9. 3. Log-Based Recovery (Cont..)
DeferredDatabaseModification
•The deferred database modification
scheme records all modifications to the log,
but defers all the writes to after partial
commit.
•Assume that transactions execute serially
•Transaction starts by writing <T
istart>
record to log.

10. 3. Log-Based Recovery (Cont..)
DeferredDatabaseModificationcont..
•Awrite(X)operationresultsinalogrecord
<T
i,X,V>beingwritten,whereVisthenew
valueforX
–Note:oldvalueisnotneededforthisscheme
•ThewriteisnotperformedonXatthistime,
butisdeferred.
•WhenT
ipartiallycommits,<T
icommit>is
writtentothelog
•Finally,thelogrecordsarereadandusedto
actuallyexecutethepreviouslydeferred
writes.

11. 3. Log-Based Recovery (Cont..)
DeferredDatabaseModificationcont..
•Duringrecoveryafteracrash,atransaction
needstoberedoneifandonlyifboth<T
i
start>and<T
icommit>arethereinthelog.
•RedoingatransactionT
i(redoT
i)setsthe
valueofalldataitemsupdatedbythe
transactiontothenewvalues.
•Crashescanoccurwhile
–thetransactionisexecutingtheoriginalupdates,
or
–whilerecoveryactionisbeingtaken

12. 3. Log-Based Recovery (Cont..)
DeferredDatabaseModificationcont..
•example transactions T
0and T
1(T
0executes before
T
1):
T
0: read (A) T
1: read(C)
A: -A -50 C:-C-100
Write (A) write (C)
read (B)
B:-B + 50
write (B)

13. 3. Log-Based Recovery (Cont..)
DeferredDatabaseModificationcont..
•Below we show the log as it appears at three
instances of time.

14. 3. Log-Based Recovery (Cont..)
DeferredDatabaseModificationcont..
Iflogonstablestorageattimeofcrashisasin
case:
(a)Noredoactionsneedtobetaken
(b) redo(T
0)mustbeperformedsince
<T
0commit>ispresent
(c)redo(T
0)mustbeperformedfollowedby
redo(T
1)since
<T
0commit>and<T
icommit>are
present

15. 3. Log-Based Recovery (Cont..)
Immediate DatabaseModification
•Theimmediate database modification
schemeallowsdatabaseupdatesofan
uncommittedtransactiontobemadeasthe
writesareissued
–sinceundoingmaybeneeded,updatelogsmust
havebotholdvalueandnewvalue

16. 3. Log-Based Recovery (Cont..)
Immediate DatabaseModificationCont…
•Updatelogrecordmustbewritten
beforedatabaseitemiswritten
–Weassumethatthelogrecordisoutput
directlytostablestorage
–Canbeextendedtopostponelogrecord
output,solongaspriortoexecutionofan
output(B)operationforadatablockB,all
logrecordscorrespondingtoitemsBmust
beflushedtostablestorage

17. 3. Log-Based Recovery (Cont..)
Immediate DatabaseModificationCont…
•Output of updated blocks can take place
at any time before or after transaction
commit
•Order in which blocks are output can be
different from the order in which they
are written.

18. 3. Log-Based Recovery (Cont..)
Immediate DatabaseModificationCont…
Log Write Output
<T
0start>
<T
0,A, 1000, 950>
T
o,B, 2000, 2050
A= 950
B= 2050
<T
0commit>
<T
1start>
<T
1, C, 700, 600>
C= 600
B
B, B
C
<T
1commit>
B
A
•Note: B
Xdenotes block containing X.

19. 3. Log-Based Recovery (Cont..)
Immediate DatabaseModificationCont…
•Recoveryprocedurehastwooperations
insteadofone:
–undo(T
i)restoresthevalueofalldataitems
updatedbyT
itotheiroldvalues,goingbackwards
fromthelastlogrecordforT
i
–redo(T
i)setsthevalueofalldataitemsupdated
byT
itothenewvalues,goingforwardfromthe
firstlogrecordforT
i
•Bothoperationsmustbeidempotent
–Thatis,eveniftheoperationisexecutedmultiple
timestheeffectisthesameasifitisexecuted
once
•Neededsinceoperationsmaygetre-executedduring
recovery

20. 3. Log-Based Recovery (Cont..)
Immediate DatabaseModificationCont…
•Whenrecoveringafterfailure:
–TransactionT
ineedstobeundoneifthelog
contains the record
<T
istart>,butdoesnotcontaintherecord
<T
icommit>.
–TransactionT
ineedstoberedoneifthelog
containsboththerecord<T
istart>and
therecord<T
icommit>.
•Undooperationsareperformedfirst,
thenredooperations.

21. 3. Log-Based Recovery (Cont..)
Immediate DB Modification Recovery
Example
Below we show the log as it appears at three instances
of time.

22. 3. Log-Based Recovery (Cont..)
Immediate DB Modification Recovery
Examplecont..
Recoveryactionsineachcaseaboveare:
(a)undo(T
0):Bisrestoredto2000andAto
1000.
(b)undo(T
1)andredo(T
0):Cisrestoredto
700,andthenAandBare
setto950and2050respectively.
(c)redo(T
0)andredo(T
1):AandBaresetto
950and2050
respectively.ThenCissetto600

23. Checkpoints
•Problemsinrecoveryprocedureasdiscussed
earlier:
1.searchingtheentirelogistime-consuming
2.wemightunnecessarilyredotransactionswhich
havealready
3.outputtheirupdatestothedatabase.
•Streamlinerecoveryprocedurebyperiodically
performingcheckpointing
1.Outputalllogrecordscurrentlyresidinginmain
memoryontostablestorage.
2.Outputallmodifiedbufferblockstothedisk.
3.Writealogrecord<checkpoint>ontostable
storage.

24. Checkpoints (Cont.)
•Duringrecoveryweneedtoconsideronlythemost
recenttransactionT
ithatstartedbeforethe
checkpoint,andtransactionsthatstartedafterT
i.
1.Scanbackwardsfromendoflogtofindthemostrecent
<checkpoint>record
2.Continuescanningbackwardstillarecord<T
istart>is
found.
3.Needonlyconsiderthepartoflogfollowingabovestart
record.Earlierpartoflogcanbeignoredduringrecovery,
andcanbeerasedwheneverdesired.
4.Foralltransactions(startingfromT
iorlater)withno<T
i
commit>,executeundo(T
i).(Doneonlyincaseof
immediatemodification.)
5.Scanningforwardinthelog,foralltransactionsstarting
fromT
iorlaterwitha<T
icommit>,executeredo(T
i).

25. Checkpoints (Cont.)
•T
1can be ignored (updates already output to disk due to
checkpoint)
•T
2and T
3redone.
•T
4undone
T
c
T
f
T
1
T
2
T
3
T
4
checkpoint system failure

26. 4. Shadow Paging
•Shadow pagingisanalternativetolog-
basedrecovery;thisschemeisusefulif
transactionsexecuteserially
•Idea:maintaintwopagetablesduringthe
lifetimeofatransaction–thecurrentpage
table,andtheshadowpagetable
•Storetheshadowpagetableinnonvolatile
storage,suchthatstateofthedatabaseprior
totransactionexecutionmayberecovered.
–Shadowpagetableisnevermodifiedduring
execution

27. 4. Shadow Paging Cont…
•Tostartwith,boththepagetablesare
identical.Onlycurrentpagetableis
usedfordataitemaccessesduring
executionofthetransaction.
•Wheneveranypageisabouttobe
writtenforthefirsttime
–Acopyofthispageismadeontoanunused
page.
–Thecurrentpagetableisthenmadeto
pointtothecopy
–Theupdateisperformedonthecopy

28. 4. Shadow Paging Cont…
•SamplePageTable

29. 4. Shadow Paging Cont…
•ExampleofShadowPaging

30. 4. Shadow Paging Cont…
•Tocommitatransaction:
1.Flushallmodifiedpagesinmain
memorytodisk
2.Outputcurrentpagetabletodisk
3.Makethecurrentpagetablethenew
shadowpagetable,asfollows:
–keepapointertotheshadowpagetableat
afixed(known)locationondisk.
–tomakethecurrentpagetablethenew
shadowpagetable,simplyupdatethe
pointertopointtocurrentpagetableon
disk

31. 4. Shadow Paging Cont…
•Oncepointertoshadowpagetablehasbeen
written,transactioniscommitted.
•Norecoveryisneededafteracrash—new
transactionscanstartrightaway,usingthe
shadowpagetable.
•Pagesnotpointedtofromcurrent/shadow
pagetableshouldbefreed(garbage
collected).

32. 5. Recovery With Concurrent Transactions
•Wemodifythelog-basedrecoveryschemesto
allowmultipletransactionstoexecute
concurrently.
–Alltransactionsshareasinglediskbufferanda
singlelog
–Abufferblockcanhavedataitemsupdatedbyone
ormoretransactions
•Weassumeconcurrencycontrolusingstrict
two-phaselocking;
–i.e.theupdatesofuncommitted transactions
shouldnotbevisibletoothertransactions
•OtherwisehowtoperformundoifT1updatesA,thenT2
updatesAandcommits,andfinallyT1hastoabort?

33. 5.Recovery With Concurrent Transactions Cont..
•Logging is done as described earlier.
–Log records of different transactions may
be interspersed in the log.
•The checkpointing technique and
actions taken on recovery have to be
changed
–since several transactions may be active
when a checkpoint is performed.

34. 5.Recovery With Concurrent Transactions Cont..
•Checkpointsareperformedasbefore,exceptthatthe
checkpointlogrecordisnowoftheform
< checkpoint L>
whereListhelistoftransactionsactiveatthetimeof
thecheckpoint
–Weassumenoupdatesareinprogresswhilethecheckpointis
carriedout(willrelaxthislater)
•Whenthesystemrecoversfromacrash,itfirstdoes
thefollowing:
1.Initializeundo-listandredo-listtoempty
2.Scanthelogbackwardsfromtheend,stoppingwhenthefirst
<checkpoint L> record is found.
Foreachrecordfoundduringthebackwardscan:
iftherecordis<T
icommit>,addT
itoredo-list
iftherecordis<T
istart>,thenifT
iisnotinredo-list,addT
ito
undo-list
3.ForeveryT
iinL,ifT
iisnotinredo-list,addT
itoundo-list

35. 5.Recovery With Concurrent Transactions Cont..
•Atthispointundo-listconsistsofincomplete
transactionswhichmustbeundone,andredo-list
consistsoffinishedtransactionsthatmustberedone.
•Recoverynowcontinuesasfollows:
1.Scanlogbackwardsfrommostrecentrecord,stoppingwhen
<T
istart>recordshavebeenencounteredforeveryT
iin
undo-list.
Duringthescan,performundoforeachlogrecordthatbelongs
toatransactioninundo-list.
2.Locatethemostrecent<checkpointL>record.
3.Scanlogforwardsfromthe<checkpointL>recordtillthe
endofthelog.
Duringthescan,performredoforeachlogrecordthatbelongs
toatransactiononredo-list

36. 5.Recovery With Concurrent Transactions Cont..
•ExampleofRecovery
•Go over the steps of the recovery algorithm
on the following log:
<T
0start>
<T
0, A, 0, 10>
<T
0commit>
<T
1start>
<T
1, B, 0, 10>
<T
2start> /* Scan in Step 4 stops
here */
<T
2, C, 0, 10>
<T
2, C, 10, 20>
<checkpoint {T
1, T
2}>
<T
3start>
<T
3,A, 10, 20>
<T
3, D, 0, 10>
<T
3commit>

37. 6.Log Record Buffering
•Logrecordbuffering:logrecordsare
bufferedinmainmemory,insteadofofbeing
outputdirectlytostablestorage.
–Logrecordsareoutputtostablestoragewhena
blockoflogrecordsinthebufferisfull,oralog
forceoperationisexecuted.
•Logforceisperformed tocommit a
transactionbyforcingallitslogrecords
(includingthecommitrecord)tostable
storage.
•Severallogrecordscanthusbeoutputusing
asingleoutputoperation,reducingtheI/O
cost.

38. 6.Log Record Buffering
•Therulesbelowmustbefollowediflog
recordsarebuffered:
–Logrecordsareoutputtostablestorageinthe
orderinwhichtheyarecreated.
–TransactionT
ientersthecommitstateonlywhen
the log record
<T
icommit>hasbeenoutputtostablestorage.
–Beforeablockofdatainmainmemoryisoutputto
thedatabase,alllogrecordspertainingtodatain
thatblockmusthavebeenoutputtostable
storage.
•Thisruleiscalledthewrite-aheadloggingorWALrule
–StrictlyspeakingWALonlyrequiresundoinformationtobe
output

39. 6.Database Buffering
•Database maintains an in-memory buffer of data
blocks
–When a new block is needed, if buffer is full an existing block
needs to be removed from buffer
–If the block chosen for removal has been updated, it must be
output to disk
•As a result of the write-ahead logging rule, if a block
with uncommitted updates is output to disk, log
records with undo information for the updates are
output to the log on stable storage first.
•No updates should be in progress on a block when it is
output to disk. Can be ensured as follows.
–Before writing a data item, transaction acquires exclusive lock
on block containing the data item
–Lock can be released once the write is completed.
•Such locks held for short duration are called latches.
–Before a block is output to disk, the system acquires an
exclusive latch on the block
•Ensures no update can be in progress on the block

40. 6.Buffer Management (Cont.)
•Databasebuffercanbeimplementedeither
–inanareaofrealmain-memoryreservedforthe
database,or
–invirtualmemory
•Implementing bufferinreservedmain-
memoryhasdrawbacks:
–Memory ispartitionedbefore-handbetween
database bufferandapplications,limiting
flexibility.
–Needsmaychange,andalthoughoperating
systemknowsbesthowmemoryshouldbedivided
upatanytime,itcannotchangethepartitioningof
memory.

41. 6.Buffer Management (Cont.)
•Databasebuffersaregenerallyimplementedinvirtual
memoryinspiteofsomedrawbacks:
–Whenoperatingsystemneedstoevictapagethathasbeen
modified,tomakespaceforanotherpage,thepageis
writtentoswapspaceondisk.
–Whendatabasedecidestowritebufferpagetodisk,buffer
pagemaybeinswapspace,andmayhavetobereadfrom
swapspaceondiskandoutputtothedatabaseondisk,
resultinginextraI/O!
•Knownasdualpagingproblem.
–Ideallywhenswappingoutadatabasebufferpage,operating
systemshouldpasscontroltodatabase,whichinturn
outputspagetodatabaseinsteadoftoswapspace(making
suretooutputlogrecordsfirst)
•Dualpagingcanthusbeavoided,butcommon operating
systemsdonotsupportsuchfunctionality.

42. 7.Remote Backup Systems
•Remotebackupsystemsprovidehighavailabilitybyallowing
transactionprocessingtocontinueeveniftheprimarysiteis
destroyed.

43. 7.Remote Backup Systems (Cont.)
•Detectionoffailure:Backupsitemustdetect
whenprimarysitehasfailed
–todistinguishprimarysitefailurefromlinkfailure
maintainseveralcommunicationlinksbetweenthe
primaryandtheremotebackup.
•Transferofcontrol:
–Totakeovercontrolbackupsitefirstperform
recoveryusingitscopyofthedatabaseandallthe
longrecordsithasreceivedfromtheprimary.
•Thus,completedtransactionsareredoneandincomplete
transactionsarerolledback.
–Whenthebackupsitetakesoverprocessingit
becomesthenewprimary
–Totransfercontrolbacktooldprimarywhenit
recovers,oldprimarymustreceiveredologsfrom
theoldbackupandapplyallupdateslocally.

44. 7.Remote Backup Systems (Cont.)
•Timetorecover:Toreducedelayintakeover,
backupsiteperiodicallyprocesestheredologrecords
(ineffect,performingrecoveryfromprevious
databasestate),performsacheckpoint,andcanthen
deleteearlierpartsofthelog.
•Hot-Spareconfigurationpermitsveryfasttakeover:
–Backupcontinuallyprocessesredologrecordastheyarrive,
applyingtheupdateslocally.
–Whenfailureoftheprimaryisdetectedthebackuprollsback
incompletetransactions,andisreadytoprocessnew
transactions.
•Alternativetoremotebackup:distributeddatabase
withreplicateddata
–Remotebackupisfasterandcheaper,butlesstolerantto
failure

45. 7.Remote Backup Systems (Cont.)
•Ensuredurabilityofupdatesbydelayingtransaction
commituntilupdateisloggedatbackup;avoidthis
delaybypermittinglowerdegreesofdurability.
•One-safe:commitassoonastransaction’scommit
logrecordiswrittenatprimary
–Problem:updatesmaynotarriveatbackupbeforeittakes
over.
•Two-very-safe:commitwhentransaction’scommit
logrecordiswrittenatprimaryandbackup
–Reducesavailabilitysincetransactionscannotcommitif
eithersitefails.
•Two-safe:proceedasintwo-very-safeifboth
primaryandbackupareactive.Ifonlytheprimaryis
active,thetransactioncommitsassoonasiscommit
logrecordiswrittenattheprimary.
–Betteravailabilitythantwo-very-safe;avoidsproblemoflost
transactionsinone-safe.