Cache Eviction Policies

Every cache has a finite size. Eventually, it fills up and you need to kick something out to make room for new entries. The strategy you use to decide what gets removed, and when, is your eviction policy. Get this wrong and your cache turns into a very expensive, very slow dictionary.

This covers the five most common eviction policies, how they work in practice, and when each one makes sense.

---

Why Eviction Policy Matters

A cache is only as good as its eviction policy. Imagine your cache holds user sessions. Most users log in once, browse for 10 minutes, and never come back. A policy that holds onto recently-used items will eventually evict those one-time visitors and make room for active users. A policy that blindly evicts the oldest items might keep dead sessions around while kicking out frequent visitors.

The wrong policy can destroy your hit rate. The right one, matched to how your users actually behave, makes everything feel fast.

---

The Five Policies

LRU (Least Recently Used)

LRU evicts the item that hasn’t been accessed for the longest time. The idea is that recently used items are more likely to be used again soon.

graph LR
    A[Cache Full] --> B[New item arrives]
    B --> C{Is item in cache?}
    C -->|No| D[Evict LRU item]
    D --> E[Add new item]
    C -->|Yes| F[Update position]

Implementation with LinkedHashMap (Java):

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true for LRU
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

Redis LRU Implementation:

Redis doesn’t have a true LRU implementation because that would require tracking access order for every item, which is expensive. Instead, it uses an approximation: it samples a few random keys and evicts the least recently used among them.

# Configure Redis to use LRU eviction
maxmemory 100mb
maxmemory-policy allkeys-lru

# Or for volatile-lru (only evict keys with TTL)
maxmemory-policy volatile-lru

Good for:

• Access patterns where recent items get hit again soon
• Stable popular items
• Working sets that fit comfortably in cache

Struggles with:

• One-time scans (every item touched once, never again)
• Large working sets that overflow memory
• Write-heavy loads with big objects

---

LFU (Least Frequently Used)

LFU evicts the item with the lowest access count. If an item was accessed 100 times and another only 5 times, LFU keeps the 100-time item.

graph LR
    A[Cache Full] --> B[New item arrives]
    B --> C{Item exists?}
    C -->|No| D[Evict LFU item]
    D --> E[Add new item, count=1]
    C -->|Yes| F[Increment count]
    F --> E

Implementation:

from collections import Counter
import heapq

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> (value, freq, timestamp)
        self.freq_heap = []  # (freq, timestamp, key)
        self.counter = Counter()
        self.timestamp = 0

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

        value, freq, ts = self.cache[key]
        self.counter[key] += 1
        self.cache[key] = (value, freq + 1, self.timestamp)
        heapq.heappush(self.freq_heap,
                      (freq + 1, self.timestamp, key))
        self.timestamp += 1
        return value

    def put(self, key, value):
        if self.capacity == 0:
            return

        if key in self.cache:
            self.cache[key] = (value, self.counter[key] + 1, self.timestamp)
        else:
            if len(self.cache) >= self.capacity:
                # Evict least frequently used
                while self.freq_heap:
                    freq, ts, k = heapq.heappop(self.freq_heap)
                    if k in self.cache and self.cache[k][1] == freq:
                        del self.cache[k]
                        del self.counter[k]
                        break

            self.cache[key] = (value, 1, self.timestamp)
            self.counter[key] = 1

        heapq.heappush(self.freq_heap,
                      (self.cache[key][1], self.timestamp, key))
        self.timestamp += 1

Redis LFU Implementation:

# Enable LFU
maxmemory-policy allkeys-lfu

# Or volatile-lfu (only keys with TTL)
maxmemory-policy volatile-lfu

# Configure LFU decay time (how often freq counters decrease)
lfu-decay-time 1

Good for:

• Items with genuinely different popularity levels
• Stable access counts over time
• Rewarding consistently popular items

Struggles with:

• New items that need time to build up access count
• Old items that stay even after they stop being popular
• Frequency counter overflow if not tuned

