Cache Eviction Policies: LRU, LFU, FIFO and TTL

A cache can be fast, perfectly connected, and still harm an application when it fills with the wrong data. A one-time scan of millions of catalog records can push out the product details customers repeatedly request. Cache eviction policies decide which value leaves when memory is scarce, so they directly affect miss rate, database load, and tail latency.

This article builds on cache-aside and write-through versus write-back caching. Those patterns define how data enters and changes in a cache. Eviction defines how a bounded cache makes room, and why a policy that seems sensible can fail on the real request trace.

Table of Contents

Why Eviction Is a Product Decision

Memory is finite. When a cache reaches its memory limit, it must either reject a new write or remove an existing value. An eviction policy is the rule for selecting that victim. It is different from invalidation: invalidation removes a value because it is incorrect; eviction removes a value because the cache needs capacity. A key can be fresh but evicted, or stale but still resident.

For a pure cache, eviction should normally be survivable: a miss reloads the authoritative source. Never put the only copy of a session, payment, or write-back event into a cache that may evict it. If a Redis instance mixes disposable response data with critical state, an allkeys-* policy can turn memory pressure into data loss. Separate those workloads or use a policy that refuses writes for protected data.

flowchart TD
    A[New value to cache] --> B{Enough memory?}
    B -->|Yes| C[Store value]
    B -->|No| D{Policy chooses victim}
    D --> E[Evict value]
    E --> C
    C --> F[Future request is hit or miss]

The right policy follows the access pattern. Recency, frequency, insertion age, and expiry are different signals. A cache that stores an hour of read traces can show whether users revisit recent items, repeatedly request a stable hot set, or send scan-like traffic that has almost no reuse.

LRU: Least Recently Used

Least Recently Used (LRU) evicts the item that has gone longest without an access. It assumes temporal locality: if a product or profile was useful a moment ago, it is more likely to be useful again than an item untouched for a long time.

For a request stream A, B, C, A, D in a three-item cache, LRU retains A because its recent reuse moved it to the most-recent position. It evicts B, the least recently accessed item. This makes LRU a reasonable general starting point for interactive web workloads, where recently viewed pages and objects are often revisited.

LRU has a well-known weakness: a sequential scan can pollute it. If a cache contains a valuable hot set and a job reads a long sequence of never-repeated keys, each new key can evict an older hot key. Some systems use approximate LRU or admission controls to reduce bookkeeping and resist one-hit wonders. The product question is not whether exact LRU is elegant; it is whether its overhead and scan behavior fit the measured workload.

LFU: Least Frequently Used

Least Frequently Used (LFU) evicts the key with the fewest accesses. It favors values that have been useful many times, even if they were not used most recently. A stable set of frequently requested country metadata, feature definitions, or popular catalog objects can benefit from that behavior.

The weakness is history. A key popular last week can retain a large frequency count long after user interest moves elsewhere, while a newly popular key needs time to earn its place. Practical LFU designs use counter decay or a bounded observation window so old popularity fades. Without decay, LFU can become a museum of yesterday’s traffic.

Redis’s LFU modes use approximate counters rather than exact globally ordered counts. That is usually appropriate for a distributed cache: exact per-hit coordination would cost more than the precision is worth. Treat the setting as a workload hypothesis, then compare hit ratio and source load under representative traffic rather than assuming LFU always wins.

FIFO: First In, First Out

First In, First Out (FIFO) evicts the oldest inserted item, regardless of whether it was read yesterday or one millisecond ago. It is cheap to explain and implement because reads do not reorder the queue.

That simplicity is also its limitation. A heavily used item can be evicted merely because it arrived first, while a new one-hit item stays. FIFO can be acceptable when entries have similar value and lifetime, or as a building block in more advanced policies, but it rarely captures interactive request locality as well as a carefully configured recency or frequency policy.

Do not call FIFO a bad policy in an interview without discussing the workload. Metadata maintenance has a cost. On a system where nearly every value is touched once and memory is modest, a simple policy may deliver enough value with less CPU overhead than one that updates recency state on every hit.

TTL Is Expiration, Not a Complete Eviction Policy

Time to live (TTL) removes a key after a chosen age. It is primarily a freshness and memory-bounding control, not a predictor of future reuse. A 60-second TTL can ensure a price is not served from a cache indefinitely; it cannot decide which of two still-valid values is least useful when memory is full.

Most production caches combine TTL with an eviction policy. TTL bounds how long an invalidation mistake can remain visible. LRU or LFU decides what to sacrifice under capacity pressure. Add jitter when many keys are created together, or they may expire together and cause a thundering herd of source requests.

Redis also distinguishes policies that consider every key from policies that consider only keys with an expiry. For example, an allkeys-lru setting can evict any key, while volatile-lru chooses among expiring keys. That distinction is a safety boundary, not a minor tuning detail. If non-expiring keys consume most memory, a volatile-only policy may leave no eligible victims and cause write errors.

Redis also offers volatile-ttl, which is an eviction policy: when memory is full, it selects an expiring key with the shortest remaining TTL. That is different from ordinary expiration. A key can expire because its configured deadline passed even when the cache has spare memory; volatile-ttl selects a victim only under memory pressure. Use it only when the application deliberately gives lower-value keys shorter TTLs. It is not a general replacement for choosing a capacity policy.

Comparing Policies With One Workload

Consider a cache with room for three values and this request stream:

A, B, C, A, D, E, A, B, A

