Cache Eviction Policies

A cache has bounded memory. When it is full and a new entry must be stored, an eviction policy chooses an existing entry to remove. A good policy removes the entry least likely to be requested again, which maximizes the hit ratio. The optimal policy (Belady's algorithm) evicts the entry whose next use is furthest in the future. It requires knowledge of future requests, so practical policies approximate it using past behavior.

Common policies

FIFO

Entries leave in insertion order regardless of use. The cost per operation is O(1) and metadata is minimal, but a frequently read entry inserted early is evicted before a never-read entry inserted later.

LRU

Least Recently Used evicts the entry whose last access is oldest. It assumes recently used entries will be used again (temporal locality). Each hit moves the entry to the "most recent" end of a list.

Implementation: a hash map from key to a node in a doubly linked list. Lookup, promotion, insertion, and eviction are all O(1).

graph LR
    subgraph list["Recency list"]
        direction LR
        H["head: most recent"] --> B["B"] --> A["A"] --> T["tail: least recent"]
    end
    M["HashMap key to node"] -.-> H
    M -.-> B
    M -.-> A

Weakness: scan pollution. A sequential scan touching many keys once each makes them all "most recent" and evicts the useful working set.

Worked example with capacity 3. The hot keys A and B are read repeatedly and sit in the cache together with C. A batch job then reads X1, X2, X3 once each. Under LRU, after X1, X2, X3 the cache holds exactly X1, X2, X3, so the next reads of A and B miss. Under LFU, A and B have counts well above 1 and the scan keys (count 1) are evicted first, so A and B keep hitting. Under FIFO the result depends only on insertion order, so A and B are evicted if they were inserted before the scan keys.

LFU

Least Frequently Used evicts the entry with the lowest access count. It keeps keys that are popular over the long run and resists scans. Problems: a key that was popular in the past keeps a high count and stays after it stops being requested, and a newly inserted key has a low count and is evicted quickly. Implementations add aging (periodically halving counts) or use approximate counters. An O(1) LFU uses a map of frequency to a list of entries plus a tracked minimum frequency. Some caches use a compact probabilistic frequency sketch (Count-Min sketch) with an admission filter instead of exact counters.

Random

Evicting a uniformly random entry needs no ordering metadata and no synchronization on reads. Redis also offers approximated LRU and LFU: it samples a small number of keys and evicts the best candidate among the sample, avoiding a global list.

TTL

Entries expire after a fixed time regardless of pressure. Expiry keeps data fresh; eviction handles memory. Most caches use both: TTL for staleness, an eviction policy for capacity.

Adaptive policies

• 2Q keeps a small FIFO queue for entries seen once and a main LRU queue for entries seen at least twice. A scan passes through the first queue without displacing the main queue.
• ARC (Adaptive Replacement Cache) keeps two LRU lists, one for entries seen once (recency) and one for entries seen more than once (frequency), plus history lists of recently evicted keys. Hits on the history lists shift the target size between the two lists, so the policy adapts to the workload.
• LRU-K evicts by the time of the K-th most recent access, which filters out one-time accesses.
• Segmented LRU splits the list into probationary and protected segments; entries promoted on a second hit enter the protected segment.

LRU in Java

The implementation below uses a HashMap from key to node and a doubly linked list of nodes joined by object references. Two sentinel nodes (head and tail, which hold no entry) remove the special cases for an empty list. The garbage collector reclaims an evicted node, including the reference cycle between neighbours, once nothing reachable refers to it.

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

public class Main {
    static final class LruCache {
        private static final class Node {
            int key;
            int value;
            Node prev;
            Node next;
        }

        private final int capacity;
        private final Map<Integer, Node> map = new HashMap<>();
        private final Node head = new Node(); // sentinel: next is the most recently used
        private final Node tail = new Node(); // sentinel: prev is the least recently used

        LruCache(int capacity) {
            if (capacity < 1) {
                throw new IllegalArgumentException("capacity must be positive");
            }
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        private void detach(Node n) {
            n.prev.next = n.next;
            n.next.prev = n.prev;
        }

        private void pushFront(Node n) {
            n.prev = head;
            n.next = head.next;
            head.next.prev = n;
            head.next = n;
        }

        Optional<Integer> get(int key) {
            var node = map.get(key);
            if (node == null) {
                return Optional.empty();
            }
            detach(node);
            pushFront(node); // a hit makes the entry the most recent
            return Optional.of(node.value);
        }

        void put(int key, int value) {
            var existing = map.get(key);
            if (existing != null) {
                existing.value = value;
                detach(existing);
                pushFront(existing);
                return;
            }
            Node node;
            if (map.size() == capacity) {
                // Reuse the node of the least recently used entry.
                node = tail.prev;
                detach(node);
                map.remove(node.key);
            } else {
                node = new Node();
            }
            node.key = key;
            node.value = value;
            map.put(key, node);
            pushFront(node);
        }
    }

    public static void main(String[] args) {
        var cache = new LruCache(2);
        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println(cache.get(1)); // 1 becomes most recent
        cache.put(3, 30); // evicts key 2
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        cache.put(1, 11); // update existing key
        System.out.println(cache.get(1));
    }
}

Optional[10]
Optional.empty
Optional[30]
Optional[11]

The library offers a shorter route: a LinkedHashMap created with access order (new LinkedHashMap<>(16, 0.75f, true)) and a subclass that overrides removeEldestEntry is an LRU cache. The hand-written version shows how the map and the list cooperate.

Both get and put are O(1) on average. A concurrent cache must synchronize the list: every read mutates recency, so a single lock (a synchronized method or a ReentrantLock) becomes a bottleneck. Real implementations shard the cache into independent segments, or record accesses in a buffer and apply them in batches.

Choosing a policy

• General-purpose workloads with temporal locality: LRU or an approximation.
• Stable popularity distributions (catalog pages, celebrity profiles): LFU with aging.
• Workloads with occasional large scans: 2Q, ARC, or segmented LRU.
• Very large caches where per-entry metadata cost matters: sampled or random eviction.

Interview questions

• Why does LRU use both a hash map and a doubly linked list? The map gives O(1) lookup of a node by key, and the doubly linked list gives O(1) removal from any position and insertion at the head. Either structure alone makes one operation O(n).
• What is scan pollution and which policies resist it? A one-pass read of many keys pushes them to the most-recent position and evicts the hot set under LRU. LFU, 2Q, ARC, and segmented LRU resist it because a single access does not earn a protected position.
• What is the downside of pure LFU? Counts never decay, so keys that were once popular stay indefinitely, and new keys start with low counts and are evicted early. Aging or admission filters address both.
• How does Redis avoid a global LRU list? It samples a few random keys and evicts the least recently used among them, which approximates LRU with no per-access list maintenance.