Caching in Search Engines

Why remembering answers works for search, and how well. Result caches and postings caches, the hit rate of a cache under a Zipf law of query popularity derived exactly and bounded, a proof that no replacement policy beats the ideal static cache when requests are independent, least-recently-used caches by the Che approximation, the knapsack view of a postings cache, and the arithmetic of expiry by time to live. A seeded synthetic query stream checks each formula. Worked problems size a cache for a million queries, solve a three-query cache exactly, set a time to live and price a two-level cache.

A search engine receives a stream of requests in which 100,000 different queries occur. The most popular one makes up 8.3 percent of the stream, the second half as much, the third a third as much, and so on down a Zipf law. The engine has room to remember the answers to 1,000 queries, one percent of them. What share of the requests can it answer from memory? With the right thousand, 61.9 percent. The rest of this article is the arithmetic behind that number, and the ways a real cache falls short of it.

A cache is a store of results already computed, consulted before computing again. A request answered from it is a hit, any other is a miss, and the hit rate is the share of requests that are hits. Search at scale introduced the two kinds a search engine keeps. A result cache stores the finished results page of a query. A postings cache stores the postings lists of terms in memory, so that a query can be evaluated without reading them from disk. That article said what each is for. This one derives how much each can do.

Here is the route. First we price a hit and a miss, and see what a hit rate is worth. Then we look at what query logs show about repetition, and fix a model: independent requests from a Zipf-like law. Next we derive the hit rate of the best cache the model allows, prove that nothing beats it, and find the ceiling that novelty puts on every cache. Then we turn to a cache that must learn what is popular, the least-recently-used cache, and to streams whose popular queries change. Then come postings caches, where entries differ in size. Finally we treat invalidation: how long an answer may be kept once the index changes. The article assumes Zipf's law as Term Statistics: Zipf's Law and Heaps' Law presents it. Its numbers are computed by tools/experiments/query-processing/caching-in-search-engines.py.

One caution governs the experiments. This site stores no searches: its privacy page says that searches "are processed to return results and are not stored by the site". There is therefore no query log to measure, and every stream below is synthetic, drawn by the script from the model with stated seeds. The experiments check the formulas against the model. They say nothing about how well the model fits real traffic, which is a matter for the cited studies of real logs.

Three kinds of statement appear. The hit-rate formulas, the optimality of the static cache, the knapsack rule and the time-to-live formulas are derived on this page. Findings about real query logs and real engines are cited. The simulation results are reported as what those runs showed.

What a hit is worth

A result-cache hit replaces the whole evaluation of a query with one lookup. If a miss costs $c_{\text{miss}}$, a hit costs $c_{\text{hit}}$, and the hit rate is $h$, the mean cost per request is

$$h\,c_{\text{hit}} + (1 - h)\,c_{\text{miss}}.$$

With a lookup at 1 millisecond, an evaluation at 120 milliseconds and a hit rate of 0.45, the mean falls from 120 to $0.45 \times 1 + 0.55 \times 120 = 66.45$ milliseconds. The evaluation itself is the subject of Dynamic Pruning with MaxScore and WAND, which reduces what a miss costs. A cache reduces how often it is paid. Worked problem 4 adds a second level.

The engine's load falls by the same factor as its cost, since requests answered by the cache never reach the index servers. Cambazoglu and colleagues (2010), describing the result cache of the Yahoo! search engine, give this as the purpose: result caches serve "to reduce the query traffic to back-end servers and also to reduce the average query processing latency".

Everything therefore turns on $h$. What decides it?

Queries repeat, and unevenly

A cache that does not fetch answers ahead of time can only answer a request it has seen before, so the first question is how often requests repeat. Fagni, Perego, Silvestri and Orlando (2006) report three logs of web search engines:

Log Requests Distinct queries Share distinct
Excite, one day in 1997 2,475,684 1,598,908 65%
Tiscali, April 2002 3,278,211 1,538,934 47%
Alta Vista, summer 2001 7,175,648 2,657,410 37%

The counts are their Table I, and the last column is computed from them by this article's script. The paper's text (section 3) says that "about 46%" of the queries of the Tiscali and Alta Vista logs are distinct and 64% of those of the Excite log, so that "only 36% (about 54% in the Tiscali and Alta Vista logs)" are resubmissions. Its own counts bear that out for Excite and Tiscali and not for Alta Vista, where they give 37 percent distinct. A request can be a hit only if its query occurred earlier or its answer was fetched in advance. So for a cache that does not prefetch, the share of requests that are not first occurrences bounds the hit rate on that log, a bound the paper states in its section 3.3: 35 percent on the Excite log, 53 percent on Tiscali and 63 percent on Alta Vista, by the counts.

