Chapter 1 REAL-TIME COMMIT PROCESSING

Chapter1REAL-TIMECOMMITPROCESSINGJayantR.HaritsaDatabaseSystemsLab,SuperomputerEduationandResearhCentreIndianInstituteofSiene,Bangalore560012,INDIA.haritsadsl.ser.iis.ernet.inKrithiRamamrithamDept.ofComputerSieneandEngineering,IndianInstituteofTehnology,Mumbai400076,INDIA.krithise.iitb.ernet.inRameshGuptaGoldenomTehnologies,In.392AomaWay,Fremont,CA94539,USA.rameshgoldenom.om1.INTRODUCTIONManyreal-timedatabaseappliationsareinherentlydistributedinna-ture[24,28℄.Theseinludetheintelligentnetworkserviesdatabasedesribedin[5℄andthemobileteleommuniationsystemdisussedin[29℄.Morereentappliationsinludethemultitudeofdiretory,data-feedandeletroniommereserviesthathavebeomeavailableontheWorldWideWeb.Anessentialrequirementformostdistributedreal-timedatabasesys-tem(DRTDBS)appliationsistransationatomiity{thisissatisedbyimplementingatransationommitprotool.Commitprotoolstypi-allyrequireexhangeofmultiplemessages,inmultiplephases,betweenthepartiipatingsiteswherethedistributedtransationexeuted.Inaddition,severallogreordsaregenerated,someofwhihhavetobe\fored,thatis,ushedtodiskimmediatelyinasynhronousman-ner.Duetothisseriesofsynhronousmessageandloggingosts,om-12mitproessingansigniantlyinreasetheexeutiontimesoftransa-tions[17,7,25℄.Thisisespeiallyproblematiinthereal-timeontextsineithasadiretadverseeetonthesystem’sabilitytomeettrans-ationtimingonstraints.Therefore,thehoieofommitprotoolisanimportantdesigndeisionforDRTDBS.Unfortunately,thereislittlere-searhliteratureonthistopi,makingitdiÆultforDRTDBSdesignerstomakeinformedhoies.Weaddressthislaunaherewithadetailedquantitativeevaluationwhoseresultsrepresenttherstsuhworkinthearea.Ourstudyisarriedoutintheontextofreal-timeappliationswith\rm-deadlines[15℄{forsuhappliations,ompletingatransationafteritshasexpiredisofnoutilityandmayevenbeharmful.Therefore,transationsthatmisstheirdeadlinesareonsideredtobeworthlessandareimmediately\killed{thatis,abortedandpermanentlydisardedfromtheRTDBSwithoutbeingexeutedtoompletion.Aordingly,theperformanemetriisKillPerent,thesteady-stateperentageofkilledtransations.12.PERFORMANCEFRAMEWORKFromaperformaneperspetive,ommitprotoolsanbeomparedwithrespettothefollowingissues:1.EetonNormalProessing:Thisreferstotheextenttowhihtheommitprotoolaetsthenormal(no-failure)dis-tributedtransationproessingperformane.Thatis,howexpen-siveisittoprovideatomiityusingthisprotool?2.ResilienetoFailures:Whenafailureoursinadistributedsystem,ideally,transationproessingintherestofthesystemshouldnotbeaetedduringthereoveryofthefailedomponent.With\blokingommitprotools,failuresanleadtotransationproessinggrindingtoahalt(asexplainedinSetion3.),whereas\non-blokingprotoolspreventsuhdisruptionsbyinurringad-ditionalmessagesandfored-log-writes.3.SpeedofReovery:Thisreferstothetimerequiredforthedatabasetobereoveredtoaonsistentstatewhenthefailedsiteomesbakupafterarash.Thatis,howlongdoesittakebeforetransationproessinganommeneagaininareoveringsite?Ofthethreeissueshighlightedabove,thedesignemphasisofmostom-mitprotoolshasbeenonthersttwo(eetonnormalproessingandresilienetofailures)sinetheydiretlyaetongoingtransation3proessing.Inomparison,thelastissue(speedofreovery)appearslessritialfortworeasons:First,failuredurationsareusuallyordersofmagnitudelargerthanreoverytimes.Seond,failuresareusuallyrareenoughthatwedonotexpettoseeadiereneinaverageper-formaneamongtheprotoolsbeauseofoneommitprotoolhavingafasterreoverytimethantheother.Basedonthisviewpoint,ourfoushereisonthemehanismsrequiredduringnormal(no-failure)opera-tiontoprovideforreoverabilityandresilienetofailures,andnotonthepost-failurereoveryproess.3.TRADITIONALDISTRIBUTEDCOMMITPROTOCOLSWeadopttheommon\subtransationmodel[3℄ofdistributedtrans-ationexeutioninourstudy.Inthismodel,thereisoneproess,alledthemaster,whihisexeutedatthesitewherethetransationissub-mitted,andasetofotherproesses,alledohorts,whihexeuteonbehalfofthetransationatthevarioussitesthatareaessedbythetransation.Cohortsarereatedbythemastersendingastartworkmessagetotheloaltransationmanageratthatsite.Thismessageinludestheworktobedoneatthatsiteandispassedontotheohort.Eahohortsendsaworkdonemessagetothemasterafterithasom-pleteditsassigneddataproessingwork,andthemasterinitiatestheommitprotool(only)afterithasreeivedthismessagefromallitsohorts.Fortheabovetransationexeutionmodel,avarietyofommitpro-toolshavebeendevised,mostofwhiharebasedonthelassialtwo-phaseommit(2PC)protool[10℄.Inthissetion,webrieydesribethe2PCprotoolandafewofitspopularvariants{ompletedesrip-tionsareavailablein[20,7,23℄.Foreaseofexposition,thefollow-ingnotationisusedinthesequel{\smallapsfontformessages,\typewriterfontforlogreords,and\sansseriffontfortransationstates.3.1TWOPHASECOMMITInthe2PCprotool,themasterinitiatestherstphaseoftheommitprotoolbysendingprepare(toommit)messagesinparalleltoallitsohorts.Eahohortthatisreadytoommitrstfore-writesapreparelogreordtoitsloalstablestorageandthensendsayesvotetothemaster.Atthisstage,theohorthasenteredapreparedstatewhereinitannotunilaterallyommitorabortthetransationbuthastowaitforthenaldeisionf