LRU caches

A least-recently-used (LRU) cache holds a fixed number of items. When it's full and a new item arrives, it evicts the item that was used longest ago. The cache needs two operations to be fast: look up a key, and move a key to the front when it's used. Doing both in O(1) takes two structures working together.

LRU is the eviction policy behind many caches, from browser and CDN caches to the buffer pool inside a database. Its effectiveness depends on the workload, as covered in caching.

The big idea

A hash map answers "where is this key?" in O(1). It can't tell which key is oldest. A doubly linked list keeps items in order of use, with the most recent at the front and the oldest at the back. Moving a node to the front or removing the back is O(1) if you hold a direct pointer to the node.

Combine them: the hash map gives the node for a key, and the list gives the order. Each operation touches only a few pointers.

Walking through it

Python's OrderedDict is a hash map that also keeps insertion order and supports moving a key to the end. That makes it a complete LRU:

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap = cap; self.d = OrderedDict()
    def get(self, k):
        if k not in self.d: return None
        self.d.move_to_end(k); return self.d[k]
    def put(self, k, v):
        self.d[k] = v; self.d.move_to_end(k)
        if len(self.d) > self.cap: self.d.popitem(last=False)

c = LRU(2)
c.put("A", 1); c.put("B", 2); c.get("A"); c.put("C", 3)
print(list(c.d))

Output:

['A', 'C']

With capacity 2, A and B fill the cache. Reading A makes it most recent, so B becomes the oldest. Adding C evicts B, leaving A and C. OrderedDict does this in O(1) per operation, using a linked list internally.

In a language without a built-in, the same design uses a hash map from key to node, and a doubly linked list of nodes. Expect this in interviews, and in production code when the library doesn't provide one.

Trade-offs

LRU is simple, but it's not always the best policy:

• A full scan through a dataset touches each item once, and pushes out hot items. The buffer pool design in buffer pool exists to handle this.
• LFU, which evicts the least frequently used, handles scans better, but it's slower to adapt when popularity changes.
• Time-based expiry suits data that goes stale regardless of use.

Common mistakes

• Implementing LRU with a plain array, so each access is O(n) to find and move an item.
• Forgetting that a get also counts as a use, so a hot key gets evicted when it shouldn't be.
• Using LRU for a workload dominated by scans, where it evicts the useful items.

Check yourself

• Why does the hash map alone not give LRU? Answer: it finds a key quickly, but it doesn't record which key was used least recently.
• Why is a doubly linked list needed, and not a single linked list? Answer: removing a node from the middle needs its predecessor, and a doubly linked list keeps that pointer, so the removal stays O(1).

Key takeaways

• LRU evicts the least recently used item, and it needs a hash map plus an ordered list.
• The hash map finds the node in O(1), and the list moves it in O(1).
• Reads count as use. Scans can flush useful items, so consider other policies for scan-heavy work.

Further learning

Next, see graphs and topological sort for ordering tasks with dependencies.