---

FIFO (First In, First Out)

FIFO is the simplest policy: whatever entered the cache first leaves first. No access tracking, no frequency counting. Just a queue.

graph LR
    A[Cache Full] --> B[New item arrives]
    B --> C[Evict oldest item]
    C --> D[Add new item]

Implementation:

from collections import deque

class FIFOCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.queue = deque()

    def put(self, key, value):
        if key in self.cache:
            return

        if len(self.cache) >= self.capacity:
            oldest = self.queue.popleft()
            if oldest in self.cache:
                del self.cache[oldest]

        self.cache[key] = value
        self.queue.append(key)

    def get(self, key):
        return self.cache.get(key)

Good for:

• Uniform access patterns
• Situations where simplicity beats optimal hit rate
• Debugging (predictable behavior)

Struggles with:

• Most real-world access patterns
• Frequently accessed items getting evicted if they happened to arrive first
• Performance compared to LRU

---

TTL (Time To Live)

TTL isn’t really an eviction policy in the traditional sense. Instead, items automatically expire after a set time. The cache doesn’t need to decide what to evict; expired items are simply ignored or cleaned up lazily.

graph LR
    A[Item added] --> B[Timer starts]
    B --> C{TTL expired?}
    C -->|Yes| D[Item invalid]
    C -->|No| E[Item valid]

Redis TTL:

# Set a 5-minute TTL on a key
SET user:123 "data"
EXPIRE user:123 300

# Or use SETEX for atomic set + expire
SETEX user:123 300 "data"

# Check remaining TTL
TTL user:123

Lazy expiration vs active cleanup:

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

    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

        return value

    def put(self, key, value, ttl=None):
        ttl = ttl or self.default_ttl
        expiry = time.time() + ttl
        self.cache[key] = (value, expiry)

Good for:

• Data that naturally expires (sessions, temporary data)
• Cache consistency without manual invalidation
• Data that might change on the backend

Struggles with:

• Finding the right TTL value (too short = cache churn, too long = stale data)
• Access patterns (ignores them entirely)
• Memory waste from expired items still sitting around

---

Random Replacement

Random replacement exactly what it sounds like: when the cache is full, pick a random item to evict. No tracking, no history, no complexity.

graph LR
    A[Cache Full] --> B[New item arrives]
    B --> C[Pick random item]
    C --> D[Evict it]
    D --> E[Add new item]

Implementation:

import random

class RandomCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}

    def put(self, key, value):
        if key in self.cache:
            self.cache[key] = value
            return

        if len(self.cache) >= self.capacity:
            # Pick random key to evict
            evict_key = random.choice(list(self.cache.keys()))
            del self.cache[evict_key]

        self.cache[key] = value

    def get(self, key):
        return self.cache.get(key)

Redis random eviction:

# Evict random keys
maxmemory-policy allkeys-random

# Or only random among keys with TTL
maxmemory-policy volatile-random

Good for:

• Uniform or unpredictable access patterns
• Extreme simplicity requirements
• Baseline comparison for other policies
• Certain distributed caching scenarios

Struggles with:

• Non-uniform access patterns
• Need for predictable performance
• Most real-world use cases

---

Comparing the Policies

Policy	Complexity	Hit Rate	Memory Overhead	Best For
LRU	Medium	Good	Medium	Temporal locality
LFU	High	Best	High	Stable popularity
FIFO	Low	Poor	Low	Uniform access
TTL	Low	Variable	Low	Freshness required
Random	Very Low	Variable	None	Uniform access, simplicity

graph TD
    A[Access Pattern Analysis] --> B{Is access uniform?}
    B -->|Yes| C{Random item acceptable?}
    B -->|No| D{Do popular items stay popular?}
    D -->|Yes| E[LFU]
    D -->|No| F{Is recent data more popular?}
    F -->|Yes| G[LRU]
    F -->|No| H[Consider TTL or Random]
    C -->|Yes| I[Random or FIFO]
    C -->|No| J[LRU]

