关系论坛头像图片

当前无法显示此图像.
Lecture13RecoverySystemQiwenDongJun20,2011SchoolofComputerScienceFudanUniversity2012-06-13SchoolofC.
S.
,FudanUniv.
2OutlineTransactionfailureLogicalerrorsSystemerrorsSystemcrashApowerfailureorotherhardwareorsoftwarefailurecausesthesystemtocrashDiskfailureAheadcrashorsimilardiskfailuredestroysallorpartofdiskstorage2012-06-13SchoolofC.
S.
,FudanUniv.
3RecoveryAlgorithmsTechniquestoensuredatabaseconsistencyandtransactionatomicityanddurabilitydespitefailuresRecoveryalgorithmshavetwoparts1.
Actionstakenduringnormaltransactionprocessing2.
Actionstakenafterafailure当前无法显示此图像.
DataAccess2012-06-13SchoolofC.
S.
,FudanUniv.
5StorageStructureVolatilestoragedoesnotsurvivesystemcrashesexamples:mainmemory,cachememoryNonvolatilestoragesurvivessystemcrashesexamples:disk,tape,flashmemoryStablestorageamythicalformofstoragethatsurvivesallfailuresapproximatedbymaintainingmultiplecopiesondistinctnonvolatilemedia2012-06-13SchoolofC.
S.
,FudanUniv.
6DataAccessPhysicalblocksarethoseblocksresidingonthedisk.
Bufferblocksaretheblocksresidingtemporarilyinmainmemory.
Blockmovementsbetweendiskandmainmemoryare:input(B)output(B)EachtransactionTihasitsprivatework-areaTi'slocalcopyofadataitemXiscalledxi.
Weassume,forsimplicity,thateachdataitemfitsin,andisstoredinside,asingleblock.
2012-06-13SchoolofC.
S.
,FudanUniv.
7DataAccess(Cont.
)Transactiontransfersdataitemsbetweensystembufferblocksanditsprivatework-areausingread(X)write(X)TransactionsPerformread(X)whileaccessingXforthefirsttimeAllsubsequentaccessesaretothelocalcopyAfterlastaccess,transactionexecuteswrite(X)output(BX)neednotimmediatelyfollowwrite(X)Systemcanperformtheoutputoperationwhenitdeemsfit2012-06-13SchoolofC.
S.
,FudanUniv.
8ExampleofDataAccessxYABx1y1bufferBufferBlockABufferBlockBinput(A)output(B)read(X)write(Y)diskworkareaofT1workareaofT2memoryx22012-06-13SchoolofC.
S.
,FudanUniv.
9Modifyingthedatabase(withoutensuringthatthetransactionwillcommit)mayleavethedatabaseinaninconsistentstate.
ConsidertransactionTithattransfers$50fromaccountAtoaccountB;goaliseithertoperformalldatabasemodificationsmadebyTiornoneatall.
SeveraloutputoperationsmayberequiredforTi(tooutputAandB).
Afailuremayoccurafteroneofthesemodificationshavebeenmadebutbeforeallofthemaremade.
RecoveryandAtomicity2012-06-13SchoolofC.
S.
,FudanUniv.
10RecoveryandAtomicity(Cont.
)Toensureatomicitydespitefailures,wefirstoutputinformationdescribingthemodificationstostablestoragewithoutmodifyingthedatabaseitself.
Therearetwoapproaches:log-basedrecovery(基于日志的恢复)shadow-paging(影子页)Weassume(initially)thattransactionsrunserially,thatis,oneaftertheother当前无法显示此图像.
Log-basedRecovery2012-06-13SchoolofC.
S.
,FudanUniv.
12Log-BasedRecoveryAlogiskeptonstablestorage.
Thelogisasequenceoflogrecords.
Weassumethatlogrecordsarenotbuffered.
WhentransactionTistarts,itregistersitselfbywritingalogrecordBeforeTiexecuteswrite(X),alogrecordiswrittenWhenTifinishesit'slaststatement,thelogrecordiswritten.
TwoapproachesusinglogsDeferreddatabasemodification(延迟数据库修改)Immediatedatabasemodification(即刻数据库修改)2012-06-13SchoolofC.
S.
,FudanUniv.
13DeferredDatabaseModificationRecordsallmodificationstothelog,butdefersallthewritestoafterpartialcommit.
Transactionstartsbywritingrecordtolog.
Awrite(X)operationresultsinalogrecordbeingwritten.
ThewriteisnotperformedonXatthistime,butisdeferred.
WhenTipartiallycommits,iswrittentothelogFinally,thelogrecordsarereadandusedtoactuallyexecutethepreviouslydeferredwrites.
2012-06-13SchoolofC.
S.
,FudanUniv.
14Duringrecoveryafteracrashatransactionneedstoberedoneiffbothandarethereinthelog.
Redo(Ti)setsthevalueofalldataitemsupdatedbythetransactiontothenewvalues.
example(T0executesbeforeT1):T0:read(A)T1:read(C)A:-A-50C:-C-100Write(A)write(C)read(B)B:-B+50write(B)DeferredDatabaseModification(Cont.
)2012-06-13SchoolofC.
S.
,FudanUniv.
15Iflogonstablestorageattimeofcrashisasincase:(a)Noredoactionsneedtobetaken(b)redo(T0)mustbeperformed(c)redo(T0)mustbeperformedfollowedbyredo(T1)DeferredDatabaseModification(Cont.
)2012-06-13SchoolofC.
S.
,FudanUniv.
16ImmediateDatabaseModificationAllowsdatabaseupdatesofanuncommittedtransactiontobemadeasthewritesareissuedUpdatelogrecordmustbewrittenbeforedatabaseitemiswrittenOutputofupdatedblockscantakeplaceatanytimebeforeoraftertransactioncommitOrderinwhichblocksareoutputcanbedifferentfromtheorderinwhichtheyarewritten.
2012-06-13SchoolofC.
S.
,FudanUniv.
17LogWriteOutputA=950B=2050C=600BB,BCBANote:BXdenotesblockcontainingXx1ImmediateDatabaseModificationExample2012-06-13SchoolofC.
S.
,FudanUniv.
18Recoveryprocedurehastwooperations:undo(Ti)redo(Ti)Bothoperationsmustbeidempotent(等幂/幂等的)Thatis,eveniftheoperationisexecutedmultipletimestheeffectisthesameasifitisexecutedonceWhenrecoveringafterfailure:TransactionTineedstobeundoneifthelogcontainstherecord,butdoesnotcontain.
TransactionTineedstoberedoneifthelogcontainsboththerecordand.
Undooperationsareperformedfirst,thenredooperations.
ImmediateDatabaseModification(Cont.
)2012-06-13SchoolofC.
S.
,FudanUniv.
19Recoveryactionsineachcaseaboveare:(a)undo(T0)(b)undo(T1)andredo(T0)(c)redo(T0)andredo(T1)ImmediateDBModificationRecoveryExample当前无法显示此图像.
Checkpoints2012-06-13SchoolofC.
S.
,FudanUniv.
21Checkpoints(检查点)Problemsintherecoveryprocedure:1.
searchingtheentirelogistime-consuming2.
wemightunnecessarilyredotransactionswhichhavealreadyoutputtheirupdatestothedatabase.
Recoveryprocedurebyperiodicallyperformingcheckpointing1.
Outputalllogrecordscurrentlyresidinginmainmemoryontostablestorage.
2.
Outputallmodifiedbufferblockstothedisk.
3.
Writealogrecordontostablestorage.
2012-06-13SchoolofC.
S.
,FudanUniv.
22Checkpoints(Cont.
)Duringrecovery:1.
Scanbackwardsfromendoflogtofindthemostrecentrecord2.
Continuescanningbackwardstillarecordisfound(Wehaveassumethatalltransactionsareexecutedserially)3.
Needonlyconsiderthepartoflogfollowingabovestartrecord.
4.
Foralltransactions(startingfromTiorlater)withno,executeundo(Ti).
5.
Scanningforwardinthelog,foralltransactionsstartingfromTiorlaterwitha,executeredo(Ti).
2012-06-13SchoolofC.
S.
,FudanUniv.
23ExampleofCheckpointsT1canbeignored(updatesalreadyoutputtodiskduetocheckpoint)T2andT3redone.
T4undoneTcTfT1T2T3T4checkpointsystemfailure当前无法显示此图像.
ConcurrentTransactions2012-06-13SchoolofC.
S.
,FudanUniv.
25Wemodifythelog-basedrecoveryschemestoallowmultipletransactionstoexecuteconcurrently.
AlltransactionsshareasinglediskbufferandasinglelogAbufferblockcanhavedataitemsupdatedbyoneormoretransactionsWeassumeconcurrencycontrolusingstricttwo-phaselocking;Loggingisdoneasdescribedearlier.
Logrecordsofdifferenttransactionsmaybeinterspersedinthelog.
ThecheckpointingtechniqueandactionstakenonrecoveryhavetobechangedRecoveryWithConcurrentTransactions2012-06-13SchoolofC.
S.
,FudanUniv.
26Checkpointsareperformedasbefore,exceptthatthecheckpointlogrecordistheformLisalistoftransactionsactiveatthetimeofthecheckpointWeassumenoupdateisinprogresswhilethecheckpointiscarriedout(thiscanberelaxed)Whenthesystemrecoversfromacrash:1.
Initializeundo-listandredo-listtoempty2.
Scanthelogbackwardsuntilarecordisfound:iftherecordis,addTitoredo-listiftherecordis,thenifTiisnotinredo-list,addTitoundo-list3.
ForeveryTiinL,ifTiisnotinredo-list,addTitoundo-listRecoveryWithConcurrentTransactions(Cont.
)2012-06-13SchoolofC.
S.
,FudanUniv.
27Recoverynowcontinuesasfollows:1.
ScanlogbackwardsfromtheendofthelogDuringthescan,performundoforeachlogrecordthatbelongstoatransactioninundo-list.
2.
Locatethemostrecentrecord.
3.
Scanlogforwardsfromtherecordtilltheendofthelog.
Duringthescan,performredoforeachlogrecordthatbelongstoatransactiononredo-listRecoveryWithConcurrentTransactions(Cont.
)2012-06-13SchoolofC.
S.
,FudanUniv.
28ExampleofRecoveryGooverthestepsoftherecoveryalgorithmonthefollowinglog:2012-06-13SchoolofC.
S.
,FudanUniv.
29LogRecordBufferingLogrecordbuffering:logrecordsarebufferedinmainmemory,insteadofofbeingoutputdirectlytostablestorage.
Logrecordsareoutputtostablestoragewhenablockoflogrecordsinthebufferisfull,oralogforceoperationisexecuted.
Logforceisperformedtocommitatransactionbyforcingallitslogrecords(includingthecommitrecord)tostablestorage.
Severallogrecordscanthusbeoutputusingasingleoutputoperation,reducingtheI/Ocost.
2012-06-13SchoolofC.
S.
,FudanUniv.
30LogRecordBuffering(Cont.
)Therulesbelowmustbefollowediflogrecordsarebuffered:Logrecordsareoutputtostablestorageintheorderinwhichtheyarecreated.
TransactionTientersthecommitstateonlywhenthelogrecordhasbeenoutputtostablestorage.
Beforeablockofdatainmainmemoryisoutputtothedatabase,alllogrecordspertainingtodatainthatblockmusthavebeenoutputtostablestorage.
Thisruleiscalledthewrite-aheadloggingorWALrule2012-06-13SchoolofC.
S.
,FudanUniv.
31DatabaseBufferingDatabasemaintainsanin-memorybufferofdatablocksWhenanewblockisneeded,ifbufferisfullanexistingblockneedstoberemovedfrombufferIftheblockchosenforremovalhasbeenupdated,itmustbeoutputtodiskNoupdateshouldbeinprogressonablockwhenitisoutputtodisk.
Canbeensuredasfollows.
Beforewritingadataitem,transactionacquiresexclusivelockonblockcontainingthedataitemLockcanbereleasedoncethewriteiscompleted.
Suchlocksheldforshortdurationarecalledlatches.
Beforeablockisoutputtodisk,thesystemacquiresanexclusivelatchontheblockEnsuresnoupdatecanbeinprogressontheblock2012-06-13SchoolofC.
S.
,FudanUniv.
32BufferManagement(Cont.
)Databasebuffercanbeimplementedeitherinanareaofrealmain-memoryreservedforthedatabase,orinvirtualmemoryImplementingbufferinreservedmain-memoryhasdrawbacks:Memoryispartitionedbefore-handbetweendatabasebufferandapplications,limitingflexibility.
Needsmaychange,andalthoughoperatingsystemknowsbesthowmemoryshouldbedividedupatanytime,itcannotchangethepartitioningofmemory.
2012-06-13SchoolofC.
S.
,FudanUniv.
33BufferManagement(Cont.
)Databasebuffersaregenerallyimplementedinvirtualmemoryinspiteofsomedrawbacks:WhenOSneedstoevictapagethathasbeenmodified,thepageiswrittentoswapspaceondisk.
WhenDBdecidestowritebufferpagetodisk,bufferpagemaybeinswapspace,andmayhavetobereadfromswapspaceondiskandoutputtothedatabaseondisk,resultinginextraI/O!
Knownasdualpagingproblem.
Ideallywhenswappingoutadatabasebufferpage,operatingsystemshouldpasscontroltodatabase,whichinturnoutputspagetodatabaseinsteadoftoswapspace(makingsuretooutputlogrecordsfirst)Dualpagingcanthusbeavoided,butcommonoperatingsystemsdonotsupportsuchfunctionality.
2012-06-13SchoolofC.
S.
,FudanUniv.
34FailurewithLossofNonvolatileStorageTechniquesimilartocheckpointingusedtodealwithlossofnon-volatilestoragePeriodicallydumptheentirecontentofthedatabasetostablestorageNotransactionmaybeactiveduringthedumpprocedure;aproceduresimilartocheckpointingmusttakeplaceOutputalllogrecordscurrentlyresidinginmainmemoryontostablestorage.
Outputallbufferblocksontothedisk.
Copythecontentsofthedatabasetostablestorage.
Outputarecordtologonstablestorage.
Torecoverfromdiskfailurerestoredatabasefrommostrecentdump.
ConsultthelogandredoalltransactionsthatcommittedafterthedumpCanbeextendedtoallowtransactionstobeactiveduringdump;knownasfuzzydumporonlinedump2012-06-13SchoolofC.
S.
,FudanUniv.
35考试要点(仅列出要点,不是全部考试范围)ER模型:能够设计ER模型,并绘制ER图能够转换成关系模式关系代数能够写出给定关系代数的结果能够针对特定查询写出对应的关系代数表达式能够写出select语句的查询结果关系模式规范化能计算属性集的闭包无损分解和保持依赖分解的判据能够分析关系是否满足某些范式能够分析关系模式的分解性质2012-06-13SchoolofC.
S.
,FudanUniv.
36考试要点(仅列出要点,不是全部考试范围)查询处理:理解各种查询处理算法能够分析并计算各种连接的代价事务处理可串行化的判定并发控制理解两阶段封锁协议和时间戳协议的执行过程死锁产生的原因和处理方法能够根据并发执行的事物,构造等待图,处理死锁树形协议的优缺点数据库恢复能够根据事物的执行写出日志能够在数据库故障时,根据日志进行恢复