Caching Part 4: Eviction Policies — LRU, LFU, and Making Room

Your cache has finite memory. When it fills up, something has to go. The question is: what do you evict, and how do you decide?

The Core Policies

LRU — Least Recently Used

Evict the item that hasn't been accessed for the longest time. The assumption: if you haven't read it recently, you probably won't read it soon.

Red = oldest (next to evict), Green = most recent

A minimal LRU cache using Java's LinkedHashMap:

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

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

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

When to use: General-purpose default. Works well for most access patterns.

LFU — Least Frequently Used

Evict the item with the lowest total access count. A page accessed 1000 times gets priority over one accessed twice, regardless of when.

public class LFUCache<K, V> {
    private final int maxSize;
    private final Map<K, V> cache = new HashMap<>();
    private final Map<K, Integer> frequencies = new HashMap<>();

    public V get(K key) {
        if (!cache.containsKey(key)) return null;
        frequencies.merge(key, 1, Integer::sum);
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (cache.size() >= maxSize && !cache.containsKey(key)) {
            evictLeastFrequent();
        }
        cache.put(key, value);
        frequencies.put(key, 1);
    }

    private void evictLeastFrequent() {
        var leastUsed = frequencies.entrySet().stream()
            .min(Map.Entry.comparingByValue())
            .map(Map.Entry::getKey).orElseThrow();
        cache.remove(leastUsed);
        frequencies.remove(leastUsed);
    }
}

When to use: When access patterns are stable — the same items stay popular over time. Bad for rapidly-changing popularity.

Other Policies at a Glance

Policy	Evicts	Best For
FIFO	Oldest entry (by insertion time)	Simple, low overhead
Random	Random entry	Zero overhead, surprisingly decent
ARC	Adaptive — balances recency & frequency	Self-tuning (used in ZFS)
LIRS	Low Inter-reference Recency Set	Better than LRU for scan-heavy workloads

In practice, you'll rarely implement these yourself. Redis, Caffeine, and Memcached have battle-tested implementations. Understand the concepts, then configure the right policy.

TTL vs Eviction: Two Different Problems

TTL (Time To Live) — "This data expires at a specific time." Used for data freshness. A product price might have a 10-minute TTL.

Eviction policy — "The cache is full, what do I remove?" Used for memory management. These are independent knobs:

Both matter. TTL keeps data fresh. Eviction keeps memory bounded.

Redis Eviction Policies

Redis has 8 built-in maxmemory-policy settings. Here's what each one does:

No Eviction

Policy	Behavior
`noeviction`	Returns errors on write when memory is full. Default.

Evict by Recency (LRU)

Policy	Scope	Behavior
`allkeys-lru`	All keys	Evict least recently used key overall
`volatile-lru`	Keys with TTL only	Evict least recently used among keys that have a TTL

Evict by Frequency (LFU)

Policy	Scope	Behavior
`allkeys-lfu`	All keys	Evict least frequently used key overall
`volatile-lfu`	Keys with TTL only	Evict least frequently used among keys that have a TTL

Evict Randomly

Policy	Scope	Behavior
`allkeys-random`	All keys	Random eviction
`volatile-random`	Keys with TTL only	Random among keys with TTL

Evict by TTL

Policy	Behavior
`volatile-ttl`	Evict key with shortest TTL among keys with TTL set

# redis.conf
maxmemory 2gb
maxmemory-policy allkeys-lru

// Or configure via Spring Boot
@Configuration
class RedisConfig {

    @Bean
    fun redisConnectionFactory(): LettuceConnectionFactory {
        val config = RedisStandaloneConfiguration("localhost", 6379)
        return LettuceConnectionFactory(config)
    }

    @Bean
    fun redisTemplate(connectionFactory: RedisConnectionFactory): RedisTemplate<String, Any> {
        return RedisTemplateBuilder<String, Any>()
            .connectionFactory(connectionFactory)
            .defaultSerializer(GenericJackson2JsonRedisSerializer())
            .build()
    }
}

Which Redis Policy Should You Use?

Monitoring Eviction Health

Track these metrics to know if your eviction policy is working:

Eviction Rate

< 5%

If >20%, your cache is too small or the wrong policy. Monitor with: INFO stats | grep evicted

Hit Ratio

> 85%

If dropping after a policy change, the new policy doesn't match your access pattern.

# Check Redis eviction stats
redis-cli INFO stats | grep -E "evicted|hit|miss"
# evicted_keys:1523
# keyspace_hits:89432
# keyspace_misses:12340

Key Takeaways

LRU is the default for a reason — it works well for most workloads
LFU is better when the same items stay popular over time
TTL (freshness) and eviction (memory) are independent — configure both
Redis has 8 policies — allkeys-lru is right for most pure-cache use cases
Monitor eviction rate and hit ratio to catch misconfigurations early
If eviction rate is >20%, your cache is undersized or your policy is wrong

Continue to Part 5: Cache Invalidation →

Your cache has finite memory. When it fills up, something has to go. The question is: what do you evict, and how do you decide?

The Core Policies

LRU — Least Recently Used

Evict the item that hasn't been accessed for the longest time. The assumption: if you haven't read it recently, you probably won't read it soon.

Red = oldest (next to evict), Green = most recent

A minimal LRU cache using Java's LinkedHashMap:

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

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

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

When to use: General-purpose default. Works well for most access patterns.

LFU — Least Frequently Used

Evict the item with the lowest total access count. A page accessed 1000 times gets priority over one accessed twice, regardless of when.

