Cache Eviction Policies: LRU, LFU, FIFO, TTL
A cache is fast because it is small. Sooner or later it fills up, and every new entry must push an old one out. The rule that chooses which entry leaves is the cache eviction policy, and it largely decides how often the cache actually helps.
Pick a good policy and most requests are served from memory. Pick a poor one and the cache keeps throwing away exactly the data that is about to be requested again. This tutorial walks through the common policies using one shared example, so you can see each rule make a different choice. For caching basics and strategies, start with What Is Caching.
1. What Is a Cache Eviction Policy?
A cache eviction policy (also called a cache replacement policy) is the algorithm a cache uses to decide which existing entry to remove when it has reached its capacity and needs room for a new one.
Eviction is different from expiration. Expiration removes an entry because its time to live (TTL) has passed, even if the cache has free space. Eviction removes a still-valid entry because space has run out. Most production caches use both: TTLs keep data fresh, and an eviction policy controls memory.
2. Where Eviction Happens
Eviction never loses data permanently, because the database remains the source of truth. Its cost is a future cache miss: if the evicted entry is requested again, the application pays the database round trip to reload it.
3. How Eviction Works
Every policy follows the same three steps:
- Track: on each read or write, the cache updates the metadata the policy needs, such as a timestamp, a counter or the insertion order.
- Detect pressure: when a new entry would exceed the size or memory limit, eviction starts.
- Choose and remove: the policy compares candidates using its metadata, removes the victim and stores the new entry.
To compare the policies fairly, every diagram below uses the same history: a cache with room for three keys sees the accesses A B C C C A A B at times t1 to t8, and then key D arrives. After that history, A was inserted first and used three times (last at t7), B was used twice (last at t8), and C was used three times (last at t5).
4. Eviction Policies Compared on One Example
LRU: Least Recently Used
LRU evicts the entry that has gone the longest without being accessed. It assumes that recently used data will be used again soon, which is true for most user-facing workloads. A classic implementation combines a hash map with a doubly linked list, so both lookup and update take O(1) time.
LFU: Least Frequently Used
LFU evicts the entry with the fewest accesses. It protects consistently popular items, such as a home page or a best-selling product, even if they were not touched in the last few seconds. Its weakness is history: an item that was popular yesterday can keep a high count and stay in the cache too long, so practical versions age or decay their counters.
FIFO: First In, First Out
FIFO evicts the oldest inserted entry, like a queue. It needs almost no bookkeeping, but it ignores usage completely, so a heavily used key is removed just because it arrived early.
MRU: Most Recently Used
MRU evicts the entry that was used most recently. It sounds backwards, but it suits looping scans over data larger than the cache, where the item just read is the one that will not be needed again for the longest time.
TTL: Time to Live
With TTL, each entry expires a fixed time after it is written. Expired entries are removed first, and an eviction policy handles the rest when memory is still short. TTL is the main tool for keeping cached data from becoming too stale.
Random replacement
Random eviction picks any entry. It needs no metadata and no locking, so it is very cheap, and when all keys are accessed about equally often it performs close to LRU.
Modern hybrids
Production caches often combine ideas. Caffeine, the popular Java cache, uses Window TinyLFU, which admits new entries through a small LRU window and keeps them only if their estimated frequency beats the entry they would replace. Redis approximates LRU and LFU by sampling a few keys and evicting the best candidate among them, which saves memory compared with tracking every key exactly.
5. Advantages and Disadvantages
| Policy | Strength | Weakness |
|---|---|---|
| LRU | Works well for most workloads; O(1) operations | A single large scan can push out all hot data |
| LFU | Keeps long-term popular items | Old popularity lingers without counter decay |
| FIFO | Simplest; almost no overhead | Ignores how often and how recently items are used |
| MRU | Good for repeated sequential scans | Poor for typical user traffic |
| TTL | Bounds staleness; predictable | Does not manage memory pressure on its own |
| Random | No metadata or locking | May evict hot items by chance |
6. Redis Eviction Policies Compared
Redis selects its behaviour with the maxmemory-policy setting. The allkeys-* policies consider every key, while the volatile-* policies consider only keys that have a TTL.
| Policy | What it evicts | Typical use |
|---|---|---|
| noeviction | Nothing; writes fail when memory is full | Redis used as a primary data store |
| allkeys-lru | Approximately least recently used key | General-purpose cache (common default choice) |
| allkeys-lfu | Approximately least frequently used key | Caches with a stable set of popular keys |
| allkeys-random | A random key | Uniform access patterns |
| volatile-lru / volatile-lfu | LRU or LFU among keys with a TTL | Mixing cache keys with keys that must stay |
| allkeys-lrm / volatile-lrm | Approximately least recently modified key (newer Redis versions) | Keep data that is read often but rarely written |
| volatile-ttl | The key with the shortest remaining TTL | Entries that are about to expire anyway |
| volatile-random | A random key with a TTL | Simple eviction of expiring keys |
Note that noeviction is Redis's default, which is safe for a database but surprising for a cache: once memory is full, writes start to fail. Set an explicit policy when Redis is used as a cache.
7. Real-World Use Cases
- Session and API caches: LRU with TTLs keeps active users' data and drops idle sessions.
- Product catalogues: LFU or TinyLFU keeps best-sellers resident during traffic spikes.
- CDN edge caches: variants of LRU and LFU decide which files stay at each point of presence.
- Database buffer pools: databases use LRU variants with protection against large scans, such as a "young" and "old" list.
- Distributed caches: each node evicts independently; see Distributed Caching.
8. Best Practices
- Start with LRU plus TTL: it fits most workloads; switch only when hit-rate metrics show a better option.
- Measure the hit ratio and the eviction rate; a high eviction rate usually means the cache is too small.
- Always set TTLs on cached data so stale values disappear even without memory pressure.
- Add jitter to TTLs so that many keys do not expire at the same moment and overload the database.
- Never rely on eviction for correctness: invalidate or update cached entries when the source data changes.
- Configure Redis explicitly: set
maxmemoryand amaxmemory-policyinstead of keeping the default. - Protect secrets: do not cache sensitive data longer than necessary, and keep the cache on a private network.
9. Summary
- An eviction policy decides which entry leaves when a cache is full; expiration removes entries whose TTL has passed.
- With the same history, LRU, LFU, FIFO and MRU can each evict a different key.
- LRU is the usual default; LFU suits stable popularity; FIFO and random are cheap; MRU suits repeated scans.
- Redis offers
allkeys-*andvolatile-*policies and defaults tonoeviction. - Monitor hit ratio and evictions, and combine eviction with TTLs and explicit invalidation.
Next, see how caches spread across many servers in Distributed Caching.
Cache Eviction Policies: Top Interview Questions
These are the cache eviction questions most often asked in system design interviews, with short answers you can explain in your own words.
Q1. What is the difference between eviction and expiration?
Expiration removes an entry because its TTL has passed, whether or not the cache is full. Eviction removes a still-valid entry because the cache has reached its size or memory limit and needs room.
Q2. How would you implement an LRU cache with O(1) operations?
Combine a hash map from key to node with a doubly linked list ordered by recency. A read moves the node to the front, a write adds it to the front, and eviction removes the node at the tail. In Java, LinkedHashMap with access order and removeEldestEntry gives the same behaviour.
Q3. When is LFU better than LRU?
When some items are consistently popular over time but are not requested every second, such as best-selling products. LRU might evict them after a burst of one-time requests; LFU keeps them because of their high access count, provided counts decay so old popularity does not linger forever.
Q4. Why does Redis evict approximately rather than exactly?
Exact LRU or LFU needs extra memory and bookkeeping for every key. Redis instead samples a small number of keys and evicts the best candidate among them, which gives results close to true LRU or LFU at much lower cost. The sample size is configurable.
Q5. What happens if Redis reaches maxmemory with the default policy?
The default policy is noeviction, so Redis stops accepting writes that need more memory and returns errors, while reads continue to work. For a cache, configure a policy such as allkeys-lru instead.