PROTOCOLS(基于锁的协议).ppt

Chapter16 ConcurrencyControl Lock BasedProtocols 基于锁的协议 Timestamp BasedProtocols 基于时间戳的协议 Validation BasedProtocols 基于有效性检查的协议 MultipleGranularity 多粒度 MultiversionSchemes 多版本机制 DeadlockHandling 死锁处理 InsertandDeleteOperations 插入与删除处理 Lock BasedProtocols 基于锁的协议 AlockisamechanismtocontrolconcurrentaccesstoadataitemDataitemscanbelockedintwomodes 1 exclusive排他锁 X mode Dataitemcanbebothreadaswellaswritten X lockisrequestedusinglock Xinstruction 2 shared共享锁 S mode Dataitemcanonlyberead S lockisrequestedusinglock Sinstruction Lockrequestsaremadetoconcurrency controlmanager Transactioncanproceedonlyafterrequestisgranted Lock BasedProtocols Cont Lock compatibilitymatrix 锁相容性矩阵 AtransactionmaybegrantedalockonanitemiftherequestedlockiscompatiblewithlocksalreadyheldontheitembyothertransactionsAnynumberoftransactionscanholdsharedlocksonanitem butifanytransactionholdsanexclusiveontheitemnoothertransactionmayholdanylockontheitem Ifalockcannotbegranted therequestingtransactionismadetowaittillallincompatiblelocksheldbyothertransactionshavebeenreleased Thelockisthengranted Lock BasedProtocols Cont Exampleofatransactionperforminglocking T1 lock X B T2 lock S A read B read A B B 50unlock A write B lock S B unlock B read B lock X A unlock B read A display A B A A 50write A unlock B Lock BasedProtocols Cont T1T2concurrency controlmanagerlock X B grant X B T1 read B B B 50write B unlock B lock S A grant S A T2 read A unlock A lock S B grant S B T2 read B unlock B display A B lock X A grant X A T1 read A A A 50write A unlock B PitfallsofLock BasedProtocols ConsiderthepartialscheduleSuchasituationiscalledadeadlock 死锁 TohandleadeadlockoneofT3orT4mustberolledbackanditslocksreleased PitfallsofLock BasedProtocols Cont Thepotentialfordeadlockexistsinmostlockingprotocols Deadlocksareanecessaryevil Starvation 饿死 isalsopossibleifconcurrencycontrolmanagerisbadlydesigned Forexample T5T6T7T8lock S Q Lock X Q lock S Q unlock Q lock S Q unlock Q unlock Q TheTwo PhaseLockingProtocol 两段锁协议 Thisisaprotocolwhichensuresconflict serializableschedules Phase1 GrowingPhase 增长阶段 transactionmayobtainlockstransactionmaynotreleaselocksPhase2 ShrinkingPhase 缩减阶段 transactionmayreleaselockstransactionmaynotobtainlocksTheprotocolassuresserializability Itcanbeprovedthatthetransactionscanbeserializedintheorderoftheirlockpoints封锁点 i e thepointwhereatransactionacquireditsfinallock TheTwo PhaseLockingProtocol Cont Two phaselockingdoesnotensurefreedomfromdeadlocksCascadingroll backispossibleundertwo phaselocking Toavoidthis followamodifiedprotocolcalledstricttwo phaselocking 严格两段锁 Hereatransactionmustholdallitsexclusivelockstillitcommits aborts Rigoroustwo phaselocking 强两段锁 isevenstricter herealllocksareheldtillcommit abort Inthisprotocoltransactionscanbeserializedintheorderinwhichtheycommit TheTwo PhaseLockingProtocol Cont LockConversions 锁的转换 Two phaselockingwithlockconversions FirstPhase canacquirealock Sonitemcanacquirealock Xonitemcanconvertalock Stoalock X upgrade SecondPhase canreleasealock Scanreleasealock Xcanconvertalock Xtoalock S downgrade Thisprotocolassuresserializability Butstillreliesontheprogrammertoinsertthevariouslockinginstructions LockConversions 锁的转换 Graph BasedProtocols 基于图的协议 Graph basedprotocolsareanalternativetotwo phaselockingImposeapartialordering onthesetD d1 d2 dh ofalldataitems Ifdi djthenanytransactionaccessingbothdianddjmustaccessdibeforeaccessingdj ImpliesthatthesetDmaynowbeviewedasadirectedacyclicgraph calledadatabasegraph Thetree protocolisasimplekindofgraphprotocol TreeProtocol 树形协议 ThefirstlockbyTimaybeonanydataitem Subsequently adataQcanbelockedbyTionlyiftheparentofQiscurrentlylockedbyTi Dataitemsmaybeunlockedatanytime AdataitemthathasbeenlockedandunlockedbyTicannotsubsequentlyberelockedbyTi 加锁指令只有lock X 事务T的首次加锁可以对任何数据项进行 此后 事务T对数据项Q加锁的前提是事务T持有Q的双亲数据项上的锁 对数据项解锁可以随时进行 数据项被事务T加锁并解锁之后 就不能再对该数据项加锁 TreeProtocol TreeProtocol Cont Unlockingmayoccurearlierinthetree lockingprotocolthaninthetwo phaselockingprotocol shorterwaitingtimes andincreaseinconcurrencyprotocolisdeadlock free norollbacksarerequiredHowever inthetree lockingprotocol atransactionmayhavetolockdataitemsthatitdoesnotaccess increasedlockingoverhead andadditionalwaitingtimepotentialdecreaseinconcurrency Timestamp BasedProtocols 基于时间戳的协议 Eachtransactionisissuedatimestampwhenitentersthesystem IfanoldtransactionTihastime stampTS Ti anewtransactionTjisassignedtime stampTS Tj suchthatTS Ti TS Tj Theprotocolmanagesconcurrentexecutionsuchthatthetime stampsdeterminetheserializabilityorder Inordertoassuresuchbehavior theprotocolmaintainsforeachdataQtwotimestampvalues W timestamp Q isthelargesttime stampofanytransactionthatexecutedwrite Q successfully R timestamp Q isthelargesttime stampofanytransactionthatexecutedread Q successfully Timestamp BasedProtocols Cont Thetimestamporderingprotocolensuresthatanyconflictingreadandwriteoperationsareexecutedintimestamporder SupposeatransactionTiissuesaread Q 1 IfTS Ti W timestamp Q thenTineedstoreadavalueofQthatwasalreadyoverwritten Hence thereadoperationisrejected andTiisrolledback 2 IfTS Ti W timestamp Q thenthereadoperationisexecuted andR timestamp Q issettothemaximumofR timestamp Q andTS Ti Timestamp BasedProtocols Cont SupposethattransactionTiissueswrite Q IfTS Ti R timestamp Q thenthevalueofQthatTiisproducingwasneededpreviously andthesystemassumedthatthatvaluewouldneverbeproduced Hence thewriteoperationisrejected andTiisrolledback IfTS Ti W timestamp Q thenTiisattemptingtowriteanobsoletevalueofQ Hence thiswriteoperationisrejected andTiisrolledback Otherwise thewriteoperationisexecuted andW timestamp Q issettoTS Ti ExampleUseoftheProtocol ExampleUseoftheProtocol Apartialscheduleforseveraldataitemsfortransactionswithtimestamps1 2 3 4 5 T1 T2 T3 T4 T5 read Y read X read Y write Y write Z read Z read X read X write Z write Y write Z Thomas WriteRule 托马斯写规则 WhenTiattemptstowritedataitemQ ifTS Ti W timestamp Q thenTiisattemptingtowriteanobsoletevalueof Q Hence ratherthanrollingbackTiasthetimestamporderingprotocolwouldhavedone this write operationcanbeignored Otherwisethisprotocolisthesameasthetimestamporderingprotocol Thomas WriteRuleallowsgreaterpotentialconcurrency Validation BasedProtocol 基于有效性检查的协议 ExecutionoftransactionTiisdoneinthreephases 1 Readphase TransactionTiwritesonlytotemporarylocalvariables2 Validationphase TransactionTiperformsa validationtest todetermineiflocalvariablescanbewrittenwithoutviolatingserializability 3 Writephase IfTiisvalidated theupdatesareappliedtothedatabase otherwise Tiisrolledback Alsocalledasoptimisticconcurrencycontrolsincetransactionexecutesfullyinthehopethatallwillgowellduringvalidation Validation BasedProtocol Cont EachtransactionTihas3timestampsStart Ti thetimewhenTistarteditsexecutionValidation Ti thetimewhenTientereditsvalidationphaseFinish Ti thetimewhenTifinisheditswritephaseSerializabilityorderisdeterminedbytimestampgivenatvalidationtime toincreaseconcurrency ThusTS Ti isgiventhevalueofValidation Ti ScheduleProducedbyValidation Exampleofscheduleproducedusingvalidation T14 T15 read B read B B B 50read A A A 50 read A validate display A B validate write B write A MultipleGranularity 多粒度 Allowdataitemstobeofvarioussizesanddefineahierarchyofdatagranularities wherethesmallgranularitiesarenestedwithinlargeronesCanberepresentedgraphicallyasatree butdon tconfusewithtree lockingprotocol Whenatransactionlocksanodeinthetreeexplicitly itimplicitlylocksallthenode sdescendentsinthesamemode Granularityoflocking levelintreewherelockingisdone finegranularity lowerintree highconcurrency highlockingoverheadcoarsegranularity higherintree lowlockingoverhead lowconcurrency ExampleofGranularityHierarchy Thehighestlevelintheexamplehierarchyistheentiredatabase Thelevelsbelowareoftypearea fileandrecordinthatorder MultiversionSchemes 多版本机制 Multiversionschemeskeepoldversionsofdataitemtoincreaseconcurrency MultiversionTimestampOrderingMultiversionTwo PhaseLockingEachsuccessfulwriteresultsinthecreationofanewversionofthedataitemwritten Usetimestampstolabelversions Whenaread Q operationisissued selectanappropriateversionofQbasedonthetimestampofthetransaction andreturnthevalueoftheselectedversion readsneverhavetowaitasanappropriateversionisreturnedimmediately DeadlockHandling 死锁处理 Considerthefollowingtwotransactions T1 write X T2 write Y write Y write X Schedulewithdeadlock T1 T2 lock XonXwrite X lock XonYwrite X waitforlock XonX waitforlock XonY DeadlockHandling Systemisdeadlockedifthereisasetoftransactionssuchthateverytransactioninthesetiswaitingforanothertransactionintheset Deadlockprevention 死锁预防 protocolsensurethatthesystemwillneverenterintoadeadlockstate MoreDeadlockPreventionStrategies Followingschemesusetransactiontimestampsforthesakeofdeadlockpreventionalone wait die 等待 死亡 scheme non preemptiveoldertransactionmaywaitforyoungeronetoreleasedataitem Youngertransactionsneverwaitforolderones theyarerolledbackinstead atransactionmaydieseveraltimesbeforeacquiringneededdataitemwound wait 受伤 死亡 scheme preemptiveoldertransactionwounds forcesrollback ofyoungertransactioninsteadofwaitingforit Youngertransactionsmaywaitforolderones maybefewerrollbacksthanwait diescheme Deadlockprevention Cont Bothinwait dieandinwound waitschemes arolledbacktransactionsisrestartedwithitsoriginaltimestamp Oldertransactionsthushaveprecedenceovernewerones andstarvationishenceavoided Timeout BasedSchemes atransactionwaitsforalockonlyforaspecifiedamountoftime Afterthat thewaittimesoutandthetransactionisrolledback thusdeadlocksarenotpossiblesimpletoimplement butstarvationispossible Alsodifficulttodeterminegoodvalueofthetimeoutinterval DeadlockDetection Deadlockscanbedescribedasawait forgraph whichconsistsofapairG V E Visasetofvertices allthetransactionsinthesystem Eisasetofedges eachelementisanorderedpairTi Tj IfTi TjisinE thenthereisadirectededgefromTitoTj implyingthatTiiswaitingforTjtoreleaseadataitem WhenTirequestsadataitemcurrentlybeingheldbyTj thentheedgeTiTjisinsertedinthewait forgraph ThisedgeisremovedonlywhenTjisnolongerholdingadataitemneededbyTi Thesystemisinadeadlockstateifandonlyifthewait forgraphhasacycle Mustinvokeadeadlock detectionalgorithmperiodicallytolookforcycles DeadlockDetection Cont Wait forgraphwithoutacycle Wait forgraphwithacycle DeadlockRecovery Whendeadlockisdetected Sometransactionwillhavetorolledback madeavictim tobreakdeadlock Selectthattransactionasvictimthatwillincurminimumcost Rollback determinehowfartorollbacktransactionTotalrollback Abortthetransactionandthenrestartit Moreeffectivetorollbacktransactiononlyasfarasnecessarytobreakdeadlock Starvationhappensifsametransactionisalwayschosenasvictim Includethenumberofrollbacksinthecostfactortoavoidstarvation InsertandDeleteOperations Iftwo phaselockingisused Adeleteoperationmaybeperformedonlyifthetransactiondeletingthetuplehasanexclusivelockonthetupletobedeleted AtransactionthatinsertsanewtupleintothedatabaseisgivenanX modelockonthetuple InsertandDeleteOperations Cont Thetransactionscanningtherelationisreadinginformationthatindicateswhattuplestherelationcontains whileatransactioninsertingatupleupdatesthesameinformation Theinformationshouldbelocked Onesolution Associateadataitemwiththerelation torepresenttheinformationaboutwhattuplestherelationcontains Transactionsscanningtherelationacquireasharedlockinthedataitem Transactionsinsertingordeletingatupleacquireanexclusivelockonthedataitem Note locksonthedataitemdonotconflictwithlocksonindividualtuples Aboveprotocolprovidesverylowconcurrencyforinsertions deletions Indexlockingprotocolsprovidehigherconcurrencywhilepreventingthephantomphenomenon byrequiringlocksoncertainindexbuckets IndexLockingProtocol Everyrelationmusthaveatleastoneindex Accesstoarelationmustbemadeonlythroughoneoftheindicesontherelation AtransactionTithatperformsalookupmustlockalltheindexbucketsthatitaccesses inS mode AtransactionTimaynotinsertatupletiintoarelationrwithoutupdatingallindicestor Timustperformalookuponeveryindextofindallindexbucketsthatcouldhavepossiblycontainedapointertotupleti haditexistedalready andobtainlocksinX modeonalltheseindexbuckets TimustalsoobtainlocksinX modeonallindexbucketsthatitmodifies Therulesofthetwo phaselockingprotocolmustbeobserved WeakLevelsofConsistency Degree twoconsistency differsfromtwo phaselockinginthatS locksmaybereleasedatanytime andlocksmaybeacquiredatanytimeX locksmustbeheldtillendoftransactionSerializabilityisnotguaranteed programmermustensurethatnoerroneousdatabasestatewilloccur Cursorstability Forreads eachtupleislocked read andlockisimmediatelyreleasedX locksareheldtillendoftransactionSpecialcaseofdegree twoconsistency WeakLevelsofConsistencyinSQL SQLallowsnon serializableexecutionsSerializable isthedefaultRepeatableread allowsonlycommittedrecordstoberead andrepeatingareadshouldreturnthesamevalue soreadlocksshouldberetained However thephantomphenomenonneednotbepreventedT1mayseesomerecordsinsertedbyT2 butmaynotseeothersinsertedbyT2Readcommitted sameasdegreetwoconsistency butmostsystemsimplementitascursor stabilityReaduncommitted allowsevenuncommitteddatatoberead ConcurrencyinIndexStructures Indicesareunlikeother