Caching & CDNs

Eviction Policies: LRU, LFU & TTL

18 min Lesson 4 of 10

Eviction Policies: LRU, LFU & TTL

A cache is a fixed-size memory structure. When it fills up and a new item must be stored, something already in the cache must be removed to make room. The algorithm that decides which item to remove is called an eviction policy. Choosing the right policy can mean the difference between a cache hit rate above 90 % and one that barely reaches 50 %.

There are three foundational policies every system designer must know: LRU (Least Recently Used), LFU (Least Frequently Used), and TTL (Time-To-Live). Each encodes a different assumption about the future value of cached data.

LRU — Least Recently Used

Core assumption: if an item has not been accessed for a long time, it is unlikely to be needed soon. LRU evicts the item whose most-recent access timestamp is the oldest.

Internally, LRU is typically implemented as a doubly-linked list + hash map. Every access moves the item to the front of the list; eviction removes from the tail. Both get and put run in O(1).

Real-world example: A product-detail page cache for an e-commerce site. Customers searching for "running shoes" access the same handful of SKU pages repeatedly during a trend spike. LRU keeps those hot pages in memory and quietly drops pages for discontinued products nobody visited in the past hour.

Redis uses LRU by default when maxmemory-policy is set to allkeys-lru or volatile-lru. It samples a configurable number of keys (default 5) and evicts the least-recently-used among the sample — a cheap probabilistic approximation of true LRU.

Where LRU struggles: a "scan" workload — e.g., a nightly batch job iterating over every record — will trash an LRU cache by loading millions of items it will never re-read, evicting all the truly hot data in the process. This is called a cache scan pollution problem.

LFU — Least Frequently Used

Core assumption: items accessed many times in the past will likely be needed again. LFU tracks a hit counter for every key and evicts the key with the lowest count.

LFU is more resistant to scan pollution than LRU because a cold batch-scan item accumulates very few hits before being evicted, whereas truly popular items have high counters and survive. The trade-off is complexity: hit counters consume extra memory, and newly-inserted items start at count 1, making them vulnerable to early eviction even if they are about to become very popular.

Real-world example: A CDN caching static assets. A site logo is fetched millions of times per day; a rarely-viewed PDF is fetched twice. Under traffic spikes, LFU will always protect the logo and sacrifice the PDF — exactly the right call.

Counter aging: Pure LFU suffers from "frequency pollution" — an item that was popular six months ago but is now irrelevant retains a high counter forever. Production systems use decaying counters (e.g., halve all counts every N seconds) or Redis's LFU with decay (lfu-decay-time) to prevent stale-popular items from occupying cache indefinitely.

TTL — Time-To-Live

TTL is conceptually different from LRU and LFU: rather than evicting based on access patterns, it evicts based on age. Every cached item is stamped with an expiry time. When the clock passes that time, the item is considered stale and is either immediately removed or lazily deleted on the next read.

TTL is the primary tool for consistency. If a database row changes, a cache entry for it becomes wrong. Setting TTL = 60 seconds means the cache will be at most 60 seconds stale — you trade perfect consistency for cache performance.

Real-world example: Caching a user's session data for 30 minutes. After 30 minutes of inactivity, the session expires automatically — no explicit eviction logic needed, and the memory is reclaimed. Authentication tokens, rate-limit counters, and OTP codes are all natural TTL use-cases.

TTL stampede (thundering herd): If 10,000 cache entries all share the same TTL and were loaded simultaneously (e.g., at application startup), they all expire at the same instant. Every request in that moment goes to the database at once, potentially overwhelming it. Fix: add a small random jitter — e.g., TTL = base + random(0, 30) seconds — so expiries are spread out.

Side-by-Side Comparison

Comparison of LRU, LFU, and TTL eviction policies across key dimensions.

How LRU Works Internally: a Concrete Walkthrough

Understanding the mechanics helps you predict behaviour. Imagine a cache with capacity = 4. Keys are accessed in this order: A, B, C, D, A, E.

Step-by-step LRU walkthrough with cache capacity = 4. When E arrives, B is evicted because it is the least recently used item.

Combining Policies in Production

Real systems rarely rely on a single policy. A common pattern is to use TTL as a consistency floor (every key has a maximum age) while also using LRU or LFU as the capacity-management layer. An entry may be evicted either because its TTL expired or because the cache filled up — whichever comes first.

Redis exposes this directly. Set maxmemory-policy allkeys-lru (capacity eviction = LRU across all keys) and use EXPIRE key 3600 per-key for TTL. The item dies when the clock hits 3600 seconds or when Redis needs space, whichever is earlier.

Choosing a policy checklist:

Does data become stale after a known time? → Always add TTL.
Is your access pattern "80 % of traffic to 20 % of keys"? → LRU works well.
Do you have clear "always hot" keys that must survive even under scan traffic? → LFU.
Is your cache tiny and every byte counts? → Avoid LFU counters; use LRU.
Are you caching auth tokens / rate-limit windows / OTP codes? → TTL only, no LRU/LFU needed.

Key Numbers to Remember

Redis default maxmemory-policy: noeviction (returns error on write when full) — change it in production!
Redis LRU sample size: default maxmemory-samples 5; raising to 10 gives near-perfect LRU accuracy at ~2× CPU cost.
A typical TTL jitter range: ±10–30 % of the base TTL is enough to flatten the expiry spike.
Memcached uses LRU only (no LFU, no TTL-based background expiry) — TTL is enforced lazily on read.

Getting eviction policies right is the difference between a cache that helps your system and one that randomly drops valuable data under load. In the next lesson we will look at cache invalidation — how to actively push freshness rather than waiting for TTL to expire it.