LRU and LFU Caches: Designing O(1) Eviction Architectures

In computing systems, memory caches have strictly limited capacity relative to persistent backing stores. When a cache reaches its maximum capacity and a new item must be stored, an eviction algorithm must decide which existing item to discard.

The two primary eviction strategies are **LRU (Least Recently Used)**, which discards the item that hasn't been accessed for the longest period of time, and **LFU (Least Frequently Used)**, which tracks access frequencies and evicts items with the lowest cumulative hit counts. Designing both systems requires combining multiple data structures to achieve strict O(1) get and put time complexity.

LRU Cache Architecture: Hash Map + Doubly Linked List

A single data structure cannot provide both O(1) random key lookup and O(1) order tracking:

• Hash Map: Provides O(1) key-to-node pointer lookups, but maintains no sequential recency order.
• Doubly Linked List (DLL): Allows O(1) node removal and O(1) insertion at the head/tail once a pointer is known, but searching for a key takes linear O(N) time.
• The Hybrid Solution: Storing pointers to Doubly Linked List nodes directly inside the Hash Map achieves simultaneous O(1) access and O(1) reordering.

LRU Invariants

• Most Recently Used (MRU): Placed right after the dummy head sentinel.
• Least Recently Used (LRU): Placed right before the dummy tail sentinel.
• On Access (get): Locate node in O(1) via map, splice it out of its current DLL position, and insert it at the head (MRU).
• On Insert (put): If key exists, update value and move node to head. If capacity is exceeded, detach node before tail (LRU), delete its entry from the hash map, and insert the new node at the head.

C++ LRU Cache Implementation Blueprint

#include <unordered_map>

class LRUCache {
private:
    struct Node {
        int key, value;
        Node *prev = nullptr;
        Node *next = nullptr;
        Node(int k, int v) : key(k), value(v) {}
    };

    int capacity;
    std::unordered_map<int, Node*> map;
    Node *head;
    Node *tail;

    void removeNode(Node *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(Node *node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void moveToHead(Node *node) {
        removeNode(node);
        addToHead(node);
    }

public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        Node *node = map[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            Node *node = map[key];
            node->value = value;
            moveToHead(node);
        } else {
            if (map.size() >= capacity) {
                Node *lru = tail->prev;
                removeNode(lru);
                map.erase(lru->key);
                delete lru;
            }
            Node *newNode = new Node(key, value);
            map[key] = newNode;
            addToHead(newNode);
        }
    }
};

LFU Cache Architecture: Frequency Buckets in O(1)

LFU evicts the item with the smallest access count. If there is a tie in frequency, it falls back to LRU eviction among the tied candidates.

Naive min-heap approaches achieve O(log N) operations. To achieve strict O(1) across all operations, an LFU cache requires three synchronized structures:

1. Key Map: Maps each key to a node containing `{key, value, frequency}`.
2. Frequency Map: Maps each frequency count (1, 2, 3...) to its own dedicated Doubly Linked List of nodes having that exact access frequency.
3. minFreq Tracker: An integer tracking the current lowest frequency present across the entire cache, updated in O(1) whenever the last element of that frequency list is promoted.

LRU vs. LFU: Performance Trade-Offs

• Scan Resistance: LRU is vulnerable to 'cache pollution'—a sequential bulk scan of single-use data flushes all frequently used hot entries out of the cache. LFU prevents this by retaining items with high historical access counts.
• Frequency Starvation: LFU can suffer from 'cache bloat' when previously popular keys become obsolete but remain in the cache due to historically accumulated frequency counts (requiring decay policies).
• Implementation Complexity: LRU requires only 1 map and 1 DLL; LFU requires 2 maps, multiple DLLs, and frequency tracking state.
• Memory Footprint: LRU has lower pointer overhead per cached entry than LFU.

Real-World Engineering Applications

1. Operating System Page Replacement: Virtual memory paging subsystems implement clock/second-chance algorithms as hardware-friendly approximations of LRU.
2. Database Buffer Pools: MySQL InnoDB and PostgreSQL shared memory managers utilize segmented LRU variations (Midpoint Insertion) to cache disk pages in RAM without pollution from sequential table scans.
3. Content Delivery Networks (CDNs): Edge nodes (e.g., Cloudflare, Akamai) use hybrid LFU/LRU policies (such as TinyLFU / W-TinyLFU) to cache static assets and media files.
4. Web Framework In-Memory Caching: API gateways and caching middleware employ LRU buffers to store precomputed JSON responses and authorization tokens.