Cache Eviction Policies

The Cache Full Problem

Imagine your cache is a parking lot with 100 spaces. When it’s full and a new car arrives, you need to decide: which car leaves?

That’s cache eviction - deciding what to remove when cache is full.

Why Eviction Matters

A good eviction policy keeps frequently accessed data in cache, maximizing cache hit rate. A bad policy evicts data you’ll need soon, wasting cache space.

The Goal

Maximize cache hit rate - keep the data you’ll access soon, evict data you won’t need.

---

Policy 1: LRU (Least Recently Used)

Most popular policy. Evicts the item that hasn’t been accessed for the longest time.

How LRU Works

Think of it like a stack of books on your desk. When you use a book, you put it on top. When your desk is full, you remove books from the bottom (least recently used).

Algorithm:

1. When item accessed → move to front (most recent)
2. When cache full → remove from back (least recent)
3. New items added to front

When to use:

• Most common use case
• Temporal locality (recently used = likely to be used again)
• Web applications, API responses
• General-purpose caching

Trade-offs:

• Simple to understand
• Works well for most access patterns
• O(1) operations with proper implementation
• Doesn’t consider frequency (one-hit wonders stay)
• Can evict frequently used items if not accessed recently

LRU Implementation (Classic LLD Problem!)

This is a classic interview problem. Here’s how to implement it efficiently:

Python

lru_cache.py

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # OrderedDict maintains insertion order
        # Most recent at end, least recent at beginning
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        # Move to end (most recent)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing
            self.cache.move_to_end(key)
        else:
            # Check if full
            if len(self.cache) >= self.capacity:
                # Evict least recent (first item)
                self.cache.popitem(last=False)

        self.cache[key] = value
        # Ensure it's at end (most recent)
        self.cache.move_to_end(key)

Java

LRUCache.java

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // LinkedHashMap with accessOrder=true maintains LRU order
        this.cache = new LinkedHashMap<Integer, Integer>(
            capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
        // LinkedHashMap automatically maintains order
    }
}

More Efficient Implementation (HashMap + Doubly Linked List for O(1) operations):

Python

lru_cache_optimized.py

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node

        # Dummy head and tail for easier operations
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, node: Node):
        # Add after head
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _move_to_head(self, node: Node):
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self) -> Node:
        last = self.tail.prev
        self._remove_node(last)
        return last

    def get(self, key: int) -> int:
        node = self.cache.get(key)
        if not node:
            return -1

        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int):
        node = self.cache.get(key)

        if not node:
            if len(self.cache) >= self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]

            node = Node(key, value)
            self.cache[key] = node
        else:
            node.value = value

        self._move_to_head(node)

Java

LRUCacheOptimized.java

import java.util.HashMap;
import java.util.Map;

class Node {
    int key, value;
    Node prev, next;

    Node() {}
    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    private Node popTail() {
        Node last = tail.prev;
        removeNode(last);
        return last;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) return -1;

        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);

        if (node == null) {
            if (cache.size() >= capacity) {
                Node tail = popTail();
                cache.remove(tail.key);
            }

            node = new Node(key, value);
            cache.put(key, node);
        } else {
            node.value = value;
        }

        moveToHead(node);
    }
}

---

Policy 2: LFU (Least Frequently Used)

Frequency-based eviction. Evicts the item with the lowest access count.

How LFU Works

Think of it like a popularity contest. Items with more “votes” (accesses) stay longer. When cache is full, the least popular item leaves.

Algorithm:

1. Track access count for each item
2. When item accessed → increment count
3. When cache full → evict item with lowest count
4. On tie, use LRU as tiebreaker

When to use:

• Items accessed many times (popular products, trending content)
• Frequency matters more than recency
• E-commerce product catalogs
• Content recommendation systems

Trade-offs:

• Keeps frequently accessed items
• Good for stable access patterns
• “One-hit wonder” problem (new items evicted quickly)
• More complex than LRU
• Needs frequency tracking overhead

---

Policy 3: FIFO (First In First Out)

Simple queue-based eviction. Evicts the oldest item regardless of usage.

How FIFO Works

Like a queue at a store - first in, first out. When cache is full, the oldest item leaves, even if it was just accessed.

Algorithm:

1. Items added to end of queue
2. When cache full → remove from front (oldest)
3. Access doesn’t change position

When to use:

