Eviction Policies

Caches have limited memory. When full, something must go. The eviction policy decides what gets removed.

Choose wrong, and your cache hit ratio tanks. Choose right, and you maximize performance with limited resources.

Why Eviction Matters

The goal: Keep the data most likely to be requested again.

LRU: Least Recently Used

The most popular eviction policy. Evicts the item that hasn't been accessed for the longest time.

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 oldest (least recently used)
            self.cache.popitem(last=False)

LRU Visualization

Cache capacity: 3 items

Access: A → Cache: [A]
Access: B → Cache: [A, B]
Access: C → Cache: [A, B, C] (full)
Access: A → Cache: [B, C, A] (A moved to end)
Access: D → Cache: [C, A, D] (B evicted - least recent)

LFU: Least Frequently Used

Evicts the item with the lowest access count.

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}           # key -> value
        self.freq = {}            # key -> frequency
        self.freq_to_keys = defaultdict(list)  # freq -> [keys]
        self.min_freq = 0

    def get(self, key):
        if key not in self.cache:
            return None

        # Increase frequency
        old_freq = self.freq[key]
        self.freq[key] += 1
        self.freq_to_keys[old_freq].remove(key)
        self.freq_to_keys[old_freq + 1].append(key)

        # Update min_freq if needed
        if not self.freq_to_keys[self.min_freq]:
            self.min_freq += 1

        return self.cache[key]

TTL: Time To Live

Items expire after a fixed duration, regardless of access patterns.

import time

class TTLCache:
    def __init__(self):
        self.cache = {}  # key -> (value, expiry_time)

    def set(self, key, value, ttl_seconds):
        expiry = time.time() + ttl_seconds
        self.cache[key] = (value, expiry)

    def get(self, key):
        if key not in self.cache:
            return None

        value, expiry = self.cache[key]
        if time.time() > expiry:
            del self.cache[key]
            return None  # Expired

        return value

Choosing TTL Values

FIFO: First In, First Out

Simple queue-based eviction. Oldest items go first.

Add A → [A]
Add B → [A, B]
Add C → [A, B, C] (full)
Add D → [B, C, D] (A evicted - oldest)

Random Eviction

Surprisingly effective! Just pick a random item to evict.

Policy Comparison

Real-World: Redis Eviction Policies

Redis offers multiple policies you can configure:

# In redis.conf
maxmemory 100mb
maxmemory-policy allkeys-lru

Key Takeaways

Next up: Cache Invalidation - The hardest problem in computer science.