Repetition is also very uneven. The same authors plot the number of submissions of each query against its popularity rank and report that "query popularity follows an inverse power-law distribution in all the three logs". Cambazoglu and colleagues (2010) describe the consequence as a commonplace of the field: "a few queries have very high frequencies and many appear very infrequently, often just once". The same shape had been found earlier for requests to web pages. Breslau, Cao, Fan, Phillips and Shenker (1999) examined six traces of web proxies and found the request frequencies Zipf-like, with exponents below one that varied from trace to trace, from 0.64 to 0.83. They showed that a simple model of independent requests reproduced how the hit rates of those traces grew with cache size.

That model is the one used here. It is the law of term statistics applied to queries in place of terms.

The model. There are $U$ distinct queries, ranked by popularity. Each request is drawn independently of all others, and is for the query of rank $i$ with probability

$$p_i = \frac{i^{-s}}{H_{U,s}}, \qquad H_{U,s} = \sum_{i=1}^{U} i^{-s},$$

where $s > 0$ is the Zipf exponent and $H_{U,s}$, a generalized harmonic number, makes the probabilities sum to one. For $s = 1$ we write $H_U$. The assumption of independent requests with fixed probabilities is called the independent reference model. In the running example $U = 100{,}000$ and $s = 1$, so $H_U = 12.0901$ and the top query has probability $1/12.0901 = 0.083$.

The model leaves out two things that real traffic has, and both will matter. Popularity changes over time. And requests are not independent: a user who asks for a page of results often asks for the next one soon after, which Fagni and colleagues exploit by prefetching. We return to the first below. Prefetching is outside this article.

The best a cache can do

Suppose the cache holds $C$ answers and we may choose which. Under the model the choice is obvious: the $C$ most popular queries. A cache whose contents are fixed in advance is a static cache. A request is a hit exactly when it is for one of the cached queries, so the hit rate of the ideal static cache is the total probability of the top $C$:

$$h_{\text{static}}(C) = \sum_{i=1}^{C} p_i = \frac{H_{C,s}}{H_{U,s}}.$$

For the running example, $H_{1000} = 7.4855$, and $7.4855/12.0901 = 0.619$. That is the 61.9 percent of the opening.

Is the obvious choice the best, among all the ways a cache could be managed, including ways that change its contents as requests arrive? It is.

Theorem 1 (no policy beats the ideal static cache). Under the independent reference model, consider any cache of capacity $C$ whose contents before each request are a function of the earlier requests and of random choices made independently of the whole request stream. The probability that any given request is a hit is at most $h_{\text{static}}(C)$.

Proof. Fix a request and let $K$ be the set of queries in the cache just before it. $K$ has at most $C$ members, and it is a function of the earlier requests and of the policy's random choices. Under the model the request is independent of the earlier requests. The random choices are independent of all the requests together. So the request is independent of the pair formed by the earlier requests and the random choices, and therefore of $K$. Given $K$, the probability of a hit is then $\sum_{i \in K} p_i$. A sum of at most $C$ of the probabilities is at most the sum of the $C$ largest, which is $p_1 + \cdots + p_C = h_{\text{static}}(C)$. This holds for every value of $K$, so it holds on average over $K$. $\blacksquare$

The theorem covers every policy that uses the history of requests in any way, including replacement policies, a static cache chosen from a training log, and policies that toss coins. The condition on the random choices cannot be weakened to independence from the current and later requests.

Example (why the random choices must be independent of the whole stream). Take two equally likely queries, called 0 and 1, and a cache of one entry. Suppose the policy had access to a bit $Z$ equal to 0 when the first two requests are the same and 1 when they differ. $Z$ is 0 or 1 with probability one half whatever the second request is, so $Z$ is independent of the second request, and of all later ones. Yet the first request and $Z$ together determine the second. A policy that loads the first request's query when $Z = 0$ and the other query when $Z = 1$ hits the second request every time, above $h_{\text{static}}(1) = \tfrac12$. Such a bit is not a coin toss. It is knowledge of the future, and the theorem's condition is what excludes it. The script checks the example by enumeration.

The theorem is about knowledge, not about cleverness. A policy that replaces entries is trying to discover which queries are popular. The static cache is assumed to know. Under the model nothing else is worth knowing, because the next request does not depend on the last. The gap between a real policy and $h_{\text{static}}$ is what it costs not to know the probabilities, and the theorem stops applying as soon as the probabilities move.

The arithmetic of the Zipf law

How does $h_{\text{static}}$ grow with $C$? Here is the idea: a sum of $i^{-s}$ is close to an integral of $x^{-s}$, and the integral has a closed form. The three cases $s = 1$, $s < 1$ and $s > 1$ behave differently.

The case $s = 1$. The function $1/x$ is decreasing, so for every $i \ge 1$,

$$\int_{i}^{i+1} \frac{dx}{x} \;\le\; \frac{1}{i} \;\le\; \int_{i-1}^{i} \frac{dx}{x} \quad (\text{the right side for } i \ge 2).$$

Adding the left inequality over $i = 1, \ldots, n$ gives $\ln(n + 1) \le H_n$. Adding the right one over $i = 2, \ldots, n$ and putting back the first term gives $H_n \le 1 + \ln n$. So