public class LFUCache<K, V> {
    private final int maxSize;
    private final Map<K, V> cache = new HashMap<>();
    private final Map<K, Integer> frequencies = new HashMap<>();

    public V get(K key) {
        if (!cache.containsKey(key)) return null;
        frequencies.merge(key, 1, Integer::sum);
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (cache.size() >= maxSize && !cache.containsKey(key)) {
            evictLeastFrequent();
        }
        cache.put(key, value);
        frequencies.put(key, 1);
    }

    private void evictLeastFrequent() {
        var leastUsed = frequencies.entrySet().stream()
            .min(Map.Entry.comparingByValue())
            .map(Map.Entry::getKey).orElseThrow();
        cache.remove(leastUsed);
        frequencies.remove(leastUsed);
    }
}

When to use: When access patterns are stable — the same items stay popular over time. Bad for rapidly-changing popularity.

Other Policies at a Glance

Policy	Evicts	Best For
FIFO	Oldest entry (by insertion time)	Simple, low overhead
Random	Random entry	Zero overhead, surprisingly decent
ARC	Adaptive — balances recency & frequency	Self-tuning (used in ZFS)
LIRS	Low Inter-reference Recency Set	Better than LRU for scan-heavy workloads

In practice, you'll rarely implement these yourself. Redis, Caffeine, and Memcached have battle-tested implementations. Understand the concepts, then configure the right policy.

TTL vs Eviction: Two Different Problems

TTL (Time To Live) — "This data expires at a specific time." Used for data freshness. A product price might have a 10-minute TTL.

Eviction policy — "The cache is full, what do I remove?" Used for memory management. These are independent knobs:

Both matter. TTL keeps data fresh. Eviction keeps memory bounded.

Redis Eviction Policies

Redis has 8 built-in maxmemory-policy settings. Here's what each one does:

No Eviction

Policy	Behavior
`noeviction`	Returns errors on write when memory is full. Default.

Evict by Recency (LRU)

Policy	Scope	Behavior
`allkeys-lru`	All keys	Evict least recently used key overall
`volatile-lru`	Keys with TTL only	Evict least recently used among keys that have a TTL

Evict by Frequency (LFU)

Policy	Scope	Behavior
`allkeys-lfu`	All keys	Evict least frequently used key overall
`volatile-lfu`	Keys with TTL only	Evict least frequently used among keys that have a TTL

Evict Randomly

Policy	Scope	Behavior
`allkeys-random`	All keys	Random eviction
`volatile-random`	Keys with TTL only	Random among keys with TTL

Evict by TTL

Policy	Behavior
`volatile-ttl`	Evict key with shortest TTL among keys with TTL set

# redis.conf
maxmemory 2gb
maxmemory-policy allkeys-lru

// Or configure via Spring Boot
@Configuration
class RedisConfig {

    @Bean
    fun redisConnectionFactory(): LettuceConnectionFactory {
        val config = RedisStandaloneConfiguration("localhost", 6379)
        return LettuceConnectionFactory(config)
    }

    @Bean
    fun redisTemplate(connectionFactory: RedisConnectionFactory): RedisTemplate<String, Any> {
        return RedisTemplateBuilder<String, Any>()
            .connectionFactory(connectionFactory)
            .defaultSerializer(GenericJackson2JsonRedisSerializer())
            .build()
    }
}

Which Redis Policy Should You Use?

Monitoring Eviction Health

Track these metrics to know if your eviction policy is working:

Eviction Rate

< 5%

If >20%, your cache is too small or the wrong policy. Monitor with: INFO stats | grep evicted

Hit Ratio

> 85%

If dropping after a policy change, the new policy doesn't match your access pattern.

# Check Redis eviction stats
redis-cli INFO stats | grep -E "evicted|hit|miss"
# evicted_keys:1523
# keyspace_hits:89432
# keyspace_misses:12340

Key Takeaways

LRU is the default for a reason — it works well for most workloads
LFU is better when the same items stay popular over time
TTL (freshness) and eviction (memory) are independent — configure both
Redis has 8 policies — allkeys-lru is right for most pure-cache use cases
Monitor eviction rate and hit ratio to catch misconfigurations early
If eviction rate is >20%, your cache is undersized or your policy is wrong

Continue to Part 5: Cache Invalidation →

Caching Deep Dive(9-part series)

The Core Policies

LRU — Least Recently Used

LFU — Least Frequently Used

Other Policies at a Glance

TTL vs Eviction: Two Different Problems

Redis Eviction Policies

No Eviction

Evict by Recency (LRU)

Evict by Frequency (LFU)

Evict Randomly

Evict by TTL

Which Redis Policy Should You Use?

Monitoring Eviction Health

Key Takeaways

Tags

Related Posts

Caching Part 6: When It Goes Wrong — Thundering Herds, Hot Keys, and Nightmares

Caching Part 1: Fundamentals — Why, When, and When Not to Cache

Caching Part 2: The Landscape — Where to Put Your Cache

Caching Deep Dive(9-part series)

The Core Policies

LRU — Least Recently Used

LFU — Least Frequently Used

Other Policies at a Glance

TTL vs Eviction: Two Different Problems

Redis Eviction Policies

No Eviction

Evict by Recency (LRU)

Evict by Frequency (LFU)

Evict Randomly

Evict by TTL

Which Redis Policy Should You Use?

Monitoring Eviction Health

Key Takeaways

Tags

Related Posts

Caching Part 6: When It Goes Wrong — Thundering Herds, Hot Keys, and Nightmares

Caching Part 1: Fundamentals — Why, When, and When Not to Cache

Caching Part 2: The Landscape — Where to Put Your Cache