vault

Least Recently Used Cache

12 min read

Least Recently Used Cache

A Least Recently Used (LRU) cache is a fixed-capacity key-value store that, when full, evicts the entry that was touched least recently to make room for a new one. The canonical implementation pairs a hash map (for O(1) key lookup) with a doubly linked list (for O(1) recency-order updates). Every get and put operation runs in O(1) worst case. LRU is the default eviction policy in Java’s LinkedHashMap (with accessOrder=true), one of Redis’s maxmemory-policy options, the basis for many database buffer pools, and LeetCode 146 — perhaps the most-asked design question in entry-level interviews.

1. Intuition — The Stack of Books on Your Desk

You have a desk with room for exactly 5 books. Every time you read a book, you put it on top of the pile. When a 6th book arrives and there’s no room, you grab the book at the bottom — the one you haven’t touched in the longest time — and shelve it.

That’s LRU in one sentence: when capacity is exceeded, evict the entry whose last access was longest ago. The temporal-locality assumption (recently-used things are likely to be used again soon) is what makes LRU effective in practice. It is not optimal — Belady’s MIN algorithm (1966) proved that the optimal page replacement is “evict the page that will not be used for the longest time in the future” — but optimality requires knowledge of the future. LRU is a past-based approximation, and it works well on workloads with strong temporal locality (most real workloads).

2. Tiny Worked Example (capacity = 3)

Operations: put(1, A); put(2, B); put(3, C); get(1); put(4, D); get(2)

Recency list shown most-recent-first (the head) → least-recent-last (the tail).

StepOperationCache State (head ← → tail)Notes
1put(1, A)[1]empty → insert at head
2put(2, B)[2, 1]insert at head; 1 ages
3put(3, C)[3, 2, 1]full now
4get(1) → A[1, 3, 2]move 1 to head (it was just touched)
5put(4, D)[4, 1, 3]full + new key → evict tail = 2, insert 4 at head
6get(2) → -1[4, 1, 3]2 was evicted in step 5

The two operations a reader must internalize:

  1. Touch (any successful get or put of an existing key) — splice that node out of its current position and reinsert at the head.
  2. Evict (only when put adds a new key and the cache is full) — pop the tail, delete its hash map entry, then insert the new node at the head and add its hash map entry.

3. The Algorithm — Hash Map + Doubly Linked List

The two requirements together are what dictate the data structures:

  • O(1) lookup by key → must have a hash map keyed by the user-facing key.
  • O(1) update of recency order → must have a list where you can move an arbitrary node to the front without scanning. A singly linked list cannot remove an arbitrary node in O(1) (you’d need to find its predecessor — O(n)). A doubly linked list can: each node has prev and next, so node.prev.next = node.next; node.next.prev = node.prev removes it in O(1).
  • O(1) eviction of the least-recently used → must know the tail in O(1). A doubly linked list with a tail sentinel gives this.

So the standard structure is:

  • Hash map key → Node*.
  • Doubly linked list of Node(key, value, prev, next). Use head and tail sentinels (dummy nodes) so the real first/last nodes always have non-null neighbors — this eliminates a swarm of null-checks in the splice code.

Pseudocode:

class Node:
    key, value, prev, next

