Cache eviction

A cache holds less than the data store behind it, so it fills, and every new entry past capacity forces an old one out. The eviction policy picks which entry leaves. That pick sets the hit ratio, the share of reads the cache answers, which is one of a cache's two figures of merit alongside latency (Wikipedia's survey of replacement policies). A better policy holds a higher hit ratio for the same memory, so the same hardware answers more reads without falling through to the store.

The base policies trade simplicity against hit ratio

FIFO evicts entries in the order they arrived and ignores how often each was read (Wikipedia). It costs almost nothing and tracks no access pattern, so its hit ratio trails the alternatives. LRU evicts the least recently used entry, betting that recent use predicts the next use. The bet holds for workloads with temporal locality and breaks on a full scan, which sweeps the whole working set out of the cache. LFU evicts the least frequently used entry, betting on long-run popularity. The bet holds for stable popularity and adapts slowly when the popular set shifts. The unreachable target above all of them is Bélády's optimal policy, which evicts the entry needed furthest in the future and needs knowledge of future requests no online cache holds (Wikipedia).

ARC tunes itself between recency and frequency

The Adaptive Replacement Cache holds two lists, one for entries seen once recently and one for entries seen at least twice recently, plus a history of entries recently evicted from each (Megiddo and Modha). The eviction history drives a feedback loop: a reference to a key in the recency history grows the recency list, a reference in the frequency history grows the frequency list, so the split between recency and frequency tracks the workload with no manual tuning. ARC stays scan-resistant and outperforms LRU across a range of workloads and cache sizes (Megiddo and Modha). IBM developed it at its Almaden Research Center (Wikipedia).

W-TinyLFU admits an entry only when it earns the space

W-TinyLFU asks a different question at insertion: is this new entry worth more than what the cache would drop to fit it? A small LRU admission window catches short recency bursts, and an entry leaving the window faces the TinyLFU admission filter before it earns a place in the main cache (Caffeine's efficiency notes). TinyLFU estimates an entry's historic frequency from a compact sketch built on Bloom-filter counting, so it tracks far more keys than the cache holds while staying small (Einziger, Friedman, and Manes). The policy keeps no evicted keys, unlike ARC, and reaches a near-optimal hit ratio competitive with ARC at a low memory cost, which is why Caffeine runs it as its default.

Production caches run sampled approximations

Production caches often approximate these policies rather than implement them exactly, because exact recency or frequency tracking costs memory and CPU on every access. Redis, for one, samples a small random set of keys on each eviction and removes the best candidate from the sample, which approximates LRU or LFU without the per-key bookkeeping a true implementation needs (Redis key eviction). You raise maxmemory-samples to get closer to true LRU at the cost of CPU (Redis). The policy you name in config sets the strategy, and the cache runs a sampled approximation of it.

Choosing a policy

Start with what your cache engine offers, since an approximated LRU or LFU covers most workloads. Reach past the default in two cases: a scan-heavy workload that thrashes an LRU cache, where a scan-resistant policy like ARC or W-TinyLFU holds a higher hit ratio, or memory tight enough that hit ratio per byte decides your database load. Measure the hit ratio under your own traffic before tuning. A policy that wins on a published benchmark trace loses on a workload it does not match.