Catalog My learning Blog
System Design Roadmap: 100-Day Course for Engineers · Phase 4 · Lesson 34 · 4 min read

Cache Eviction Policies: LRU, LFU and TTL

On this page
  1. Cache eviction vs expiration (TTL)
  2. Cache eviction policies: LRU, LFU and more
  3. How to choose a cache TTL
  4. Why TTLs need jitter
  5. Worked example: LRU vs LFU for two caches
  6. Check yourself

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

PolicyEvictsGood when
LRU, least recently usedThe entry untouched the longestRecent access predicts future access, the common case
LFU, least frequently usedThe entry used least oftenA stable set of popular items should survive bursts of one-off reads
FIFOThe oldest entryRarely the best choice
RandomAny entryVery cheap; surprisingly decent with many keys
TTL-based (volatile-ttl in Redis)The entry closest to expiryEntries 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.

LRU eviction removes the least recently used key when memory is full; a TTL removes a key when its expiry time passes.
LRU eviction removes the least recently used key when memory is full; a TTL removes a key when its expiry time passes.

How to choose a cache TTL

Two questions:

  1. 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.
  2. 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:

Code
ttl = 3600 + random(0, 600)      # expiries spread over 10 minutes

The 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.