interesttaobaoprotect.exe

Tempo:RobustandSelf-TuningResourceManagementinMulti-tenantParallelDatabasesZilongTanDukeUniversityztan@cs.
duke.
eduShivnathBabuDukeUniversityshivnath@cs.
duke.
eduABSTRACTMulti-tenantdatabasesystemshaveacomponentcalledtheRe-sourceManager,orRMthatisresponsibleforallocatingresourcestotenants.
RMstodaydonotprovidedirectsupportforperfor-manceobjectivessuchas:"AveragejobresponsetimeoftenantAmustbelessthantwominutes",or"Nomorethan5%oftenantB'sjobscanmissthedeadlineof1hour.
"Thus,DBAshavetotinkerwiththeRM'slow-levelcongurationsettingstomeetsuchobjec-tives.
WeproposeaframeworkcalledTempothatbringssimplicity,self-tuning,androbustnesstoexistingRMs.
Tempoprovidesasim-pleinterfaceforDBAstospecifyperformanceobjectivesdeclara-tively,andoptimizestheRMcongurationsettingstomeettheseobjectives.
Tempohasasolidtheoreticalfoundationwhichgiveskeyrobustnessguarantees.
WereportexperimentsdoneonTempousingproductiontracesofdata-processingworkloadsfromcom-paniessuchasFacebookandCloudera.
Theseexperimentsdemon-stratesignicantimprovementsinmeetingdesiredperformanceob-jectivesoverRMcongurationsettingsspeciedbyhumanexperts.
1.
INTRODUCTIONManyenterprisestodayrunmulti-tenantdatabasesystemsonlargeshared-nothingclusters.
ExamplesofsuchsystemsincludeparallelSQLdatabasesystemslikeRedShift[1],Teradata[5],andVertica[6],Hadoop/YARNrunningSQLandMapReducework-loads,SparkrunningonMesos[25]orYARN[46],andmanyoth-ers.
Meetingtheperformancegoalsofbusiness-criticalworkloads(popularlycalledservice-levelobjectives,orSLOs)whileachiev-inghighresourceutilizationinmulti-tenantdatabasesystemshasbecomemoreimportantandchallengingthanever.
Theproblemofhandlingmany(oftenin1000s)smallandinde-pendentdatabasesonamulti-tenantdatabasePlatform-as-a-Service(usuallycalledPaaSorDBaaS)hasreceivedconsiderableattentioninrecentyears[50,37,32,36,15].
Thatisnottheproblemwefo-cusoninthispaper.
Ourfocusisonhandlingfewer,butmuch"big-ger",tenantswhoprocessverylargeamountsofdataonashared-ThisworkwassupportedbygrantsCNS1423128,IIS1423124,CNS1218981,andIIS0964560.
ThisworkislicensedundertheCreativeCommonsAttribution-NonCommercial-NoDerivatives4.
0InternationalLicense.
Toviewacopyofthislicense,visithttp://creativecommons.
org/licenses/by-nc-nd/4.
0/.
Foranyusebeyondthosecoveredbythislicense,obtainpermissionbyemailinginfo@vldb.
org.
ProceedingsoftheVLDBEndowment,Vol.
9,No.
10Copyright2016VLDBEndowment2150-8097/16/06.
nothingclusterthatisusuallyrunwithinanenterprise.
Hadoop,Spark,Teradata,Vertica,etc.
,aretypicallyruninsuchsettings.
Thesemulti-tenantdatabasesystemseachhaveacomponent—commonlyreferredtoastheResourceManager(RM)—thatisre-sponsibleforallocatingresourcestotenants.
MostwidelydeployedRMslikeYARNandMesosfocusonresourceisolationanddonotsupportSLOs.
Instead,theyrelyontheDatabaseAdminis-trator(DBA)to"guesstimate"answerstoquestionssuchas:"Howmuchresourcesareneededtocompletethisjobbeforeitsdead-line"Then,DBAshavetotranslatetheiranswersintolow-levelcongurationsettingsintheRM.
Thisprocessisbrittleandincreas-inglyhardasworkloadsevolve,dataandclustersizeschange,andnewworkloadsareadded.
Thus,techniqueshavebeenproposedintheliteraturetosupportspecicSLOssuchasdeadlines[14,33,18,47],fastjobresponsetimes[11,14,21,39],highresourceuti-lization[2,11,14],scalability[2,43,51],andtransparentfailurerecovery[51].
Inthispaper,wepresentaframeworkcalledTempothatbringsthreepropertiestoexistingRMs:simplicity,self-tuning,andro-bustness.
First,TempoprovidesasimpleinterfaceforDBAstospecifySLOsdeclaratively.
Thus,TempoenablestheRMtobemadeawareofSLOssuchas:"Averagejobresponsetimeoften-antAmustbelessthantwominutes",and"Nomorethan5%oftenantB'sjobscanmissthedeadlineof1hour.
"Second,TempoconstantlymonitorstheSLOcomplianceinthedatabase,andadap-tivelyoptimizestheRMcongurationsettingstomaximizeSLOcompliance.
Third,Tempohasasolidtheoreticalfoundationwhichgivesvecriticalrobustnessguarantees:1)Tempomakeshigh-qualityresourceschedulingdecisionsinpresenceofnoise,e.
g.
,jobfailures,commonlyobservedinproductiondatabasesystems.
2)Tempodeliversprovablyend-to-endtenantperformanceisola-tionwithPareto-optimalSLOs.
Thisisoftenmoredesirablethantraditionalresourceisolation.
3)WhenallSLOscannotbesatised—whichiscommoninbusydatabasesystems—Tempoguaranteesmax-minfairnessoverSLOsatisfactions[34].
4)Tempoadaptstoworkloadpatternsandvariations.
5)Temporeducestheriskofmajorperformanceregressionwhilebeingappliedtoproductiondatabasesystems.
WehaveimplementedTempoasadrop-incomponentintheRMsusedbymulti-tenantdatabasesrunningonHadoopandSpark.
Wereportexperimentsdoneusingproductiontracesofdata-processingworkloadsfromcompaniessuchasFacebookandCloudera.
TheexperimentsshowthatTempocanreducetheaveragejobresponsetimeby50%forbest-effortworkloadsandincreaseresourceuti-lizationby15%,withouthurtingthedeadline-drivenworkloads.
720Table1:TenantcharacteristicsatCompanyABC.
TenantCharacteristicsBII/O-intensiveSQLqueriesDEVMixtureofdifferenttypesofjobsAPPSmall,lightweightjobsSTRHadoopstreamingjobsMVLong-running,CPU-intensiveETLI/O-intensive,periodicbutburstyThispapermakesthefollowingcontributions:WeproposeseveralrobustnesspropertiesofRMs,andinvesti-gatewaystoachieverobustnessprovably.
Weprovideasolidtheoreticalfoundationformulti-objectiveSLOoptimizationunderuncertainty,andpresentanovelsolu-tionalgorithm.
Wedesigntime-warpbasedmechanismstoestimatetheimpactofdifferentRMcongurationsontenants'SLOs.
WeevaluateTempoforvariousreal-lifeusecasesbasedonpro-ductiontraces.
2.
BACKGROUNDTempo'sdesignwasmotivatedbyourobservationsfromseverallargeproductiondatabasesystems.
WhiledesigningTempo,wean-alyzedworkloadtracesfromthreecompanieseachofwhichrunsmulti-tenantdatabasesystemsonlargeclusters.
Twoofthesesys-temsrunon600+nodeswhiletheotherrunsonabout150nodes.
(Whileallthreearewell-knowncompanies,wecannotsharetheirnamesduetolegalrestrictions.
)Wetalkedtobusinessanalysts,applicationdevelopers,teammanagers,andDBAsintheseteamstounderstandtheSLOsthattheyneedtomeetandthechallengestheyfaceinresourcemanagement.
Fromallourinterviews,thefollowingemergedasthetopconcerns:ConcernA:Deadline-basedworkloadsandbest-effortwork-loadshavetobesupportedonthesamedatabasesystem.
ConcernB:Repeatedly-runjobsoftenhaveunpredictablecom-pletiontimes.
ConcernC:Resourceutilizationwaslowerthanexpected.
ConcernD:Resourceallocationdoesnotadaptautomaticallytothepatternsandvariationsintheworkloads.
Toelaborateonthesefourconcerns,wewilluseoneofthethreecompanies—henceforth,referredtoasCompanyABC—whichisareal-lifecompanythatrunsamulti-tenantdatabasesystemona700-nodeHadoopclusterwithover30Petabytesofdata.
2.
1ConcernACompanyABChasthreetypesofuserswhogeneratedatabaseworkloads.
BusinessIntelligence(BI)analystsandDataScientistspredominantlydoexploratoryanalysisonthedata.
Engineersde-velopandmaintainrecurringjobsthatrunonthedatabase.
OnesuchcategoryofjobsisExtract-Transform-Load(ETL)whichbringsnewdataintothesystem.
Eachjobgoesthroughmanyrunsinadevelopmentphaseontheclusterbeforebeingcertiedtorunasaproductionjob.
Thus,thesystemsupportsbothdevelopmentandproductionrunsofjobs.
Distinctworkloadsfromtheseusersformthetenantsinthemulti-tenantsystem.
Table1showsthesixtenantsatCompanyABCandtheirdistinctworkloadcharacteristics.
(Theexperimentalevalua-tionsectiongivesmorene-graineddetailsoftheseworkloads.
)TheBIandETLuserscorresponddirectlytosimilarly-namedtenants.
Amongtheothertenants,MVcorrespondstothecreationofMaterializedViewssuchasjoinedresultsofmultipletablesaswellasstatisticalmodelscreatedfromtheincomingdatabroughtthroughETL.
TheBIusersandDataScientistsusuallywritetheirqueriesandanalysisprogramsonthesematerializedviews.
TheAPPtenantrunsjobsfromaspecichigh-priorityproductionap-plication.
TheDEVandSTRtenantsmostlycomprisequeriesandanalysisprogramsbeingrunaspartofapplicationdevelopmentbyengineersandDataScientists.
AtCompanyABC:JobsfromtheETLandMVtenantshavedeadlinesbecauseanydelayinthesejobswillaffecttheentiredailyoperationsofthecompany.
Wehaveseenmulti-daydelayscausedbydeadlinemissesfortheETLandMVtenantsthathadsignicantbusinessimpact.
About30%ofhigh-priorityjobsinAPPmissdeadlines.
Whilealltenantswantaslowjobresponsetimeaspossibleforcompletionoftheirjobs,BI,DEV,andSTRaretreatedas"best-effort"tenantsinthatthegoalistoprovidetheirjobsaslowresponsetimeaspossiblesubjecttomeetingtherequirementsoftheETL,MV,andAPPtenants.
2.
2ConcernBPredictabilityofcompletiontimeforrecurringjobsisakeyneedinmostcompanies.
Thisdemandstemsfromeaseofresourceplan-ningandschedulingfordependentjobs.
AtCompanyABC:ThecompletionofoneoftherecurringjobsoftheETLtenantvariesbetween5and60minutes.
ThecompletionofoneoftherecurringjobsoftheMVtenantvariesbetween2and6hours.
Whileweobservedthatthisvarianceiscausedpartlybyvariationintheinputsizesofthejobsacrossruns,thesesizesexhibitstrongtemporalpatterns.
Forexample,theinputsizesoftherecurringjobsinETLvaryacrossdayswithinaweek,butremainstableacrossmultipleweeks.
2.
3ConcernCResourcescanbewastedinmulti-tenantsystemsduetoreasonssuchas:(i)taskpreemption;(ii)suboptimalcongurationofre-sourcelimits;and(iii)jobsinpoorly-writtenqueriesbeingkilledbyDBAs.
AtCompanyABC,17.
5%ofmaptasksand27.
7%ofre-ducetaskswerepreemptedforthejobsrunbytheMVtenantoveraweekinterval.
Thiscausedconsiderableamountofwastedre-sources,especiallybecausethereducetasksoftheMVtenanthavelongexecutiontimes.
2.
4ConcernDAresourceallocationwhichmeetstheSLOsperfectlyatonemo-mentmaybesub-optimalatanothermomentduetovariousfactors.
First,inputdatasizesforatenantmayvaryconsiderablyacrossshortertimeintervalswhileshowingdistinctpatternsacrosslongerintervals.
AtCompanyABC,ETLjobsprocessWebactivitylogswhichcomeinmuchsmallerquantitiesonweekends.
Second,theresourcedemandsofdifferenttenantscanbecorrelatedovertime.
Forexample,Figure1showsthememoryconsumptionoftwoten-antsatCompanyABCoverthecourseofaday.
ThehorizontallinesinthegureshowtherespectiveresourcelimitsthathavebeenconguredbytheDBAtoprotectagainstresourcehoardingbyten-ants.
Noticethatwhilethereareperiodswherebothtenantsuseupallavailableresources,thereareotherperiodswheretheconguredresourcelimitpreventsonetenantfromusingtheresourcesunusedbytheother.
721Figure1:Memoryconsumptionoftwotenantsduringaday.
3.
OVERVIEWOFPROBLEMFromourinterviews,twosalientpointsemergedthatsummarizethecruxofwhatTempoattemptstosolve:Workloadsinmulti-tenantparalleldatabaseshaveSLOs.
Cur-rentRMsdonotprovideeasywaystoensurethattheseSLOsaresatised.
CurrentRMsrequiretheDBAtoestimateresourcestomeettheper-tenantSLOs,andthenspecifylow-levelRMcongurationlikeresourceshares,resourcelimits,andpreemptiontimeoutsinordertomeettheseSLOs.
Thisprocessisbrittleandincreas-inglyhardasworkloadsevolve,dataandclustersizeschange,andnewworkloadsareadded.
3.
1Multi-tenantWorkloadsParalleldatabasesdecomposequeriesandanalysisprogramstoDirectedAcyclicGraphs(DAGs)ofjobsthateachconsistofoneormoretasks.
Wewillusethefollowingrepresentationformulti-tenantworkloadsthroughoutthispaper:Task:Ataskisthesmallestunitofworkforthepurposeofresourceallocation.
Ataskhasastarttimewhenthetaskacquiresresourcestostartrunning;andanishtimewhenthetaskcompletes.
Weconsiderworkloadswherethetaskduration,whichistheintervalfromstarttimetonishtime,isgiven.
Job:Ajobconsistsofasetofparalleland/ordependenttasks,e.
g.
,mapandreducetasksinaMapReducejoborthetasksinaSparkstage.
Thejobresponsetimeistheintervalfromthejobsubmissiontimetothenishtimeofthelasttask.
Jobresponsetimesvarybasedonwhenresourcesareallocatedtothetasksofthejob.
Workload:Aworkloadisaxedsequenceofjobsoveraperiodoftimewherethesubmissiontimeofeachjobandthetenantsubmit-tingthejobaregiven.
Throughoutthispaper,weusewtodenoteamulti-tenantworkload.
InTempo,wcanbeobtainedinoneoftwoways.
First,wcanbeanactualjobtracesubmittedtoaparalleldatabasesystem.
Weusethisapproachinourexperiments.
Second,wcanbegeneratedfromastatisticalworkloadmodelaswewilldiscusslater.
3.
2SLOsFromourinterviewswithusersandDBAs,weidentiedvemajorclassesofSLOs.
Ratherthanaimingforanyparticularjob,theseSLOsreecttheperformanceoftheworkloadasawholeoveraperiodoftime.
Thus,Tempodealswiththeseworkload-levelSLOsthataredenedoveragiventimewindow.
Therstclassspeciesthefractionofjobsthatviolatedthedead-line.
Forrecurringjobs,thedeadlineiseitherthestartofthenextrunoranabsolutetimepointlike5:00AM.
Thesecondclassspec-iesthattheaveragejobresponsetimemustbelessthanagiventhreshold.
SuchSLOsareoftenassociatedwithad-hocjobs.
Thethirdclassisaboutensuringthateachtenantgetsafairallocationofresources.
Inparticular,whenthedatabaseisundercontention,theproportionofresourcesallocatedtoeachtenantmustadheretopredeterminedvalues.
ThisSLOclasspreventsindividualten-antsfrommonopolizingtheresourcesintentionallyorotherwise.
Fourth,theresourceutilizationorjobthroughputmustbeaboveathreshold.
ThisSLOclassgenerallyservestheinterestofDBAstomaximizethereturnoninvestment(ROI)inthecluster.
AfthtypeofSLOorderstheotherSLOsintermsofpriority.
ThisspecialSLOmandatesthatSLOswithhigherprioritiesbeconsideredrstwhennotallSLOscanbemetwiththeresourcesavailable.
3.
3GlobalRMCongurationSpaceInthissection,wewilldescribethetypicalsetofper-tenantcon-gurationparameterssupportedbymodernRMs.
Theglobalcon-guration,representedthroughoutthispaperasthevectorxxx,usedbytheRMatanypointisthecollectionoftheseper-tenantcong-urationsacrossalltenants.
xxxcharacterizeshowtheresourceareal-locatedinordertoprocessw.
Aswewilldescribeinlatersections,TempoconstantgoalistomaximizeSLOcomplianceadaptivelyforagivenwbycomputingtheoptimalxxx.
CPU,Memory,andotherresourcesareallocatedtoexecutethetasksinw.
Theresourcesallocatedtoanytenantcanbecapturedinane-grainedmannerbasedonthestarttime,nishtime,andtheresourceallocationvectordforeachofthetasksrunonbehalfofthetenant.
Inthispaper,foreaseofexposition,wewillconsiderauni-dimensionalrepresentationofdasanintegernumberofcontainers(orslots)asdoneinRMslikeMesosandYARN.
Namely,ataskisruninacontainerthatisallocatedonbehalfofatenantwhosubmitsthetask.
Notwotaskscansharethesamecontainer.
TheRMofamulti-tenantdatabasesystemhasaxedtotalnumberofcontainersthatitcanallocateacrossalltenantsatanypointoftime.
Thisallo-cationisgovernedbyasetofper-tenantcongurationparametersfallingintothreecategories,describednext.
ResourceShares:Theresourceshareforatenantspeciestheproportionoftotalresourcesthatthistenantshouldgetwithrespecttoothertenants.
Forexample,supposetherearethreetenantsA,B,andCwithsharesintheratio1:2:3respectively.
Supposethedatabasesystemhas12containersthatitcanallocateatanypointoftime.
Then,ifalltenantshavetaskstorun,thentenantsA,B,andCwillget2,4,and6containersrespectively.
Supposeatenantdoesnothavetaskstoruninitsfullquotaofresources.
Then,theunusedquotaofresourceswillbeallocatedtoothertenantswhohavetaskstorun.
Thisallocationwillbepro-portionaltotheresourcesharesoftheothertenants.
Intheexampleabove,supposetenantChasnotaskstorun,butAandBhavemanytaskstorun.
Then,tenantsAandBwillget4and8containersre-spectively.
ResourceLimits:Foranytenant,minimumandmaximumlimitscanbespeciedfortheresourcesthatthistenantcangetatanypointoftime.
IntheexampleabovewheretenantsA,B,andChavesharesintheratio1:2:3respectively,supposealltenantshavemanytaskstorun,butthemaximumresourcelimitfortenantCissetto3.
Then,tenantsA,B,andCwillget3,6,and3containersrespectively.
Limitsarespeciedtoensuretwothings:(i)notenantcanmonopolizeallresources,and(ii)criticalworkloadsfromatenantcanstartrunningasquicklyaspossible.
ResourcePreemption:Foranytenant,acongurationcanbesettopreempt—afteracertaintimeintervalcalledapreemptiontime-out—tasksfromothertenantsthatusingresourcesthatarerightlyowedtothistenant.
Suchpreemptionwillfreeupresourcesforthistenant.
Therearetwolevelsofpreemptiontimeouts.
Onelevelofpreemptioniswhenthetenant'scurrentresourceallocationis722Figure2:Tempoarchitecture.
belowitsconguredresourceshare.
Theother,andmorecriticallevel,iswhenthetenant'scurrentresourceallocationisbelowitsconguredminimumresourcelimit.
Preemptionisimportantinmulti-tenantsystems.
Withoutpre-emption,alow-prioritytenantwhosubmittedtasksearlierthanahigh-prioritytenantcancausethehigh-prioritytenanttomissdead-lines.
Preemptioncanbeimplementedbysuspendingtasksorbykillingtasksrunninginthecontainer.
Whiletasksuspensionisthepreferredmechanism,itisnotsupportedinmostmulti-tenantsys-temsthatarecommonlyusedtoday.
AsindicatedinSection2.
3,ifthetwolevelsofpreemptiontimeoutsarenotconguredcarefully,thenpreemptionbykillingtaskscancausealotofwastedworkandlowresourceutilization.
3.
4RoleofTempoOurinterviewsrevealedthatDBAsmanuallytunetheper-tenantRMcongurationparametersinordertomeettenantSLOs.
Forex-ample,atCompanyABC,theRMcongurationistunedwhenevertenantscomplainaboutdeadlineorjobresponsetimeSLOsnotbe-ingmet.
ThisprocessisbrittlebecauseitishardfortheDBAstotakeintoaccounttheworkloadpatternsandevolution,constantadditionofnewworkloads,andthemultipleobjectivesandtrade-offsinvolved.
ThegoalofTempoistomakethisprocesseasyandprincipled.
4.
TEMPOAsdiscussedinSection1,Tempoisdesignedtobringthreeprop-ertiestoexistingRMs:simplicity,self-tuning,androbustness.
Aspartofsimplicity,TempointroducestheconceptofQS(Quantita-tiveSLO).
AQSisaquantitativemetricdenedperSLOtomeasurethesatisfactionoftheSLOatanypointoftime.
InSection5,wewillshowhowtheQSconceptsupportsseveraltenantSLOsthatariseinreal-lifeusecases.
Operationally,theQSforanSLOcanbethoughtofintwoways(recallSection3.
3):1.
Asafunctionf(xxx,w),wherexxxandwaredescribedinSection3.
2.
Asafunctionoftheactualtaskresourceallocationschedule(henceforthcalledtaskschedule)thatisproducedwhenwrunsunderxxx.
AswewillshowinSection5,itisconceptuallyeasierforhumanstounderstandandusetheQSconceptwhendenedintermsofthetaskschedule.
Atthesametime,Temponeedsthef(xxx,w)notioninordertocreateamodulararchitecturethatprovidesself-tuningandrobustness.
Figure2showshowthismodulararchitecturedrivestherepeatedexecutionofTempo'scontrolloop.
TheTempocontrolloopconsistsoftheeightstepsdenoted(1)-(8)inFigure2.
TheinputstotheTempocontrollooparetheSLOsdenedforeachtenant(whichcanbespeciedconvenientlyviapredenedtemplatesasdiscussedinSection5).
Step(1)ofthecon-trolloopextractstherecenttaskscheduleforevaluatingQSmetricsfortheinputSLOsunderthecurrentRMcongurationxxx.
ThroughSteps(2)-(8),TemporeplacesthecurrentRMcongurationxxxwithanewonexxx;concludingoneiterationofthecontrolloop.
OncetheQSmetricsfortheinputSLOsunderxxxareobservedatStep(1)ofthenextiteration,theTempocontrolloopwillreverttheRMcongurationxxxbacktoxxxifthecurrentlyobservedQSmetricsdonotdominatethepreviouslyobservedones.
ThismechanismaddsrobustnessinTempobyguardingagainstperformancedegradationduringtheself-tuningapproach.
Steps(2)-(8)areorchestratedbyTempo'sOptimizerwhichap-pliesaself-tuningalgorithmcalledPALD.
PALDisanovelmulti-objectiveoptimizationalgorithmthatwedevelopedforthenoisyenvironmentsseeninproductionmulti-tenantparalleldatabasesys-tems.
AswewillshowinSection6,PALDprovablyconvergestoaRMcongurationthatprovidesaPareto-optimalsettingfortheQSmetricsoftheinputSLOs.
Inaddition,wheneveravailablere-sourcesareinsufcienttofullysatisfyallSLOs,PALDhandlestheSLOtradeoffsgracefullybyminimizingthelargestregretacrossallSLOsatisfactionsasmeasuredbytheQSmetrics.
InSteps(2)-(8),theOptimizerexploresasetofRMcongura-tionsbyproposingtheRMcongurations(3)-(4),gettingthesimu-latedtaskschedule(6)oftheworkloads(5)basedonthejobtraces(2).
ThepredictedQSmetricsundertheseRMcongurationsarepassedbacktotheOptimizer(7)tocomputeaPareto-improvingRMconguration(8).
Toimplementthesesteps,theOptimizerusesthreeothercomponentsasshowninFigure2:WorkloadGen-erator,SchedulePredictor,andWhat-ifModel.
TheWorkloadGeneratorreplayshistoricaljobtracesorsynthe-sizesworkloadswithgivencharacteristics.
TheSchedulePredictorproducesthesimulatedtaskscheduleofthegeneratedworkloadsundergivenRMcongurations.
TheWhat-ifModelestimatestheQSmetricsfortheinputSLOsusingthesimulatedtaskschedule.
Together,thethreecomponentsenabletheOptimizertoexploretheimpactofdifferentRMcongurationsontheinputSLOsandusethePALDalgorithm(describedinSection6)toproducePareto-optimalRMcongurationsfortheseSLOs.
WhileproposingRMcongurationsinStep(3),theOptimizermeticulouslygeneratescongurationsonlywithinagivenmaxi-mumdistancetothecurrentlyusedRMconguration.
Tempousesnormalizedl2-normasthedistancemetric,andallowstheDBAtospecifythemaximumdistancebasedonherrisktolerance.
ThistechniquefurtherreducestheriskofcausingdramaticimpactontherunningworkloadswhenapplyinganewRMconguration;whichisparticularlydesirableinproductionenvironments.
5.
QS:QUANTIFIABLEMETRICSTOMEA-SURESLOSATISFACTIONAkeydesigngoalinTempowastoprovideaquantitativeunder-standingofhowtheworkloadandRMcongurationimpacteachSLO.
WedevelopedtheQSmetricwhichcanbeusedtocom-paretherelativeSLOsatisfactionsunderdifferentworkloadsandRMcongurations.
MinimizingtheQSmetricimprovesthecorre-spondingSLO.
723TheQSmetricforanSLOisdenedasafunctionoftheresult-ingtaskscheduleforaworkloadunderagivenRMconguration.
RecallfromSection3.
3thatataskscheduleconsistsofstarttime,nishtime,andtheresourceallocationdforeachofthetasksrunonbehalfofatenant.
Foreaseofexposition,dcanbeconsideredasanintegernumberofcontainersasdoneinRMslikeMesosandYARN.
5.
1QSMetricsforPopularSLOsWewillnowdescribeQSmetricsforthecommonclassesofSLOsthatwecameacrossinourinterview(recallSection3.
2).
NotethatSLOsandcorrespondingQSmetricscanbedenedatdifferentlevelssuchasatthelevelofarecurringjob,attheleveloftheentireworkloadofatenant,attheleveloftheentirecluster,etc.
Inthissection,wewilldeneQSmetricsatthejoblevel,buttheideasgeneralize.
ConsideracertainintervaloftimeL.
LetJidenotethesetofjobsfromtenantiwhichwassubmittedandcom-pletedduringthisinterval.
LetTibethesetoftasksassociatedwithJi.
Basedonthisnotation,wecandenethefollowingQSmetricsforthecommonSLOs.
Lowaveragejobresponsetime:TheQSmetricforjobresponsetimeSLOtakestheaverageacrossalljobsexecutedbythetenant,asgivenby(1)wheretsjandtfjarethesubmissionandnishtimeofjobj,respectively.
|Ji|representsthecardinalityofthejobsetJi.
QSAJR(Ji)=1|Ji|∑j∈Jitfjtsj.
(1)Deadlines:TheQSmetricfordeadlineSLOcanbedenedasthefractionofjobsofatenantthatmissedtheirdeadline.
Lettdjbethedeadlineofthejobj,thedeadlineQSmetriccanbedenedasQSDL(Ji)=1|Ji|∑j∈JiItfj>γtfjtlj+tdj,(2)whereI(·)istheindicatorfunction,andγisaslack(tolerance)whenidentifyingthedeadlineviolation.
Thatis,ajobjisconsid-eredviolatingthedeadlinetdjonlyifitscompletionislaterthanthedeadlinebyafactorγintermsofthejobdurationtfjtlj.
TheslackmakestheQSmetriclesssensitivetosystemvariability.
Highresourceutilization:Theresourceutilizationcanbecalcu-latedastheintegralofthefractionofoverallresourcesallocatedtothetenantoverthetimeinterval.
Wecanusethedominantre-sourceusagewhenmultipleresourcetypesareconsidered[20,19,44].
Notethatthedominantresourceusageisrepresentedbyaratiobetweenzeroandone.
Whenthereisonlyasingleresourcetype,wenormalizetheresourceusage.
wecandenetheQSmetricforachievinghighresourceutilizationasQSUTIL(Ji)=1L∑j∈Tidjtfttlt,(3)whereLbethelengthoftheinterval,anddjistheamountofre-sourcesallocatedtotaskj.
ThisQSmetriccanalsobeappliedtoevaluatetheimpactofpreemptionbycomparingtheQSvaluescomputedusingalltasksversususingonlytasksthatwerenotpre-empted.
Highjobthroughput:Thejobthroughputisdenedasthenumberofjobssubmittedandcompletedwithintheinterval.
TheQSmetricforachievinghighjobthroughputisthusgivenbyQSTHR(Ji)=|Ji|.
(4)Resourcefairness:Thefairnesscanbedenedbycomparingtherelativeratioofresourceutilizationusedbythetenantsversusthedesiredratio.
Thisdenitionisalsoknownasthelong-termfairness[45].
Letcidenotethedesiredshareofresources,thefairnessQSmetricfollowsQSFAIR(Ji)=|ci+QSUTIL(Ji)|.
Furthermore,othercostmodelscanalsobeusedasQSmetrics.
Forexample,PersonalizedServiceLevelAgreements(PLSAs)[38]canbeusedastheQSmetricforSQLqueries.
5.
2QSTemplatesTosimplifytheuseofTempo,wehaveimplementedQStem-platestoenabletenantstospecifySLOsdeclaratively.
AQStem-platespecies:(a)auniquequeuetowhichthetenantsubmitsitsworkload,(b)apredenedQSmetricfortheSLOtobeoptimized(wecurrentlysupporttheQSmetricsgivenabove,butTempoisextensible),(c)optionalconstraintsononeormorepredenedQSmetrics(e.
g.
,athresholdonaveragejobresponsetimefortheten-ant'sworkload),and(d)anoptionalpriorityvalue(prioritiesareincorporatedbymultiplyingtheQSmetricwiththepriorityvalue).
Asanexample,theETLtenantmayspecifythefollowingSLOs:OPTIMIZEQSTHR;CONSTRAINTQSDL1isthemagnitudeofthepromotion.
6.
2GoalsandNotationWenowpresentanovelPAretoLocalDescent(PALD)algorithmforsolvingthemulti-objectiveQSoptimizationproblem(SP1).
AcomparisonofPALDtostate-of-the-artisillustratedinTable2,inwhichtheefciencyisbasedonbothsampleandcomputationalcomplexity.
Inthefollowingsections,wedescribePALDandproveitsproperties.
Table2:Multi-objectiveoptimizationalgorithms.
EfcientNoisyQSsConstraintsPareto-optimalSCALAR[8],MGDA[16],PESMO[23]PAL[52],SMSego[41]ParEGO[31],EHI[17],SUR[40]MSPD[35]PALDWedenotevectorsandmatricesbyboldfacesymbols.
Thesim-pliednotationsfiandfi(xxx)areusedinterchangeablytorefertotheQSmetricfunctionfi(xxx,w,ξ),andweusefff(xxx)torefertothevectorofQSfunctions.
ForeachQSmetric,wedenotetheaverageofNmeasuresbyfi(xxx).
ThegoalofPALDistondaweakPareto-optimalsolutionto(SP1).
Ifafeasiblesolutionexists,thentheresultingRMcong-urationsatisesthe"hard"SLOsrepresentedbytheconstraintsin(SP1),whileimprovingthe"best-effort"SLOs.
Ifthereisnofea-siblesolution,thentheresultingRMcongurationbalancestheSLOsrepresentedbytheconstraintsbasedonmax-minfairness.
ThisfeaturesupportsprioritizingtheSLOsbyweightingthecorre-spondingconstraints.
6.
3ProxyModelThekeytechniqueusedinPALDisaproxymodel,whichtrans-formstheoriginalproblem(SP1)toaproxyproblem(SP2)suchthatallsolutionstotheproxyproblemaresolutionstotheoriginalone,butnottheotherwayaround.
Weshowthattheproxyproblemcanbesolvedefciently.
First,itshouldbenotedthatthewell-knownweightedsumscalar-ization([8])—whichconvertsthemulti-dimensionalQSvectortoascalarbytakingaweightedsumoftheQSfunctions—doesnotapplyinthiscase;foritdoesnotensuretherstsetofconstraintsintheproblem(SP1).
Forexample,considertwoRMcongura-tionsandtwoQSfunctions.
SupposethattheQSvectorscorre-spondingtothetwosolutionsare(5,5)and(0,7),respectively.
Letrrr=(6,6).
Whentheweightsareequal,theoptimizationus-ingweightedsumscalarizationyieldstheQSvector(0,7),whichdoesnotdominaterrr=(6,6).
OursolutionPALDsolvesthefollowingproxyproblem:argminxxx∈Xccc[fff(xxx)ρmax(fff(xxx),rrr)](SP2)s.
t.
E[fi(xxx)]≤rii=1,2,···,k.
Here,ccc,whichisapositivevector,andρri,andisindependentofthevectorccc.
Thisisanadvantageoverconicscalarization[28].
Onespecialcaseisthatwhenρ=0,theproblem(SP2)becomestheweightedsumscalarization.
THEOREM1.
Foranyarbitrarypositivevectorcccandparame-terρrjsj(xxx)=∑i:fi(xxx)≤rici[fi(xxx)ρri]+(5)∑j:fj(xxx)>rjcj(1ρ)fj(xxx).
(6)Both(5)and(6)arestrictlymonotonicallyincreasingwithrespecttofi(xxx),soistheobjective(SP2).
Considerasolutionxxxfor(SP2).
SupposethatxxxisnotaweakPareto-optimalsolutionfor(SP1),thenthereexistsanotherweakPareto-optimalsolutionxxxfortheproblem(SP1)thatdominatesxxx.
However,thiscontradictsthehy-pothesisthatxxxisasolutionfortheproblem(SP2),duetothemono-tonicity.
6.
3.
1ParametersWenowderivetheparameterscccandρintheproxymodel(SP2).
PALDusesStochasticApproximation[30]forsolvingtheproxyproblem,inwhichthegradientsareestimatedusingthewell-knownLOESS[13].
Lets(xxx)denotetheobjectiveoftheproxyproblem(SP2),theupdateforeachiterationisgivenbyxxxnew=xxxoldαxxxs(xxx),(SGD)whereαisthestepsize.
TheparameterscccandρarechosensuchthattheaboveupdatedoesnotincreasethoseQSfunctionsfi(xxx)≥ri.
Wetherebyobtaini:fi(xxx)≥ri,αxxxfi(xxx)xxxs(xxx)≤0,orequivalentlyxxxfi(xxx)xxxs(xxx)≥0.
Theparametersarealsochosentobestimprovethoseviolatedconstraintsfi(xxx)≥ri.
Fixingccc,ρisobtainedbysolvingargmaxρmini:fi(xxx)≥rixxxfi(xxx)xxxs(xxx)(RHO)s.
t.
xxxfixxxs(xxx)≥0,i:fi(xxx)≥riccc≥0,ρ<1.
Notethattheobjectiveoftheproxymodel(SP2)isnotdifferen-tiableatpoints{xxx∈X:fff(xxx)=rrr},andweneedtoconditiononthesubgradients.
Letusrstassumethats(xxx)/fj(xxx)x=r=cj(1ρ).
Theobjectiveoftheproblem(RHO)canberewrittenas∑jcjxxxfixxxfjρ∑j:fj(xxx)≥rjcjxxxfixxxfj.
(7)Basedontherangeofthesubgradientofs(xxx),wecanboundρ.
Tosatisfytherstsetofconstraintsintheproblem(RHO)atan725indifferentiablepoint,wehavethatmini,sfj:fi(xxx)≥ri∑jxxxfixxxfjsfj≥0.
(8)Nowconsiderseparatelytwocasesρ≥0andρ<0.
Whenρ≥0theinequality(8)isequivalenttoi:xxxfi=000∧fi(xxx)≥rithat(1ρ)cixxxfixxxfi≥∑j:j=imins/fjxxxfixxxfjsfj=(1ρ)∑j:j=i,xxxfixxxfj≥0cjxxxfixxxfj∑j:j=i,xxxfixxxfj<0cjxxxfixxxfj,whichsimpliesto0≤ρ≤mini:xxxfi=000,fi(xxx)≥ri∑jcjxxxfixxxfj∑j:xxxfixxxfj≥0cjxxxfixxxfj.
Similarly,wecanobtaintheboundforthecaseρ<0.
Itshouldbenotedthattheseboundsareusefulonlywhenthefollowingcondi-tionsaresatised:∑jcjxxxfixxxfj≥0,i:xxxfj=000∧fi(xxx)≥ri.
(9)TheseconditionscanbesatisedforconvexQSfunctions,usingthevectorcccdescribedinMGDA[16].
Combiningtheresultsar-rivesattheoptimalchoiceofρfortheproblem(RHO):ρ=mini:xxxfj=000,fi(xxx)≥ri∑jcjxxxfixxxfj∑j:xxxfixxxfj≥0cjxxxfixxxfj,ρ≥0maxi:xxxfj=000,fi(xxx)≥ri∑jcjxxxfixxxfj∑j:xxxfixxxfj<0cjxxxfixxxfj,ρ<0.
Thesignoftheparameterρdependsonthelasttermoftheobjec-tive(7)astomaximizetheobjective.
Todelivertheaboveoptimalρ,thevectorcccmustalsosatisfytheconditions(9).
Toachievemax-minfairnessofSLOs,PALDchoosescccthatim-provesthemostviolatedconstraint,throughthefollowinglinearprogram.
maximizezsubjecttoJJJi:fi(xxx)≥riJJJccc≥z111ccc≥0,z≤ε.
Here,JJJistheJacobianoftheQSvector,andJJJi:fi(xxx)≥ridenotestherowsoftheJacobianJJJindexedbyi:fi(xxx)≥ri.
εisanar-bitrarypositiveconstant,andthesolutionvectorcccisnormalizedusinganydesirablemetricssuchasthel2-norm.
TherstsetofconstraintscorrespondtotheQSfunctionsfi(xxx)≥ri,andthesearetheonlyQSfunctionsthatneedtobeconvexinPALD.
Thus,PALDprovidesbettersupportfornon-convexQSoptimizationascomparedtoMGDA.
Moreover,randomlychoosingdifferentini-tialpointscanalsohelpdealwithnon-convexQSfunctionsinthissense.
7.
WHAT-IFMODELTempo'sOptimizerdependsontheWhat-ifModeltoestimatethevaluesofnoisyQSmetricsfi(xxx,w,ξ).
TheWhat-ifModelbreakseachpredictionintotwostepsandleveragestheWorkloadGeneratorandSchedulePredictorrespectivelyforthesesteps.
Re-callthattheQSmetricisexpressedasafunctionofthetasksched-uleofwunderxxx.
TheWorkloadGeneratorisresponsibleforgen-eratingtheworkload,andtheSchedulePredictorisresponsibleforgeneratingthetaskschedulegiventheworkloadandtheRMcon-guration.
7.
1WorkloadGenerationAsdiscussedinSection3.
1,therearetwowaystogeneratewinTempo:samplingfromhistoricaltracesorusingastatisticalmodeloftheworkload.
TempoofferusersbothoptionsintheWorkloadModel(seeFigure2).
Asaruleofthumb,usingajobtraceyieldsmorerealisticw,andistherebypreferredwhenevertracesareavail-able.
Incontrast,thestatisticalmodel,whichisusuallytrainedfromhistoricaltraces,hassomekeyadvantages.
Themodelcanbeusedtogeneratemultiplesyntheticw'swithperturbeddistribu-tionsinordertotestthesensitivityofparametersettings.
Moreimportantly,themodelcanbeusedtogeneratewwithextendedcharacteristicssuchasagrowthindatasizeby30%.
Forexample,wedevelopedastatisticalmodelbasedononemonthofhistoricaltracesfromCompanyABC'sproductiondatabaseworkload.
TheworkloaddistributionsfromCompanyABC(reportedfurtherintheevaluationsection)aresimilartothedistributionsdescribedin[42].
Inparticular,thetaskdurationapproximatelyfollowsalognormaldistribution,andthejobarrivalapproximatelyfollowsaPoissonprocess.
7.
2FastSchedulePredictionGivenaworkloadgeneratedasabove,theSchedulePredictorinFigure2estimatesthetaskscheduleoftheworkloadunderagivenRMconguration.
SincetheWhat-ifModelneedstoexploretheimpactofmanydifferentRMcongurations,fastpredictionofschedulescanspeedupTempo'soptimizationprocesssignicantly.
Forveryfasttaskschedulesimulation,weimplementedaSched-ulePredictorfortheRMsusedinHadoop,Spark,andYARNus-ingtimewarpmechanism[27].
Ourimplementationcomputestheclusterresourceusageatonlythesubmissiontime,tentativenishtime,andpossiblepreemptiontimeofeachtask,basedonthework-loadinformationandRMcongurationparametersettings.
ThistechniquehelpsthePredictorgetridofactuallyrunningthetasksaswellassynchronizationwithintheRM.
ToextendtootherRMs,TempocanleverageexistingRMsimu-latorsthathavealreadybeendevelopedforseveralpopularsystems,suchasBorg[49],Apollo[11],Omega[43],MapReduce[48,24,22],andYARN[7].
Mostoftheseexistingsimulatorsaredesignedtoreproducethereal-timebehavioroftheRM,whichisasupersetofourgoalofcomputingthetaskscheduleefciently.
8.
EVALUATIONWenowreportanend-to-endevaluationofTempousingproduc-tionworkloadtracesfromFacebook,multiplecustomersofCloud-era[12],aswellasCompanyABC.
WeapplyTempotofourreal-lifescenariosandshow,respectively,theimprovementsinjobre-sponsetime,resourceutilization,adaptivitytoworkloadvariations,andpredictiveresourceprovisioning.
Intheexperimentswhereabaselineperformanceisneededforcomparison,weusedresourceallocationsasdeterminedbyexpertDBAsandclusteroperatorsinCompanyABC.
Thefollowinginsightsemergefromtheevalua-tion:TempocantailortheresourceallocationtoSLO-drivenbusiness-criticalworkloads,andofferstenantsthefreedomtospecifySLOs.
726Tempoimprovestheresourceutilizationby15%,andjobre-sponsetimeforbest-efforttenantsby50%under25%slackwithoutbreakingthedeadlinesforproductionworkloads.
TempoeffectivelyadaptstoworkloadvariationsbyperiodicallyupdatingtheRMcongurationusingarecentworkloadwin-dow.
TempocanhelpDBAsandclusteroperatorsdeterminetheap-propriateclustersizefortheirmulti-tenantparalleldatabaseforthegivenSLOsandworkloads,minimizingtheoverallresourcecosts.
Theseresultsaredueto:1)informedresourceallocationwhichtakesintoaccounttheworkloadcharacteristicsrevealedfromhis-toricaljobtraces;and2)optimizedRMcongurationsaimingfortheSLOsbecauseTempomakestheconnectionbetweentheRMcongurationandSLOsmoretransparentandpredictable.
8.
1ValidatingtheschedulepredictionWebeginbyvalidatingthetaskschedulepredictionona700-nodeproductionclusteratCompanyABC.
Inparticular,wemea-suretheaccuracyofthepredictionusingoneweek'sproductionworkloadfromsixindependenttenants,asdescribedinTable1.
Theworkloadconsistofapproximately60,000jobsand35mil-lionproductiontaskscollectedinanoisyenvironmentwheretherewerejobandtaskfailures,jobskilledbyusersandDBAs,andnodeblacklisting,failures,andrestarts.
Figure3showsthekeystatisticsoftheworkload.
Theschedulepredictionforthe35milliontasksfromsixtenantstakesjust4minutes,orapproximately150,000taskspersecond.
Wecomparethepredictedtaskscheduleandtheobservedschedulebasedonthetraces,andcomputethepredictionerror.
Boththerelativeabsoluteerror(RAE)andtherelativesquarederror(RSE)areusedastheerrormetrics.
TheRAEandRSEoftenantiaredenedrespectivelyasRAEi=∑j|pijlij|∑j|lijEj[lij]|,RSEi=∑j(pijlij)2∑j(lijEj[lij])2.
Herepijandlijrepresentthepredictedandobservednishtimeofjobjfortenanti,respectively.
Table8.
1givestheRAEandRSEfortheestimatedjobnishtime.
Ascanbeseen,thehighesterror(24.
4%)wasincurredfortheMVtenantinCompanyABC.
MostjobsfromMVwerelong-runningjobs,especiallywithlargedura-tionofreducetasks.
WeobservedaconsiderableamountofkilledreducetasksforMVduetopreemptions.
Forkilledandfailedtasks,thetaskstarttimeandnishtimearenotrecordedaccuratelyinworkloadtraces;whichexplainswhyMVhasahigherpredictionerrorthanothers.
Table3:Jobnishtimeestimationerrorsforeachtenant.
TenantRAERSETenantRAERSEBI0.
15850.
2210STR0.
16100.
1463DEV0.
21950.
2267MV0.
23180.
2437APP0.
18120.
1599ETL0.
12100.
19088.
2End-to-endevaluationTheend-to-endexperimentsinvolvefourreal-lifescenarios,andwereperformedona20-nodeAmazonEC2clusterwithm3.
xlargeinstances.
TheproductionworkloadtracesfromCompanyABC,Facebook,andClouderacustomerswerescaledandreplayedontheEC2clusterusingSWIM[12].
Inaddition,theinitialRMcong-urationwasderiveddirectlyfromtheexpertonecreatedbyDBAsforCompanyABC'sproductiondatabase.
Eachend-to-endexper-imentinvolvesapproximately30,000tasksfromtwotenants,andeachTempocontrolloopexplores5RMcongurationcandidates.
Thus,oneTempocontrollooprequirespredictionfor150,000tasks,whichtakesonesecond.
8.
2.
1Mixofdeadline-drivenandbest-effortwork-loadsTherstscenarioinvolvestwotenantsrunningworkloadswhichcomewiththedeadlineSLOspeciedwithQSDL,andthelowav-eragejobresponse(AJR)timeSLOspeciedwithQSAJR,respec-tively.
TheexperimentaimedtoobtainanRMcongurationwhichisbetterthantheexpertoneusedinproduction.
Inparticular,un-derthenewRMconguration,everyjobfromthedeadline-drivenworkloadmustcompletenolaterthanthecompletionofthesamejobundertheexpertRMconguration.
Thisisastrictconstraint,wherethedeadlinesinQSDLaregivenbythecompletiontimesofdeadline-drivenjobsundertheexpertRMconguration,andthecorrespondingri=0(for0%deadlineviolations).
Anothercon-straintinvolvingQSAJRenforcesthattheaveragejobresponsetimeofthebest-effortworkloadsunderthenewRMcongurationcan-notbegreaterthantheaveragejobresponsetime(ri)undertheexpertconguration.
Whencountingthenumberofdeadlineviolations,a25%slack,i.
e.
,γ=0.
25,isusedinQSDLtoreducethesensitivitytonoise,sinceeventheworkloadsunderthesameRMcongurationwithaslack0(γ=0inQSDL)canyieldalargedeadlineviolationfraction(upto83%).
Figure4showstheSLOs(QSvalues)ateachiterationintheTempocontrolloop.
Attheiteration0,theinitialexpertRMcon-gurationwasused.
TheRMcongurationwastheniterativelyoptimizedbytheTempocontrolloop.
Itcanbeseenthat,atcon-vergence,theimprovementsinaveragejobresponsetimeofthebest-efforttenantare50%and58%for25%and50%slack,re-spectively.
Thegapbetweentheimprovementsisrelativelysmall,i.
e.
,8%.
Onereasonisthatbothimprovementsbenetedfromthereducedcontentionforresources,whichisconrmedinthenextexperiment.
Inaddition,thefractionofdeadlineviolationsrstdropsandthenbreaksevenatconvergence.
ThistrendisduetothefactthatoncetheParetofrontierisreached,wecannotimproveoneSLOwithoutsacricinganother.
8.
2.
2ImprovingresourceutilizationInadditiontothepreviousscenario,thisexperimentconsideredathirdSLO,highresourceutilization,whichisspeciedwithQSUTIL.
WefocusedexclusivelyonMapReduceworkloadsduetotheob-servationofsignicanttaskpreemptionsinproduction.
Theexper-imentaddedtwoconstraintscorrespondingtothemapcontainerutilizationandreducecontainerutilization,respectively.
Theri'sweresetaccordingtothemeasuredmapandreducecontaineruti-lizationundertheexpertRMconguration.
TheresultsshowfewerpreemptionsundertheTempooptimizedRMcongurationaswellasimprovementsinjobresponsetimesubjecttothedeadlineSLOs.
Aswediscussed,preemptionhappenswhenatenanthasbeenstarvedforacertainperiodoftime(theconguredpreemptiontimeout),killingacertainnumberofmostrecentlylaunchedtasksfromothertenants.
Thus,preemptionresultsinlostworkandde-creasedresourceutilization.
Eachtenantcanspecifyaper-tenantpreemptiontimeoutintheRMconguration,andthesesettingsaredifculttogetrightmanually(evenforexperts)duetotheircom-plexconnectionstoworkloadsandSLOs.
WeobservedasignicantnumberofpreemptedMapReducetasksontheproductionclusteratCompanyABC.
Figure5showsthe7271001021040.
60.
70.
80.
91ReducesBIDEVAPPSTRMVETL10010210410600.
20.
40.
60.
81Maps10110310500.
20.
40.
60.
81Responsetime[sec]JobsCDF10310600.
20.
40.
60.
81Waittime[sec]Figure3:KeystatisticsofCompanyABC'sworkloads.
Figure4:Averagejobresponsetimeforthebest-efforttenant(left)andfractionofdeadlineviolationsforthedeadline-driventenant(right)ateachiteration.
Figure5:TaskpreemptionsforMapReduceworkloadsatCompanyABC.
Ontheleftshowsthepreemptedmaptasks,andthepreemptedreducetasksaregivenontheright.
mapandreducepreemptionsovertheperiodofoneweek.
Dur-ingthisperiod,6%maptasksand23%reducetaskshadbeenpre-empted,andthereducepreemptionsweremostlyfromthebest-efforttenant.
Themainreasonwasthattheworkloadsofthebest-efforttenantcontainmostlylong-runningreducetasks,asshowninFigure6.
Figure6:TaskdurationdistributionsforMapReducework-loadsatCompanyABC.
Figure7showstheSLOsundertheoriginalexpertRMcong-urationandtheTempooptimizedRMconguration.
Ascanbeseen,theoptimizedresourceallocationdelivers22%improvementintheaveragejobresponsetimeofthebest-efforttenantworkloadsand10%inthedeadlineQSs.
Anotherimprovementisintheuti-lizationofreducecontainers,whiletheutilizationofmapcontain-ersremainsatthesamelevel.
Theresultsareconsistentwithourobservationsofpreemptionstatistics,andtheimprovementsinre-ducecontainerutilizationisduetothealleviatedpreemptions.
Inparticular,thepreemptiontimeoutsettingsintheTempo-optimizedRMcongurationhadbeenself-tunedappropriatelytothework-loaddistribution.
Figure7:SLOsundertheoriginalandoptimized(slack=0)RMconguration:AJR,DL,UTILMAP,andUTILREDaretheaveragejobresponsetimeofthebest-efforttenant,fractionofdeadlineviolationsforthedeadline-driventenant,mapcon-tainerutilization,andreducecontainerutilization,respectively.
8.
2.
3PerformanceofPALDVs.
State-of-the-artInthisexperiment,wecomparetheproposedPALDalgorithmtostate-of-the-artformulti-objectiveQSoptimization(seeTable2).
Specically,weconsidersixtenantsAtoFwithaveragejobresponsetime,deadline,andthroughputSLOs,andevaluatethecongurationsproducedbythealgorithmsincomparison.
ThesetenantsrunSWIM-generatedworkloadsbasedonproductiontracesfromClouderaclientsandFacebook.
SincemeasuringQSsandmakingQSestimationsarethemosttime-consumingphasesinTempo,wenaturallyruleoutalgorithmswithlargesamplecomplexity,e.
g.
,evolutionaryalgorithms.
TheQSoptimization(SP1)alsorequiresthesolutiontosupportcon-straints.
ThisconditionremovesPAL,PESMO,andSURfromconsidera-tion.
MSPDisthestate-of-artwhichsupportsconstraints;however,MSPDdoesnotseekaPareto-optimalsolution.
ThegoalofMSPDisinsteadtooptimizeoneselectedobjectivewhilesatisfyingalltheotherobjectiveswithrespecttothespeciedthresholds.
728Figure9:Instantjobresponsetimedistributions.
OntheleftshowstheproductionworkloadsofCompanyABCoverthepe-riodofaweek.
Ontherightgivesthetwo-hourexperimentworkloadsonEC2usingFacebookandClouderatraces.
Figure10:SLOsfordifferentintervallengthsinTempocontrolloop.
AJRdenotesthenormalizedaveragejobresponsetimeofthebest-effortworkloads,andDLrepresentsthefractionofdeadlineviolations(computedviaQSDLwithslackγ=25%).
Fortheabovereasons,wecomparethreealgorithms:SCALAR,MSPD,andPALD.
SCALARisthewidely-usedscalarizationwhichservesasanaiveapproach.
Theexperimentstartswiththesamear-bitraryconguration,andperformstheoptimizationusingdifferentalgorithms.
Thesamenumberofiterationsareperformeduntilev-eryalgorithmhasconverged.
Eachiterationtakes1minforeveryalgorithmandusestwohoursofjobhistoryforcomputingSLOs.
Figure8showsthenormalizedresults,ascomparedtotheexpertconguration,fortheinitialarbitrarycongurationandcongura-tionsoptimizedbydifferentalgorithms.
Inparticular,theSLOsachievedundertheexpertcongurationarespeciedasconstraintsforthesealgorithmstotrytoforcetheoptimizedcongurationtodominatetheexistingone.
Figure8:ComparisonofalgorithmsforQSoptimization.
Ex-pertisthebaselinecongurationandothersarenormalizedaccordingly.
AJR,DL,THRarerespectivelytheaveragejobresponsetime,deadline,andthroughput(#jobs/hr)SLOs.
Ascanbeseen,thearbitrarycongurationresultedindecreasedperformanceforalltenantsexceptD.
Unsurprisingly,SCALARleadstoincreaseddeadlineviolationsforCandEwhileachiev-ingdecentimprovementsinAJRSLOsduetotheignoranceofSLOconstraints.
SinceMSPDdoesnotseekPareto-improvingso-lutions,theresultingcongurationdoesnotdominatetheexpertone.
WealsonotedthatMSPDassumesaconvexcongurationspace,whichgenerallydoesnotholdforRMs.
Forexample,thepreemptionparametersareinbinaryandintegerdomains.
Thecon-gurationoptimizedbytheproposedPALDisPareto-improvingasdesired.
8.
2.
4AdaptivitytoworkloadvariationsInthisexperiment,weappliedTempotomeetSLOsunderslowlychangingworkloaddistributions.
Figure9depictstheinstantjobresponsetimedistributionfordeadline-drivenandbest-effortten-ants.
Theinstantjobresponsetimeiscomputedusingthemov-ingaverageofa30-minutewindow.
Ascanbeseen,theinstantjobresponsetimeofdeadline-drivenworkloadsexhibitsaperiodicpatternwhilethejobresponsetimeofthebest-effortworkloadschangesdramaticallyovertime.
RecallthateachiterationoftheTempocontrolloopusesaxed-lengthintervalofmostrecentjobtracesasinput.
Thenextex-perimentevaluateshowdifferentintervallengthsimpactTempo'sperformance.
Figure10showstheSLOsundertheoriginalexpertRMcongu-rationandTempo-optimizedRMcongurationsforintervallength15min,30min,and45min.
Similarly,theexperimentusesSLOsspeciedwithQSAJR,andQSDL(25%slack).
Ascanbeseen,asmallwindowsizefavorstheaveragejobresponsetimeofthebest-effortworkloadswhileleadingtoahigherpercentofdeadlinevio-lations.
Accordingtotheresults,the45minintervallengthyieldsasimilarfractionofdeadlineviolationsastheoriginalRMcongu-ration,buta22%improvementintheaveragejobresponsetimeofthebest-effortworkloads.
TheresultsshowthatTempocanadapttoworkloadvariationsusingasmallintervallength.
8.
2.
5ResourceprovisioningandcuttingcostsThelastexperimentdemonstratestheapplicationofTempotore-sourceprovisioning,estimatingtheminimumamountofresourcesneededtomeetthegivenSLOs.
Thisapplicationcanhelpusersdobetterresourceplanningandcutoverprovisioningcosts.
Inad-dition,thisapplicationcanbridgethegapinresourceallocationbetweenthedevelopmentclusterandtheproductioncluster,thatis,convertingtheresourceallocationonthedevelopmentclusterforuseintheproductioncluster.
Theexperimentinvolvesrunningthesamegivendeadline-drivenworkloadsandbest-effortworkloadsonthreeEC2clusterswith20nodes(100%),10nodes(50%),and5nodes(25%),respectively.
TempowasusedtoestimatetheSLOsoftheworkloadswhenexe-cutedonthe100%cluster,usingtracesrespectivelyfromthe100%cluster,50%cluster,and25%cluster.
Thisexperimentmimicsthescenarioinwhichuserscollecttracesoftheworkloadonthecurrentcluster,andwouldliketoknowhowanewclustersizewillimpacttheSLOs.
(Fromourexperience,thisusecaseiscommonatcom-panieslikeLinkedInandYahoo.
)Inthiscase,Tempocanserveasakeycomponentinthedecision-makingforresourceprovisioning.
Figure11givestheSLOestimationerrorsusingtracesfromequalandsmallerclusters.
Ascanbeseen,Tempocanpredict—withtheerrornomorethan20%—theSLOsofthecurrentwork-loadsrunonadouble-sizecluster;usingtracescollectedfromthecurrentcluster.
PredictingtheSLOsofthecurrentworkloadsrunonaquadruple-sizeclusterresultsinamaximumerrorof35%.
9.
RELATEDWORKGeneral-purposeRMs.
MostResourceManagers(RMs)thataredeployedonmulti-tenant"bigdata"databasesystemstodaylike729Figure11:ErrorsinSLOestimationusingtracesbasedonequalandsmallerclustersizes.
RedShift,Teradata,Vertica,Hadoop,andSparkarebasedonre-sourceallocationprinciplessuchasstaticresourcepartitioning[1],max-minfairness[4,3],dominantresourcefairness[20,19,44],orreservations[14].
Variantsalsoconsiderdatalocality[26],jobplacementconstraints[20],andmulti-resourcepackingoftaskstomachines[21].
Moreover,RMs(usuallycalledWorkloadMan-agers)inparalleldatabasesystemslikeIBMDB2PE,RedShift,Teradata,andVerticaallowDBAstospecifyrulestodynamicallyadjusttheresourceallocationoftenants,aswellasdeneuser-denedeventsrelevanttoworkloadmanagementandactionstobetakenbasedonthem.
RedShiftandVerticauseresourcepoolswhereeachpoolhasparameterssuchasresourcelimits,priorities,andmaximumconcurrencyliketheRMcongurationdescribedinSection3.
3.
Alargebodyofrecentresearchfocusesondevelopinggeneral-purposeRMslikeYARN[46]andMesos[25].
Themaineffortslieinscalability,responsiveness,andfault-toleranceoftheRMs.
Omega[43]proposesparallelism,sharedstate,andlock-freeopti-misticconcurrencycontrolforincreasedscalability.
Sparrow[39]leveragesload-balancingtechniquestomaketheschedulermoreresponsiveforschedulinglow-latencytasks.
Fuxi[51]enhancesthefaulttoleranceandscalabilityofRMsbyintroducingtrans-parentfailurerecoveryfeaturesandafailuredetectionmechanism.
Apollo[11]takesintoaccountthedatalocalityandserverloadtoachievehigh-qualityschedulingdecisions.
Apolloalsointroducescorrectionmechanismstocopewithunexpectedclusterdynamics,sub-optimalestimations,andotherabnormalruntimebehaviors.
TheaboveRMsgenerallyprovideeffectivecontrolandisolationoverresources.
However,theyhavelimitedsupportforapplication-levelandtenant-orientedSLOs,andoftenrelyonDBAstoguesstherightcapacities.
SingleSLO-drivenRMs.
ManyexistingRMsaimtoachieveasingletypeofSLO.
In[29],theauthorsdevelopadeadlineestima-tionmodelandapplyreal-timeschedulingtomeetjobdeadlines.
ARIA[47]providessupportforjobdeadlinesbyprolingjobsandmodelingresourcerequirementsinordertocompletebeforethedeadline.
WOHA[33]improvesworkowdeadlinesatisfactionsinHadoop.
Amoeba[9]bringslightweightelasticitytocomputeclustersbysplittingoriginaltasksintosmallerones,andallowingsafeexitofarunningtaskandlaterresumingthetaskbyspawninganewtaskforitsremainingwork.
Pisces[44]deliversdatacenter-wideper-tenantperformanceisolationandfairnessformulti-tenantcloudstorage.
Tenant-orientedRMs.
AhandfulofRMshavebeenproposedtoprovidetenantperformanceisolation.
Unlikeresourceisola-tion,theseRMstypicallyincorporatecapacityestimationtomeettenant-orientedSLOs.
Pulsar[10]usesvirtualdatacenterabstrac-tion(VDC),whichissimilartotheQSabstractioninTempo,todescribetheSLOsforatenant.
UnlikeTempo,Pulsarfocusesonscenarioswhereresourcesaresufcient,anddoesnotguaranteeParetooptimalityofSLOs.
TheeffectivenessofPulsaralsoreliesontheaccuracyofuser-speciedcostfunctionsinVDCsaswellasresourcedemandestimation.
Thus,Pulsarcanbesensitivetonoiseinbothcostanddemandestimation.
Retro[34]supportsresource-limitedscenariosanddeliversmax-minfairnessacrossSLOsbybalancingtheprogressofapplications(referredtoasworkows).
RetrodoesnotguaranteethePareto-optimalityoftenantSLOs.
Forexample,onemayusetechniqueslikemulti-resourcepacking[21]toobtainPareto-improvingcongurationswithsimilarrelativefair-nessratiosamongtenants.
10.
CONCLUSIONProvidingend-to-endtenantperformanceisolationwhileachiev-inghighresourceutilizationinmulti-tenant"bigdata"databasesystemsisanimportantproblem.
Thevastmajorityofresourcemanagersdeployedonmulti-tenantdatabasesystemstodayrelyonDBAstocontinuallycongurelow-levelresourcesettingstosup-porttenantperformanceisolation.
Thisprocessisbrittleandin-creasinglyhardasworkloadsevolve,dataandclustersizeschange,andnewworkloadsareadded.
Inthispaper,wepresentedaframe-work,Tempo,whichenablesDBAstoworkwithhigh-levelSLOsconveniently.
Inparticular,weshowedthatTempohasprovablerobustnesspropertieswhichenforcetenantperformanceisolation,andmoredesirablyPareto-optimalSLOs.
TheevaluationreportsthatTempoisself-tuningandrobustforachievingguaranteedSLOsinproductiondatabasesystems.
11.
REFERENCES[1]Amazonredshift.
http://goo.
gl/nS8cQH.
[2]Facebookcorona.
https://goo.
gl/MN9VpK.
[3]Hadoopcapacityscheduler.
https://goo.
gl/hh6Ood.
[4]Hadoopfairscheduler.
https://goo.
gl/8Ov2nj.
[5]Teradata.
http://goo.
gl/TjU7qR.
[6]Vertica.
http://tinyurl.
com/ovgufev.
[7]Yarnschedulerloadsimulator.
https://goo.
gl/JNUPoj.
[8]F.
B.
Abdelaziz.
Solutionapproachesforthemultiobjectivestochasticprogramming.
216(1):1–16,2012.
[9]G.
Ananthanarayanan,C.
Douglas,R.
Ramakrishnan,S.
Rao,andI.
Stoica.
Trueelasticityinmulti-tenantdata-intensivecomputeclusters.
InSOCC,pages24:1–24:7,2012.
[10]S.
Angel,H.
Ballani,T.
Karagiannis,G.
O'Shea,andE.
Thereska.
End-to-endperformanceisolationthroughvirtualdatacenters.
InOSDI,pages233–248,2014.
[11]E.
Boutin,J.
Ekanayake,W.
Lin,B.
Shi,J.
Zhou,Z.
Qian,M.
Wu,andL.
Zhou.
Apollo:Scalableandcoordinatedschedulingforcloud-scalecomputing.
InOSDI,pages285–300,102014.
[12]Y.
Chen,S.
Alspaugh,andR.
Katz.
Interactiveanalyticalprocessinginbigdatasystems:Across-industrystudyofmapreduceworkloads.
5(12):1802–1813,082012.
[13]W.
S.
ClevelandandS.
J.
Devlin.
Locallyweightedregression:Anapproachtoregressionanalysisbylocaltting.
83:596–610,1988.
[14]C.
Curino,D.
E.
Difallah,C.
Douglas,S.
Krishnan,R.
Ramakrishnan,andS.
Rao.
Reservation-basedscheduling:Ifyou'relatedon'tblameus!
InSOCC,pages2:1–2:14,2014.
730[15]S.
Das,V.
Narasayya,F.
Li,andM.
Syamala.
Cpusharingtechniquesforperformanceisolationinmulti-tenantrelationaldatabase-as-a-service.
InPVLDB,2013.
[16]J.
-A.
Desideri.
Multiple-gradientdescentalgorithm(MGDA)formultiobjectiveoptimization.
Tome350(Fascicule5-6):313–318,032012.
[17]A.
Emmerich.
ThecomputationoftheexpectedimprovementindominatedhypervolumeofParetofrontapproximations,2008.
[18]A.
D.
Ferguson,P.
Bodik,S.
Kandula,E.
Boutin,andR.
Fonseca.
Jockey:Guaranteedjoblatencyindataparallelclusters.
InEuroSys,pages99–112,2012.
[19]A.
Ghodsi,M.
Zaharia,B.
Hindman,A.
Konwinski,S.
Shenker,andI.
Stoica.
Dominantresourcefairness:Fairallocationofmultipleresourcetypes.
InNSDI,pages323–336,2011.
[20]A.
Ghodsi,M.
Zaharia,S.
Shenker,andI.
Stoica.
Choosy:Max-minfairsharingfordatacenterjobswithconstraints.
InEuroSys,pages365–378,2013.
[21]R.
Grandl,G.
Ananthanarayanan,S.
Kandula,S.
Rao,andA.
Akella.
Multi-resourcepackingforclusterschedulers.
44(4):455–466,082014.
[22]S.
Hammoud,M.
Li,Y.
Liu,N.
K.
Alham,andZ.
Liu.
MRSim:AdiscreteeventbasedMapReducesimulator.
6:2993–2997,082010.
[23]D.
Hernandez-Lobato,J.
M.
Hernandez-Lobato,A.
Shah,andR.
P.
Adams.
Predictiveentropysearchformulti-objectivebayesianoptimization.
InNIPSWorkshoponBlack-boxLearningandInference,2015.
[24]H.
Herodotou,H.
Lim,G.
Luo,N.
Borisov,L.
Dong,F.
B.
Cetin,andS.
Babu.
Starsh:Aself-tuningsystemforbigdataanalytics.
InCIDR,pages261–272,2011.
[25]B.
Hindman,A.
Konwinski,M.
Zaharia,A.
Ghodsi,A.
D.
Joseph,R.
Katz,S.
Shenker,andI.
Stoica.
Mesos:Aplatformforne-grainedresourcesharinginthedatacenter.
InNSDI,pages295–308,2011.
[26]M.
Isard,V.
Prabhakaran,J.
Currey,U.
Wieder,K.
Talwar,andA.
Goldberg.
Quincy:Fairschedulingfordistributedcomputingclusters.
InSOSP,pages261–276,2009.
[27]D.
Jefferson,H.
Sowizral,andR.
Corporation.
FastConcurrentSimulationUsingtheTimeWarpMechanism:PartI,LocalControl.
FastConcurrentSimulationUsingtheTimeWarpMechanism:PartI,LocalControl.
RandCorporation,1982.
[28]R.
Kasimbeyli.
Aconicscalarizationmethodinmulti-objectiveoptimization.
56(2):279–297,2013.
[29]K.
KcandK.
Anyanwu.
Schedulinghadoopjobstomeetdeadlines.
InCLOUDCOM,pages388–392,2010.
[30]J.
KieferandJ.
Wolfowitz.
Stochasticestimationofthemaximumofaregressionfunction.
23:462–466,1952.
[31]J.
Knowles.
Parego:Ahybridalgorithmwithon-linelandscapeapproximationforexpensivemultiobjectiveoptimizationproblems.
10(1):50–66,092006.
[32]W.
Lang,S.
Shankar,J.
Patel,andA.
Kalhan.
Towardsmulti-tenantperformanceslos.
InICDE,2012.
[33]S.
Li,S.
Hu,S.
Wang,L.
Su,T.
Abdelzaher,I.
Gupta,andR.
Pace.
Woha:Deadline-awaremap-reduceworkowschedulingframeworkoverhadoopclusters.
InICDCS,pages93–103,2014.
[34]J.
Mace,P.
Bodik,R.
Fonseca,andM.
Musuvathi.
Retro:Targetedresourcemanagementinmulti-tenantdistributedsystems.
InNSDI,pages589–603,052015.
[35]M.
Mahdavi,T.
Yang,andR.
Jin.
Stochasticconvexoptimizationwithmultipleobjectives.
InNIPS,pages1115–1123.
2013.
[36]V.
Narasayya,S.
Das,M.
Syamala,B.
Chandramouli,andS.
Chaudhuri.
Sqlvm:Performanceisolationinmulti-tenantrelationaldatabase-as-a-service.
InCIDR,January2013.
[37]V.
Narasayya,S.
Das,M.
Syamala,S.
Chaudhuri,F.
Li,andH.
Park.
Ademonstrationofsqlvm:Performanceisolationinmulti-tenantrelationaldatabase-as-a-service.
InSIGMOD,pages1077–1080,2013.
[38]J.
Ortiz,V.
T.
deAlmeida,andM.
Balazinska.
Changingthefaceofdatabasecloudserviceswithpersonalizedservicelevelagreements.
InCIDR,2015.
[39]K.
Ousterhout,P.
Wendell,M.
Zaharia,andI.
Stoica.
Sparrow:Distributed,lowlatencyscheduling.
InSOSP,pages69–84,2013.
[40]V.
Picheny.
Multiobjectiveoptimizationusinggaussianprocessemulatorsviastepwiseuncertaintyreduction.
25(6):1265–1280,2014.
[41]W.
Ponweiser,T.
Wagner,D.
Biermann,andM.
Vincze.
Multiobjectiveoptimizationonalimitedbudgetofevaluationsusingmodel-assistedS-metricselection.
InProceedingsofthe10thInternationalConferenceonParallelProblemSolvingfromNature:PPSNX,pages784–794,2008.
[42]Z.
Ren,X.
Xu,J.
Wan,W.
Shi,andM.
Zhou.
Workloadcharacterizationonaproductionhadoopcluster:Acasestudyontaobao.
InIEEEInternationalSymposiumonWorkloadCharacterization,pages3–13,2012.
[43]M.
Schwarzkopf,A.
Konwinski,M.
Abd-El-Malek,andJ.
Wilkes.
Omega:Flexible,scalableschedulersforlargecomputeclusters.
InEuroSys,pages351–364,2013.
[44]D.
Shue,M.
J.
Freedman,andA.
Shaikh.
Performanceisolationandfairnessformulti-tenantcloudstorage.
InOSDI,pages349–362,2012.
[45]S.
Tang,B.
-s.
Lee,B.
He,andH.
Liu.
Long-termresourcefairness:Towardseconomicfairnessonpay-as-you-usecomputingsystems.
InICS,pages251–260,2014.
[46]V.
K.
Vavilapalli,A.
C.
Murthy,C.
Douglas,S.
Agarwal,M.
Konar,R.
Evans,T.
Graves,J.
Lowe,H.
Shah,S.
Seth,B.
Saha,C.
Curino,O.
O'Malley,S.
Radia,B.
Reed,andE.
Baldeschwieler.
Apachehadoopyarn:Yetanotherresourcenegotiator.
InSOCC,pages5:1–5:16,2013.
[47]A.
Verma,L.
Cherkasova,andR.
H.
Campbell.
Aria:Automaticresourceinferenceandallocationformapreduceenvironments.
InICAC,pages235–244,2011.
[48]A.
Verma,L.
Cherkasova,andR.
H.
Campbell.
Playitagain,simmr!
InCLUSTER,pages253–261,2011.
[49]A.
Verma,L.
Pedrosa,M.
R.
Korupolu,D.
Oppenheimer,E.
Tune,andJ.
Wilkes.
Large-scaleclustermanagementatGooglewithBorg.
InEuroSys,2015.
[50]P.
Xiong,Y.
Chi,S.
Zhu,H.
J.
Moon,C.
Pu,andH.
Hacigumus.
Intelligentmanagementofvirtualizedresourcesfordatabasesystemsincloudenvironment.
InICDE,pages87–98,2011.
[51]Z.
Zhang,C.
Li,Y.
Tao,R.
Yang,H.
Tang,andJ.
Xu.
Fuxi:Afault-tolerantresourcemanagementandjobschedulingsystematinternetscale.
7(13):1393–1404,082014.
[52]M.
Zuluaga,A.
Krause,G.
Sergent,andM.
P¨uschel.
Activelearningformulti-criterionoptimization.
InICML,2013.
731