Workload-aware load balancing for clustered web se

Workload-AwareLoadBalancingforClusteredWebServers∗QiZhang1AlmaRiska2WeiSun3EvgeniaSmirni1GianfrancoCiardo41DepartmentofComputerScience,CollegeofWilliamandMary2InterfacesandArchitectureGroup,SeagateResearch3SymantecCorporation4DepartmentofComputerScienceandEngineering,UniversityofCaliforniaatRiversideAbstractWefocusonloadbalancingpoliciesforhomogeneousclusteredwebserversthattunetheirparam-eterson-the-flytoadapttochangesinthearrivalratesandservicetimesofincomingrequests.Theproposedschedulingpolicy,ADAPTLOAD,monitorstheincomingworkloadandself-adjustsitsbalanc-ingparametersaccordingtochangesintheoperationalenvironmentsuchasrapidfluctuationsinthearrivalratesordocumentpopularity.Usingactualtracesfromthe1998WorldCupwebsite,weconductadetailedcharacterizationoftheworkloaddemandsanddemonstratehowon-lineworkloadmonitoringcanplayasignificantpartinmeetingtheperformancechallengesofrobustpolicydesign.Weshowthattheproposedloadbalancingpolicybasedonstatisticalinformationderivedfromrecentworkloadhistoryprovidessimilarperformancebenefitsaslocality-awareallocationschemes,withoutrequiringlocalitydata.ExtensiveexperimentationindicatesthatADAPTLOADresultsinaneffectivescheme,evenwhenserversmustsupportbothstaticanddynamicwebpages.Keywords:clusteredwebservers,self-managingclusters,loadbalance,localityawareness,work-loadcharacterization,staticanddynamicpages.1IntroductionThewidedeploymentofwebbrowsersasthestandardinterfaceforITapplicationssuchasnewssites,e-commercestores,andsearchenginesmakeswebserverclustersthearchitectureofchoice.Servingtheever-increasinganddiversifiedcustomerpopulationinsuchsystemswhileensuringhighavailabilityinacost-effectivewayisachallenge.Servicereplicationistheobviousvehicletoachievescalabilityandavail-ability,butthisrequiresrobustloadbalancingpolicies,especiallygiventhecomplexityoftheworkloadcharacteristicsexperiencedbyawebcluster.Contemporaryserversprovidenotonlystaticandread-onlyin-formation,butalsopersonalizeddynamicpagescreatedondemand.This,inconjunctionwithburstyclientrequestratesthatfluctuatedramaticallyevenwithinshortperiodsoftimeandthewidedisparityofper-requestCPUandI/Oresourcerequirements,furthercomplicatesresourceallocationinwebserverclusters.Beingabletoswiftlyadapttheschedulingpolicytotheworkloadwithouthumaninterventioniscriticalforthecommercialsuccessofwebsites[21].Inthispaper,wefocusonself-adjustingstrategiesforeffectiveloadbalancinginalocally-distributedwebserverclusterthatprovidesreplicatedservices.Weassumeawebserverarchitectureconsistingofafront-enddevice(commonlycalledawebswitch)andasetofhomogeneous,back-endwebservernodes.∗ThisworkwaspartiallysupportedbytheNationalScienceFoundationundergrantsEIA-9974992,CCR-0098278,andACI-0090221.Apreliminaryversionofthispaperappearedatthe22thInternationalConferenceonDistributedComputerSystems,(ICDCS’02),pages103–111,Vienna,Austria,July2002.1TheswitchactsastheinitialinterfacebetweentheclusternodesandtheInternet,anddistributestheincomingrequeststotheservers,tryingtobalancetheloadamongthem.Theservernodesareresponsibleforservingindividualrequests[2];inparticular,aservernodehandlesrequestsforstaticcontentlocatedeitherinitslocalmemoryorinitslocaldisk,whiledynamicrequestsareforwardedfirsttoaspecializedserver,e.g.,adatabaseserver,beforetheycanbetransmittedtotheclientbytheservernode.Arobustself-tunedloadbalancingpolicyinsuchanenvironmentiscriticalforhighperformance.Previ-ousresearchaddressedissuesofscalability,availability,andqualityofservicesupportwithinthecontextofloadbalancinginclusteredwebservers.Foracomprehensivesurveysee[11].However,mostoftheseclassicworksontaskassignmentassumethatjobservicerequirementsfollowthewell-behavedexponentialdistri-bution,thustheyarelesseffectivewhentheworkloadhashighlyvariablearrivalandserviceprocesses[23].Highvariabilityinthearrivalratescanbeduetoperiodicity,e.g.,dependenceonthetimeofthedayordayoftheweek,maybetriggeredbyunpredictableevents,e.g.,breakingnewsinanewssite,ormaybeduetothenatureofInternetitself:burstyarrivalscanleadtoperiodsoftransientoverloadwherethenumberofrequestsinthesystemincreasesdramaticallywithinaveryshorttimeperiod.Effectiveloadbalancingpoliciesshouldofferrapidsystemadaptationundertransientoverloadconditions.Variabilityintheserviceprocessbecomesanadditionalobstacletoeffectiveloadbalancing.Forstaticrequests,itiswell-documentedthatthesizeofwebdocuments(andconsequentlytheirservicedemands)followsheavy-taileddistributions[4,7],while,fordynamicrequests,thereisvirtuallynocorrelationbetweendocumentsizeandservicedemand.Ourthesisisthataneffectiveloadbalancingpolicymustself-adjustitsparametersasthearrivalandservicecharacteristicsoftheincomingworkloadchange.In[23],weproposedanewpolicynamedADAPT-LOADandgaveaproofofconceptthatdynamicallyre-adjustingitsparametersbasedonthemonitoredworkloadisapromisingapproach.ADAPTLOADadvocatesdedicatingserverstorequestsofsimilarsize,withtheaimofreducingtheaveragejobslowdownthroughseparationoflongandshortjobs.Thepolicyisbasedontheempiricaldistributionoftheworkloadresourcedemands,i.e.,therequestsizesand