Cache Eviction Policies: LRU, LFU and TTL
On this page
Cache eviction vs expiration (TTL)
A cache has fixed memory. Data leaves it in two ways, and they solve different problems:
- Eviction: the cache is full and needs room. A policy picks a victim.
- Expiry (TTL): an entry has a time-to-live and is treated as gone when it passes, even if memory is plentiful.
Eviction protects memory. TTL protects freshness. Most caches use both.
Cache eviction policies: LRU, LFU and more
| Policy | Evicts | Good when |
|---|---|---|
| LRU, least recently used | The entry untouched the longest | Recent access predicts future access, the common case |
| LFU, least frequently used | The entry used least often | A stable set of popular items should survive bursts of one-off reads |
| FIFO | The oldest entry | Rarely the best choice |
| Random | Any entry | Very cheap; surprisingly decent with many keys |
| TTL-based (volatile-ttl in Redis) | The entry closest to expiry | Entries with TTLs where soon-to-expire ones matter least |
LRU's weakness: one batch job that reads a million old products once makes them all "recent", pushing out the popular ones. LFU resists that, because one access doesn't make an item frequent. Redis approximates both by sampling a few keys and evicting the best candidate among them, rather than tracking exact order.
In Redis, the volatile-* policies only evict keys that have a TTL. If your code sets keys without one, a full Redis under volatile-lru has nothing it may evict and starts rejecting writes. Use allkeys-lru or allkeys-lfu for a pure cache.
How to choose a cache TTL
Two questions:
- How often does the data change, and how stale may it be? Exchange rates: seconds. A product description: minutes to hours. A country list: days.
- How expensive is a miss? A cheap query can have a short TTL. A 2-second report should be cached longer and refreshed deliberately.
If you also invalidate on write (Day 36), the TTL becomes a safety net that bounds staleness when an invalidation is missed, so it can be longer.
Sliding expiration resets the clock on every read. In .NET's IMemoryCache, an entry with only a sliding expiration that's read constantly never expires, so it never picks up changes. Combine it with an absolute expiration to put a ceiling on its age.
Cache misses for things that don't exist. Requests for product 999999, which doesn't exist, miss the cache every time and hit the database every time. A bot hammering random ids gets straight through your cache. Cache the "not found" result too, with a short TTL such as 30 seconds.
Why TTLs need jitter
Warm the cache at 9:00 with 100,000 keys, all with a TTL of exactly 3,600 seconds, and at 10:00 they all expire together. The next second, the database receives the misses for all of them. Add jitter, a random offset, to every TTL:
ttl = 3600 + random(0, 600) # expiries spread over 10 minutesThe same applies after deploys and restarts that warm caches in bulk. Day 39 covers the related problem of one hot key expiring.
Worked example: LRU vs LFU for two caches
- Product pages: millions of possible pages, a small fraction browsed at any time. LRU eviction, a 30-minute TTL with jitter, and invalidation when a product is edited.
- Trending items: a small set requested constantly, a long tail rarely. LFU keeps the trending set in memory even when a crawler sweeps through old items. A 1-minute TTL keeps the trending data fresh.
Check yourself
LFU. Under LRU, the crawler's one-off reads made every old product the most recently used item, pushing the genuinely popular products out of the cache. LFU tracks how often items are used, so a single read doesn't outrank items read thousands of times, and the popular set survives.
Negative caching. Every lookup for an id that doesn't exist misses the cache and queries the database. Caching "not found" results for a short TTL, such as a minute, lets repeated lookups for missing ids be answered from the cache. Keep the TTL short so a newly created product appears quickly.
Entries loaded at the same time with the same TTL expire at the same moment, sending a burst of misses, and database queries, all at once. Adding a random spread, such as plus or minus 10 percent, staggers expiry so the load stays smooth.
From how stale the data may safely be and how often it changes. Prices shown at checkout may need seconds or explicit invalidation, while a product description can live for hours. Short TTLs reduce staleness but raise database load, so pick per data type.
Expiration removes an item when its TTL passes, regardless of memory. Eviction removes items when the cache is full and needs room, chosen by a policy like LRU or LFU. A healthy cache uses both: TTLs for freshness, eviction for memory.