• Simple implementation needed
• Access patterns are random
• Items have equal importance
• Rarely used in practice (ignores access patterns)

Trade-offs:

• Very simple to implement
• O(1) operations
• Ignores access patterns
• Can evict frequently used items
• Poor cache hit rate

---

Policy 4: TTL (Time To Live)

Time-based expiration. Items expire after a fixed time period.

How TTL Works

Like milk with an expiration date. After a certain time, items are automatically removed, regardless of usage.

Algorithm:

1. Each item has expiration timestamp
2. Background process checks for expired items
3. Expired items removed automatically
4. Often combined with LRU/LFU for eviction when full

When to use:

• Data has natural expiration (API responses, sessions)
• Staleness matters (news, stock prices)
• Combined with other policies
• Simple freshness guarantee

Trade-offs:

• Automatic freshness
• Simple concept
• Good for time-sensitive data
• Doesn’t consider access patterns
• Background cleanup overhead

---

Real-World Examples

Different eviction policies are used by major companies based on their specific access patterns:

LRU: Google Search Results Cache

The Challenge: Google caches billions of search results. Recent searches are more likely to be repeated than old ones.

The Solution: Google uses LRU for search result caching:

• Most recent searches stay in cache
• Old searches evicted when cache is full
• Perfect for temporal locality (users often repeat recent searches)

Why LRU? Search patterns show strong temporal locality. If someone searched “weather” 5 minutes ago, they’re likely to search it again soon. LRU keeps recent results hot.

Example: Cache size: 1 million results. User searches “Python tutorial” → cached. 10 minutes later, searches again → instant from cache. After 1 hour of no access → evicted to make room for newer searches.

Impact: 60% of searches served from cache. Average response time: 10ms (cache) vs 100ms (database).

LFU: Amazon Product Catalog

The Challenge: Amazon has millions of products, but only thousands are popular. Popular products (iPhone, bestsellers) are accessed constantly.

The Solution: Amazon uses LFU for product catalog:

• Frequently accessed products stay in cache
• One-hit wonder products evicted quickly
• Keeps bestsellers and trending items hot

Why LFU? Product access patterns show frequency matters more than recency. iPhone 15 is accessed thousands of times per day - it should stay in cache. A random obscure product accessed once should be evicted.

Example: Cache size: 100,000 products. iPhone 15 accessed 10,000 times/day → stays in cache. Random product accessed once → evicted quickly.

Impact: 80% cache hit rate for popular products. Product pages load instantly for bestsellers.

TTL: Twitter Tweet Cache

The Challenge: Tweets are time-sensitive. A tweet from 1 hour ago is less relevant than a tweet from 1 minute ago.

The Solution: Twitter uses TTL-based eviction:

• Recent tweets cached for 5 minutes
• Older tweets expire automatically
• Combined with LRU for eviction when full

Why TTL? Tweets have natural expiration. A tweet from yesterday is less likely to be accessed than a tweet from 5 minutes ago. TTL ensures freshness.

Example: Tweet created at 10:00 AM. Cached until 10:05 AM. After 10:05 AM, expires. If cache is full before expiration, LRU evicts least recently accessed tweets.

Impact: 70% of timeline requests served from cache. Reduces database load during peak events (viral tweets).

Hybrid: Netflix Content Cache

The Challenge: Netflix has different content types: popular shows (accessed frequently), new releases (accessed recently), old content (rarely accessed).

The Solution: Netflix uses hybrid policy:

• LFU for popular shows (Stranger Things, The Crown) - accessed frequently
• LRU for new releases - accessed recently
• TTL for trending content - time-sensitive

Why Hybrid? Different content has different access patterns. Popular shows benefit from LFU, new releases from LRU, trending from TTL.

Example:

• Stranger Things (popular): LFU keeps it in cache (accessed 1000x/day)
• New movie release: LRU keeps it in cache (accessed recently)
• Trending show: TTL expires after 1 hour (trends change quickly)

Impact: 85% cache hit rate. Content loads instantly for popular shows, reducing bandwidth costs.

Redis Default: LRU with Sampling

The Challenge: Redis needs to evict keys when memory is full, but checking all keys for LRU is expensive.

The Solution: Redis uses approximate LRU:

• Samples random keys (5 keys by default)
• Evicts least recently used from sample
• Fast and efficient for large caches

Why Sampling? Checking all keys for true LRU is O(n). Sampling is O(1). The approximation is good enough for most use cases.

