-
High performance query processing is fundamental for the success of a Web
search engine. In fact, Web search engine can receive billions of queries per
day [
5
]. Additionally, the issuing users are often impatient and expect
subsecond response times to their queries (e.g., 500 ms). Indeed, users become less
engaged [
1
] or migrate to other search services [
11
] when a search engine fails
to provide fast responses to queries. For such reasons, search companies adopt
distributed query processing strategies to cope with huge volumes of incoming
queries and to provide sub-second response times.
Web search engines perform distributed query processing on computer
clusters composed by thousands of computers and hosted in large data centers [
5
].
While such facilities enable large-scale online services, they also raise economical
and environmental concerns. Indeed, a large-scale data center { like those used
by Web search engines { can draw tens of megawatts of electricity to operate
and it can cost 9 million US dollars per year in terms of energy expenditure [
8
].
Therefore, an important problem to address is how to reduce the energy
expenditure of data centers. Additionally, producing and consuming electricity can
involve the emission of carbon dioxide, which is the main cause of global
warming due to the greenhouse e ect. In 2007, the Information and Communication
Technology (ICT) sector has been reported to be responsible for roughly 2% of
global carbon emissions, with general purpose data centers accounting for 14% of
the ICT footprint. These emission levels were projected to more than double by
2020 [
13
]. Therefore, another problem to tackle is how to reduce these emissions
and the negative impact of the data centers on the environment.
Obviously, a possible solution to these challenges consists in designing more
energy-e cient data centers, which consume less energy and, consequently,
pollute and cost less. In the past, a large part of the energy consumption of a data
center could be accounted to ine ciencies in its cooling and power supply
systems. However, search companies already adopt state-of-the art techniques to
reduce the energy wastage of such systems1,2, leaving little room for more
improvements in those areas. Indeed, the energy consumption of a state-of-the-art
data center would be reduced by less than 24% if all the overheads in its cooling
and power supply systems were eliminated [
2
]. Therefore, new approaches are
necessary to mitigate the environmental impact and the energy expenditure of
Web search engines.
One option consists in using green energy. In fact, several search companies
use green energy to partially power their data centers, i.e., energy which comes
from resources that are renewable and do not emit carbon dioxide, such as
sunlight and wind3,4,5. At the same time, Web search engines experience spatial
and temporal variations in electricity prices [
10
] as they distribute their
infrastructures and operations across several, geographically distant data centers [
5
].
Stemming from these observations, we propose a novel query forwarding
algorithm that exploits both the green energy sources available at di erent data
centers and the di erences in market energy prices [
3
]. The main idea is to
dispatch queries from the data center that rstly received the requests to a di erent
one, if the latter can rely on green energy or cheaper energy sources than the
former. The problem of exploiting di erent energy sources to reduce costs when
forwarding queries is modeled as a Minimum Cost Flow Problem. The model
takes into account the di erent and limited processing capacities of data
centers, query response time constraints and communication latencies among sites.
We evaluate the proposed algorithm using workloads obtained from the Yahoo
search engine, together with realistic electricity price data. Our experimental
results show that the proposed solution maintains an high query throughput,
while reducing by up to 25% the energy operational costs of multi-center search
engines. Moreover, our algorithm can reduce by almost 6% the consumption of
non-green energy.
The energy expenditure and carbon footprint of a search company can also
be mitigated by reducing the energy consumption of its computing resources. In
particular, reducing the energy consumption of CPUs represents an attractive
venue for Web search engines. In fact, CPUs are the most energy consuming
component in servers dedicated to query processing, accounting for 40% of total
1 https://www.google.com/about/datacenters/efficiency/internal/
2 https://www.microsoft.com/about/csr/downloadhandler.ashx?Id=02-01-12
3 https://environment.google/
4 https://www.microsoft.com/about/csr/environment/
5 https://sustainability.fb.com
energy consumption when a server is idle and for 66% of total energy
consumption when it is fully utilized [
2
]. Dynamic Voltage and Frequency Scaling (DVFS)
technologies can be used to reduce the CPU energy consumption of a server [
12
].
DVFS permits to adjust the frequency and voltage at which the CPU cores
operate, trading o performance for power consumption. In fact, higher core
frequencies mean faster computations but higher power consumption, while lower
frequencies lead to slower computations but reduced power consumption.
However, carefulness is required when reducing the operating frequency of the CPU
cores since low frequencies entail longer query processing times that may be
unacceptable for the users.
Typically, DVFS mechanisms are managed by operating system (OS)
components, called frequency governors [
4, 14
]. However, the OS misses
domainspeci c information regarding the utilization and load of the query processing
application. This knowledge can be exploited to better throttle the frequency of
the CPU cores, thereby reducing the power consumption of a query processing
server. Therefore, in [
6
] we propose to delegate the CPU power management
from the OS frequency governors to the query processing application, and we
devise search engine-speci c frequency governors. We experimentally evaluate
such governors upon the TREC ClueWeb09B corpus and the query stream from
the MSN 2006 query log. Results show that the knowledge of the query
processing server utilization and load facilitates a more re ned control of the CPU
to achieve power savings. In fact, the proposed search engine-speci c governors
can reduce up to 24% a server power consumption, with only limited (but
uncontrollable) drawbacks in the quality of search results with respect to a system
operating at maximum CPU frequency.
Another important aspect that can be exploited to reduce the energy
consumption of a server is the fact that users can hardly notice response times that
are faster than their expectations [
1, 11
]. Therefore, we advise that Web search
engines should not process queries faster than user expectations and,
consequently, we propose the Predictive Energy Saving Online Scheduling (PESOS)
algorithm [
7
]. PESOS selects the most appropriate CPU frequency to process a
query by its deadline, on a per-core basis. It considers the latency requirement
of queries as an explicit parameter, and it tries to process queries no faster than
required. In doing so, the CPU energy consumption is reduced while respecting
the query latency constraints. PESOS bases its decision on query e ciency
predictors, which are techniques to estimate the processing volume and processing
time of a query before its execution [
9
]. We experimentally evaluate PESOS upon
the TREC ClueWeb09B collection and the MSN 2006 query log. Depending on
the required latency, results show that PESOS can reduce the CPU energy
consumption of a query processing server from 24% up to 48% when compared to
an high performance system running at maximum CPU core frequency. Also,
PESOS outperforms our best search engine-speci c frequency governor [
6
] with
a 20% energy saving, while the competitor requires a ne parameter tuning and
it may incurs in uncontrollable latency violations.