Cache Eviction

LRU - Least Recently Used

LRU evicts the item that hasn't been accessed for the longest time.

How LRU Works

LRU Cache (Capacity: 3):

Access: A, B, C, D (evicts A), B (hit), E (evicts C)

State after each access:
[A] → [B,A] → [C,B,A] → [D,B,A] → [D,B,A] → [E,D,B]
                                              ↑
                                           Evicts C (LRU)

Implementation

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> value
        self.order = []  # Track access order
    
    def get(self, key):
        if key in self.cache:
            # Move to most recently used
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        return None
    
    def put(self, key, value):
        if key in self.cache:
            # Update existing
            self.cache[key] = value
            self.order.remove(key)
            self.order.append(key)
        else:
            # Evict if at capacity
            if len(self.cache) >= self.capacity:
                lru_key = self.order.pop(0)
                del self.cache[lru_key]
            
            # Add new entry
            self.cache[key] = value
            self.order.append(key)

# O(1) implementation with OrderedDict
from collections import OrderedDict

class LRUCacheOptimized:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return None
    
    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:
            self.cache.popitem(last=False)

Characteristics

• Time complexity: O(1) for get/put
• Space complexity: O(capacity)
• Best for: General purpose caching
• Redis implementation: Uses LRU by default

LFU - Least Frequently Used

LFU evicts the item with the lowest access count.

How LFU Works

LFU Cache (Capacity: 3):

Access: A, A, A, B, B, C, D (evicts B)

Counts: A=3, B=2, C=1, D=1
Evict B (lowest frequency, but A has highest)

Implementation

import heapq
from collections import defaultdict

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> value
        self.freq = {}   # key -> frequency
        self.freq_keys = defaultdict(list)  # freq -> [keys]
        self.min_freq = 0
        self.size = 0
    
    def get(self, key):
        if key not in self.cache:
            return None
        
        # Update frequency
        freq = self.freq[key]
        self.freq[key] = freq + 1
        
        # Move to new frequency bucket
        self.freq_keys[freq].remove(key)
        if not self.freq_keys[freq]:
            del self.freq_keys[freq]
            if self.min_freq == freq:
                self.min_freq = freq + 1
        
        self.freq_keys[freq + 1].append(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache[key] = value
            self.get(key)  # Update frequency
            return
        
        if self.size >= self.capacity:
            # Evict least frequent
            evict_key = self.freq_keys[self.min_freq].pop(0)
            if not self.freq_keys[self.min_freq]:
                del self.freq_keys[self.min_freq]
            del self.cache[evict_key]
            del self.freq[evict_key]
            self.size -= 1
        
        # Add new entry
        self.cache[key] = value
        self.freq[key] = 1
        self.freq_keys[1].append(key)
        self.min_freq = 1
        self.size += 1

Characteristics

• Best for: Workloads with skewed access patterns
• Adaptive: Automatically favors frequently accessed items
• More complex: Requires frequency tracking
• Redis: Does not natively support LFU (can be simulated)

FIFO and Random Eviction

FIFO - First In First Out

from collections import deque

class FIFOCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.queue = deque()
    
    def get(self, key):
        return self.cache.get(key)
    
    def put(self, key, value):
        if key in self.cache:
            self.cache[key] = value
            return
        
        if len(self.cache) >= self.capacity:
            oldest = self.queue.popleft()
            del self.cache[oldest]
        
        self.cache[key] = value
        self.queue.append(key)

Random Eviction

import random

class RandomCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
    
    def get(self, key):
        return self.cache.get(key)
    
    def put(self, key, value):
        if len(self.cache) >= self.capacity:
            # Evict random key
            random_key = random.choice(list(self.cache.keys()))
            del self.cache[random_key]
        
        self.cache[key] = value

Comparison

Algorithm	Complexity	Hit Rate	Use Case
LRU	O(1)	High	General purpose
LFU	O(log n)	Highest	Skewed access patterns
FIFO	O(1)	Medium	Simple, predictable
Random	O(1)	Low	Uniform access patterns

When to Use Each

• LRU: Default choice for most workloads
• LFU: When access frequency varies significantly
• FIFO: When order matters more than frequency
• Random: Simple workloads, uniform distribution

When to Evict

Eviction Triggers

Eviction occurs when:

1. Memory Limit Reached:
   - Cache at maximum capacity
   - New item needs space
   - Eviction policy selects victim

2. TTL Expiration:
   - Item's TTL has passed
   - Background cleanup process
   - Immediate on access

3. Manual Invalidation:
   - Explicit delete operation
   - Pattern-based deletion
   - Administrative action

Eviction Monitoring

# Track eviction metrics
metrics = {
    'evictions_total': 0,
    'evictions_by_policy': defaultdict(int),
    'memory_usage': 0,
    'hit_ratio': 0.0
}

def on_eviction(key, policy):
    metrics['evictions_total'] += 1
    metrics['evictions_by_policy'][policy] += 1
    
    # Alert if eviction rate too high
    if metrics['evictions_total'] > 1000:
        alert('High eviction rate detected')

Tuning Eviction

# Redis eviction configuration
# redis.conf
maxmemory 1gb
maxmemory-policy allkeys-lru

# Policies:
# noeviction: Return errors when memory limit reached
# allkeys-lru: LRU across all keys
# volatile-lru: LRU only for keys with TTL
# allkeys-lfu: LFU across all keys (Redis 4.0+)
# volatile-ttl: Evict shortest TTL first
# allkeys-random: Random eviction

Best Practices

1. Monitor eviction rates - high rates indicate undersized cache
2. Choose policy based on workload - LRU for most cases
3. Set appropriate maxmemory - based on available RAM
4. Use volatile policies - when only some keys should be evictable
5. Test with production patterns - validate policy choice