数据库系统概念全套配套课件PPT ch15.ppt 88页

'Chapter15:ConcurrencyControl Chapter15:ConcurrencyControlLock-BasedProtocolsTimestamp-BasedProtocolsValidation-BasedProtocolsMultipleGranularityMultiversionSchemesInsertandDeleteOperationsConcurrencyinIndexStructures Lock-BasedProtocolsAlockisamechanismtocontrolconcurrentaccesstoadataitemDataitemscanbelockedintwomodes:1.exclusive(X)mode.Dataitemcanbebothreadaswellaswritten.X-lockisrequestedusinglock-Xinstruction.2.shared(S)mode.Dataitemcanonlyberead.S-lockisrequestedusinglock-Sinstruction.Lockrequestsaremadetoconcurrency-controlmanager.Transactioncanproceedonlyafterrequestisgranted. Lock-BasedProtocols(Cont.)Lock-compatibilitymatrixAtransactionmaybegrantedalockonanitemiftherequestedlockiscompatiblewithlocksalreadyheldontheitembyothertransactions.Anynumberoftransactionscanholdsharedlocksonanitem,butifanytransactionholdsanexclusiveontheitemnoothertransactionmayholdanylockontheitem.Ifalockcannotbegranted,therequestingtransactionismadetowaittillallincompatiblelocksheldbyothertransactionshavebeenreleased.Thelockisthengranted. Lock-BasedProtocols(Cont.)Exampleofatransactionperforminglocking:T2:lock-S(A);read(A);unlock(A);lock-S(B);read(B);unlock(B);display(A+B)Lockingasaboveisnotsufficienttoguaranteeserializability—ifAandBgetupdatedin-betweenthereadofAandB,thedisplayedsumwouldbewrong.Alockingprotocolisasetofrulesfollowedbyalltransactionswhilerequestingandreleasinglocks.Lockingprotocolsrestrictthesetofpossibleschedules. PitfallsofLock-BasedProtocolsConsiderthepartialscheduleNeitherT3norT4canmakeprogress—executinglock-S(B)causesT4towaitforT3toreleaseitslockonB,whileexecutinglock-X(A)causesT3towaitforT4toreleaseitslockonA.Suchasituationiscalledadeadlock.TohandleadeadlockoneofT3orT4mustberolledbackanditslocksreleased. PitfallsofLock-BasedProtocols(Cont.)Thepotentialfordeadlockexistsinmostlockingprotocols.Deadlocksareanecessaryevil.Starvationisalsopossibleifconcurrencycontrolmanagerisbadlydesigned.Forexample:AtransactionmaybewaitingforanX-lockonanitem,whileasequenceofothertransactionsrequestandaregrantedanS-lockonthesameitem.Thesametransactionisrepeatedlyrolledbackduetodeadlocks.Concurrencycontrolmanagercanbedesignedtopreventstarvation. TheTwo-PhaseLockingProtocolThisisaprotocolwhichensuresconflict-serializableschedules.Phase1:GrowingPhasetransactionmayobtainlockstransactionmaynotreleaselocksPhase2:ShrinkingPhasetransactionmayreleaselockstransactionmaynotobtainlocksTheprotocolassuresserializability.Itcanbeprovedthatthetransactionscanbeserializedintheorderoftheirlockpoints(i.e.,thepointwhereatransactionacquireditsfinallock). TheTwo-PhaseLockingProtocol(Cont.)Two-phaselockingdoesnotensurefreedomfromdeadlocks.Cascadingroll-backispossibleundertwo-phaselocking.Toavoidthis,followamodifiedprotocolcalledstricttwo-phaselocking.Hereatransactionmustholdallitsexclusivelockstillitcommits/aborts.Rigoroustwo-phaselockingisevenstricter:herealllocksareheldtillcommit/abort.Inthisprotocoltransactionscanbeserializedintheorderinwhichtheycommit. TheTwo-PhaseLockingProtocol(Cont.)Therecanbeconflictserializableschedulesthatcannotbeobtainediftwo-phaselockingisused.However,intheabsenceofextrainformation(e.g.,orderingofaccesstodata),two-phaselockingisneededforconflictserializabilityinthefollowingsense:GivenatransactionTithatdoesnotfollowtwo-phaselocking,wecanfindatransactionTjthatusestwo-phaselocking,andascheduleforTiandTjthatisnotconflictserializable. LockConversionsTwo-phaselockingwithlockconversions:–FirstPhase:canacquirealock-Sonitemcanacquirealock-Xonitemcanconvertalock-Stoalock-X(upgrade)–SecondPhase:canreleasealock-Scanreleasealock-Xcanconvertalock-Xtoalock-S(downgrade)Thisprotocolassuresserializability.Butstillreliesontheprogrammertoinsertthevariouslockinginstructions. AutomaticAcquisitionofLocksAtransactionTiissuesthestandardread/writeinstruction,withoutexplicitlockingcalls.Theoperationread(D)isprocessedas:ifTihasalockonDthenread(D)elsebeginifnecessarywaituntilnoothertransactionhasalock-XonDgrantTialock-SonD;read(D)end AutomaticAcquisitionofLocks(Cont.)write(D)isprocessedas:ifTihasalock-XonDthenwrite(D)elsebeginifnecessarywaituntilnoothertrans.hasanylockonD,ifTihasalock-SonDthenupgradelockonDtolock-XelsegrantTialock-XonDwrite(D)end;Alllocksarereleasedaftercommitorabort ImplementationofLockingAlockmanagercanbeimplementedasaseparateprocesstowhichtransactionssendlockandunlockrequests.Thelockmanagerrepliestoalockrequestbysendingalockgrantmessages(oramessageaskingthetransactiontorollback,incaseofadeadlock).Therequestingtransactionwaitsuntilitsrequestisanswered.Thelockmanagermaintainsadata-structurecalledalocktabletorecordgrantedlocksandpendingrequests.Thelocktableisusuallyimplementedasanin-memoryhashtableindexedonthenameofthedataitembeinglocked. LockTableBlackrectanglesindicategrantedlocks,whiteonesindicatewaitingrequestsLocktablealsorecordsthetypeoflockgrantedorrequestedNewrequestisaddedtotheendofthequeueofrequestsforthedataitem,andgrantedifitiscompatiblewithallearlierlocksUnlockrequestsresultintherequestbeingdeleted,andlaterrequestsarecheckedtoseeiftheycannowbegrantedIftransactionaborts,allwaitingorgrantedrequestsofthetransactionaredeletedlockmanagermaykeepalistoflocksheldbyeachtransaction,toimplementthisefficiently Graph-BasedProtocolsGraph-basedprotocolsareanalternativetotwo-phaselocking.ImposeapartialorderingonthesetD={d1,d2,...,dh}ofalldataitems.Ifdidjthenanytransactionaccessingbothdianddjmustaccessdibeforeaccessingdj.ImpliesthatthesetDmaynowbeviewedasadirectedacyclicgraph,calledadatabasegraph.Thetree-protocolisasimplekindofgraphprotocol. TreeProtocolOnlyexclusivelocksareallowed.ThefirstlockbyTimaybeonanydataitem.Subsequently,adataQcanbelockedbyTionlyiftheparentofQiscurrentlylockedbyTi.Dataitemsmaybeunlockedatanytime.AdataitemthathasbeenlockedandunlockedbyTicannotsubsequentlyberelockedbyTi. Graph-BasedProtocols(Cont.)Thetreeprotocolensuresconflictserializabilityaswellasfreedomfromdeadlock.Unlockingmayoccurearlierinthetree-lockingprotocolthaninthetwo-phaselockingprotocol.shorterwaitingtimes,andincreaseinconcurrencyprotocolisdeadlock-free,norollbacksarerequiredDrawbacksProtocoldoesnotguaranteerecoverabilityorcascadefreedomNeedtointroducecommitdependenciestoensurerecoverabilityTransactionsmayhavetolockdataitemsthattheydonotaccess.increasedlockingoverhead,andadditionalwaitingtimepotentialdecreaseinconcurrencySchedulesnotpossibleundertwo-phaselockingarepossibleundertreeprotocol,andviceversa. DeadlockHandlingConsiderthefollowingtwotransactions:T1:write(X)T2:write(Y)write(Y)write(X)Schedulewithdeadlock DeadlockHandlingSystemisdeadlockedifthereisasetoftransactionssuchthateverytransactioninthesetiswaitingforanothertransactionintheset.Deadlockpreventionprotocolsensurethatthesystemwillneverenterintoadeadlockstate.Somepreventionstrategies:Requirethateachtransactionlocksallitsdataitemsbeforeitbeginsexecution(predeclaration).Imposepartialorderingofalldataitemsandrequirethatatransactioncanlockdataitemsonlyintheorderspecifiedbythepartialorder(graph-basedprotocol). MoreDeadlockPreventionStrategiesFollowingschemesusetransactiontimestampsforthesakeofdeadlockpreventionalone.wait-diescheme—non-preemptiveoldertransactionmaywaitforyoungeronetoreleasedataitem.Youngertransactionsneverwaitforolderones;theyarerolledbackinstead.atransactionmaydieseveraltimesbeforeacquiringneededdataitemwound-waitscheme—preemptiveoldertransactionwounds(forcesrollback)ofyoungertransactioninsteadofwaitingforit.Youngertransactionsmaywaitforolderones.maybefewerrollbacksthanwait-diescheme Deadlockprevention(Cont.)Bothinwait-dieandinwound-waitschemes,arolledbacktransactionsisrestartedwithitsoriginaltimestamp.Oldertransactionsthushaveprecedenceovernewerones,andstarvationishenceavoided.Timeout-BasedSchemes:atransactionwaitsforalockonlyforaspecifiedamountoftime.Afterthat,thewaittimesoutandthetransactionisrolledback.thusdeadlocksarenotpossiblesimpletoimplement;butstarvationispossible.Alsodifficulttodeterminegoodvalueofthetimeoutinterval. DeadlockDetectionDeadlockscanbedescribedasawait-forgraph,whichconsistsofapairG=(V,E),Visasetofvertices(allthetransactionsinthesystem)Eisasetofedges;eachelementisanorderedpairTiTj.IfTiTjisinE,thenthereisadirectededgefromTitoTj,implyingthatTiiswaitingforTjtoreleaseadataitem.WhenTirequestsadataitemcurrentlybeingheldbyTj,thentheedgeTiTjisinsertedinthewait-forgraph.ThisedgeisremovedonlywhenTjisnolongerholdingadataitemneededbyTi.Thesystemisinadeadlockstateifandonlyifthewait-forgraphhasacycle.Mustinvokeadeadlock-detectionalgorithmperiodicallytolookforcycles. DeadlockDetection(Cont.)Wait-forgraphwithoutacycleWait-forgraphwithacycle DeadlockRecoveryWhendeadlockisdetected:Sometransactionwillhavetorolledback(madeavictim)tobreakdeadlock.Selectthattransactionasvictimthatwillincurminimumcost.Rollback--determinehowfartorollbacktransactionTotalrollback:Abortthetransactionandthenrestartit.Moreeffectivetorollbacktransactiononlyasfarasnecessarytobreakdeadlock.Starvationhappensifsametransactionisalwayschosenasvictim.Includethenumberofrollbacksinthecostfactortoavoidstarvation MultipleGranularityAllowdataitemstobeofvarioussizesanddefineahierarchyofdatagranularities,wherethesmallgranularitiesarenestedwithinlargerones.Canberepresentedgraphicallyasatree(butdon"tconfusewithtree-lockingprotocol)Whenatransactionlocksanodeinthetreeexplicitly,itimplicitlylocksallthenode"sdescendentsinthesamemode.Granularityoflocking(levelintreewherelockingisdone):finegranularity(lowerintree):highconcurrency,highlockingoverheadcoarsegranularity(higherintree):lowlockingoverhead,lowconcurrency ExampleofGranularityHierarchyThelevels,startingfromthecoarsest(top)levelare:databaseareafilerecord IntentionLockModesInadditiontoSandXlockmodes,therearethreeadditionallockmodeswithmultiplegranularity:intention-shared(IS):indicatesexplicitlockingatalowerlevelofthetreebutonlywithsharedlocks.intention-exclusive(IX):indicatesexplicitlockingatalowerlevelwithexclusiveorsharedlockssharedandintention-exclusive(SIX):thesubtreerootedbythatnodeislockedexplicitlyinsharedmodeandexplicitlockingisbeingdoneatalowerlevelwithexclusive-modelocks.IntentionlocksallowahigherlevelnodetobelockedinSorXmodewithouthavingtocheckalldescendentnodes. CompatibilityMatrixwithIntentionLockModesThecompatibilitymatrixforalllockmodesis: MultipleGranularityLockingSchemeTransactionTicanlockanodeQ,usingthefollowingrules:Thelockcompatibilitymatrixmustbeobserved.Therootofthetreemustbelockedfirst,andmaybelockedinanymode.AnodeQcanbelockedbyTiinSorISmodeonlyiftheparentofQiscurrentlylockedbyTiineitherIXorISmode.AnodeQcanbelockedbyTiinX,SIX,orIXmodeonlyiftheparentofQiscurrentlylockedbyTiineitherIXorSIXmode.Ticanlockanodeonlyifithasnotpreviouslyunlockedanynode(thatis,Tiistwo-phase).TicanunlockanodeQonlyifnoneofthechildrenofQarecurrentlylockedbyTi.Observethatlocksareacquiredinroot-to-leaforder,whereastheyarereleasedinleaf-to-rootorder. Timestamp-BasedProtocolsEachtransactionisissuedatimestampwhenitentersthesystem.IfanoldtransactionTihastime-stampTS(Ti),anewtransactionTjisassignedtime-stampTS(Tj)suchthatTS(Ti),yetisnotconflictequivalentorviewequivalenttoit.Determiningsuchequivalencerequiresanalysisofoperationsotherthanreadandwrite. TestforViewSerializabilityTheprecedencegraphtestforconflictserializabilitycannotbeuseddirectlytotestforviewserializability.Extensiontotestforviewserializabilityhascostexponentialinthesizeoftheprecedencegraph.TheproblemofcheckingifascheduleisviewserializablefallsintheclassofNP-completeproblems.Thus,theexistenceofanefficientalgorithmisextremelyunlikely.However,practicalalgorithmsthatjustchecksomesufficientconditionsforviewserializabilitycanstillbeused. Validation-BasedProtocolExecutionoftransactionTiisdoneinthreephases.1.Readandexecutionphase:TransactionTiwritesonlytotemporarylocalvariables2.Validationphase:TransactionTiperformsa``validationtest""todetermineiflocalvariablescanbewrittenwithoutviolatingserializability.3.Writephase:IfTiisvalidated,theupdatesareappliedtothedatabase;otherwise,Tiisrolledback.Thethreephasesofconcurrentlyexecutingtransactionscanbeinterleaved,buteachtransactionmustgothroughthethreephasesinthatorder.Assumeforsimplicitythatthevalidationandwritephaseoccurtogether,atomicallyandseriallyi.e.,onlyonetransactionexecutesvalidation/writeatatime.Alsocalledasoptimisticconcurrencycontrolsincetransactionexecutesfullyinthehopethatallwillgowellduringvalidation Validation-BasedProtocol(Cont.)EachtransactionTihas3timestamps:Start(Ti):thetimewhenTistarteditsexecutionValidation(Ti):thetimewhenTientereditsvalidationphaseFinish(Ti):thetimewhenTifinisheditswritephaseSerializabilityorderisdeterminedbytimestampgivenatvalidationtime,toincreaseconcurrency.ThusTS(Ti)isgiventhevalueofValidation(Ti).Thisprotocolisusefulandgivesgreaterdegreeofconcurrencyifprobabilityofconflictsislow.becausetheserializabilityorderisnotpre-decided,andrelativelyfewtransactionswillhavetoberolledback. ValidationTestforTransactionTjIfforallTiwithTS(Ti).EachversionQkcontainsthreedatafields:Content--thevalueofversionQk.W-timestamp(Qk)--timestampofthetransactionthatcreated(wrote)versionQkR-timestamp(Qk)--largesttimestampofatransactionthatsuccessfullyreadversionQkwhenatransactionTicreatesanewversionQkofQ,Qk"sW-timestampandR-timestampareinitializedtoTS(Ti).R-timestampofQkisupdatedwheneveratransactionTjreadsQk,andTS(Tj)>R-timestamp(Qk). MultiversionTimestampOrdering(Cont)SupposethattransactionTiissuesaread(Q)orwrite(Q)operation.LetQkdenotetheversionofQwhosewritetimestampisthelargestwritetimestamplessthanorequaltoTS(Ti).IftransactionTiissuesaread(Q),thenthevaluereturnedisthecontentofversionQk.IftransactionTiissuesawrite(Q)ifTS(Ti)9,thanQ5willneverberequiredagain SnapshotIsolationMotivation:DecisionsupportqueriesthatreadlargeamountsofdatahaveconcurrencyconflictswithOLTPtransactionsthatupdateafewrowsPoorperformanceresultsSolution1:Givelogical“snapshot”ofdatabasestatetoreadonlytransactions,read-writetransactionsusenormallockingMultiversion2-phaselockingWorkswell,buthowdoessystemknowatransactionisreadonly?Solution2:Givesnapshotofdatabasestatetoeverytransaction,updatesaloneuse2-phaselockingtoguardagainstconcurrentupdatesProblem:varietyofanomaliessuchaslostupdatecanresultPartialsolution:snapshotisolationlevel(nextslide)ProposedbyBerensonetal,SIGMOD1995VariantsimplementedinmanydatabasesystemsE.g.,Oracle,PostgreSQL,SQLServer2005 SnapshotIsolationAtransactionT1executingwithSnapshotIsolationtakessnapshotofcommitteddataatstartalwaysreads/modifiesdatainitsownsnapshotupdatesofconcurrenttransactionsarenotvisibletoT1writesofT1completewhenitcommitsFirst-committer-winsrule:CommitsonlyifnootherconcurrenttransactionhasalreadywrittendatathatT1intendstowrite.T1T2T3W(Y:=1)CommitStartR(X)0R(Y)1W(X:=2)W(Z:=3)CommitR(Z)0R(Y)1W(X:=3)Commit-ReqAbortConcurrentupdatesnotvisibleOwnupdatesarevisibleNotfirst-committerofXSerializationerror,T2isrolledback BenefitsofSIReadingisneverblockedandalsodoesn’tblockothertxnsactivitiesPerformancesimilartoReadCommittedAvoidstheusualanomaliesNodirtyreadNolostupdateNonon-repeatablereadPredicatebasedselectsarerepeatable(nophantoms)ProblemswithSISIdoesnotalwaysgiveserializableexecutionsSerializable:amongtwoconcurrenttxns,oneseestheeffectsoftheotherInSI:neitherseestheeffectsoftheotherResult:Integrityconstraintscanbeviolated SnapshotIsolationE.g.,ofproblemwithSIT1:x:=yT2:y:=xInitiallyx=3andy=17Serialexecution:x=??,y=??ifbothtransactionsstartatthesametime,withsnapshotisolation:x=??,y=??CalledskewwriteSkewalsooccurswithinsertsE.g.,:FindmaxordernumberamongallordersCreateaneworderwithordernumber=previousmax+1 SnapshotIsolationAnomaliesSIbreaksserializabilitywhentxnsmodifydifferentitems,eachbasedonapreviousstateoftheitemtheothermodifiedNotverycommoninpracticeE.g.,theTPC-CbenchmarkrunscorrectlyunderSIwhentxnsconflictduetomodifyingdifferentdata,thereisusuallyalsoashareditemtheybothmodifytoo(likeatotalquantity)soSIwillabortoneofthemButdoesoccurApplicationdevelopersshouldbecarefulaboutwriteskewSIcanalsocausearead-onlytransactionanomaly,whereread-onlytransactionmayseeaninconsistentstateevenifupdatersareserializableWeomitdetails SIInOracleandPostgreSQLWarning:SIusedwhenisolationlevelissettoserializable,byOracleandPostgreSQLPostgreSQL’simplementationofSIdescribedinSection26.4.1.3Oracleimplements“firstupdaterwins”rule(variantof“firstcommitterwins”)concurrentwritercheckisdoneattimeofwrite,notatcommittimeAllowstransactionstoberolledbackearlierNeithersupportstrueserializableexecutionCansidestepforspecificqueriesbyusingselect..forupdateinOracleandPostgreSQLLocksthedatawhichisread,preventingconcurrentupdatesE.g.,selectmax(orderno)fromordersforupdatereadvalueintolocalvariablemaxorderinsertintoorders(maxorder+1,…) InsertandDeleteOperationsIftwo-phaselockingisused:Adeleteoperationmaybeperformedonlyifthetransactiondeletingthetuplehasanexclusivelockonthetupletobedeleted.AtransactionthatinsertsanewtupleintothedatabaseisgivenanX-modelockonthetupleInsertionsanddeletionscanleadtothephantomphenomenon.Atransactionthatscansarelation(e.g.,findsumofbalancesofallaccountsinPerryridge)andatransactionthatinsertsatupleintherelation(e.g.,insertanewaccountatPerryridge)(conceptually)conflictinspiteofnotaccessinganytupleincommon.Ifonlytuplelocksareused,non-serializableschedulescanresultE.g.,thescantransactiondoesnotseethenewaccount,butreadssomeothertuplewrittenbytheupdatetransaction InsertandDeleteOperations(Cont.)Thetransactionscanningtherelationisreadinginformationthatindicateswhattuplestherelationcontains,whileatransactioninsertingatupleupdatesthesameinformation.Theinformationshouldbelocked.Onesolution:Associateadataitemwiththerelation,torepresenttheinformationaboutwhattuplestherelationcontains.Transactionsscanningtherelationacquireasharedlockinthedataitem.Transactionsinsertingordeletingatupleacquireanexclusivelockonthedataitem.(Note:locksonthedataitemdonotconflictwithlocksonindividualtuples.)Aboveprotocolprovidesverylowconcurrencyforinsertions/deletions.Indexlockingprotocolsprovidehigherconcurrencywhilepreventingthephantomphenomenon,byrequiringlocksoncertainindexbuckets. WeakLevelsofConsistencyDegree-twoconsistency:differsfromtwo-phaselockinginthatS-locksmaybereleasedatanytime,andlocksmaybeacquiredatanytimeX-locksmustbeheldtillendoftransactionSerializabilityisnotguaranteed,programmermustensurethatnoerroneousdatabasestatewilloccur]Cursorstability:Forreads,eachtupleislocked,read,andlockisimmediatelyreleasedX-locksareheldtillendoftransactionSpecialcaseofdegree-twoconsistency WeakLevelsofConsistencyinSQLSQLallowsnon-serializableexecutionsSerializable:isthedefaultRepeatableread:allowsonlycommittedrecordstoberead,andrepeatingareadshouldreturnthesamevalue(soreadlocksshouldberetained)However,thephantomphenomenonneednotbepreventedT1mayseesomerecordsinsertedbyT2,butmaynotseeothersinsertedbyT2Readcommitted:sameasdegreetwoconsistency,butmostsystemsimplementitascursor-stabilityReaduncommitted:allowsevenuncommitteddatatobereadInmanydatabasesystems,readcommittedisthedefaultconsistencylevelhastobeexplicitlychangedtoserializablewhenrequiredsetisolationlevelserializable IndexLockingProtocolIndexlockingprotocol:Everyrelationmusthaveatleastoneindex.AtransactioncanaccesstuplesonlyafterfindingthemthroughoneormoreindicesontherelationAtransactionTithatperformsalookupmustlockalltheindexleafnodesthatitaccesses,inS-modeEveniftheleafnodedoesnotcontainanytuplesatisfyingtheindexlookup(e.g.,forarangequery,notupleinaleafisintherange)AtransactionTithatinserts,updatesordeletesatupletiinarelationrmustupdateallindicestormustobtainexclusivelocksonallindexleafnodesaffectedbytheinsert/update/deleteTherulesofthetwo-phaselockingprotocolmustbeobservedGuaranteesthatphantomphenomenonwon’toccur ConcurrencyinIndexStructuresIndicesareunlikeotherdatabaseitemsinthattheironlyjobistohelpinaccessingdata.Index-structuresaretypicallyaccessedveryoften,muchmorethanotherdatabaseitems.Treatingindex-structureslikeotherdatabaseitems,e.g.,by2-phaselockingofindexnodescanleadtolowconcurrency.Thereareseveralindexconcurrencyprotocolswherelocksoninternalnodesarereleasedearly,andnotinatwo-phasefashion.Itisacceptabletohavenonserializableconcurrentaccesstoanindexaslongastheaccuracyoftheindexismaintained.Inparticular,theexactvaluesreadinaninternalnodeofaB+-treeareirrelevantsolongaswelandupinthecorrectleafnode. ConcurrencyinIndexStructures(Cont.)Exampleofindexconcurrencyprotocol:Usecrabbinginsteadoftwo-phaselockingonthenodesoftheB+-tree,asfollows.Duringsearch/insertion/deletion:Firstlocktherootnodeinsharedmode.Afterlockingallrequiredchildrenofanodeinsharedmode,releasethelockonthenode.Duringinsertion/deletion,upgradeleafnodelockstoexclusivemode.Whensplittingorcoalescingrequireschangestoaparent,locktheparentinexclusivemode.AboveprotocolcancauseexcessivedeadlocksSearchescomingdownthetreedeadlockwithupdatesgoingupthetreeCanabortandrestartsearch,withoutaffectingtransactionBetterprotocolsareavailable;seeSection16.9foronesuchprotocol,theB-linktreeprotocolIntuition:releaselockonparentbeforeacquiringlockonchildAnddealwithchangesthatmayhavehappenedbetweenlockreleaseandacquire Next-KeyLockingIndex-lockingprotocoltopreventphantomsrequiredlockingentireleafCanresultinpoorconcurrencyiftherearemanyinsertsAlternative:foranindexlookupLockallvaluesthatsatisfyindexlookup(matchlookupvalue,orfallinlookuprange)AlsolocknextkeyvalueinindexLockmode:Sforlookups,Xforinsert/delete/updateEnsuresthatrangequerieswillconflictwithinserts/deletes/updatesRegardlessofwhichhappensfirst,aslongasbothareconcurrent EndofChapterThankstoAlanFeketeandSudhirJorwekarforSnapshotIsolationexamples SnapshotReadConcurrentupdatesinvisibletosnapshotread SnapshotWrite:FirstCommitterWinsVariant:“First-updater-wins”Checkforconcurrentupdateswhenwriteoccurs(Oracleusesthisplussomeextrafeatures)Differsonlyinwhenabortoccurs,otherwiseequivalent Figure15.01 Figure15.04 Figure15.07 Figure15.08 Figure15.09 Figure15.10 Figure15.11 Figure15.12 Figure15.13 Figure15.14 Figure15.15 Figure15.16 Figure15.17 Figure15.18 Figure15.19 Figure15.20 Figure15.21 Figure15.22 Figure15.23 Figurein-15.1'