The eviction policies compared
Which policy fits which position in a hierarchy, and why does randomized eviction have the best worst case?
The policies, compared properly
| Policy | Signal | Per-entry state | Write on the read path? | Pathology | Best position in a hierarchy |
|---|---|---|---|---|---|
| FIFO | insertion order | none | no | ignores locality entirely | bottom tiers and very large caches, where metadata and contention dominate |
| LRU | recency | list pointers | yes | a cyclic scan just larger than C gives 0% hits | top tier only |
| LFU (without aging) | frequency | counter | yes | pollution by dead popularity | nowhere, unless aged |
| LRU-K / 2Q / ARC | recency + frequency | more | yes | many parameters to tune | built for filtered streams, such as buffer pools |
| W-TinyLFU | aged sketch + small window | ~10 bits, amortized | no (batched) | needs a workload with structure | general default |
| Cost-aware (GDSF) | f · c / s | counter + cost | yes | feedback oscillation | mixed cost classes |
| Random / marking | none | none (marking: one bit) | no | exploits no locality | best provable worst case; no contention |
(A filtered stream is one where an earlier cache has already taken the easy repeats away, as What makes data cacheable explained.)
Two rows deserve attention.
FIFO's return is real current engineering practice, not nostalgia. Recent research shows that FIFO variants can match the hit rates of the LRU family at very large scale, with much less metadata and no lock on the read path. The reason comes from What makes data cacheable: at the bottom of a hierarchy, the stream has already lost its recency (the upper tiers absorbed the repeats), so LRU's signal is worth little, while its contention cost is not.
Randomized eviction (the marking algorithm) has a provably better worst case, at one bit per entry and zero contention. That is a strange fact: the simplest policy is the best behaved in theory. It loses in practice only because real streams have the locality that the adversarial bound ignores. (The Θ(log k) guarantee is proved for the marking algorithm, which evicts a random unmarked entry. Plain random eviction is k-competitive, the same as LRU.)
Compression: Position and cost variance choose the policy. A read that changes state is the hidden cost. The best-behaved policy in theory needs only one bit per entry.