Cache Eviction Policies

When cache is full, what gets kicked out?

Home
Hld Concepts
Caching
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

Section titled “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)

Section titled “Policy 1: LRU (Least Recently Used)”

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

How LRU Works

Section titled “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:

When item accessed → move to front (most recent)
When cache full → remove from back (least recent)
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!)

Section titled “LRU Implementation (Classic LLD Problem!)”

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

Python
Java

lru_cache.py

1
from collections import OrderedDict
2

3
class LRUCache:
4
    def __init__(self, capacity: int):
5
        self.capacity = capacity
6
        # OrderedDict maintains insertion order
7
        # Most recent at end, least recent at beginning
8
        self.cache = OrderedDict()
9

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

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

18
    def put(self, key: int, value: int) -> None:
19
        if key in self.cache:
20
            # Update existing
21
            self.cache.move_to_end(key)
22
        else:
23
            # Check if full
24
            if len(self.cache) >= self.capacity:
25
                # Evict least recent (first item)
26
                self.cache.popitem(last=False)
27

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

LRUCache.java

1
import java.util.LinkedHashMap;
2
import java.util.Map;
3

4
class LRUCache {
5
    private final int capacity;
6
    private final LinkedHashMap<Integer, Integer> cache;
7

8
    public LRUCache(int capacity) {
9
        this.capacity = capacity;
10
        // LinkedHashMap with accessOrder=true maintains LRU order
11
        this.cache = new LinkedHashMap<Integer, Integer>(
12
            capacity, 0.75f, true) {
13
            @Override
14
            protected boolean removeEldestEntry(Map.Entry eldest) {
15
                return size() > capacity;
16
            }
17
        };
18
    }
19

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

24
    public void put(int key, int value) {
25
        cache.put(key, value);
26
        // LinkedHashMap automatically maintains order
27
    }
28
}

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

Python
Java

lru_cache_optimized.py

1
class Node:
2
    def __init__(self, key=0, value=0):
3
        self.key = key
4
        self.value = value
5
        self.prev = None
6
        self.next = None
7

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

13
        # Dummy head and tail for easier operations
14
        self.head = Node()
15
        self.tail = Node()
16
        self.head.next = self.tail
17
        self.tail.prev = self.head
18

19
    def _add_node(self, node: Node):
20
        # Add after head
21
        node.prev = self.head
22
        node.next = self.head.next
23
        self.head.next.prev = node
24
        self.head.next = node
25

26
    def _remove_node(self, node: Node):
27
        node.prev.next = node.next
28
        node.next.prev = node.prev
29

30
    def _move_to_head(self, node: Node):
31
        self._remove_node(node)
32
        self._add_node(node)
33

34
    def _pop_tail(self) -> Node:
35
        last = self.tail.prev
36
        self._remove_node(last)
37
        return last
38

39
    def get(self, key: int) -> int:
40
        node = self.cache.get(key)
41
        if not node:
42
            return -1
43

44
        self._move_to_head(node)
45
        return node.value
46

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

50
        if not node:
51
            if len(self.cache) >= self.capacity:
52
                tail = self._pop_tail()
53
                del self.cache[tail.key]
54

55
            node = Node(key, value)
56
            self.cache[key] = node
57
        else:
58
            node.value = value
59

60
        self._move_to_head(node)

LRUCacheOptimized.java

1
import java.util.HashMap;
2
import java.util.Map;
3

4
class Node {
5
    int key, value;
6
    Node prev, next;
7

8
    Node() {}
9
    Node(int key, int value) {
10
        this.key = key;
11
        this.value = value;
12
    }
13
}
14

15
class LRUCache {
16
    private final int capacity;
17
    private final Map<Integer, Node> cache;
18
    private final Node head, tail;
19

20
    public LRUCache(int capacity) {
21
        this.capacity = capacity;
22
        this.cache = new HashMap<>();
23
        this.head = new Node();
24
        this.tail = new Node();
25
        head.next = tail;
26
        tail.prev = head;
27
    }
28

29
    private void addNode(Node node) {
30
        node.prev = head;
31
        node.next = head.next;
32
        head.next.prev = node;
33
        head.next = node;
34
    }
35

36
    private void removeNode(Node node) {
37
        node.prev.next = node.next;
38
        node.next.prev = node.prev;
39
    }
40

41
    private void moveToHead(Node node) {
42
        removeNode(node);
43
        addNode(node);
44
    }
45

46
    private Node popTail() {
47
        Node last = tail.prev;
48
        removeNode(last);
49
        return last;
50
    }
51

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

56
        moveToHead(node);
57
        return node.value;
58
    }
59

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

63
        if (node == null) {
64
            if (cache.size() >= capacity) {
65
                Node tail = popTail();
66
                cache.remove(tail.key);
67
            }
68

69
            node = new Node(key, value);
70
            cache.put(key, node);
71
        } else {
72
            node.value = value;
73
        }
74

75
        moveToHead(node);
76
    }
77
}

Policy 2: LFU (Least Frequently Used)

Section titled “Policy 2: LFU (Least Frequently Used)”

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

How LFU Works

Section titled “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:

Track access count for each item
When item accessed → increment count
When cache full → evict item with lowest count
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)

Section titled “Policy 3: FIFO (First In First Out)”

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

