Eviction policies

The problem it solves

A cache is full and a new entry needs a home. Something must leave. The policy that decides which is the most over-discussed and least consequential decision in caching — right up until the moment it is the entire problem.

Both halves of that sentence are true and the simulation shows both. On ordinary skewed traffic the five classic policies land within about ten points of one another, which means cache size is the decision and policy is the detail. Then a single sequential scan arrives — a nightly report, an analytics query, a backfill — and LRU collapses to nearly zero while LFU sails through. Knowing the second half is what separates recall from understanding.

The mechanism

Every policy is a guess about the future dressed as a fact about the past.

LRU evicts the least recently used entry, betting that recency predicts reuse. It is right about most workloads, cheap to implement with a hash map and an intrusive doubly-linked list, and it has one catastrophic blind spot.

LFU evicts the least frequently used, betting that popularity predicts reuse. It resists scans by construction — an entry seen once cannot outrank an entry seen a thousand times — and it has the opposite blind spot: it clings to entries that used to be popular. Real implementations add ageing or windowing to forget.

FIFO evicts the oldest inserted entry, ignoring use entirely. It is the cheapest and it is a scan-vulnerable as LRU, for a different reason.

Random picks a victim at random. It sounds like a joke and it is not: it has no pathological ordering to exploit, which makes it the most robust of the five on adversarial or looping workloads. It also needs no metadata at all.

CLOCK is LRU’s practical approximation: entries sit in a circular buffer with a reference bit, a hand sweeps, and an entry with its bit set gets a second chance instead of eviction. One bit per entry instead of two pointers, no list manipulation on every hit, and behaviour close enough to LRU that operating-system page caches have used it for fifty years.

What the simulation shows

Start with the default Zipfian workload. All five policies cluster. The spread is real but small, and the practical conclusion is that arguing about policy while the cache is undersized is the wrong argument.

Now switch the workload to a sequential scan. LRU falls off a cliff. The mechanism is worth stating precisely, because it is the single best-known cache pathology: a scan touches each entry once and never again, so every scanned entry becomes the most recently used, and LRU dutifully evicts everything genuinely popular to make room for data that will never be read again. Worse, it evicts them in exactly the order they will next be needed. LFU, meanwhile, barely notices — a key seen once does not displace a key seen a thousand times.

Then try the looping working set: a working set 10% larger than the cache, walked repeatedly. LRU and FIFO go to zero — every entry is evicted exactly one access before it is wanted, every time round. Random keeps most of it, because random eviction has no ordering for the loop to defeat. This is the cleanest demonstration available that “better policy” is workload-relative.

Finally, mix a scan into normal traffic, which is what production actually looks like: the report runs while users keep browsing. The hit-ratio-over-time chart shows the exact moment the scan arrives.

The numbers worth carrying

On typical skewed web traffic, the five policies land within roughly ten points. If you are choosing between them to gain three points, buy memory instead — the cache hit ratio curve will tell you what three points costs.

On a scan larger than the cache, LRU’s hit ratio for the previously cached working set goes to approximately zero, and stays there until the working set is re-warmed. The recovery cost, not the scan itself, is usually what shows up as an incident.

CLOCK costs one bit per entry against LRU’s two pointers plus list maintenance on every hit — the reason it wins in kernels and in any cache where hits vastly outnumber misses and you do not want a write on the hit path.

Where it breaks down

Uniform cost is assumed. Every policy above treats all entries as equally expensive to recompute. In reality a 5 ms miss and a 5-second miss are not the same loss, and neither is a 100-byte entry and a 10 MB one. Cost-aware and size-aware policies (GDSF, and the size-aware admission in modern CDNs) exist for this, and are worth naming.

Admission beats eviction. The most effective modern development is not a better eviction rule but an admission rule: TinyLFU keeps a compact frequency sketch of what it has seen recently and refuses to admit a new entry unless it looks more valuable than the victim it would displace. A scan’s entries never get in at all. W-TinyLFU (a small LRU window in front of a TinyLFU-guarded main region) is what Caffeine ships and it beats plain LRU across essentially every published trace.

TTLs interact. A policy evicting on capacity and a TTL expiring on time are two different removal mechanisms, and a cache dominated by TTL expiry has a hit ratio the eviction policy barely influences.

Concurrency. Strict LRU requires mutating shared state on every read, which is a contention point at high throughput. This, more than hit ratio, is why real caches approximate: CLOCK, sampled-LRU (Redis picks a few entries at random and evicts the least recently used among them), or amortised buffering of access records.

What people get wrong

“LRU is the best policy.” It is the best default. Name the workload that kills it, or the claim is recall rather than understanding.

“LFU is strictly better because it resists scans.” Plain LFU never forgets. A key that was hot last month can be un-evictable this month. Every usable LFU has ageing.

“Random is a straw man.” Random is the most robust policy on this page against pathological patterns, and Redis’s default allkeys-lru is really sampled random with an LRU tie-break, for precisely that reason.

“Redis LRU is LRU.” It samples five keys by default (maxmemory-samples) and evicts the oldest among them. It is an approximation, tunable, and the default is fine.

In production

Redis offers allkeys-lru, allkeys-lfu, allkeys-random, volatile-* variants and noeviction; the LFU implementation uses a probabilistic counter with decay, which is the ageing mentioned above. Memcached uses a segmented LRU with a background crawler. Caffeine (JVM) and its ports use W-TinyLFU. Linux’s page cache uses two CLOCK-ish lists — active and inactive — with promotion on second access, which is itself a scan-resistance mechanism: a page read once stays in the inactive list and leaves without ever disturbing the active set.

Notice the pattern across all of them: nobody ships plain LRU. Every production cache has some scan resistance, because scans are not hypothetical — they are your backup job, your analytics query, and your migration.

The follow-up questions

“Which eviction policy would you use?” — LRU by default, then immediately: “unless we have scans, in which case the question is admission, not eviction.”

“A nightly report tanks our cache hit ratio. Why?” — The scan pathology. Fixes: a separate cache or replica for analytics, LFU or TinyLFU admission, or marking scan reads as non-caching (SELECT ... /* no cache */, fadvise(NOREUSE), a bypass flag in your client).

“How is LRU implemented?” — Hash map plus intrusive doubly-linked list, O(1) on hit and eviction. Then say why production caches approximate it: a hit becomes a write, and writes contend.

“Your working set is slightly larger than your cache. What happens?” — Under LRU and FIFO, a hit ratio near zero. This is the most counter-intuitive result on the page and the one worth saying unprompted.