kc第16讲-事务管理技术.ppt

第10讲 第15章 事务管理技术重庆大学计算机学院 课程名称 数据库系统 第16讲 事务管理技术 项目驱动目标 如何在数据库中实现可靠的事务处理 一 事务的基本概念 二 并发执行 三 可串行化 四 其它事务相关知识 主要讨论问题 什么是事务事务应具备什么样的特征如何实现事务的原子性和持久性什么是调度什么叫调度的可串行化什么是调度的优先图冲突可串行化如何判定什么是可恢复调度 Exercise16 TransactionConcept Atransactionisaunitofprogramexecutionthataccessesandpossiblyupdatesvariousdataitems Atransactionmustseeaconsistentdatabase Duringtransactionexecutionthedatabasemaybetemporarilyinconsistent Whenthetransactioncompletessuccessfully iscommitted thedatabasemustbeconsistent Afteratransactioncommits thechangesithasmadetothedatabasepersist eveniftherearesystemfailures Multipletransactionscanexecuteinparallel Twomainissuestodealwith Failuresofvariouskinds suchashardwarefailuresandsystemcrashesConcurrentexecutionofmultipletransactions 1 1什么是事务 1 1事务 问题1答案 一事务的基本知识 ACIDProperties 原子性Atomicity Eitheralloperationsofthetransactionareproperlyreflectedinthedatabaseornoneare 一致性Consistency Executionofatransactioninisolationpreservestheconsistencyofthedatabase 隔离性Isolation Althoughmultipletransactionsmayexecuteconcurrently eachtransactionmustbeunawareofotherconcurrentlyexecutingtransactions Intermediatetransactionresultsmustbehiddenfromotherconcurrentlyexecutedtransactions Thatis foreverypairoftransactionsTiandTj itappearstoTithateitherTjfinishedexecutionbeforeTistarted orTjstartedexecutionafterTifinished 即每个事务都感觉不到其它事务在并行执行 持久性Durability Afteratransactioncompletessuccessfully thechangesithasmadetothedatabasepersist eveniftherearesystemfailures Topreservetheintegrityofdatathedatabasesystemmustensure 1 2事务应具备什么样的特征 1 1事务 问题2答案 ExampleofFundTransfer 资金转账 Transactiontotransfer 50fromaccountAtoaccountB 1 read A 2 A A 503 write A 4 read B 5 B B 506 write B Atomicityrequirement ifthetransactionfailsafterstep3andbeforestep6 thesystemshouldensurethatitsupdatesarenotreflectedinthedatabase elseaninconsistencywillresult Consistencyrequirement thesumofAandBisunchangedbytheexecutionofthetransaction IsolationrequirementDurabilityrequirement 1 3你能举出要求事务的实例 1 1事务 ExampleofFundTransfer 资金转账 续 Isolationrequirement ifbetweensteps3and6 anothertransactionisallowedtoaccessthepartiallyupdateddatabase itwillseeaninconsistentdatabase thesumA Bwillbelessthanitshouldbe Isolationcanbeensuredtrivially一般地byrunningtransactionsserially thatisoneaftertheother However executingmultipletransactionsconcurrentlyhassignificantbenefits aswewillseelater Durabilityrequirement oncetheuserhasbeennotifiedthatthetransactionhascompleted i e thetransferofthe 50hastakenplace theupdatestothedatabasebythetransactionmustpersistdespitefailures afterstep3andbeforestep6 1 1事务 TransactionState Active theinitialstate thetransactionstaysinthisstatewhileitisexecutingPartiallycommitted afterthefinalstatementhasbeenexecuted Failed afterthediscoverythatnormalexecutioncannolongerproceed Aborted afterthetransactionhasbeenrolledbackandthedatabaserestoredtoitsstatepriortothestartofthetransaction Twooptionsafterithasbeenaborted restartthetransaction canbedoneonlyifnointernallogicalerrorkillthetransactionCommitted aftersuccessfulcompletion 直观图示 事务状态变化 1 4事务执行时可能出现哪些状态 1 2事务的状态 TransactionState 直观图示 1 2事务的状态 ImplementationofAtomicityandDurability 原子性 持久性 Therecovery managementcomponentofadatabasesystemimplementsthesupportforatomicityanddurability The引子shadow databasescheme assumethatonlyonetransactionisactiveatatime apointercalleddb pointeralwayspointstothecurrentconsistentcopyofthedatabase allupdatesaremadeonashadowcopyofthedatabase anddb pointerismadetopointtotheupdatedshadowcopyonlyafterthetransactionreachespartialcommitandallupdatedpageshavebeenflushedtodisk incasetransactionfails oldconsistentcopypointedtobydb pointercanbeused andtheshadowcopycanbedeleted 直观图示 数据库指针切换 1 5如何实现事务的原子性和持久性 1 3如何保证事务的ACID性质 问题3答案 ImplementationofAtomicityandDurability 原子性 持久性 续 AssumesdisksdonotfailUsefulfortexteditors butextremelyinefficientforlargedatabases why 复制整个数据库开销很大 DoesnothandleconcurrenttransactionsWillstudybetterschemesinChapter17 Theshadow databasescheme 1 3如何保证事务的ACID性质 ConcurrentExecutions Multipletransactionsareallowedtorunconcurrentlyinthesystem Advantagesare increasedprocessoranddiskutilization leadingtobettertransactionthroughput onetransactioncanbeusingtheCPUwhileanotherisreadingfromorwritingtothediskreducedaverageresponsetimefortransactions shorttransactionsneednotwaitbehindlongones Concurrencycontrolschemes mechanismstoachieveisolation thatis tocontroltheinteractionamongtheconcurrenttransactionsinordertopreventthemfromdestroyingtheconsistencyofthedatabaseWillstudyinChapter16 afterstudyingnotionofcorrectnessofconcurrentexecutions 二并发执行与调度 2 1什么是并发执行和并发控制 2 1并发执行 Schedules Schedule asequencesofinstructionsthatspecifythechronological按时间顺序排列的orderinwhichinstructionsofconcurrenttransactionsareexecutedascheduleforasetoftransactionsmustconsistofallinstructionsofthosetransactionsmustpreservetheorderinwhichtheinstructionsappearineachindividualtransaction Atransactionthatsuccessfullycompletesitsexecutionwillhaveacommitinstructionsasthelaststatement willbeomittedifitisobvious Atransactionthatfailstosuccessfullycompleteitsexecutionwillhaveanabortinstructionsasthelaststatement willbeomittedifitisobvious 例子 Schedule1 4 2 2什么是调度 Schedule 2 2调度Schedule 问题4答案 Schedule1 LetT1transfer 50fromAtoB andT2transfer10 ofthebalancefromAtoB AserialscheduleinwhichT1isfollowedbyT2 2 3什么是合理的调度 2 2调度Schedule Schedule2 AserialschedulewhereT2isfollowedbyT1 2 2调度Schedule Schedule3 LetT1andT2bethetransactionsdefinedpreviously Thefollowingscheduleisnotaserialschedule butitisequivalenttoSchedule1 InSchedules1 2and3 thesumA Bispreserved 合理转账 2 2调度Schedule Schedule4 Thefollowingconcurrentscheduledoesnotpreservethevalueof A B 不合理转账 2 4什么是不合理的调度 2 2调度Schedule Serializability BasicAssumption Eachtransactionpreservesdatabaseconsistency Thusserialexecutionofasetoftransactionspreservesdatabaseconsistency A possiblyconcurrent scheduleisserializableifitisequivalenttoaserialschedule Differentformsofscheduleequivalencegiverisetothenotionsof 后面将分别详细讨论 conflictserializability冲突可串行化viewserializability视图可串行化Weignoreoperationsotherthanreadandwriteinstructions andweassumethattransactionsmayperformarbitrarycomputationsondatainlocalbuffersinbetweenreadsandwrites Andsooursimplifiedschedulesconsistofonlyreadandwriteinstructions 三可串行化 3 1什么叫调度的可串行化 3 1基本概念 问题5答案 ConflictingInstructions ConflictSerializability 冲突指令 InstructionsliandljoftransactionsTiandTjrespectivelyconflictifandonlyifthereexistssomeitemQaccessedbybothliandlj andatleastoneofthetwoinstructionswroteQ 1 li read Q lj read Q liandljdon tconflict 2 li read Q lj write Q Theyconflict 3 li write Q lj read Q Theyconflict4 li write Q lj write Q TheyconflictIntuitively aconflictbetweenliandljforcesa logical temporalorderbetweenthem Ifliandljareconsecutiveinascheduleandtheydonotconflict theirresultswouldremainthesameeveniftheyhadbeeninterchangedintheschedule 3 2什么叫冲突可串行化 冲突等价 IfascheduleScanbetransformedintoascheduleS byaseriesofswapsofnon conflictinginstructions wesaythatSandS areconflictequivalent 冲突可串行化 WesaythatascheduleSisconflictserializableifitisconflictequivalenttoaserialschedule 直观例示 3 1基本概念 ConflictSerializability 冲突可串行化例示 Schedule3canbetransformedintoSchedule6 aserialschedulewhereT2followsT1 byseriesofswapsofnon conflictinginstructions ThereforeSchedule3isconflictserializable Schedule3 Schedule6 3 2冲突可串行化 ConflictSerializability 冲突不可串行化例示 Exampleofaschedulethatisnotconflictserializable Weareunabletoswapinstructionsintheabovescheduletoobtaineithertheserialschedule ortheserialschedule 3 2冲突可串行化 ViewSerializability 视图等价 视图等价 LetSandS betwoscheduleswiththesamesetoftransactions SandS areviewequivalentifthefollowingthreeconditionsaremet 1 ForeachdataitemQ iftransactionTireadstheinitialvalueofQinscheduleS thentransactionTimustinscheduleS alsoreadtheinitialvalueofQ 2 ForeachdataitemQ iftransactionTiexecutesread Q inscheduleS andthatvaluewasproducedbytransactionTj ifany thentransactionTimustinscheduleS alsoreadthevalueofQthatwasproducedbytransactionTj 3 ForeachdataitemQ thetransaction ifany thatperformsthefinalwrite Q operationinscheduleSmustperformthefinalwrite Q operationinscheduleS Ascanbeseen viewequivalenceisalsobasedpurelyonreadsandwritesalone 视图可串行化 3 3什么叫视图等价和视图可串行化 3 3视图可串行化 ViewSerializability 视图可串行化 视图可串行化 AscheduleSisviewserializableitisviewequivalenttoaserialschedule 性质 Everyconflictserializablescheduleisalsoviewserializable 例子 Belowisaschedulewhichisview serializablebutnotconflictserializable Whatserialscheduleisaboveequivalentto Everyviewserializableschedulethatisnotconflictserializablehasblindwrites 盲目写 如上图例中有两个盲目写 仅T6写保存 3 3视图可串行化 OtherNotionsofSerializability ThescheduleS1belowproducessameoutcomeastheserialscheduleS2 yetisnotconflictequivalentorviewequivalenttoit Determiningsuchequivalencerequiresanalysisofoperationsotherthanreadandwrite 原因说明 S1中T5读初始值B 但在S2中T5只能读到B 50 而非值B 3 4还有什么可串行化术语 3 4其它可串行化概念 ConsidersomescheduleofasetoftransactionsT1 T2 Tn优先图Precedencegraph adirectgraphwheretheverticesarethetransactions names WedrawanarcfromTitoTjifthetwotransactionconflict andTiaccessedthedataitemonwhichtheconflictaroseearlier Wemaylabelthearcbytheitemthatwasaccessed 例子 Example 3 5什么是调度的优先图 Precedencegraph 3 5可串行化的检测 问题6答案 ExampleofScheduleA ItsPrecedenceGraph T1T2T3T4T5read X read Y read Z read V read W read W read Y write Y write Z read U read Y write Y read Z write Z read U write U 3 5可串行化的检测 TestforConflictSerializability Ascheduleisconflictserializableifandonlyifitsprecedencegraphisacyclic 无环的Cycle detectionalgorithmsexistwhichtakeordern2time wherenisthenumberofverticesinthegraph Betteralgorithmstakeordern ewhereeisthenumberofedges Ifprecedencegraphisacyclic theserializabilityordercanbeobtainedbyatopologicalsorting拓扑排序ofthegraph Thisisalinearorderconsistentwiththepartialorderofthegraph Forexample aserializabilityorderforScheduleAwouldbeT5 T1 T3 T2 T4Arethereothers T5 T1 T2 T3 T4 3 6冲突可串行化如何判定 又例 3 5可串行化的检测 问题7答案 TestforViewSerializability Theprecedencegraphtestforconflictserializabilitycannotbeuseddirectlytotestforviewserializability Extensiontotestforviewserializabilityhascostexponentialinthesizeoftheprecedencegraph TheproblemofcheckingifascheduleisviewserializablefallsintheclassofNP completeproblems Thusexistenceofanefficientalgorithmisextremelyunlikely Howeverpracticalalgorithmsthatjustchecksomesufficientconditionsforviewserializabilitycanstillbeused 3 7视图可串行化可以判定 3 5可串行化的检测 RecoverableSchedules 可恢复调度 Recoverableschedule ifatransactionTjreadsadataitempreviouslywrittenbyatransactionTi thenthecommitoperationofTiappearsbeforethecommitoperationofTj Thefollowingschedule Schedule11 isnotrecoverableifT9commitsimmediatelyaftertheread原因分析 IfT8shouldabort T9wouldhaveread andpossiblyshowntotheuser aninconsistentdatabasestate Hence databasemustensurethatschedulesarerecoverable Needtoaddresstheeffectoftransactionfailuresonconcurrentlyrunningtransactions 四其它事务相关知识 4 1什么是可恢复调度 为何需要 4 1可恢复与无级联调度 问题8答案 CascadingRollbacks 定义 Cascadingrollback asingletransactionfailureleadstoaseriesoftransactionrollbacks 例子 Considerthefollowingschedulewherenoneofthetransactionshasyetcommitted sothescheduleisrecoverable IfT10fails T11andT12mustalsoberolledback 效果 Itcanleadtotheundoingofasignificantamountofwork 4 2什么叫事务的级联回卷 4 1可恢复与无级联调度 CascadelessSchedules 无级联调度 Cascadelessschedules cascadingrollbackscannotoccur foreachpairoftransactionsTiandTj suchthatTjreadsadataitempreviously之前writtenbyTi thecommitoperationofTiappearsbeforethereadoperationofTj 若Tj读了由Ti所写的数据 则Ti先于Tj提交 显然 EverycascadelessscheduleisalsorecoverableItisdesirabletorestricttheschedulestothosethatarecascadeless 4 3什么是无级联调度 有何作用 4 1可恢复与无级联调度 ConcurrencyControl Adatabasemustprovideamechanismthatwillensurethatallpossibleschedulesareeitherconflictorviewserializable andarerecoverableand 最好是无级联的 preferablycascadelessApolicyinwhichonlyonetransactioncanexecuteatatimegeneratesserialschedules butprovidesapoordegreeofconcurrencyAreserialschedulesrecoverable cascadeless 问题如何解决 提高事务并发执行度 Testingascheduleforserializabilityafterithasexecutedisalittletoolate Goal todevelopconcurrencycontrolprotocols并发控制协议thatwillassureserializability 4 4DBMS并发控制应满足什么要求 4 2并发控制 ConcurrencyControlprotocol Concurrency controlprotocolsallowconcurrentschedules butensurethattheschedulesareconflict viewserializable andarerecoverableandcascadeless ConcurrencycontrolprotocolsgenerallydonotexaminetheprecedencegraphasitisbeingcreatedInsteadaprotocolimposes强 加于adiscipline规则thatavoidsnonseralizableschedules WestudysuchprotocolsinChapter16 Differentconcurrencycontrolprotocolsprovidedifferenttradeoffs权衡 折中betweentheamountofconcurrencytheyallowandtheamountofoverheadthattheyincur Testsforserializabilityhelpusunderstandwhyaconcurrencycontrolprotocoliscorrect 4 5什么是并发控制协议 4 2并发控制 WeakLevelsofConsistency 弱一致性级别 Someapplicationsarewillingtolivewithweaklevelsofconsistency allowingschedulesthat