$$\frac{\ln(C + 1)}{1 + \ln U} \;\le\; h_{\text{static}}(C) \;\le\; \frac{1 + \ln C}{\ln(U + 1)}.$$

For $C = 1{,}000$ and $U = 100{,}000$ the bounds are 0.552 and 0.687, around the exact 0.619. The simplest estimate, $\ln C/\ln U$, gives 0.600. The hit rate is roughly the ratio of the logarithms of the two sizes.

Example (a common misstatement). "A cache ten times larger answers ten times as many requests." Under a Zipf law with $s = 1$ it answers a fixed amount more. Since $H_{10C} - H_C$ is close to $\ln 10$ once $C$ is large, each tenfold increase in capacity adds about $\ln 10/H_U$ to the hit rate, which is 0.190 for $U = 100{,}000$. The exact values are 0.429 for $C = 100$, 0.619 for $C = 1{,}000$ and 0.810 for $C = 10{,}000$: two steps of 0.190. The first hundred entries are worth more than the next nine hundred, and those more than the next nine thousand. Breslau and colleagues (1999) derive the same logarithmic growth and note that many measurement studies had observed hit rates growing "in a log-like fashion" with cache size.

The case $s < 1$. The same comparison with $\int x^{-s}\,dx = x^{1-s}/(1-s)$ gives

$$\frac{(n+1)^{1-s} - 1}{1 - s} \;\le\; H_{n,s} \;\le\; 1 + \frac{n^{1-s} - 1}{1 - s}.$$

Both bounds grow like $n^{1-s}/(1-s)$, so for large $C$ and $U$ the hit rate approaches $(C/U)^{1-s}$, a power of the share of queries cached. The approach is slow. For $s = 0.8$ and $U = 100{,}000$ the exact hit rates are 0.179, 0.340 and 0.595 for $C = 100$, 1,000 and 10,000, where $(C/U)^{0.2}$ gives 0.251, 0.398 and 0.631. A flatter popularity curve needs a much larger cache for the same hit rate: at $s = 0.8$, ten thousand entries do less than a thousand do at $s = 1$.

The case $s > 1$. Now the sum converges as $U$ grows, and what matters is the tail left out. Comparing with the integral from the other side,

$$\frac{(C+1)^{1-s} - (U+1)^{1-s}}{s - 1} \;\le\; \sum_{i=C+1}^{U} i^{-s} \;\le\; \frac{C^{1-s} - U^{1-s}}{s - 1},$$

so the miss rate of the ideal static cache falls like $C^{1-s}$. For $s = 1.2$ and $U = 100{,}000$, where $H_{U,s} = 5.092$, the hit rates are 0.708, 0.852 and 0.943. The script checks every bound in this section against the exact sums.

The ceiling set by novelty

Capacity is not the only limit. A request for a query never seen before is a miss for every cache, however large. How common is that?

Let the cache be unlimited and suppose $R$ requests have been made. The next request is for query $i$ with probability $p_i$, and query $i$ has been requested before unless all $R$ earlier requests missed it, which has probability $(1 - p_i)^R$. So the probability that request $R + 1$ is a repeat is

$$\sum_{i=1}^{U} p_i\left(1 - (1 - p_i)^R\right),$$

which is equation 1 of Breslau and colleagues (1999). By the same reasoning, the expected number of distinct queries among the first $R$ requests is $\sum_i \left(1 - (1 - p_i)^R\right)$, and the expected number seen exactly once is $\sum_i R\,p_i(1 - p_i)^{R-1}$.

In the running example, after 100,000 requests the stream has shown 24,449 distinct queries on average, and 16,511 of them have been seen exactly once. The share of those 100,000 requests that repeated an earlier one is 0.756. The probability that the next request is a repeat is 0.835. It was 0.461 after 1,000 requests and 0.650 after 10,000, and it reaches 0.976 after a million. In this model the vocabulary of queries is finite and the ceiling eventually rises to one. Real logs do not behave so. The logs in the table above still had 37 to 65 percent of their requests distinct after millions of requests, which is consistent with new queries continuing to arrive. The model's finite vocabulary makes its ceiling optimistic in that respect.

A cache that has to learn

No engine is handed the probabilities. A cache with a replacement policy starts empty, stores each answer it computes, and when full evicts an entry chosen by rule. The most common rule evicts the entry that has gone longest without a request: the least-recently-used (LRU) policy. How far below the ideal does it fall? Two small cases can be solved exactly, and they show the mechanism.

One entry. An LRU cache with $C = 1$ holds the previous request. A request is a hit exactly when it equals the one before it. Two independent requests are both for query $i$ with probability $p_i^2$, so the hit rate is $\sum_i p_i^2$. The ideal static cache with one entry has hit rate $p_1$. In the running example these are 0.0113 and 0.083. For the exponents 0.8 and 1.2 the one-entry LRU rate is 0.0011 and 0.0534. LRU's single slot is usually occupied by an unpopular query, because most requests are for unpopular queries.