Example: Cache has 1 million keys. Memory full. Redis samples 5 random keys, evicts the least recently used one. Fast and efficient.

Impact: Eviction overhead: O(1) instead of O(n). Handles millions of keys efficiently.

---

Choosing the Right Policy

• LRU: Most common, works well for general use cases (web apps, APIs)
• LFU: Use when frequency matters (e-commerce, content platforms)
• FIFO: Rarely used, only for truly random access patterns
• TTL: Use for time-sensitive data (news, social media, real-time data)
• Hybrid: Use when you have multiple access patterns (large platforms)

---

Policy Comparison

Policy	Complexity	Hit Rate	Use Case	Implementation
LRU	Medium	High	General purpose	HashMap + Doubly Linked List
LFU	High	High	Frequency-based	HashMap + Frequency tracking
FIFO	Low	Low	Simple cases	Queue
TTL	Low	Medium	Time-sensitive	Timestamp tracking

---

LLD Connection: Choosing the Right Policy

At the code level, eviction policies are strategies you can swap:

Python

eviction_strategy.py

from abc import ABC, abstractmethod
from typing import Any

class EvictionStrategy(ABC):
    @abstractmethod
    def evict(self, cache: dict) -> Any:
        """Return key to evict"""
        pass

class LRUStrategy(EvictionStrategy):
    def evict(self, cache: dict) -> Any:
        # Return least recently used (first in OrderedDict)
        return next(iter(cache))

class LFUStrategy(EvictionStrategy):
    def __init__(self):
        self.access_counts = {}

    def evict(self, cache: dict) -> Any:
        # Return least frequently used
        return min(self.access_counts.items(), key=lambda x: x[1])[0]

class Cache:
    def __init__(self, capacity: int, strategy: EvictionStrategy):
        self.capacity = capacity
        self.strategy = strategy
        self.cache = {}

    def evict_if_needed(self):
        if len(self.cache) >= self.capacity:
            key = self.strategy.evict(self.cache)
            del self.cache[key]

Java

EvictionStrategy.java

import java.util.Map;

interface EvictionStrategy<K> {
    K evict(Map<K, ?> cache);
}

class LRUStrategy<K> implements EvictionStrategy<K> {
    public K evict(Map<K, ?> cache) {
        // Return first key (least recent)
        return cache.keySet().iterator().next();
    }
}

class LFUStrategy<K> implements EvictionStrategy<K> {
    private final Map<K, Integer> accessCounts = new HashMap<>();

    public K evict(Map<K, ?> cache) {
        // Return key with minimum access count
        return accessCounts.entrySet().stream()
            .min(Map.Entry.comparingByValue())
            .map(Map.Entry::getKey)
            .orElse(null);
    }
}

class Cache<K, V> {
    private final int capacity;
    private final EvictionStrategy<K> strategy;
    private final Map<K, V> cache;

    public Cache(int capacity, EvictionStrategy<K> strategy) {
        this.capacity = capacity;
        this.strategy = strategy;
        this.cache = new HashMap<>();
    }

    private void evictIfNeeded() {
        if (cache.size() >= capacity) {
            K key = strategy.evict(cache);
            cache.remove(key);
        }
    }
}

---

Real-World Considerations

Hybrid Policies

Most production systems use combinations:

• LRU + TTL: Evict by recency, but also expire old items
• LFU + LRU: Use frequency, tiebreak by recency
• Adaptive: Switch policies based on access patterns

Cache Warming

Pre-populate cache with likely-to-be-accessed data:

• Popular products
• User profiles
• Frequently accessed content

Monitoring

Track these metrics:

• Hit rate: % of requests served from cache
• Eviction rate: How often eviction happens
• Access patterns: Understand your workload

---

Key Takeaways

🎯 LRU is Default

Use LRU for most cases. It’s simple, effective, and handles temporal locality well.

📊 Frequency vs Recency

LRU = recency, LFU = frequency. Choose based on your access patterns.

⚡ O(1) Operations

Proper LRU implementation uses HashMap + Doubly Linked List for O(1) get/put.

🔄 Strategy Pattern

Make eviction policy swappable using strategy pattern in your code.

---

Next Steps

• Learn about Distributed Caching - caching across multiple servers
• Master Cache Invalidation - keeping cache consistent
• Understand CDN & Edge Caching - caching at the edge