00:00

Cache Eviction Policies: LRU, LFU, FIFO, TTL

Last updated:

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

Where an eviction policy runs An application reads key D from a cache that is already full with keys A, B and C. On the cache miss the application loads D from the database. Before D can be stored, the eviction policy chooses a victim, here key C, which is removed so that D fits. Applicationreads key D CACHE · CAPACITY 3 (FULL) A B C Eviction policypicks the victim: C Databasesource of truth cache miss: load D from the database
When a full cache must store a new entry, the eviction policy decides which existing entry to drop. The dropped entry is reloaded from the database if it is needed again.

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:

  1. Track: on each read or write, the cache updates the metadata the policy needs, such as a timestamp, a counter or the insertion order.
  2. Detect pressure: when a new entry would exceed the size or memory limit, eviction starts.
  3. 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.

LRU eviction example The cache holds A, B and C. Their last-used times are t7, t8 and t5. LRU evicts C because t5 is the oldest last use. Access order: A B C C C A A B (t1 to t8) · capacity 3 · new key D arrives cache (full) key inserted last used uses A t1 t7 3 B t2 t8 2 C t3 t5 3 Evict Cleast recently used (t5)
LRU looks only at the "last used" column. C was last touched at t5, earlier than A and B, so C is evicted even though it was used three times.

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.

LFU eviction example The cache holds A, B and C with use counts 3, 2 and 3. LFU evicts B because it has the fewest uses. Access order: A B C C C A A B (t1 to t8) · capacity 3 · new key D arrives cache (full) key inserted last used uses A t1 t7 3 B t2 t8 2 C t3 t5 3 Evict Bleast frequently used (2)
LFU looks only at the "uses" column. B has the lowest count, so it is evicted even though it was the most recently used key.

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.

FIFO eviction example The cache holds A, B and C inserted at t1, t2 and t3. FIFO evicts A because it was inserted first, regardless of how often or how recently it was used. Access order: A B C C C A A B (t1 to t8) · capacity 3 · new key D arrives cache (full) key inserted last used uses A t1 t7 3 B t2 t8 2 C t3 t5 3 Evict Afirst in (t1)
FIFO looks only at the "inserted" column. A arrived first, so it leaves first, even though it is one of the busiest keys.

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.

MRU eviction example The cache holds A, B and C with last-used times t7, t8 and t5. MRU evicts B because it was used most recently. Access order: A B C C C A A B (t1 to t8) · capacity 3 · new key D arrives cache (full) key inserted last used uses A t1 t7 3 B t2 t8 2 C t3 t5 3 Evict Bmost recently used (t8)
MRU does the opposite of LRU: B was touched last (t8), so it is evicted. This helps only when a just-used item is the least likely to be needed again.

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.

TTL expiry example At time t10 the cache holds A with a 5-unit TTL set at t7, B with a 6-unit TTL set at t2, and C with a 10-unit TTL set at t5. B expired at t8, so it is removed before any eviction policy is needed. Current time: t10 · new key D arrives cache with TTLs key set at TTL expires A t7 5 t12 B t2 6 t8 C t5 10 t15 Remove Bexpired at t8 < t10
With TTL, every entry carries an expiry time. At t10, B (expired at t8) is already invalid and is removed first; no access statistics are needed.

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.

Random eviction example The cache holds A, B and C. Random eviction ignores all statistics and picks any key with equal probability; in this run it picked A. A B C random()any key Evict Athis time
Random eviction keeps no statistics at all and simply picks any key. It is cheap and surprisingly effective when access is evenly spread.

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

PolicyStrengthWeakness
LRUWorks well for most workloads; O(1) operationsA single large scan can push out all hot data
LFUKeeps long-term popular itemsOld popularity lingers without counter decay
FIFOSimplest; almost no overheadIgnores how often and how recently items are used
MRUGood for repeated sequential scansPoor for typical user traffic
TTLBounds staleness; predictableDoes not manage memory pressure on its own
RandomNo metadata or lockingMay 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.

PolicyWhat it evictsTypical use
noevictionNothing; writes fail when memory is fullRedis used as a primary data store
allkeys-lruApproximately least recently used keyGeneral-purpose cache (common default choice)
allkeys-lfuApproximately least frequently used keyCaches with a stable set of popular keys
allkeys-randomA random keyUniform access patterns
volatile-lru / volatile-lfuLRU or LFU among keys with a TTLMixing cache keys with keys that must stay
allkeys-lrm / volatile-lrmApproximately least recently modified key (newer Redis versions)Keep data that is read often but rarely written
volatile-ttlThe key with the shortest remaining TTLEntries that are about to expire anyway
volatile-randomA random key with a TTLSimple 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 maxmemory and a maxmemory-policy instead 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-* and volatile-* policies and defaults to noeviction.
  • Monitor hit ratio and evictions, and combine eviction with TTLs and explicit invalidation.

Next, see how caches spread across many servers in Distributed Caching.