Uniform popularity. If all $U$ queries are equally likely, an LRU cache that has filled holds $C$ distinct queries, and by the argument of Theorem 1 the next request hits with probability $C/U$, the same as any static cache. With nothing to learn, LRU loses nothing.

Between these lies the general case, for which there is an accurate approximation.

The Che approximation

Here is the idea in one sentence: a query is still in an LRU cache if it was requested recently enough, and "recently enough" is very nearly the same length of time for every query.

Precisely, a request for query $i$ is a hit if fewer than $C$ other distinct queries have been requested since the previous request for $i$. Let $t_C$, the characteristic time of the cache, be the number of requests it takes for $C$ distinct queries to appear. It is a random quantity, but for a large cache it varies little, and the approximation treats it as a constant. Treat request times as continuous, with query $i$ requested at rate $p_i$ per request, so that the time since its last request is exponential with mean $1/p_i$. Then:

  • the probability that query $i$ was requested in the last $t_C$ requests is $1 - e^{-p_i t_C}$;
  • the number of distinct queries requested in that time has mean $\sum_i \left(1 - e^{-p_i t_C}\right)$, and it must be $C$.

The second line fixes $t_C$ and the first gives the hit rate:

$$\sum_{i=1}^{U}\left(1 - e^{-p_i t_C}\right) = C, \qquad h_{\text{LRU}}(C) \approx \sum_{i=1}^{U} p_i\left(1 - e^{-p_i t_C}\right).$$

This is the approximation of Che, Tung and Wang as Fricker, Robert and Roberts (2012) state it in their equations 1 and 2. Their paper explains why it is accurate well beyond the conditions its authors supposed, and compares it with simulations, with agreement they describe as "perfect, for all practical purposes" for Zipf popularity. It is an approximation and is not proved here. One check can be made by hand. For uniform popularity, $p_i = 1/U$, the first equation gives $1 - e^{-t_C/U} = C/U$ and the second gives a hit rate of exactly that, $C/U$, which is the true value found above.

For the running example the equation gives a characteristic time of 1,735.5 requests: a query survives in the cache of 1,000 entries for about that long after its last request. The approximate hit rate is 0.506, against 0.619 for the ideal static cache. The difference is the cost of learning. An LRU cache spends part of its capacity on queries that were requested once and will not be requested again soon.

The formulas against a synthetic stream

The script draws streams from the model and runs four caches on them. For each of 30 seeds and each exponent it draws 400,000 requests over $U = 100{,}000$ queries. The first 100,000 are a training log and warm the caches, and the hit rate is measured on the other 300,000. The caches are:

  • the ideal static cache, holding the $C$ queries of highest probability;
  • a trained static cache, holding the $C$ most frequent queries of the training log;
  • an LRU cache;
  • a cache that is half static, trained as above, and half LRU.

The table gives the median over the 30 seeds. The interquartile range is at most 0.002 in every cell.

$s$ $C$ Static, formula Ideal static, simulated LRU, Che approximation LRU, simulated Trained static, simulated
0.8 100 0.179 0.179 0.068 0.068 0.178
0.8 1,000 0.340 0.340 0.204 0.204 0.334
0.8 10,000 0.595 0.595 0.469 0.469 0.566
1.0 100 0.429 0.429 0.290 0.290 0.429
1.0 1,000 0.619 0.619 0.506 0.506 0.615
1.0 10,000 0.810 0.810 0.737 0.737 0.791
1.2 100 0.708 0.708 0.606 0.606 0.707
1.2 1,000 0.852 0.851 0.795 0.795 0.848
1.2 10,000 0.943 0.943 0.918 0.917 0.922

Four things can be read from it.

  • The static formula is exact. The simulated ideal cache agrees with $H_{C,s}/H_{U,s}$ to within 0.001 in every row, as it must, since the formula is the expected value of what the simulation counts.
  • The Che approximation is accurate here. It agrees with the simulated LRU cache to within 0.001 in every row, over hit rates from 0.07 to 0.92.
  • LRU pays for learning. It is below the ideal static cache in every row, by 0.10 on average. The largest gap is 0.139, at $s = 1$ and $C = 100$. Relative to the ideal, the loss is greatest where the cache is small and the curve flat: at $s = 0.8$ and $C = 100$ LRU reaches 0.068 where the ideal reaches 0.179.
  • A training log is a good guide to the head and a poor one to the tail. The trained static cache nearly matches the ideal when $C$ is small. At $C = 10{,}000$ it falls short, by 0.03 for $s = 0.8$. The reason is the ceiling of the previous section: a log of 100,000 requests shows only about 40,000 distinct queries when $s = 0.8$, and about 24,000 when $s = 1$, most of them once, so it cannot tell which of the rare queries are the 10,000 most probable.