How FIFO Works

Section titled “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:

Items added to end of queue
When cache full → remove from front (oldest)
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)

Section titled “Policy 4: TTL (Time To Live)”

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

How TTL Works

Section titled “How TTL Works”

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

Algorithm:

Each item has expiration timestamp
Background process checks for expired items
Expired items removed automatically
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

Policy Comparison

Section titled “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

Section titled “LLD Connection: Choosing the Right Policy”

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

Python
Java

eviction_strategy.py

1
from abc import ABC, abstractmethod
2
from typing import Any
3

4
class EvictionStrategy(ABC):
5
    @abstractmethod
6
    def evict(self, cache: dict) -> Any:
7
        """Return key to evict"""
8
        pass
9

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

15
class LFUStrategy(EvictionStrategy):
16
    def __init__(self):
17
        self.access_counts = {}
18

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

23
class Cache:
24
    def __init__(self, capacity: int, strategy: EvictionStrategy):
25
        self.capacity = capacity
26
        self.strategy = strategy
27
        self.cache = {}
28

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

EvictionStrategy.java

1
import java.util.Map;
2

3
interface EvictionStrategy<K> {
4
    K evict(Map<K, ?> cache);
5
}
6

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

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

17
    public K evict(Map<K, ?> cache) {
18
        // Return key with minimum access count
19
        return accessCounts.entrySet().stream()
20
            .min(Map.Entry.comparingByValue())
21
            .map(Map.Entry::getKey)
22
            .orElse(null);
23
    }
24
}
25

26
class Cache<K, V> {
27
    private final int capacity;
28
    private final EvictionStrategy<K> strategy;
29
    private final Map<K, V> cache;
30

31
    public Cache(int capacity, EvictionStrategy<K> strategy) {
32
        this.capacity = capacity;
33
        this.strategy = strategy;
34
        this.cache = new HashMap<>();
35
    }
36

37
    private void evictIfNeeded() {
38
        if (cache.size() >= capacity) {
39
            K key = strategy.evict(cache);
40
            cache.remove(key);
41
        }
42
    }
43
}

Real-World Considerations

Section titled “Real-World Considerations”

Hybrid Policies

Section titled “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

Section titled “Cache Warming”

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

Popular products
User profiles
Frequently accessed content

Monitoring

Section titled “Monitoring”

Track these metrics:

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

Key Takeaways

Section titled “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

Section titled “Next Steps”

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

📚 Related Articles

Continue learning with these related topics

Design LRU Cache

Design and implement a Least Recently Used (LRU) Cache data structure that supports get and put operations in O(1) time complexity. The cache should maintain a fixed capacity and evict the least recently used item when the capacity is exceeded. Master this easy Low Level Design interview problem with step-by-step guidance, interactive UML class diagram builder, and complete solutions in Python, Java, C++, TypeScript, JavaScript, and C#.

→

Designing a Tic Tac Toe Game

Design a Tic Tac Toe game that allows two players to play on a 3x3 grid. Players take turns placing their symbols (X or O) in empty cells. The game should detect wins (three in a row horizontally, vertically, or diagonally) and handle draws when all cells are filled. Master this easy Low Level Design interview problem with step-by-step guidance, interactive UML class diagram builder, and complete solutions in Python, Java, C++, TypeScript, JavaScript, and C#.

→

Design a Cache Manager

Design an in-memory cache manager system that supports multiple eviction policies (LRU/LFU), time-to-live (TTL) expiration for cache entries, and thread-safe operations. The system should efficiently manage cache capacity, handle concurrent access, and provide flexible eviction strategies for different use cases. Master this hard Low Level Design interview problem with step-by-step guidance, interactive UML class diagram builder, and complete solutions in Python, Java, C++, TypeScript, JavaScript, and C#.

→

Design an Elevator System - Request Feasibility (Single Lift)

Design an elevator system for a single elevator that can determine if a new request can be fulfilled given the current elevator state. The system should check feasibility based on capacity constraints, route planning, time estimation, conflict detection, and suggest alternative times if a request is not immediately feasible. Master this hard Low Level Design interview problem with step-by-step guidance, interactive UML class diagram builder, and complete solutions in Python, Java, C++, TypeScript, JavaScript, and C#.

→

Design a Coffee Machine

Design a coffee machine system that can prepare various beverages (coffee, tea, cappuccino, latte) based on predefined recipes, manage ingredient inventory (coffee beans, milk, water, sugar), allow user customization (sugar level, milk type), monitor ingredient levels with alerts, and handle the dispensing process with proper state management. Master this easy Low Level Design interview problem with step-by-step guidance, interactive UML class diagram builder, and complete solutions in Python, Java, C++, TypeScript, JavaScript, and C#.

→

Design a Hotel Management System

Design a hotel management system that allows guests to search for available rooms, make reservations, check in, and check out. The system should handle room management with different room types and amenities, check room availability for date ranges, manage reservations with proper state transitions, and apply pricing strategies based on room type and season. Master this easy Low Level Design interview problem with step-by-step guidance, interactive UML class diagram builder, and complete solutions in Python, Java, C++, TypeScript, JavaScript, and C#.

→

Last updated: Jan 6, 2026

Previous
Caching Fundamentals Next
Distributed Caching