Cache Eviction Policies: What Gets Thrown Out When the Cache Is Full
Series: System Design · Caching — Pillar 5 of 8
Systems Design
| # | Post | What it covers |
|---|---|---|
| 00 | Caching: The Fastest Database Query Is the One You Don't Make | Caching is one of the most impactful and error-prone tools in system design. Six concepts covering the full lifecycle of a production cache layer. |
| 01 | Caching: Storing Results Closer to Where They're Needed | Caching stores expensive results closer to the reader. Learn how it works, the main patterns, and when it hurts more than it helps. |
| 02 | Cache Invalidation: Knowing When the Copy Is Wrong | Cache invalidation is notoriously difficult. Learn the main strategies, when each applies, and how to avoid serving stale data at scale. |
| 03 | Distributed Cache: Spreading Cache Across a Cluster | A single cache node is a bottleneck and a SPOF. Learn how distributed caches partition data, replicate for availability, and handle node failures. |
| 04 | Cache Eviction Policies: What Gets Thrown Out When the Cache Is Full ← you are here | When a cache fills up, something must go. Learn how LRU, LFU, FIFO, and TTL-based eviction work and how to choose the right policy for your data. |
| 05 | Cache Stampede: When Expiry Triggers a Database Avalanche | When a hot cache entry expires, hundreds of servers query the database simultaneously. Learn how cache stampedes happen and how to prevent them. |
| 06 | Cache Warming: Starting Hot Instead of Cold | A cold cache causes database overload on startup. Learn how to warm caches proactively using predictive loading, lazy warming, and scheduled jobs. |
| 07 | Caching: Wrap-Up | A recap of all 6 caching concepts: what caching is, invalidation strategies, distributed caches, eviction policies, stampedes, and warming. How they connect. |
Cache Eviction Policies: What Gets Thrown Out When the Cache Is Full
The problem
Your URL shortener caches destination URLs in Redis. The cache has 16 GB of memory and holds roughly 80 million URL entries. Traffic is fine.
Then your platform goes viral — a marketing campaign creates five million new short links in a week, all of them being clicked. New links flood into the cache alongside the existing ones. Memory fills. Redis starts evicting entries to make room.
What gets evicted? That's entirely up to the eviction policy. With the wrong policy, Redis might evict the hundred most popular links — the ones being clicked thousands of times per second — to make room for cold links that were created last week and never clicked again. Your hit ratio collapses. Your database melts.
Eviction policies determine which data gets discarded when the cache runs out of space. The right policy keeps the most valuable data in cache; the wrong one throws it away.
The core idea
A cache has finite memory. When it fills and a new entry needs to be added, something already in the cache must be removed. An eviction policy is the algorithm the cache uses to decide which existing entry to discard.
Different policies make different assumptions about what "valuable" means: the most recently used entry? the most frequently used? the one that's been sitting longest? The policy that best matches your access pattern produces the highest cache hit ratio.
The analogy: books on a small bookshelf
You have a single shelf that holds twenty books. You own hundreds of books but only keep twenty on the shelf for convenient access. When you buy a new book and the shelf is full, something must come off.
LRU: You remove the book you haven't touched in the longest time. The assumption: if you haven't needed it recently, you probably won't need it soon.
LFU: You remove the book you've referenced least overall. The assumption: the book you've picked up fifty times this year is more valuable than the one you've opened once.
FIFO: You remove the book that's been on the shelf longest, regardless of how often you use it. A classic that you read every month could be evicted simply because it was placed on the shelf first — which is why FIFO rarely works well for caches.
Random: You close your eyes and pull a book off. Surprisingly reasonable in practice when the access distribution is uniform.
The main eviction policies
LRU — Least Recently Used
Evict the entry that was accessed least recently. Operates on a recency-ordered list: every access moves an entry to the front; the entry at the back (least recently accessed) is evicted when space is needed.
Access sequence: A, B, C, D, A, B
Cache size: 3
After A,B,C: [C, B, A] (front=most recent)
After D: [D, C, B] — A was least recent, evicted
After A: [A, D, C] — B was least recent (but B is in set), C still there
After B: [B, A, D]
Strengths: Excellent for workloads with temporal locality — recently accessed data is likely to be accessed again soon. The most common default.
Weaknesses: A single sequential scan (iterating through millions of records once) pollutes the cache by evicting genuinely hot entries to make room for cold ones that are never accessed again. This is the "cache pollution" problem.
Redis implementation: maxmemory-policy allkeys-lru or volatile-lru (only evicts keys with TTL set). Redis uses an approximation — it samples N random keys and evicts the least recently used among them, rather than maintaining a full ordered list. Configurable via maxmemory-samples.
LFU — Least Frequently Used
Evict the entry that has been accessed least often overall. Tracks a frequency counter for each entry.
Frequency counters:
url:x7Kp2 → 45,231 accesses
url:aB3cD → 12,004 accesses
url:zZ9qR → 3 accesses ← evict this one
Strengths: Better than LRU for stable hot sets — if the top 1% of links get 90% of traffic, LFU keeps them in cache indefinitely. Resistant to cache pollution from sequential scans.
Weaknesses: Frequency counters must be maintained and decay over time. Without decay, a link that was popular three months ago but now receives no traffic keeps a high counter and is never evicted, crowding out currently popular links. Redis implements frequency with logarithmic counter decay — recent accesses count more than old ones.
Redis implementation: allkeys-lfu or volatile-lfu. Added in Redis 4.0. Generally superior to LRU for stable, power-law access distributions (which most URL shorteners have).
FIFO — First In, First Out
Evict the entry that was inserted into the cache first, regardless of access history.
Insertion order: A(t=0), B(t=1), C(t=2), D(t=3)
Cache full — add E: evict A (inserted first)
Strengths: Simple. Zero bookkeeping overhead beyond an insertion queue.
Weaknesses: Entirely ignores access patterns. A link cached first and accessed constantly will be evicted before a link cached recently and never accessed. In practice, FIFO almost always has a lower hit ratio than LRU or LFU for cache workloads. Rarely used as a primary policy.
TTL-based eviction
Entries expire after their configured TTL. When a new entry needs space and all keys have remaining TTL, Redis evicts the one closest to expiry (volatile-ttl).
This isn't really an eviction policy in the traditional sense — it's the natural consequence of TTL — but it interacts with eviction. If only some keys have TTL set, policies like volatile-lru only evict from the TTL-keyed set, leaving keys without TTL permanent unless explicitly deleted.
Random eviction
Evict a randomly selected entry. Surprisingly effective when access patterns are uniform — if everything is equally likely to be accessed, random eviction has the same expected hit ratio as LRU. Fails badly when access is non-uniform (which is most real-world workloads).
Redis: allkeys-random — rarely used in production caches.
No eviction
Reject new writes when memory is full. Redis returns an error on write operations (noeviction). Suitable when the cache is used as a primary store (not a cache) and data loss is unacceptable — but for actual caches, this causes write failures and is usually wrong.
Redis maxmemory policies at a glance
| Policy | Evicts from | Algorithm |
|---|---|---|
noeviction |
— | Error on write |
allkeys-lru |
All keys | LRU approximation |
allkeys-lfu |
All keys | LFU with decay |
allkeys-random |
All keys | Random |
volatile-lru |
TTL keys only | LRU approximation |
volatile-lfu |
TTL keys only | LFU with decay |
volatile-ttl |
TTL keys only | Evict soonest-expiring |
volatile-random |
TTL keys only | Random |
Tradeoffs
LRU vs LFU. LRU wins for workloads where recently accessed items are likely to be accessed again soon. LFU wins for workloads with a stable popular set accessed over a long period. For a URL shortener — where a small number of links get the vast majority of traffic, and that distribution is relatively stable — LFU tends to outperform LRU. For a session cache — where recently active sessions are the ones that need to be cached — LRU is appropriate.
Counter overhead. LFU requires frequency counters per key. Redis's logarithmic approximation is lightweight but not free. LRU's recency tracking via sampling is also approximate. Both are negligible at normal cache sizes.
Scan resistance. If any part of your workload scans large numbers of keys (analytics, batch jobs, reprocessing), LFU is more scan-resistant than LRU. A batch scan won't pollute an LFU cache because the scanned keys get low frequency counts; under LRU, a scan can evict hot data.
When to use each
LRU: session caches, user context caches, any cache where "recently used = likely needed again" holds.
LFU: URL shorteners, content caches, any cache with a stable power-law access distribution where a small hot set dominates traffic.
TTL-based (volatile-ttl): caches where TTLs encode priority — entries with longer remaining TTL are more "valuable."
Avoid FIFO and random unless you have a specific reason (uniform access patterns, extreme simplicity requirements).
In the URL shortener: allkeys-lfu for the destination URL cache — the top 0.1% of links get most traffic, LFU keeps them in cache. volatile-lru for session and rate-limit data — these have TTLs set and recency matters most.
The one thing to remember
Eviction policy choice matters most when your working set exceeds your cache size. If your cache is large enough to hold everything, eviction rarely triggers and the policy doesn't matter much. When the cache is constrained — as it usually is in production — the policy determines which fraction of your data stays hot. Match the policy to your access pattern: LFU for stable popular sets, LRU for recency-driven workloads. And set
maxmemoryexplicitly — Redis without a memory limit will use all available RAM and potentially trigger OOM kills.
← Previous: Distributed Cache — a single cache server is a single point of failure; here's how to spread cache across a cluster and what that changes.
→ Next: Cache Stampede — what happens when a hot cache entry expires and every server rushes to repopulate it at the same time.