The half-and-half cache lies between LRU and the trained static cache in most rows: 0.294, 0.575 and 0.826 for $C = 1{,}000$ at the three exponents. In one row it passes the trained static cache. At $s = 1.2$ and $C = 10{,}000$ it reaches 0.927 against 0.922, because its LRU half picks up popular queries that the training log happened to miss. None of the three learned caches passes the ideal static cache in any row, as Theorem 1 requires of their expected hit rates.

Under the model the trained static cache beats LRU at every size tried. That ranking depends on the one thing the model assumes and real traffic lacks: fixed popularity. The next experiment relaxes it. The setting is the running example with $C = 1{,}000$. After the training log, every 10,000 requests, $m$ of the 1,000 most popular ranks are handed to queries drawn at random from all 100,000, which lose their old ranks in exchange. A query that was obscure becomes popular, and one that was popular fades. The medians over 30 seeds:

Ranks changed per 10,000 requests, $m$ Trained static LRU Half static, half LRU
0 0.615 0.506 0.575
5 0.578 0.506 0.567
20 0.461 0.506 0.545
50 0.319 0.505 0.514

The static cache decays as its contents go out of date. LRU hardly notices the change, since a newly popular query enters it at its first request. The mixed cache is best once the change is appreciable, because its static half still holds the queries that stayed popular and its LRU half follows the ones that moved. The amount of change in this experiment is an arbitrary choice, and the table shows only the direction of the effect.

That direction matches what was measured on real logs. Fagni and colleagues (2006) proposed exactly this mixed design, which they call SDC for static-dynamic cache, and report that it "remarkably outperformed in all the tests either purely static ... or purely dynamic caching", with the best static share depending on the log: 0.4 for Tiscali, 0.8 for Alta Vista and 0.3 for Excite, and little difference in hit rate anywhere between 0.3 and 0.8 (section 5.1). They also observe that the replacement policies they tried for the dynamic part "behaved similarly", and suggest as the reason that the most popular queries were already answered by the static part. Baeza-Yates and colleagues (2007), studying a query log that spanned a year, report that the distribution of queries "changes slowly over time", which is the condition under which a static part trained on the past stays useful.

Postings caches

A result cache answers only a query it has seen. A postings cache answers part of a query it has never seen, as long as the query's terms are common ones. Search at Scale made the point that such hits are less valuable and much more frequent, and Baeza-Yates and colleagues (2007) report it as a measurement: on their log, "caching posting lists can achieve higher hit rates than caching query answers". The Zipf arithmetic suggests why. The hit rate of a cache depends on the share of distinct items it can hold, and the terms that occur in queries are far fewer than the queries that can be built from them.

One thing is new. Result pages are all about the same size, so a result cache holds a fixed number of entries and should hold the most frequent. Postings lists differ in length by orders of magnitude, and a term that is common in queries can also be common in documents, with a long list. A postings cache has a budget of memory, and choosing its contents is a different problem.

The knapsack view. Let term $t$ account for a share $f_t$ of all term lookups, and let its list occupy $z_t$ bytes. A static postings cache of $B$ bytes should hold the set of terms that maximizes $\sum f_t$ subject to $\sum z_t \le B$. This is the knapsack problem. Its natural rule is to rank the terms by $f_t/z_t$, lookups saved per byte, and to fill the cache in that order.

Here is the idea of why the ratio is the right quantity: a byte of cache is worth the lookups it saves, so bytes should go to the lists that save the most lookups per byte.

Theorem 2 (the ratio rule is optimal when lists may be cut). Suppose any fraction $x_t \in [0, 1]$ of a list may be cached, earning $f_t x_t$. Order the terms so that $f_1/z_1 \ge f_2/z_2 \ge \cdots$, cache whole lists in that order while they fit, and cache the fraction of the next list that fills the budget exactly. No other choice with $\sum z_t x_t \le B$ earns more.

Proof. Let $x$ be the choice of the rule and $y$ any other feasible choice. Let $m$ be the term that the rule cuts, or the last term it takes if the budget ends exactly, and let $\rho = f_m/z_m$. For every term before $m$ in the order, $x_t = 1 \ge y_t$ and $f_t/z_t \ge \rho$. For every term after it, $x_t = 0 \le y_t$ and $f_t/z_t \le \rho$. In both cases $(x_t - y_t)(f_t/z_t - \rho) \ge 0$, and for $t = m$ the product is zero. Multiplying by $z_t > 0$ and adding over all terms,

$$\sum_t f_t\,(x_t - y_t) \;\ge\; \rho \sum_t z_t\,(x_t - y_t) = \rho\left(B - \sum_t z_t y_t\right) \;\ge\; 0,$$

where the middle step uses that the rule fills the budget exactly, $\sum z_t x_t = B$ (if all lists fit, then $x_t = 1 \ge y_t$ for every term and the claim is immediate). So $\sum f_t x_t \ge \sum f_t y_t$. $\blacksquare$

A cache cannot keep seven eighths of a list and use it as a whole one, so the theorem gives an upper bound and a guide, not an algorithm. A small example shows both the guide and its limit.