class LRUCache(capacity):
    map        = {}                       # key -> Node
    head, tail = sentinel, sentinel       # head <-> tail initially
    head.next  = tail
    tail.prev  = head

    function get(key):
        if key not in map: return -1
        node = map[key]
        remove(node)
        add_to_head(node)
        return node.value

    function put(key, value):
        if key in map:
            node = map[key]
            node.value = value
            remove(node)
            add_to_head(node)
            return
        if len(map) == capacity:
            lru = tail.prev               # real least-recent (skip sentinel)
            remove(lru)
            del map[lru.key]
        node = Node(key, value)
        add_to_head(node)
        map[key] = node

    function remove(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    function add_to_head(node):
        node.next        = head.next
        node.prev        = head
        head.next.prev   = node
        head.next        = node

Every step in get and put is O(1): hash-map lookup, four pointer reassignments, hash-map insert/delete. No loops, no scans.

4. Python Implementation

A from-scratch implementation (no collections.OrderedDict shortcut, since the interview point is to demonstrate the structure):

class _Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None
 
class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map: dict[int, _Node] = {}
        # Sentinel head/tail — eliminates None-checks on splice.
        self.head, self.tail = _Node(), _Node()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    # --- internal helpers -------------------------------------------------
    def _remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _push_front(self, node: _Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
 
    # --- public API -------------------------------------------------------
    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._push_front(node)
        return node.val
 
    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.val = value
            self._remove(node)
            self._push_front(node)
            return
        if len(self.map) >= self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = _Node(key, value)
        self._push_front(node)
        self.map[key] = node

The __slots__ declaration on _Node shrinks the per-node memory footprint by eliminating the per-instance __dict__ — modest savings (~50%) on a node that holds only four attributes, but worth doing in any production cache.

A one-liner cheat using Python’s built-in OrderedDict (which is itself implemented as a hash map + doubly linked list — the same idea):

from collections import OrderedDict
 
class LRUCache:
    def __init__(self, capacity):  self.cap, self.d = capacity, OrderedDict()
    def get(self, k):
        if k not in self.d: return -1
        self.d.move_to_end(k)        # mark as most-recent
        return self.d[k]
    def put(self, k, v):
        if k in self.d: self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap: self.d.popitem(last=False)  # evict LRU

In an interview, write the from-scratch version first — interviewers want to see you understand the doubly-linked-list mechanics, not just that you know the standard library.

5. Complexity

OperationTimeSpace
get(key)O(1) worst case—
put(key, value)O(1) worst case—
ConstructionO(1)O(capacity)
Total memory—O(capacity) for the map + O(capacity) for the list nodes

Why true O(1) (not amortized). Hash table get/put is expected O(1), but the doubly-linked-list splice operations are deterministic O(1). Counting the hash table strictly gives “amortized expected O(1)”; in interview parlance “O(1)” is the expected answer.

Why doubly, not singly, linked. A singly linked list can move a node to the front in O(1) only if you have a pointer to its predecessor. With just the node itself, finding the predecessor requires an O(n) scan. The hash map gives you a pointer to the node directly — but not to its predecessor. The prev pointer fills exactly that gap.

6. Variants

6.1 LRU-K

Track the time of the K-th most recent access instead of the most recent. An item only “graduates” out of the eviction-candidate pool after K hits. Better at distinguishing “actually hot” entries from “scanned once” entries — the classic case being a sequential table scan that pollutes a buffer pool. LRU-2 (O’Neil, O’Neil & Weikum, 1993, SIGMOD) is widely used in databases.

6.2 2Q (Two-Queue)

Maintain a small FIFO queue of recent first-time inserts and a larger LRU queue of “graduated” entries. Cheaper than LRU-K, similar scan-resistance benefits.

6.3 SLRU (Segmented LRU)

Two LRU lists: a probationary segment for new entries and a protected segment for entries that have been hit at least twice. On eviction, prefer the probationary tail.

6.4 ARC (Adaptive Replacement Cache)

Combines recency and frequency adaptively by maintaining two LRU lists (one for entries seen once, one for entries seen at least twice) plus “ghost” lists of recently-evicted keys, then dynamically retuning the split point between the two based on which ghost list takes hits. Invented at IBM by Megiddo and Modha and covered by IBM patent US 6,996,676 (filed November 2002, issued February 2006), which expired around February 2024 after a term extension — PostgreSQL famously adopted ARC in 8.0.0 then backed it out citing the patent. Sun’s ZFS uses an ARC variant as its page cache. Worth a cross-link to Adaptive Replacement Cache for the full mechanism.

6.5 W-TinyLFU

Used by Caffeine (the Java cache library that powers Spring’s default cache and many Android apps). Combines a tiny LFU (Least Frequently Used) admission filter with an SLRU main store. Empirically beats LRU on most real workloads.

6.6 Approximate LRU (Redis)

Redis does not maintain a true LRU list (the bookkeeping cost would dominate small-value workloads). Instead, on each eviction it samples maxmemory-samples random keys (default 5) and evicts the least-recently-used among them; since Redis 3.0 it keeps a pool of the best candidates seen across evictions to refine the choice. Raising the sample count to 10 yields an approximation the Redis docs describe as “very close to” true LRU at a modest CPU cost, and on the power-law access patterns typical of real workloads the difference between sampled and exact LRU is “minimal or non-existent” (per the Redis eviction docs). The same sampling machinery backs allkeys-lfu/volatile-lfu, which approximate LFU using a per-key access counter rather than a recency timestamp.

7. Production Use Cases

  • Java’s LinkedHashMap — pass accessOrder=true to the constructor and override removeEldestEntry() to get a complete LRU cache in ~10 lines.
  • Operating systems — page replacement in virtual memory historically used LRU approximations like the clock algorithm (a circular bit-walk that’s a constant-factor cheaper than maintaining an exact LRU order).
  • Database buffer pools — PostgreSQL uses a clock-sweep variant; MySQL InnoDB uses a midpoint-insertion LRU (new pages enter the middle, not the front, as a scan-resistance heuristic).
  • CDN edge caches — content servers running Varnish, NGINX, etc. typically use LRU or LFU.
  • CPU caches — pseudo-LRU (PLRU) using a tree of single bits, because true LRU bookkeeping is too expensive at hardware speeds.
  • Browser back-forward cache — recently visited pages cached in memory, evicted LRU.
  • Redis — allkeys-lru and volatile-lru are two of the eviction policies (per the Redis eviction docs cited above).

8. Pitfalls

8.1 Singly Linked List Won’t Work

A common bug-on-the-whiteboard: candidate sketches a hash map → “list of values” without specifying doubly linked. Without prev pointers, splicing an arbitrary node out is O(n). Always say doubly linked list explicitly.

8.2 Forgetting to Delete From the Hash Map on Eviction

On eviction, you must (a) pop the tail node from the list and (b) delete its key from the hash map. Skipping (b) leaks memory and silently corrupts subsequent get(key) calls (the map says “present” but the node has been unlinked).

8.3 Updating Value Without Updating Recency

On put(existing_key, new_value), you must move the node to the head — a write counts as a “touch” too. Forgetting this is one of the most common bugs in the LeetCode 146 submissions.

8.4 Sentinel Nodes Save Lives

Without head/tail sentinels, every splice has four edge cases (empty list, one element, splicing from front, splicing from back). With sentinels, every splice is the same four lines. Use sentinels.

8.5 Capacity Zero

A capacity-0 cache should reject every put and return -1 from every get. Many naive solutions crash or infinite-loop. Handle the edge case explicitly or note that the constraints exclude it.

8.6 Thread Safety

The above is not thread-safe. Concurrent puts can corrupt the linked list. In production: wrap with a single mutex, or use a striped/segmented design. Java’s Caffeine library demonstrates how to get high-throughput concurrency with the W-TinyLFU policy via a write-buffer and read-ring batched application.

8.7 Iteration Cost

Iterating an LRU cache (e.g., for serialization) is O(n) — fine. But iterating and doing gets during iteration moves entries to the head and reorders the list under you. Don’t.

9. Diagram — Hash Map + Doubly Linked List Topology

flowchart LR
    subgraph "Hash Map (key → Node*)"
        K1["k=1"] --> N1
        K2["k=2"] --> N2
        K3["k=3"] --> N3
    end
    subgraph "Doubly Linked List (recency order)"
        H["[head sentinel]"] <--> N3["[k=3, v=C]"]
        N3 <--> N1["[k=1, v=A]"]
        N1 <--> N2["[k=2, v=B]"]
        N2 <--> T["[tail sentinel]"]
    end

What this diagram shows. The hash map points directly at the linked-list nodes, so a get(2) is a single dictionary probe (no list traversal). After the lookup, the node is spliced out and reinserted right after the head sentinel — that splice is four pointer writes regardless of where in the list the node started. The tail sentinel’s prev is always the LRU candidate; on eviction we splice it out and remove its key from the map. Sentinels mean head and tail real nodes always have non-null neighbors, eliminating the special cases that plague linked-list code.

10. Common Interview Problems

ProblemLeetCode #What’s being tested
LRU Cache146The canonical implementation above
LFU Cache460Harder cousin — see Least Frequently Used Cache
Design In-Memory File System588Often combined with cache eviction
Design HashMap706Foundation that LRU builds on
Design Hit Counter362Sliding-window cousin
Insert Delete GetRandom O(1)380Same hash-map + array trick, different problem

System-design rounds: “Design Memcached”, “Design a CDN”, “Design a database buffer pool” all expect a coherent answer about LRU vs LFU vs ARC vs W-TinyLFU and when each is the right call.

11. Open Questions

  • When does a workload benefit from W-TinyLFU over LRU enough to justify the complexity? (Caffeine benchmarks suggest “almost always” but real-world adoption is still mostly LRU.)
  • How does the clock algorithm’s hit-rate compare to true LRU at typical buffer-pool sizes? (Empirically very close; the OS folklore says “within 1-2%.”)
  • At what cache-entry size does the per-node pointer overhead of doubly-linked LRU dominate the value payload, and should you use a different structure?

12. See Also

Graph View

Backlinks