LRU protects A because it is repeatedly recent. FIFO can discard A when it is the oldest insertion even though it remains hot. LFU can also retain A, but the result depends on how its counters age. Now change the stream to a popular item P followed by a long catalog scan of never-repeated keys. LRU can lose P during the scan; LFU can keep it if P’s count is sufficiently high, but may cling to it after the trend changes.

That is why toy examples are useful for intuition but insufficient for configuration. Replay sampled production access logs or run a shadow cache experiment. Compare not only hit ratio but byte hit ratio, p95 source latency, source database CPU, eviction rate, and the behavior of the highest-value endpoints.

Choosing and Configuring a Policy

Start with constraints before a policy name:

1. Set a memory limit with capacity reserved for the server, replication, and operational headroom.
2. Classify keys as disposable cache, protected state, or durable data. Do not mix their eviction rules accidentally.
3. Define a freshness budget and TTL for each disposable response type.
4. Examine whether reuse is recent, frequent, or nearly absent using access traces.
5. Pick a policy and a baseline, then test a failure and a saturation scenario.

For a standard cache-aside Redis cluster containing only disposable, read-heavy values, an all-keys recency or frequency policy can be a sensible experiment. For sessions or rate-limit counters, set expiration intentionally and isolate them from content-cache pressure. For critical records, use a database or explicitly durable store rather than relying on cache survival.

Here is a conservative Redis starting point for a dedicated, disposable response cache:

maxmemory 6gb
maxmemory-policy allkeys-lru

maxmemory must leave room for the operating system, replication buffers, persistence work, and deployment headroom; it is not the machine’s total RAM. allkeys-lru makes every key eligible because every key is safe to reload. Do not copy this into an instance that holds sessions, queues, or counters. For protected state, isolate the workload and consider noeviction, which rejects writes rather than deleting keys when the limit is reached.

An eviction setting cannot rescue an undersized cache. Estimate working-set size in bytes, not only key count. A 95% hit ratio can still be disappointing if misses target large, expensive objects. Conversely, a lower hit ratio might be acceptable if it misses cheap values while the costly source reads stay hot.

For example, sample one hour of production requests and replay it against a 4 GB and 6 GB shadow cache. For each size, record request hit ratio, byte hit ratio, p95 source latency, database QPS, eviction rate, and the top endpoints by miss cost. If 6 GB reduces database QPS materially but only raises request hit ratio by one point, the extra space may still be worthwhile because it retained large, expensive responses. This turns a policy choice into a capacity decision that can be defended with production evidence.

Production Metrics and Failure Modes

Monitor eviction as an application behavior, not just an infrastructure number. A sudden eviction-rate increase often means the working set exceeded capacity, a deployment changed serialization size, a TTL bug created too many keys, or a scan polluted the cache. Pair the eviction rate with memory usage, object size distribution, hit and miss rate, cache command latency, source QPS, and database saturation.

Memory pressure hides in large values

One endpoint that caches unbounded result lists can evict thousands of small, useful keys. Put upper bounds on cached payload size, paginate collection responses, and separately monitor bytes stored and bytes returned. The slow SQL debugging guide is still relevant here: caching a needlessly large query result is not a substitute for a sound query.

Eviction storms cause source storms

When many keys leave together, the next requests all miss. Use conservative memory limits, TTL jitter, request coalescing for hot misses, and source capacity planning. The forthcoming cache-stampede article will cover that recovery path in detail; for now, make sure a cache restart and an eviction burst are tested before relying on a high hit ratio in production.

Configuration differs by engine

Names and exact algorithms vary by cache engine and managed service. Verify the deployed engine’s documentation and inspect the live configuration, rather than copying a Redis setting into Memcached or an in-process cache. The policy must match the service’s role in the larger distributed cache system design.

Interview Questions

1. What is the difference between eviction and invalidation?

Invalidation removes or changes a value because it may be incorrect after a source update. Eviction removes a value because the cache needs capacity. I use TTL and invalidation to bound staleness, then choose an eviction policy to preserve the most valuable reusable data under memory pressure.

2. When would you choose LRU over LFU?

I would start with LRU when recent requests predict near-future requests, such as interactive browsing. I would test LFU when the workload has a stable, highly skewed hot set that should survive temporary scans. The decision comes from trace replay and source-load metrics, not from the algorithm names.

3. Why is TTL not enough for cache eviction?

TTL sets an age limit. Before keys expire, a full cache still needs a victim selection rule. TTL also says nothing about which key will be requested again, so I pair it with a memory policy and use it as a freshness safeguard.

4. What happens if a Redis cache uses all-keys LRU for session data?

The server can evict a live session under memory pressure. If the session is the only record, users can be logged out or lose state. I would isolate sessions, give them explicit expiry, and use a durable store or a policy that protects critical keys rather than treating them as a disposable content cache.

5. How would you diagnose a drop in cache hit ratio after a deployment?

I would compare key cardinality, serialized object size, TTL distribution, eviction count, and source QPS before and after deployment. Then I would look for changed key prefixes, a cache namespace version bump, a scan-like job, or a smaller effective memory limit. I would roll back or limit the offender before tuning LRU versus LFU blindly.

Conclusion

LRU, LFU, FIFO, and TTL make different bets about what remains useful. TTL bounds age and freshness; eviction policies decide what gives way when memory is full. Choose only after classifying data, measuring the working set, and replaying real access patterns. The best cache policy is the one that keeps costly, reusable reads hot without putting any correctness-critical data at risk.

References

1. Redis: Key Eviction
2. AWS: Caching Best Practices
3. Redis: LFU vs LRU, How to Choose

YouTube Videos

1. Cache Eviction Policies Explained
2. Cache Eviction Techniques: LRU, LFU, FIFO and More