Term Share of lookups $f$ List size (KB) $f$ per megabyte
zinc 0.02 5 4.0
jaguar 0.06 30 2.0
oil 0.12 120 1.0
price 0.20 400 0.5
the 0.30 900 0.33

With a budget of 600 KB the ratio rule takes zinc, jaguar and oil, and then price, which just fits: 555 KB for a share of 0.40. The most requested term, the, is left out. Its list is so long that it saves fewer lookups per byte than any other. The length of such lists is also why a stop list removes so large a share of an index's postings. With a budget of 500 KB the rule takes zinc, jaguar and oil, 155 KB for a share of 0.20, and then finds that price does not fit. Taking price first, with jaguar and zinc, uses 435 KB for a share of 0.28, which is the best any whole lists can do here. The bound of Theorem 2 for 500 KB is 0.3725, from cutting price. So the ratio rule can fall short when one long list is at the margin, and no choice of whole lists can exceed the cut-list bound. Baeza-Yates and colleagues (2007) propose an algorithm for static caching of posting lists and study how to divide memory between cached answers and cached lists. Only the abstract of their paper was read for this article, so its algorithm is not described here.

Invalidation: how long may an answer be kept?

A cached answer is correct for the index that produced it. When the index changes, as Updating an Index describes, the answer may no longer be what the engine would compute. Serving it anyway is fast and wrong. Cambazoglu and colleagues (2010) argue from their experience with a production engine that this is the real problem of result caching at scale, and that the eviction policy is not: what matters is "the ability to cope with changes to the index, i.e., cache freshness". They point out that an engine can keep millions of result entries on disk and still answer faster than by evaluating, so capacity is plentiful, and what limits the cache is how long its entries stay valid.

They distinguish two approaches. A coupled design tells the cache which entries an index change has affected. They judge it "difficult to realize in practice" because determining exactly which results a change affects is costly. A decoupled design invalidates without that knowledge. The simplest decoupled rule is a time to live (TTL): an entry expires a fixed time $\tau$ after it was computed, and the next request for it is a miss that recomputes it. Their own contribution adds refreshing: idle capacity of the back end is used to recompute entries before a request finds them expired.

A time to live trades hits for freshness, and both sides of the trade can be derived.

What a time to live costs in hits

Here is the idea in one sentence: each computed answer serves the requests of the next $\tau$ units of time, so a query asked $\lambda\tau$ times in that window turns one miss into one miss and $\lambda\tau$ hits.

The formal version. Let the requests for one query arrive as a Poisson process of rate $\lambda$, and let the cache be large enough that entries leave only by expiry. Follow the query from one miss to the next. The miss computes the answer at some time $t_0$. Every request in $(t_0, t_0 + \tau]$ is a hit, and their number has mean $\lambda\tau$. The first request after $t_0 + \tau$ is the next miss. A Poisson process has no memory, so what happens after that miss repeats the same pattern independently. Each such cycle contains exactly one miss and on average $\lambda\tau$ hits. The cycles are independent and identically distributed. By the law of large numbers, the long-run share of hits is therefore the mean number of hits per cycle over the mean number of requests per cycle:

$$h(\lambda, \tau) = \frac{\lambda\tau}{1 + \lambda\tau}.$$

A query asked ten times per time to live is a hit 0.909 of the time. One asked once per time to live is a hit half the time, and one asked a tenth as often, 0.091 of the time. For a whole stream with total rate $\Lambda$, in which query $i$ has rate $\Lambda p_i$, the hit rate is the average over requests:

$$h(\tau) = \sum_{i=1}^{U} p_i\,\frac{\Lambda p_i \tau}{1 + \Lambda p_i \tau}.$$

What it buys in freshness

Now suppose the correct answer to a query changes at random, at rate $\mu$, so that an answer computed at $t_0$ is still correct at age $a$ with probability $e^{-\mu a}$. A hit at age $a$ is then stale with probability $1 - e^{-\mu a}$. Within a cycle the hits form a Poisson process on $(t_0, t_0 + \tau]$, so the expected number of stale hits is $\int_0^{\tau} \lambda\left(1 - e^{-\mu a}\right)da = \lambda\left(\tau - \frac{1 - e^{-\mu\tau}}{\mu}\right)$. Dividing by the expected number of hits, $\lambda\tau$:

$$\text{stale share of hits} = 1 - \frac{1 - e^{-\mu\tau}}{\mu\tau}.$$

The rate $\lambda$ has cancelled. The share of served answers that are stale depends only on $\mu\tau$, the expected number of changes during a time to live, and not on how popular the query is. For small $\mu\tau$ it is close to $\mu\tau/2$, since $1 - e^{-x} \approx x - x^2/2$: a hit is on average half a time to live old.

The script checks both formulas on the running example. Requests arrive as a Poisson process at one per unit of time, each computed answer is given an exponential time until it goes stale with $\mu = 1/20{,}000$, and the cache is unlimited. Each of 30 seeds draws 500,000 requests, and those after time 100,000 are counted. The table gives medians.

