Eviction Policies: LRU, LFU, TTL

In one line

When the cache is full, what leaves? LRU, LFU, FIFO, random, and how Redis does it.

0/16 · 0%

Think of it like this

A small fridge that's full: to fit new groceries, you have to throw something out. LRU throws out whatever you haven't touched in the longest time; LFU throws out whatever you use least often; TTL just tosses food after its expiry date, regardless.

Key ideas

01
LRU (Least Recently Used): evict the key not touched for the longest time — the default people actually mean.
02
LFU (Least Frequently Used): evict the least-accessed — better for skewed access, worse for scanning bursts.
03
TTL: time-based expiry — the freshness dial; not an eviction policy but a partner of one.
04
FIFO / random / LIRS exist; interviews want you to name LRU and justify it over the rest.
05
Redis eviction modes: noeviction, allkeys-lru, volatile-lru (only expiring keys), and LFU + random variants — configured via maxmemory-policy.
06
Implementing LRU: LinkedHashMap access-order, or HashMap + doubly-linked list — an LLD favorite.

Java / Spring map

→
Implement LinkedHashMap(0.75f, true) with removeEldestEntry — that's LRU in 5 lines.

Code & diagrams

LruCache.javajava

The 5-line LRU that interviews love, plus the Redis config line.

public class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;

  public LruCache(int max) {
    super(16, 0.75f, true);          // access-order = true → LRU behavior
    this.max = max;
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;             // evict least-recently-used when over
  }
}

// Redis side — the production version is one line:
// maxmemory 8gb
// maxmemory-policy allkeys-lru      (or volatile-lru / allkeys-lfu)

Explain without notes

LFU vs LRU under a scan burst: which one gets flushed out, and why does that matter for a feed?

Practice

Add a 'last access' timestamp map + O(1) eviction to the concurrent cache from Phase 5.

Trade-offs

↔
LRU is simple and burts-friendly; LFU resists thrash but is more bookkeeping. TTL adds freshness on top of both.

Run it in production

You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:

Stateful · Redis memory, eviction & persistence

maxmemory policies, big and hot keys, RDB/AOF, and slow commands.

Completion checklist

I can answer 'what's evicted when the cache is full' with LRU/LFU and a why.

Back to phase

Command Palette