Cache Eviction Policies: LRU, LFU, FIFO, and Beyond

Cache Eviction Policies: LRU, LFU, FIFO, and Beyond

Every cache has a finite amount of memory. When the cache is full and a new entry needs to be stored, the system must decide which existing entry to remove. This decision is governed by an eviction policy — an algorithm that determines which cached data is least valuable and should be discarded to make room for new data.

Choosing the right eviction policy can dramatically impact your cache hit ratio. A well-chosen policy keeps the most valuable data in cache; a poor choice evicts data that will be needed again soon, causing unnecessary cache misses and increased load on your backend systems.

Why Eviction Matters

Consider a Redis instance with 16 GB of memory serving as a cache for a database with 500 GB of data. Only about 3% of the total data fits in cache at any time. The eviction policy determines which 3% stays — and getting it right means the difference between a 95% cache hit ratio and a 60% one.

Common Eviction Policies

LRU — Least Recently Used

LRU evicts the entry that has not been accessed for the longest time. The assumption is that recently accessed data is more likely to be accessed again soon — this is called temporal locality.

LRU is the most widely used eviction policy and the default recommendation for most workloads. It performs well when access patterns show recency bias, which is true for the majority of web applications.

Implementation: A true LRU cache uses a doubly-linked list combined with a hash map. The linked list maintains access order, and the hash map provides O(1) lookups.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key):
        if key not in self.cache:
            return None
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Remove least recently used (first item)
            self.cache.popitem(last=False)

# Usage
cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
cache.get("a")        # Access "a", moves it to most recent
cache.put("d", 4)     # Cache full — evicts "b" (least recently used)
print(cache.get("b")) # Returns None — evicted

Time Complexity: O(1) for both get and put operations.
Space Overhead: Doubly-linked list pointers per entry (typically 16 bytes per entry on 64-bit systems).

LFU — Least Frequently Used

LFU evicts the entry that has been accessed the fewest times. It tracks a frequency counter for each entry and removes the one with the lowest count.

LFU works well when some items are consistently popular over long periods. However, it can hold onto historically popular items that are no longer relevant (cache pollution). For example, a trending product that was accessed 10,000 times last week but is no longer popular will stay in cache over a newly trending item with only 100 accesses.

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}          # key -> value
        self.freq = {}           # key -> frequency count
        self.freq_keys = defaultdict(list)  # frequency -> list of keys
        self.min_freq = 0
    
    def get(self, key):
        if key not in self.cache:
            return None
        self._increment_freq(key)
        return self.cache[key]
    
    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.cache:
            self.cache[key] = value
            self._increment_freq(key)
            return
        if len(self.cache) >= self.capacity:
            # Evict least frequently used
            evict_key = self.freq_keys[self.min_freq].pop(0)
            del self.cache[evict_key]
            del self.freq[evict_key]
        self.cache[key] = value
        self.freq[key] = 1
        self.freq_keys[1].append(key)
        self.min_freq = 1
    
    def _increment_freq(self, key):
        f = self.freq[key]
        self.freq_keys[f].remove(key)
        if not self.freq_keys[f] and f == self.min_freq:
            self.min_freq += 1
        self.freq[key] = f + 1
        self.freq_keys[f + 1].append(key)

FIFO — First In, First Out

FIFO evicts the oldest entry in the cache regardless of how recently or frequently it was accessed. It treats the cache like a queue — the first item added is the first to be removed.

FIFO is the simplest to implement but generally has the worst hit ratio because it ignores access patterns entirely. It works acceptably when all entries have roughly equal access probability, or when used as a building block in more sophisticated algorithms.

Random Eviction

Random eviction selects a random entry to remove. Surprisingly, random eviction performs reasonably well in practice — often only slightly worse than LRU. Its advantage is zero overhead: no linked lists, no frequency counters, no extra memory per entry.

Redis uses an approximated LRU that is essentially random sampling: it picks N random keys and evicts the one that was least recently accessed among the sample. This gives near-LRU behavior with minimal overhead.

TTL-Based Eviction

TTL-based eviction removes entries whose time-to-live has expired. This is more of an invalidation mechanism than a memory management strategy, but it directly affects which entries remain in cache. Redis supports volatile eviction policies that only evict keys with an expiration set.

MRU — Most Recently Used