$\tau$ Hit rate, formula Hit rate, simulated Stale share, formula Stale share, simulated
1,000 0.413 0.413 [0.413, 0.414] 0.025 0.024 [0.023, 0.026]
10,000 0.603 0.603 [0.602, 0.603] 0.213 0.211 [0.207, 0.219]
30,000 0.692 0.692 [0.692, 0.693] 0.482 0.480 [0.472, 0.490]

The brackets are the first and third quartiles over the seeds. Every formula value lies inside the interquartile range of its simulated column. The stale shares vary more from seed to seed than the hit rates, because one stale entry of a popular query accounts for many stale hits. Lengthening the time to live thirtyfold raises the hit rate from 0.413 to 0.692 and raises the share of stale answers among the hits from one in forty to nearly half. That is the trade a time to live sets, and it explains the interest in refreshing: recomputing popular entries in idle time shortens their age without giving up their hits.

Segments make one cache easier than the other

The two kinds of cache age differently, and the reason follows from how an index is updated. In an index made of immutable segments, as Updating an Index describes, a term's postings within one segment never change. A postings cache keyed by segment and term therefore never holds a wrong list. Its entries become useless when their segment is merged away, and they never become incorrect. Deletions are applied from the deletion record at query time and do not touch the lists. A result cache has no such protection. A results page depends on the whole collection, so one new document that belongs in a query's top $k$ makes the cached page stale. This is reasoning from the definitions. It is one more reason an engine keeps both levels. The lower one is safe to keep for as long as its segment lives. The upper one saves more work per hit and must be watched.

Worked problems

No course text sets exercises on caching, so these four problems are posed on the model of this article and on small exact cases. The script recomputes every number.

Problem 1 (sizing a static cache). A stream follows a Zipf law with $s = 1$ over $U = 10^6$ queries. Find the hit rate of the ideal static cache with 100 and with 10,000 entries, and the smallest capacity that answers half of the requests, and nine tenths.

Solution. The hit rates are 0.360 and 0.680. Half the requests need 749 entries. Nine tenths need 237,100.

The harmonic number of a million is $H_U = 14.3927$. Then $H_{100}/H_U = 0.360$ and $H_{10{,}000}/H_U = 0.680$. For the capacities, we need the smallest $C$ with $H_C \ge 0.5\,H_U = 7.196$ and with $H_C \ge 0.9\,H_U = 12.953$. For large $n$, $H_n$ is close to $\ln n + \gamma$ with $\gamma = 0.5772$, Euler's constant, so $C \approx e^{7.196 - 0.5772} = 749$ and $C \approx e^{12.953 - 0.5772} = 237{,}100$. Summing the series term by term, the script finds the same two numbers as the exact answers.

Three quarters of a thousandth of the queries carry half the traffic, and raising the hit rate from one half to nine tenths takes more than three hundred times the cache. The simplest estimate, $\ln C/\ln U$, gives the same picture without a computer: it is 0.5 at $C = \sqrt{U} = 1{,}000$, against the exact 749.

Problem 2 (three queries, solved exactly). Three queries are requested independently with probabilities $\tfrac{6}{11}$, $\tfrac{3}{11}$ and $\tfrac{2}{11}$, a Zipf law with $s = 1$. Find the hit rates of the ideal static cache and of an LRU cache, for capacities 1 and 2, and compare the Che approximation.

Solution.

$C = 1$ $C = 2$
Ideal static 0.545 0.818
LRU, exact 0.405 0.740
LRU, Che approximation 0.390 0.738

Static. The best single entry is the first query, $\tfrac{6}{11} = 0.545$. The best two are the first two, $\tfrac{9}{11} = 0.818$.

LRU with one entry. The hit rate is $\sum p_i^2 = \frac{36 + 9 + 4}{121} = \frac{49}{121} = 0.405$.

LRU with two entries. The cache holds the two most recently requested distinct queries. Let $i$ be the most recent request and $j$ the most recent request that differs from $i$. The last request is $i$ with probability $p_i$. Reading the stream backward from there and skipping repeats of $i$, the first different query is $j$ with probability $p_j/(1 - p_i)$, because the requests are independent. So the cache holds $i$ and $j$ in that order with probability $\pi(i, j) = p_i\,p_j/(1 - p_i)$, and the next request hits with probability $p_i + p_j$. The six ordered pairs give:

Most recent, next $\pi$ Hit probability Product
1, 2 $\frac{18}{55}$ $\frac{9}{11}$ $\frac{162}{605}$
1, 3 $\frac{12}{55}$ $\frac{8}{11}$ $\frac{96}{605}$
2, 1 $\frac{9}{44}$ $\frac{9}{11}$ $\frac{81}{484}$
2, 3 $\frac{3}{44}$ $\frac{5}{11}$ $\frac{15}{484}$
3, 1 $\frac{4}{33}$ $\frac{8}{11}$ $\frac{32}{363}$
3, 2 $\frac{2}{33}$ $\frac{5}{11}$ $\frac{10}{363}$