---

Real-World Considerations

Redis-Specific Notes

Redis 4.0+ introduced LFU and improved LRU. The maxmemory-policy setting controls what happens when memory limit is reached:

# Volatile policies (only evict keys with an expiry)
maxmemory-policy volatile-lru    # Remove LRU keys with TTL
maxmemory-policy volatile-lfu    # Remove LFU keys with TTL
maxmemory-policy volatile-ttl    # Remove keys with shortest TTL
maxmemory-policy volatile-random # Random removal of keys with TTL

# Allkeys policies (evict any key)
maxmemory-policy allkeys-lru     # LRU on all keys
maxmemory-policy allkeys-lfu     # LFU on all keys
maxmemory-policy allkeys-random  # Random on all keys

Approximate LRU in Redis

True LRU requires maintaining access order for all items, which is expensive. Redis samples N keys and picks the best among them:

# Number of samples to check (default 5)
maxmemory-samples 10

Higher values approach true LRU but use more CPU.

Memory vs Speed

There’s a fundamental trade-off in eviction policy design:

• More tracking = better decisions but more CPU/memory overhead
• Less tracking = faster operations but potentially worse hit rates

For most applications, LRU with a small samples count (3-5) strikes a good balance. The hit rate difference between true LRU and 5-sample LRU is usually negligible.

---

When to Use / When Not to Use

Policy	When to Use	When Not to Use
LRU	Access has temporal locality (recent items accessed again); stable working set that fits in memory	One-time scans that touch every item; large working sets that exceed memory
LFU	Items have stable popularity over time; you want to reward consistently hot items	Rapidly changing access patterns; new items need time to build frequency
FIFO	Debugging or testing; uniform access where simplicity is paramount	Production systems with real access patterns; any case where hit rate matters
TTL	Data that naturally expires (sessions, temporary tokens); freshness-critical data	Static reference data; data without natural expiration
Random	Uniform access patterns; extreme simplicity requirements; baseline comparison	Non-uniform access patterns; any case where specific items must be retained

Decision Guide

graph TD
    A[Access Pattern] --> B{Is access temporal?}
    B -->|Yes| C{Working set fits memory?}
    B -->|No| D{Is frequency stable?}
    C -->|Yes| E[LRU]
    C -->|No| F[LRU with smaller cache or LFU]
    D -->|Yes| G[LFU]
    D -->|No| H{Need freshness?}
    H -->|Yes| I[TTL]
    H -->|No| J[Random or FIFO]

Capacity Estimation: Overhead per Million Keys per Policy

Different eviction policies have different memory overheads for tracking access. This matters when you’re trying to size your cache.

Memory overhead per million keys (approximate Redis):

Policy	Metadata Overhead per Key	Per 1M Keys
FIFO	~8 bytes (queue pointer)	~8MB
Random	0 bytes (no tracking)	0MB
LRU (approximate, 5 samples)	~16 bytes (access timestamp)	~16MB
LFU	~24 bytes (counter + decay timestamp)	~24MB
TTL-only	0 bytes (Redis native)	0MB

Working set size estimation:

working_set_bytes = unique_keys_per_second × avg_key_size × avg_ttl_seconds
cache_hit_probability = min(1, cache_size / working_set_bytes)

For a session cache with 100,000 unique sessions per second, average session size 2KB, average TTL 30 minutes (1800 seconds): working set = 100,000 × 2KB × 1800 = 360GB. A 64GB cache gives hit probability of 64/360 = 17.8% — too low, session cache is not fitting in cache. A 512GB cache gives 512/360 = 142% — working set fits with headroom.

Redis LRU vs LFU memory: LFU needs two values per key: the access counter and a decay timestamp. Counter overflow is a real concern — Redis LFU counters are 8-bit (0-255). After 255 increments, the counter stops growing unless decay kicks in. The lfu-decay-time controls how often counters are halved: lfu-decay-time 10 means every 10 minutes, all counters are multiplied by 0.5. This prevents counter freeze but means occasional access keeps items alive longer than expected.

