ENERGY-EFFICIENT QUERY PROCESSING IN WEB SEARCH ENGINES
ABSTRACT
Web search engines are composed by thousands of query processing nodes, i.e., servers dedicated to process user queries.Such many servers consume a significant amount of energy, mostly accountable to their CPUs, but they are necessary to ensure lowlatencies, since users expect sub-second response times (e.g., 500 ms). However, users can hardly notice response times that are fasterthan their expectations. Hence, we propose the Predictive Energy Saving Online Scheduling Algorithm (PESOS) to select the mostappropriate CPU frequency to process a query on a per-core basis. PESOS aims at process queries by their deadlines, and leveragehigh-level scheduling information to reduce the CPU energy consumption of a query processing node. PESOS bases its decision onquery efficiency predictors, estimating the processing volume and processing time of a query. We experimentally evaluate PESOS uponthe TREC ClueWeb09B collection and the MSN2006 query log. Results show that PESOS can reduce the CPU energy consumptionof a query processing node up to _48% compared to a system running at maximum CPU core frequency. PESOS outperforms alsothe best state-of-the-art competitor with a _20% energy saving, while the competitor requires a fine parameter tuning and it mayincurs in uncontrollable latency violations.
EXISTING SYSTEM:
While Web search engines can consume tens of megawattsof electric power to operate, there is only a limited bodyof research that aims to reduce the energy expenditure ofWeb search engines. These works can be divided in threecategories which focus on different level of a Web searchengine architecture: 1) geographically distributed datacenters,2) processing clusters within a datacenter, and 3) a singlequery processing node.The works in focus on multi-site Websearch engines, i.e., search engines composed by multiple andgeographically distant datacenters. These studies propose touse query forwarding, i.e., to shift the query workload betweendatacenters. Kayaaslan et al. consider a scenario wheredatacenters hold the same replica of the inverted index. Theypropose to use query forwarding to exploit the difference inenergy price at different sites, due to the different datacenterlocations and timezones. In this way, they aim to minimize theenergy expenditure of the search engine. At the same time, theapproach ensures that the remote sites can process forwardedqueries without exceeding their processing capacity. Blancoet al. extend this idea by forwarding queries towardsdatacenters that can use renewable energy sources that areboth environmentally friendly and economically convenient.Teymorian et al., instead, consider a scenario where eachsite hold a different inverted index. In their approach, theauthors use query forwarding to maximize the quality ofsearch results, collecting relevant document from the differentsites, while satisfying energy cost budget constraints. Queryforwarding techniques may be applied in conjunction withPESOS to deploy more energy-efficient architectures.The works infocus on reducing the energyconsumption of query processing node clusters within a singledatacenter. Sazoglu et al. investigate the role of resultcaching in the energy expenditure of search engines. Theypresent a financial cost metric to measure the price of cachemisses and find that cost-aware caching strategies can reducethe energy expenditure of a datacenter when there is an highvariation of energy prices during the day. Freire et al. propose a self-adaptive model that exploits the historical andcurrent query loads of the system. The model autonomouslydecide whether to activate a query processing node, to provideacceptable query response times, or put it in standby to saveenergy.
PROPOSED SYSTEM:
In this work we propose the Predictive Energy Saving OnlineScheduling algorithm (PESOS), which considers the taillatency requirement of queries as an explicit parameter. Viathe DVFS technology, PESOS selects the most appropriateCPU frequency to process a query on a per-core basis, sothat the CPU energy consumption is reduced while respectinga required tail latency. The algorithm bases its decision onquery efficiency predictors rather than core utilization. Queryefficiency predictors are techniques to estimate the processingtime of a query before its processing. They have been proposedto improve the performance of a search engine, for instance totake decision about query scheduling or query processingparallelization However, to the best of our knowledge,query efficiency predictor have not been considered forreducing the energy consumption of query processing nodes.We build upon the approach described in and proposetwo novel query efficiency predictor techniques: one to estimatethe number of postings that must be scored to process aquery, and one to estimate the response time of a query undera particular core frequency given the number of postings toscore. PESOS exploits these two predictors to determine whichis the lowest possible core frequency that can be used to process a query, so that the CPU energy consumption is reducedwhile satisfying the required tail latency. As predictors can beinaccurate, in this work we also propose and investigate a wayto compensate prediction errors using the root mean squareerror of the predictors.We experimentally evaluate PESOS upon the TRECClueWeb09 corpus and the query stream from the MSN2006query log. We compare the performance of our approachwith those of three baselines: perf , which always usesthe maximum CPU core frequency, power, which throttlesCPU core frequencies according to the core utilizations, andcons , which performs frequency throttling according tothe query server utilization. PESOS, with predictors correction,is able to meet the tail latency requirements while reducingthe CPU energy consumption from _24% up to _44%with respect to perf and up to _20% with respect to cons,which however incurs in uncontrollable latency violations.Moreover, the experiments show that energy consumption canbe further reduced by PESOS when prediction correction isnot used, but with higher tail latencies.
Conclusions
In this paper we proposed the Predictive Energy SavingOnline Scheduling (PESOS) algorithm. In the context ofWeb search engines, PESOS aims to reduce the CPU energyconsumption of a query processing node while imposinga required tail latency on the query response times. Foreach query, PESOS selects the lowest possible CPU corefrequency such that the energy consumption is reduced andthe deadlines are respected. PESOS selects the right CPU corefrequency exploiting two different kinds of query efficiencypredictors (QEPs). The first QEP estimates the processingvolume of queries. The second QEP estimates the queryprocessing times under different core frequencies, given thenumber of postings to score. Since QEPs can be inaccurate,during their training we recorded the root mean square error(RMSE) of the predictions. In this work, we proposed to sumthe RMSE to the actual predictions to compensate predictionerrors.We then defined two possible configuration for PESOS:time conservative, where prediction correction is enforced, andenergy conservative, where QEPs are left unmodified.We experimentally evaluated the performance of PESOSusing the ClueWeb09B corpus and processing queries fromthe MSN2006 log applying two different dynamic pruningretrieval strategies: MaxScore and WAND. We compared theperformance of PESOS with those of three baselines: perf,which always uses the maximum CPU core frequency, power,which throttles frequencies according to the core utilizations,and cons, which throttles frequencies according to the utilizationof the query servers.We found that time conservative PESOSwas able to meet a required tail latency of 500 and 1,000ms for the same workload sustainable by perf. At the sametime, time conservative PESOS was able to reduce the CPUenergy consumption of the CPU by _12% with WAND up to_25% with MaxScore, for which we could train more accuratequery efficiency predictors than for WAND. Greater energysavings were observable with energy conservative PESOS, butat the cost of higher latencies. Predictors correction is hencenecessary to obtain the required tail latency, still providingsignificant energy savings. Moreover, we processed a realisticquery workload which reflects the query arrivals of one dayof the MSN2006 log. We found that time conservative PESOSwas able to meet a 500 ms (with very few violations) and a1,000 ms tail latency requirements, while reducing the CPUenergy consumption, respectively, by _24% and by _44%when compared to perf. From the same set of experiments, wereported that power can reduce the CPU energy consumptionby just _4% with respect to perf. On the other hand, conswas able to reduce the CPU energy consumption by _27% butincurring in considerable latency violations. We justified thesuperior perf provided by PESOS thanks to the applicationlevelinformation exploited by our algorithm, such as theknowledge about the state of the query queues and the queryefficiency predictions.
References
[1] L. A. Barroso, J. Clidaras, and U. H¨olzle, The Datacenter as aComputer: An Introduction to the Design of Warehouse-ScaleMachines, 2nd ed. Morgan & Claypool Publishers, 2013.
[2] I. Arapakis, X. Bai, and B. B. Cambazoglu, “Impact of responselatency on user behavior in web search,” in Proc. SIGIR, 2014,pp. 103–112.
[3] U.S. Department of Energy, “Quick start guide to increasedata center energy efficiency,” 2009. [Online]. Available:http://goo.gl/ovDP26
[4] The Climate Group for the Global e-Sustainability Initiative,“Smart 2020: Enabling the low carbon economy in theinformation age,” 2008. [Online]. Available: http://goo.gl/w5gMXa
[5] European Commission – Joint Research Centre, “The EuropeanCode of Conduct for Energy Efficiency in Data Centre.” [Online].Available: http://goo.gl/wmqYLQ
[6] U.S. Department of Energy, “Best Practices Guide forEnergy-Efficient Data Center Design.” [Online]. Available:http://goo.gl/pikFFv
[7] D. C. Snowdon, S. Ruocco, and G. Heiser, “Power Managementand Dynamic Voltage Scaling: Myths and Facts,” in Proc. ofWorkshop on Power Aware Real-time Computing, 2005.
[8] The Linux Kernel Archives, “Intel P-State driver.” [Online].Available: https://goo.gl/w9JyBa
[9] D. Brodowski, “CPU frequency and voltage scaling code in theLinux kernel.” [Online]. Available: https://goo.gl/QSkft2
[10] C. Macdonald, N. Tonellotto, and I. Ounis, “Learning to predictresponse times for online query scheduling,” in Proc. SIGIR,2012, pp. 621–630.
[11] M. Jeon, S. Kim, S.-w. Hwang, Y. He, S. Elnikety, A. L. Cox,and S. Rixner, “Predictive parallelization: Taming tail latenciesin web search,” in Proc. SIGIR, 2014, pp. 253–262.