MRU is the opposite of LRU — it evicts the most recently accessed item. This seems counterintuitive but works well for specific access patterns, such as sequential scans of large datasets where recently accessed items are unlikely to be accessed again.

Eviction Policy Comparison

How Redis Implements Eviction

Redis provides eight eviction policies configured via the maxmemory-policy directive:

# Redis configuration (redis.conf)
maxmemory 4gb
maxmemory-policy allkeys-lru

# Available policies:
# noeviction      — Return errors when memory limit reached (default)
# allkeys-lru     — Evict LRU keys from all keys
# volatile-lru    — Evict LRU keys only from keys with TTL set
# allkeys-lfu     — Evict LFU keys from all keys
# volatile-lfu    — Evict LFU keys only from keys with TTL set
# allkeys-random  — Evict random keys from all keys
# volatile-random — Evict random keys only from keys with TTL set
# volatile-ttl    — Evict keys with shortest TTL first

# Check current policy at runtime
CONFIG GET maxmemory-policy

# Change policy at runtime
CONFIG SET maxmemory-policy allkeys-lfu

# Tune LRU sampling (higher = more accurate, default 5)
maxmemory-samples 10

Redis does not implement true LRU because maintaining a linked list of all keys would be too expensive. Instead, it uses an approximated LRU: when eviction is needed, Redis samples maxmemory-samples random keys and evicts the one with the oldest access time. With the default sample size of 5, this approximation is remarkably close to true LRU.

Choosing the Right Policy

Default recommendation: Start with LRU (specifically allkeys-lru in Redis). It works well for the vast majority of web application workloads where recent data is more likely to be accessed again.

Use LFU when: Your workload has a stable set of popular items and you want to keep them cached even during bursts of other activity. Example: A news site where the top 50 articles get 80% of traffic.

Use volatile-ttl when: You mix persistent and temporary data in the same Redis instance and want to preferentially evict short-lived data.

Use noeviction when: Your Redis instance is used as a primary data store (not just a cache) and you cannot afford to lose data. Your application must handle the out-of-memory errors gracefully.

Advanced: Adaptive Replacement Cache (ARC)

ARC is a sophisticated eviction algorithm developed by IBM that dynamically balances between recency (LRU) and frequency (LFU). It maintains two LRU lists — one for recently accessed items and one for frequently accessed items — and adapts the size of each list based on observed access patterns. ARC generally outperforms both pure LRU and pure LFU but is more complex to implement. ZFS file system uses ARC for its caching layer.

Real-World Considerations

In production systems, eviction policies interact with other caching concerns:

• Hot keys: Hot keys are rarely evicted by any policy because they are accessed frequently. The challenge is that they concentrate load on specific cache nodes in a distributed cache.
• Cache warming: After a restart or eviction storm, the cache is cold and hit ratio drops. Consider pre-loading popular keys based on historical access patterns.
• Memory fragmentation: Even with the right eviction policy, memory fragmentation can reduce effective cache capacity. Redis uses jemalloc to minimize this issue.

Frequently Asked Questions

Which eviction policy should I use for a general-purpose web application cache?

LRU is the safest default for most web applications. It handles the common case well — recently viewed pages, recently active user sessions, and recently updated data tend to be accessed again soon. In Redis, set maxmemory-policy allkeys-lru and adjust from there based on observed hit ratios.

How does LRU handle the scan pollution problem?

Scan pollution occurs when a one-time scan (like a batch job reading every item) pushes frequently-used items out of the LRU cache. Since every scanned item becomes "recently used," truly popular items get evicted. LFU handles this better because one-time accesses do not inflate frequency counts. Some systems use a combination of LRU and LFU, or use segmented LRU where new entries start in a probation segment and must be re-accessed to move into a protected segment.

Can I use different eviction policies for different types of data?

Not within a single Redis instance — the eviction policy is global. However, you can use separate Redis instances or databases for different data types, each with its own eviction policy. Alternatively, manage eviction at the application level using TTL-based strategies where you control the TTL per key type.

What is the performance impact of a poor eviction policy choice?

A poor eviction policy can reduce your cache hit ratio by 10-30%, which translates directly to increased database load and higher latency. For a system handling 100,000 requests per second with a 90% hit ratio, dropping to 70% means 20,000 additional database queries per second — potentially overwhelming your database. Monitor your cache hit ratio and eviction rate to detect policy mismatches early.