Memcached slab class sizing: Memcached organizes memory into slab classes of 1MB each, divided into fixed-size chunks. For LRU with eviction, choose chunk size matching your average value size. If your values average 200 bytes but your slab class uses 128-byte chunks, you waste memory. If you use 1MB chunks for 200-byte values, you waste even more. The slabs reassign command can rebalance slab classes in production.

Real-World Case Study: Netflix’s Cache Tuning for Streaming

Netflix streams video to 250+ million subscribers. Their caching strategy is among the most sophisticated in the industry.

Netflix uses a tiered caching approach. The bottom tier is origin storage (Amazon S3). Above that, regional caches handle requests for entire geographic regions. At the top, edge caches serve individual streams. The eviction policy at each tier differs based on content lifecycle.

For the “continue watching” feature — which shows a user’s in-progress videos — Netflix uses LFU eviction. The logic: videos that 10,000 people are actively watching should stay cached over videos that 10 people are watching. LFU keeps the most-requested content. The counter decay is tuned aggressively (lfu-decay-time 1) because a video’s popularity can drop dramatically after it leaves the ” trending” window.

For the “top 10” recommendations list, they use LRU. The list changes daily, and yesterday’s list becomes irrelevant quickly. LRU naturally evicts yesterday’s recommendations as today’s take over.

The lesson: one eviction policy does not fit all use cases. Netflix runs multiple cache clusters for different features, each tuned to its specific access pattern. Auditing which content lives in which cache tier and whether the policy matches the content’s access pattern is ongoing operational work.

Interview Questions

Q: Your Redis cache shows high memory usage but low hit rate. What is likely happening?

The working set does not fit in the available cache. With LRU, if your most frequently accessed data exceeds available memory, those hot items get evicted by newer items that are accessed once and never again (the “one-time access” problem). Diagnose with redis-cli --latency-histogram to see response time distribution, and OBJECT freq to check access frequency of keys. The fix: either increase cache memory, reduce working set size (trim keys or reduce TTL), or move to LFU which rewards consistently popular items over one-time accesses.

Q: You are designing a cache for API responses. The API has 1 million unique endpoints but your cache can only hold 100,000 entries. Which eviction policy would you choose?

With 1M unique endpoints and 100K capacity, 90% of cache entries will never be revisited (assuming uniform distribution). LRU would constantly evict to make room for new entries that arrive once and are never requested again. Better approaches: use API response fingerprinting to identify which endpoints are actually popular (cache only top N), or use LFU to identify truly popular endpoints. TTL alone is not sufficient — without LRU/LFU, the popular endpoints still get evicted when one-time-access items fill the cache. The practical answer is to investigate actual access distribution first: if 20% of endpoints account for 80% of requests, filter your cache to those first.

Q: What happens to LFU frequency counters over time for rarely-accessed items?

LFU counters decay via lfu-decay-time. Every N minutes (default 1), Redis multiplies all LFU counters by 0.5, effectively halving them. A key accessed once (counter = 1) becomes 0.5 → 0 → never considered “least frequently used” for eviction purposes. An item accessed 100 times (counter = 100) becomes 50, then 25, then 12.5. This means LFU with decay correctly ages out old popularity, but if decay is too aggressive, genuinely popular items get evicted because their counters dropped too far. The counter is 8-bit (0-255 max), so items with very high counts can saturate. If decay time is too long, counters never shrink and old popularity data poisons the cache. Tuning lfu-decay-time requires understanding your content lifecycle — video streaming with week-long popularity windows needs different decay than news with hour-long windows.

Q: You are using volatile-lru but some keys have no TTL. The cache fills up and evictions stop working. Why?

