System Design: LRU and LFU Cache

Apr 7, 2026 7 minutes to read

LRU and LFU cache design is a classic interview question that combines data structures with systems thinking. Most candidates implement the data structure correctly; the EM-level discussion extends into eviction trade-offs, distributed cache behavior, and when to use each. Here’s the complete picture.

LRU Cache (Least Recently Used)

Eviction policy: When the cache is full, evict the item that was accessed least recently.

The insight: Temporal locality — recently accessed items are more likely to be accessed again soon. If you haven’t touched an item in a while, you’re less likely to need it.

Data Structure: HashMap + Doubly Linked List

The combination gives O(1) for all operations: get, put, and eviction.

HashMap (key → Node): O(1) lookup
Doubly linked list: Maintains access order. Most recently used at head; least recently used at tail. O(1) insert/remove when you have a pointer to the node.

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head;  // dummy head (most recent side)
    private final Node tail;  // dummy tail (LRU side)
    
    static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node);  // mark as most recently used
        return node.value;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node lru = tail.prev;  // LRU is just before the dummy tail
                removeNode(lru);
                map.remove(lru.key);
            }
        }
    }
    
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

Complexity:

get: O(1) — HashMap lookup + O(1) list node move
put: O(1) — HashMap insert/update + O(1) list insert, O(1) eviction
Space: O(capacity)

Java built-in shortcut: LinkedHashMap with accessOrder = true implements LRU in ~5 lines:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int cap;
    LRUCache(int cap) { super(cap, 0.75f, true); this.cap = cap; }
    public int get(int k) { return super.getOrDefault(k, -1); }
    public void put(int k, int v) { super.put(k, v); }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
        return size() > cap;
    }
}

LFU Cache (Least Frequently Used)

Eviction policy: When the cache is full, evict the item that has been accessed the fewest times total. Ties broken by LRU (least recently used among equal-frequency items).

The insight: Frequency locality — items accessed many times are likely to be accessed again. Protects hot items even if they weren’t accessed recently.

Data Structure: HashMap + Frequency Buckets

LFU is harder to implement than LRU. The key challenge: O(1) eviction requires knowing which item has the minimum frequency, and updating frequency in O(1).

Three data structures:

keyToVal: HashMap of key → value
keyToFreq: HashMap of key → frequency
freqToKeys: HashMap of frequency → LinkedHashSet<key> (ordered set for LRU tie-breaking)
minFreq: integer tracking the current minimum frequency

class LFUCache {
    private final int capacity;
    private int minFreq;
    private final Map<Integer, Integer> keyToVal;
    private final Map<Integer, Integer> keyToFreq;
    private final Map<Integer, LinkedHashSet<Integer>> freqToKeys;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        minFreq = 0;
        keyToVal  = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
    }
    
    public int get(int key) {
        if (!keyToVal.containsKey(key)) return -1;
        incrementFreq(key);
        return keyToVal.get(key);
    }
    
    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, value);
            incrementFreq(key);
            return;
        }
        if (keyToVal.size() >= capacity) evict();
        keyToVal.put(key, value);
        keyToFreq.put(key, 1);
        freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;  // newly inserted item has frequency 1
    }
    
    private void incrementFreq(int key) {
        int freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        freqToKeys.get(freq).remove(key);
        if (freqToKeys.get(freq).isEmpty()) {
            freqToKeys.remove(freq);
            if (minFreq == freq) minFreq++;  // minimum may have increased
        }
        freqToKeys.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }
    
    private void evict() {
        LinkedHashSet<Integer> minFreqKeys = freqToKeys.get(minFreq);
        int evictKey = minFreqKeys.iterator().next();  // oldest = first in LinkedHashSet
        minFreqKeys.remove(evictKey);
        if (minFreqKeys.isEmpty()) freqToKeys.remove(minFreq);
        keyToVal.remove(evictKey);
        keyToFreq.remove(evictKey);
    }
}

Complexity: O(1) for all operations. The LinkedHashSet preserves insertion order for LRU tie-breaking within a frequency bucket.

LRU vs LFU: When to Use Each

LRU Wins When:

Recency is a better predictor than frequency. Most web caches: a page viewed recently is more likely to be viewed again than one viewed 100 times six months ago.
Workload has temporal locality. News feeds, trending content, session data.
Simpler is better. LRU is much easier to implement and reason about.
Scan resistance isn’t needed. (LRU is vulnerable to scan pollution — scanning a large dataset evicts hot items. LFU isn’t.)

LFU Wins When:

Frequency is a better predictor than recency. Database buffer pool: frequently accessed table pages should stay in memory regardless of when they were last touched.
Protecting hot items from cold scans. A rare sequential scan evicts your hot items with LRU. LFU keeps frequently accessed items even through a scan.
Long-lived caches with stable hot items. Configuration data, lookup tables, product catalog that’s accessed millions of times.

Real-world usage:

Redis: Supports both allkeys-lru and allkeys-lfu eviction policies. Redis’s LFU uses a probabilistic approximate frequency counter (not exact count) for efficiency.
Database buffer pools: PostgreSQL uses a variant of clock sweep (approximate LRU). Oracle and MySQL use LRU with some LFU characteristics.
CPU caches: Hardware uses LRU approximations.
CDNs: Typically LRU with frequency considerations for popular content.

Thread Safety Considerations

The implementations above are not thread-safe. For concurrent access:

Option 1: Synchronized wrapper

Map<Integer, Integer> cache = Collections.synchronizedMap(new LRUCache(100));

Simple but serializes all access — poor concurrent performance.

Option 2: ReadWriteLock

ReadWriteLock lock = new ReentrantReadWriteLock();
// Multiple readers OR one writer

Better throughput for read-heavy workloads (multiple concurrent reads allowed).

Option 3: Caffeine (Java library) For production use, use Caffeine rather than rolling your own. It implements an advanced variant called W-TinyLFU — a window-based TinyLFU that provides near-optimal hit rate for most workloads, is highly concurrent, and handles eviction off the critical path.

Cache<String, User> cache = Caffeine.newBuilder()
    .maximumSize(10_000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build();

W-TinyLFU outperforms both LRU and LFU on real-world workloads by using a frequency sketch (Count-Min Sketch) for space-efficient frequency estimation and a small admission window for new items.

Distributed Cache Eviction

In Redis (distributed cache), eviction happens when maxmemory is reached. Redis eviction policies:

Policy	Behavior
`noeviction`	Return error when memory full
`allkeys-lru`	Evict least recently used across all keys
`volatile-lru`	Evict LRU among keys with TTL set
`allkeys-lfu`	Evict least frequently used (Redis 4.0+)
`volatile-lfu`	Evict LFU among keys with TTL set
`allkeys-random`	Evict random keys
`volatile-ttl`	Evict keys with shortest TTL first

Recommendation:

allkeys-lru for general caching (session data, results cache)
allkeys-lfu for stable-hot-item caches (config, lookup data)
volatile-lru if you have a mix of permanent and ephemeral keys and don’t want permanent ones evicted
Never noeviction unless your application explicitly handles cache-full errors

Redis LFU implementation detail: Redis doesn’t count exact access frequency (too much memory). Instead, it uses a probabilistic counter that increments logarithmically (each access has a decreasing probability of incrementing the counter). Combined with a decay factor over time, this approximates LFU efficiently.

EM Talking Points

Why not just use a TreeMap? Sorted by frequency, yes — but put and get are O(log N), not O(1). The LinkedHashMap/HashMap combination achieves O(1).
Cache size vs hit rate: Doubling cache size often doesn’t double hit rate. The relationship follows the working set — once you’ve cached the hot working set, adding more capacity has diminishing returns. Profile hit rate vs memory to find the knee of the curve.
Memory estimation: 1M LRU entries, each key/value 64 bytes → ~64MB plus HashMap overhead (~32 bytes/entry for Java HashMap) → ~96MB. Know how to estimate memory requirements.
When to prefer application-level cache (Caffeine) vs Redis: Caffeine is sub-microsecond, Redis is ~1ms. For very high frequency lookups (10M/sec), Caffeine wins. For shared cache across instances, Redis. Often use both: Caffeine L1, Redis L2.