搜索
!#%$’&( *),+-!/., 01)/+2!/34+56 *78 79),+-!/3: 7;=?A@’BDCDEF@HG I8JKALNMPORQ=SJUT VXWYWZW[TWZ\]_^ ‘:^[aD^cbedgfZhib ‘jdHkbKl9^caf6m6nodHprq sYkn1m#‘jdHputwvxmyqz^ ‘4{|sY}^ }(v~ud bedz^ prq’ SdH} ‘4prd }xv({ ^ } }ib ‘4{ ‘:m ‘jd s f#qH{|dH}yq d S^ }i P^ |s p dg X X y z y x }xv({ ^ % 1 6 4 1 y ( S y i ¢¡£ ⁄1⁄6 1¡¥ R y #ƒ? Z § ⁄cƒ¤“'“« ‹fi› fl– ‡† ·* •¶ ‹,‚fi›„« ”“»fi… ‰¿«` ,…`«:´| ,ˆ ˜– ,¯‡‰¿ ˘«`« ”„‰¿ ˘¯,˙F¨ ,ˆ˘‰¿´‡ ¨ /˚2›¸‰ ›¸‚fi›„«: ‡†˛˝ˇ« … —˘ , ‡ ¿ ‡¯‡ •˙fi * •¶ ,´ ‡ • ,˙•¨ /ˆfi‰¿´,fl 'e«`‹fi› fl |† ·* ‡¶ ‹˘‚fi›¸«`” »fi…`‰Æ« ,… « ´‡ ,ˆ ˜– ˘¯•‰Æ ˘« «`”¸‰Æ ,¯,˙ ¨ ,ˆfi‰ ´| ¨ ,˚-›„‰Æ›„‚˘›„« ‡†ª˝ˇ« … —˘ , ‡ ¿ ‡¯‡ • fi * •¶ ,´ •˙ c‚˘¶ ,´‡‰˘ • • ‡ F ˘˙ ¨ ,ˆ˘‰¿´,flAddingPEPtoReal-TimeDistributedCommitProcessingJayantR.Haritsa KrithiRamamritham DatabaseSystemsLab,SERCDept.ofCSEIndianInstituteofScienceIndianInstituteofTechnologyBangalore560012,INDIAMumbai400076,INDIAharitsa@dsl.serc.iisc.ernet.inkrithi@cse.iitb.ernet.inSeptember4,2000AbstractOne-phasecommitprotocolssubstantiallyreducetheoverheadsoftransactioncommitprocessing,makingthemattractiveforincorporationindistributedreal-timedatabases.Amajorobstacle,however,isthatthesepro-tocolssignificantlyincreasetheoccurrenceofpriorityinversions.Thisarisesfromthecohortsofeachdistributedtransactionbeinginapreparedstateforextendedperiodsoftime,duringwhichtheirdatalockscannotbepre-empted.Wepresenthereanewone-phasereal-timecommitprotocol,calledPEP,thataddressestheabove-mentionedproblembyapplyingthetechniqueofcontrolledborrowingofprepareddata,whichwehadpreviouslyproposedandsuccessfullyutilizedformulti-phasecommitprotocols.Simulation-basedevaluationofPEPforreal-timeap-plicationswithfirmdeadlinesdemonstratesthat,foravarietyofenvironments,itsubstantiallyreducesthenumberofkilledtransactionsascomparedtoitsmulti-phasecounterparts.Infact,PEPoftenprovidesbetterperformancethanevenanequivalentcentralizedsystem.1IntroductionManytime-criticalapplications,includingemerginge-commerceande-informationservicesaswellasintelligenttelecomsystems,accessdatathatislocatedonmultiplesites.Tohelpachievetheirreal-timeobjectives,theseap-plicationsrequireefficientsupportforconsistentlyandatomicallyperformingupdatesacrosstheirdatarepositories[16].Distributeddata-basedsystemstypicallyimplementatransactioncommitprotocolsuchastheclassicalTwoPhaseCommit(2PC)[4]toensuretheatomicityofmulti-siteupdates.Commitprotocolsrequireexchangeofmulti-plemessages,inmultiplephases,betweentheparticipatingsiteswhereadistributedtransactionexecutes.Inaddition,severallogrecordsaregenerated,someofwhichhavetobe“forced”,thatis,flushedtodiskimmediately.Duetothesecosts,commitprocessingcanresultinasignificantincreaseintransactionexecutiontimes[11].Developinghigh-performancetransactioncommitprotocolsisthereforeanimportantprobleminthedesignofdistributedreal-timedatabasesystems(DRTDBS).Wetookafirststeptowardsaddressingtheaboveissueinarecentpaper[6],whereinweinvestigatedthereal-timeperformanceofavarietyofcommitprotocols,includingtheclassicalTwo-PhaseCommit(2PC)[4]andThree-Phase PartofthisworkwasdoneduringasabbaticalatLucentBellLabs,600MountainAvenue,MurrayHill,NJ07974,USA. AlsoaffiliatedwithDept.ofComputerScience,Univ.ofMassachusetts,Amherst,MA01003,USA.1Commit(3PC)[13].Wealsoproposedanew2PC-basedcommitprotocolcalledPROMPTandshowedthat,forfirm-deadline[5]applications,itwasfarmoresuccessfulthantheclassicalprotocolsinminimizingthenumberof“killed”(permanentlyabortedduetomissingtheirdeadlines)transactions.Ourearlierstudiesfocussedexclusivelyontwoandthree-phasecommitprotocols.Intheseprotocols,commitprocessingbeginsonlyafterallthedataprocessingassociatedwithatransactionhasbeencompleted.Wemoveon,inthispaper,toinvestigatingthereal-timecharacteristicsofone-phasecommit(1PC)protocols.Thereisnoexplicit“votingphase”todecideontheoutcome(commitorabort)ofthetransactionintheseprotocolssincecohortsenterthe“preparedstate”atthetimeofsendingtheworkcompletionmessageitself–thatis,thecommitprocessinganddataprocessingactivitiesareeffectivelyoverlapped.ExamplesofsuchprotocolsincludeEarlyPrepare(EP)[14],UnsolicitedVote(UV)[15]andIYV[2].Byeliminatinganentirephaseandtherebyreducingcommitprocessingoverheadsanddurations,1PCprotocolsseempotentiallycapableofcompletingmoretransactionsbeforetheirdead-lines.Inthispaper,weevaluatethereal-timeperformanceoftheEarlyPrepare(EP)1PCprotocol.Afundamentalproblemwithreal-timecommitprocessingisthatcohortsthatareinthepreparedstatecannotbepre-empted,evenifahigherprioritytransactionrequirestheirdata,resultinginpriorityinversion.In1PCprotocols,theinsidiouseffectsofpriorityinversionareexacerbatedbecauseoftheoverlapbetweendataprocessingandcommitprocessing,whichmeansthatacohortcanenterthepreparedstatelongbeforethetransactionhascompleteditsfulldataprocessing.Thereishencethepossibilitythattheadvantagesgainedfromeliminatingaprotocolphasemaybenegatedbytheill-effectsofincreasedpriorityinversion.Toaddresstheaboveproblem,weincorporatethetechniqueofcontrolledbor