volatile-lru only considers keys with a TTL for eviction. If keys without TTL (no expiration) fill 80% of your cache, volatile-lru can only evict from the 20% that have TTL. When the volatile subset fills, volatile-lru runs out of candidates and maxmemory cannot be respected. The solution: either use allkeys-lru to evict from the entire cache regardless of TTL, or ensure ALL keys in the cache have a TTL set. Mixing persistent keys (no TTL) with volatile keys in the same Redis instance when using volatile-lru is an anti-pattern — those persistent keys will eventually fill memory and cause eviction failure.

---

Production Failure Scenarios

Failure	Impact	Mitigation
LRU with full memory	Old items hog cache, new popular items evicted immediately	Monitor eviction rates; use volatile-lru to only evict items with TTL
LFU frequency counter overflow	Items stop being properly ranked, hit rate drops	Tune lfu-decay-time; use maxmemory-samples for better approximation
TTL items not expiring	Memory fills with dead entries; cache becomes ineffective	Enable active expiration (lazyfree_lazy_expire in Redis); monitor expires stat
Random evicts hot items	Users experience random slow requests; inconsistent performance	Switch to LRU or LFU; track what’s actually being evicted
Cache restart with no persistence	All items lost, cold start causes database stampede	Implement cache warming; use Redis RDB persistence or replica for warm restart

Observability Checklist

Metrics to Track

• evicted_keys - Number of items evicted per second; indicates memory pressure
• expired_keys - Number of items that expired via TTL
• stat_keyspace_hits/misses - Cache hit ratio calculation
• used_memory - Current memory usage
• maxmemory - Configured memory limit

# Redis INFO stats to monitor
INFO stats | grep -E "keyspace|evicted|expired"
# Keyspace hits:123456789
# Keyspace misses:12345678
# Expiredkeys:1234567
# Evictedkeys:12345

Logs to Capture

import structlog
logger = structlog.get_logger()

# Monitor eviction events
def check_eviction_risk(redis_client, threshold=0.7):
    info = redis_client.info('memory')
    used = info['used_memory']
    maxmem = info['maxmemory']

    if maxmem > 0:
        usage_ratio = used / maxmem
        if usage_ratio > threshold:
            logger.warning("cache_memory_pressure",
                usage_percent=f"{usage_ratio * 100:.1f}%",
                evicted_recently=info.get('evicted_keys', 0))
    return usage_ratio

Alert Rules

- alert: HighEvictionRate
  expr: rate(redis_evicted_keys_total[5m]) > 100
  for: 5m
  labels:
    severity: warning
  annotations:
    summary: "High cache eviction rate - memory pressure"

- alert: LowHitRate
  expr: redis_keyspace_hits_total / (redis_keyspace_hits_total + redis_keyspace_misses_total) < 0.7
  for: 10m
  labels:
    severity: critical
  annotations:
    summary: "Cache hit rate below 70%"

Security Checklist

• Configure memory limits - Prevent cache from consuming all system memory
• Disable dangerous commands - FLUSHDB, FLUSHALL can wipe entire cache
• Use ACLs - Restrict which commands each user/role can execute
• Bind to internal interfaces - Never expose Redis/Memcached to public internet
• Monitor for abnormal eviction patterns - Could indicate attack or misconfiguration
• Validate key inputs - Prevent injection of extremely long or special character keys
• Set up replication authentication - Replicas should require auth to sync from primary

# Redis security configuration
rename-command FLUSHDB ""
rename-command FLUSHALL ""
rename-command DEBUG ""
maxmemory 100mb
maxmemory-policy allkeys-lru

Common Pitfalls / Anti-Patterns

1. Assuming LRU Means “Oldest Recently Used”

LRU evicts the least recently used - the item whose last access was longest ago. Not the item with the oldest timestamp in absolute terms.

# WRONG understanding: LRU keeps oldest items
# The item added 1 year ago but accessed 1 minute ago is NOT
# the LRU item. The item added 1 second ago but not accessed
# since is the LRU item.