The probabilities $\pi$ sum to $\frac{30}{55} + \frac{12}{44} + \frac{6}{33} = \frac{6}{11} + \frac{3}{11} + \frac{2}{11} = 1$. The hit rate is $\frac{258}{605} + \frac{96}{484} + \frac{42}{363} \approx 0.740$. The script confirms that these $\pi$ satisfy the balance equations of the cache's Markov chain.

Che. With three items the approximation is outside the large-cache setting it was made for. It gives 0.390 and 0.738, within 0.015 of the exact values. LRU is below the static cache at both sizes, as Theorem 1 requires, and the gap is 0.140 at one entry.

Problem 3 (choosing a time to live). A query is asked 40 times an hour, and the result cache uses a time to live of 15 minutes. (a) What share of its requests are hits? (b) The query's true results change on average once in two hours. What share of the answers served from the cache are stale? (c) What do both become with a time to live of two hours? (d) What is the hit rate of a query asked once a day?

Solution. (a) $\lambda\tau = 40 \times \tfrac14 = 10$, so the hit rate is $\tfrac{10}{11} = 0.909$. (b) $\mu\tau = \tfrac12 \times \tfrac14 = 0.125$, and the stale share is $1 - \frac{1 - e^{-0.125}}{0.125} = 0.060$. (c) With $\tau = 2$ hours, $\lambda\tau = 80$ and the hit rate is $\tfrac{80}{81} = 0.988$, while $\mu\tau = 1$ and the stale share is $1 - (1 - e^{-1}) = e^{-1} = 0.368$. Eight times the time to live gains eight points of hit rate and makes more than a third of the cached answers wrong. (d) $\lambda\tau = \tfrac{1}{24} \times \tfrac14 = \tfrac{1}{96}$, and the hit rate is $\tfrac{1}{97} = 0.010$. A time to live shorter than the gap between a query's requests makes its entry nearly useless, which is why the hit rate under a time to live is dominated by the head of the popularity curve.

Problem 4 (two levels). An engine evaluates a query in 120 milliseconds. A result cache answers in 1 millisecond and has a hit rate of 0.45. Among the queries that miss it, 80 percent find all their postings lists in a postings cache, which shortens their evaluation by 70 milliseconds. Find the mean time per query with the result cache alone and with both.

Solution. With the result cache alone the mean is $0.45 \times 1 + 0.55 \times 120 = 66.45$ milliseconds. With both, a result-cache miss costs $0.8 \times 50 + 0.2 \times 120 = 64$ milliseconds on average, and the mean is $0.45 \times 1 + 0.55 \times 64 = 35.65$ milliseconds. The two levels together remove 70 percent of the time. The postings cache is consulted only on the 55 percent of requests that miss the result cache, and saves less per hit, but its hit rate among those is high, since queries that are new as wholes are mostly built from terms that are not.

What we have learned

Caching works for search because requests repeat and repeat unevenly. Under a Zipf law with independent requests, the best cache holds the most popular queries, its hit rate is the ratio of generalized harmonic numbers $H_{C,s}/H_{U,s}$, and no replacement policy can beat it. For $s = 1$ that rate is close to $\ln C/\ln U$, so each tenfold increase in capacity adds the same amount. A least-recently-used cache, which must learn what is popular, falls below the ideal by an amount the Che approximation predicts to within 0.001 on the synthetic streams. When popularity drifts, the ranking of static and learned caches reverses, and a mixture does best. A postings cache is a knapsack, filled by lookups saved per byte. A time to live $\tau$ gives a query of rate $\lambda$ the hit rate $\lambda\tau/(1 + \lambda\tau)$ and makes a share $1 - (1 - e^{-\mu\tau})/(\mu\tau)$ of the cached answers stale. All the measurements here are on synthetic streams, because the site keeps no query log.

So far one engine has held one index, however it is updated and however its answers are remembered. The last article of the unit takes up the case in which the documents are in several engines that cannot be merged, and a query must first decide which of them to ask: Federated Search.

References

  • Baeza-Yates, R., Gionis, A., Junqueira, F., Murdock, V., Plachouras, V., and Silvestri, F. (2007). The impact of caching on search engines. In Proceedings of SIGIR 2007, 183–190. record · 2 pages
  • Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. (1999). Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of IEEE INFOCOM 1999, 126–134. record
  • Cambazoglu, B. B., Junqueira, F. P., Plachouras, V., Banachowski, S., Cui, B., Lim, S., and Bridge, B. (2010). A refreshing perspective of search engine caching. In Proceedings of WWW 2010, 181–190. record
  • Fagni, T., Perego, R., Silvestri, F., and Orlando, S. (2006). Boosting the performance of Web search engines: Caching and prefetching query results by exploiting historical usage data. ACM Transactions on Information Systems, 24(1), 51–78. record · 2 pages
  • Fricker, C., Robert, P., and Roberts, J. (2012). A versatile and accurate approximation for LRU cache performance. arXiv:1202.3974. record