Eviction has a proven limit

Why can no eviction policy beat a proven bound, and where must improvement come from instead?

CaseConstructed case · Ifeoma at Dawnpost

The nightly crawl and the viral article

Another set of symptoms, all in one month.

A nightly job crawls the 5 million article archive (400 GB) to build a search index. Each night, at about 02:00, the article cache hit rate falls from 95% to under 30%. It takes hours to recover, and the 06:00 early readers feel it.
One article goes viral on social media. A single cache node, which owns that key, runs at 100% CPU, while the other nodes are nearly idle. Adding more nodes does not help.
The analytics team starts to use the same cache cluster for dashboard results. When their big queries run, the article cache loses memory and the article database gets more load.

The second copy, What makes data cacheable, The derivation ladder and Keeping it honest treated capacity as a single number and assumed that an entry, once cached, could be found. Both assumptions now fail.

How it ends →

The first assumption fails against an impossibility, not just an expense. It is the only limit here that is proved and not merely hard to compute.

Belady's MIN is the best possible eviction rule: when the cache is full, throw out the entry whose next use is farthest in the future. It needs to know the future. Formally, for a cache of size k, every deterministic online paging algorithm is at best k-competitive, which means that on a worst-case request sequence it can make up to k times as many misses as the best offline choice. Both LRU (evict the least recently used entry) and FIFO (evict the oldest entry) reach exactly k. Randomized algorithms do better: the marking algorithm is Θ(log k)-competitive, and that bound is tight up to constant factors.

Two consequences follow. The second is more useful.

First, a correction. LRU and FIFO have the same competitive ratio. LRU's practical advantage over FIFO is large and real, but competitive analysis cannot see it, because the bound comes from an adversarial request stream, and real streams are not adversarial. People quote the theory as if it supported LRU in practice. It does not. Knowing this stops you from expecting theoretical guidance where none exists.

Second, a structural consequence. If no policy can beat the bound, then every real advance comes from changing the request stream, not from improving the policy. The ways to change the stream are: hints, pinning, bypass, admission, and one more that only data systems have, declaration.

Declaration deserves emphasis. It is the one real advantage a data system has over a general-purpose cache:

An engine that knows it is about to scan a 400 GB table knows, before touching a byte, that these pages will not be reused. Belady's rule cannot be achieved in general, but it is partly achievable inside a query engine. This is why scan resistance (protection of the cache from a big one-time scan) in a database buffer pool is a matter of the engine telling the cache the truth, not of the cache guessing cleverly.