Cache Eviction Policies

Chapter 05 · Caching

Caches have limited memory. When full, you must evict something. The eviction policy decides what gets thrown out and is one of the highest-leverage tuning knobs in your system.

Why eviction matters

A cache is a finite-size store. The point is to keep the most useful data in memory. As new data comes in and the cache fills up, something must leave. The eviction policy decides what.

A bad eviction policy can wreck a cache's hit rate. Worst case, the cache evicts hot data and keeps cold data. Now every request misses, and the cache adds latency without saving any work.

The classic policies

LRU (Least Recently Used)

Throw out the item that was accessed longest ago. The most popular default for a reason: it tracks "still being used" well. If something has been read in the last few minutes, keep it. If nothing has touched it in an hour, it's probably done.

Implementation: a doubly-linked list combined with a hash map. Each access moves the item to the front of the list; eviction removes from the back. O(1) for both ops.

LFU (Least Frequently Used)

Throw out the item that has been accessed fewest times. Better than LRU when access frequency is the right signal (not recency). The classic example: the home page is hit a million times an hour and would be wrongly evicted by LRU during a quiet stretch.

Cost: tracking frequencies has overhead, and "popular long ago" items can stick around forever (the cold start problem). Modern variants (LFU with aging, TinyLFU) fix this.

FIFO (First In, First Out)

Evict whatever entered the cache first. Simple, fast, but ignores how often items are used. Rare in real caches.

Random

Evict a random item. Sounds dumb, but at very high speeds with similar access distributions it performs surprisingly close to LRU and uses no extra memory. Used in some HW caches.

TTL (Time To Live)

Not really an eviction policy on its own; rather a time-based expiry. Each item has a max age. After that, it's gone whether memory is full or not. Combined with LRU/LFU for the eviction-on-pressure decision.

LRU keeps the recently used at the front. The oldest gets evicted when space runs out.

Try it: LRU vs LFU vs FIFO on the same access pattern

Three caches of size 4 receive the same sequence. Generate a skewed pattern (some keys are hot) and see hit rates diverge.

LRU

LFU

FIFO

Hit rate: 0%

Last access: -

Modern algorithms worth knowing

ARC (Adaptive Replacement Cache). Balances recency and frequency. Used by ZFS. Patented (originally), but the patent has expired.

TinyLFU and W-TinyLFU. The current state of the art for in-memory caches. Used by Caffeine (Java) and other modern caches. Excellent hit rates with low memory overhead.

2Q. Two queues, one for first-time hits, one for repeat hits. Promotes from short to long. Decent compromise.

How to actually choose

Workload	Best policy
General purpose web cache	LRU (or W-TinyLFU)
Highly skewed access (a few hot items)	LFU or W-TinyLFU
Time-windowed data	TTL primary, LRU secondary
Streaming / scan-heavy	Random or FIFO (LRU performs poorly)

Sizing the cache The right cache size is roughly the size of your hot working set. Watch hit rate as cache grows. Once doubling memory only nudges hit rate up by 1-2%, you've hit the curve's knee. Spending more is mostly waste.

Redis defaults

Redis offers noeviction (default; refuses writes when full), allkeys-lru, allkeys-lfu, volatile-lru (only items with a TTL), and a few more. For a general cache, allkeys-lru is a sensible starting point. Set maxmemory and let Redis manage the rest.

← Previous

Caching Strategies

Distributed Caching