# RIGHT understanding:
# LRU = Least Recently Used = longest time since last access

2. Mixing Volatile and Non-Volatile Keys

Using both volatile-lru and non-volatile (no TTL) keys can cause memory issues.

# PROBLEM: Cache fills with non-volatile keys
# volatile-lru can only evict keys WITH TTL
# If keys without TTL fill memory, volatile-lru has nothing to evict

# SOLUTION: Either use only volatile keys with TTL, or use allkeys-lru
# to evict from entire cache
maxmemory-policy allkeys-lru  # Evicts anything
# OR
maxmemory-policy volatile-lru  # Only evicts keys with TTL
# Never mix strategies - pick one approach

3. Setting TTL Too Long for Volatile Policies

If using volatile-lru or volatile-lfu, keys without TTL never get evicted and can fill memory.

# PROBLEM: Some keys have no TTL, some have very long TTL
redis.setex("user:123", 86400, data)      # 24 hour TTL
redis.set("config", json.dumps(config))   # NO TTL - never expires

# After cache fills with NO-TTL keys, volatile-lru can't free space
# because it only touches keys with TTL

# SOLUTION: Always use SETEX/SET with EX option; never use SET without TTL
redis.setex("config", 86400, json.dumps(config))  # Always with TTL

4. Ignoring Eviction Rate in Production

Low eviction count in dev, high eviction count in production means memory miscalculation.

# Development: Small dataset, everything fits
# Production: Large dataset, cache too small

# Monitor in production:
# redis-cli INFO stats | grep evicted_keys
# If evicted_keys > 0 frequently, cache is too small or policy wrong

5. Not Accounting for LRU Approximation in Redis

Redis doesn’t do true LRU. It samples keys. Small samples = inaccurate LRU.

# Default 5 samples - may miss true LRU candidate
maxmemory-samples 5

# For more accurate LRU (more CPU, better decisions)
maxmemory-samples 10

# For very large caches with non-uniform access
maxmemory-samples 16

Quick Recap

Key Bullets

• LRU is the default choice for most use cases because temporal locality is common
• LFU rewards consistency - items accessed frequently stay cached longer
• TTL is not an eviction policy per se - it’s a freshness mechanism
• FIFO and Random are baselines, not production choices for hit-rate-critical workloads
• Redis samples ~5 keys for LRU approximation (configurable with maxmemory-samples)
• volatile-* policies only evict keys that have a TTL set

Copy/Paste Checklist

# Redis eviction policy configuration
# For general caching (evict any key):
maxmemory 100mb
maxmemory-policy allkeys-lru

# For cache with some persistent keys:
maxmemory 100mb
maxmemory-policy allkeys-lru  # OR allkeys-lfu

# For cache where items MUST have TTL:
maxmemory 100mb
maxmemory-policy volatile-lru  # Only evict keys WITH TTL
maxmemory-policy volatile-lfu

# For pure TTL-based expiration (no eviction):
maxmemory-policy volatile-ttl  # Evicts keys closest to expiration
maxmemory 100mb

# For debugging or very specific cases:
maxmemory-policy allkeys-random
maxmemory-policy volatile-random

# Monitoring commands
INFO stats | grep -E "keyspace|evicted|expired"
OBJECT freq user:123  # Check access frequency of a key
DEBUG OBJECT LRU user:123  # Check LRU position of a key

---

See Also

• Caching Strategies — How to use caches effectively with these eviction policies
• Redis & Memcached — Implementing these policies in real caching engines
• Distributed Caching — Scaling eviction across multiple nodes

---

Conclusion

Pick your eviction policy based on your access patterns. LRU is the default for most use cases because temporal locality is common. LFU rewards consistency. FIFO and random are mostly for specialized cases or as baselines.

The biggest mistake people make is treating eviction policy as a one-time decision. Monitor your hit rate. If it drops, your access patterns might have changed and a different policy might serve you better.