Interview questions

Try each one before you open the answer.

What a cache is, and what it costs

1Why is a cache always potentially stale, even when it is working correctly?

A cache is a second copy of the data that can be read without asking the original, and nothing forces the two copies to agree. So staleness is the default, not a bug. It is bounded only by what you add on top: a time-to-live (TTL), invalidation messages, or version numbers.

2A cache serves 95% of reads. How dependent is the system on it?

Very. The store behind it now sees only 1 read in 20. This dependency, the cache's leverage, is 1 / (1 − h), where h is the hit rate: at h = 95% it is 20 to 1. If the cache disappears, the store gets 20 times the load it normally sees, and it was probably sized for the normal load.

3The hit rate falls from 99% to 98%. What happens to the database behind the cache?

Its load doubles. Misses go from 1% of reads to 2%, so at λ reads per second the database sees 0.02λ instead of 0.01λ. A one-point drop looks small on a dashboard and is a 2× change for the store.

4When does caching a computed result pay for itself?

When each version of the result is read often enough to repay the cost of producing it. As an inequality, λ / w > P / S:

λ is reads per second and w is changes (new versions) per second, so λ / w is reads per version;
P is the cost of producing the entry, and S is what each hit saves.

If the data changes nearly as often as it is read, each entry is thrown away before it earns back P.

5An object is read very heavily. Does that make it a good candidate for caching?

Not by itself. Volume does not decide; the ratio of reads to writes does, because it says how many reads each cached version serves before it changes. A heavily read object that changes on most reads gains nothing. A modestly read object that never changes is ideal.

Hit rate, sizing and tiers

6What is reuse distance, and why does it predict cache hits better than the time since a key was last accessed?

Reuse distance is the number of distinct other keys accessed between two accesses to the same key. It is what matters because an entry is evicted when enough new, distinct items push it out, not when the clock moves. A key reused after an hour with nothing else touched in between still hits; a key reused after a second, with millions of distinct keys in between, misses.

7How can one trace of requests predict the hit rate of an LRU cache at every possible size?

By Mattson's result: under LRU, an access hits if and only if its reuse distance is smaller than the cache size in entries. So one histogram of reuse distances gives the miss ratio at every size at once, the miss-ratio curve (MRC). Sampling methods such as SHARDS make the histogram cheap to build from production traffic.

8For which eviction policies can you not read the miss-ratio curve off a reuse-distance histogram?

For any policy that is not a stack algorithm, one where a bigger cache always holds everything a smaller one would. LRU is one. FIFO, CLOCK, random eviction and any policy with an admission filter are not, and caches with variable item sizes break the property too. For those, each cache size has to be simulated.

9Key popularity is skewed. How does the amount of skew change the way a cache must grow as the data grows?

Popularity usually follows a Zipf distribution with exponent α: the larger α, the more traffic goes to the top keys. Above α = 1, the cache size needed for a given hit rate stays about the same however large the data set becomes. At or below α = 1, a fixed-size cache loses hit rate as the data grows, silently, with no change to your code or configuration.

10Your cache has a 95% hit rate. Why can it not improve your p99 latency?

Because the slowest 5% of requests are the misses. Every percentile above h, here above p95, is made only of misses, so p99 is a miss latency whatever the cache does. To improve the tail, make the miss path faster, hedge slow requests or shed load; a bigger cache does not help.

What to cache: results, metadata, views and absences

15You cache query results keyed by the query text. What else must go into the cache key?

Everything the result depends on that is not in the text: session settings, the user's identity and permissions, the snapshot (data version) the query read, and the values of volatile functions such as the current time. Leave any of these out and two users, or two moments, get each other's answers. Sometimes that is a security bug, not just a stale one.

Freshness, invalidation and stampedes

19What are the ways to keep a cache close to the truth, and who pays for each?

There are three, and each is paid in a different currency:

Coordination (write-through, invalidation broadcasts): the writer pays, with extra work on every write.
Staleness (TTLs, serving stale data): the reader pays, silently, by sometimes getting old data.
Verification (ETags, leases, conditional GETs): the reader pays a round trip, but without the payload.

There is no fourth currency; every freshness scheme mixes these three.

20Write-through, write-around and write-back are often presented as three settings of one dial. Why is that misleading?

They mix two independent decisions. One is write routing: where a write goes (the cache and the store, the store only, or the cache first). The other is freshness bounding: how the cache is kept close to the truth (not at all, TTL, versions, invalidation or leases). You choose both, and some combinations of the two are unsafe and must stay empty.

21When should a write also go into the cache (write-through), and when should it skip the cache (write-around)?

Ask how likely the written key is to be read soon after the write. If the write predicts a read, such as a user's session, cart or own profile, write through so that the read hits. If it does not, as with event ingestion or bulk loads, write around, so that written keys do not push useful entries out of the cache.

Eviction, admission and distribution

31Why can no eviction policy be optimal, and what follows from that?

Eviction is an online problem: the policy must choose without knowing future requests. For a cache of k entries, any deterministic policy can be made to miss k times as often as the best policy that knows the future, and LRU and FIFO both reach exactly that bound; randomized policies do no better than Θ(log k). So big improvements come from changing what reaches the cache rather than from cleverer eviction: hints, bypass, admission filters, and queries that declare they will not reuse what they read.