The LRU Cache — and How It Powers API Response Caching
A weekly series where we break down real systems — from the business problem, to the architecture, to the exact data structure that makes it work.
The Problem
Any caching layer — API response caching, database query caching, CDN edge caching — has the same fundamental constraint: memory is finite. When the cache is full and a new item needs to be added, something has to be evicted.
LRU (Least Recently Used) is one of the most common and effective eviction strategies: when the cache is full, remove whatever hasn't been accessed in the longest time. The intuition is simple — data that hasn't been touched recently is statistically less likely to be needed again soon.
The interesting engineering challenge isn't the eviction policy — it's implementing it so that both reading and writing stay fast, even as the cache grows.
Step 1: Define the Requirements
Functional requirements:
- get(key) — return the value if present, otherwise indicate a miss
- put(key, value) — insert or update a value; if the cache is at capacity, evict the least recently used item first
- Accessing an item (via get or put) marks it as "recently used"
Non-functional requirements:
Both get and put must run in O(1) time — this is the constraint that makes the problem interesting. At real scale (thousands of cache operations per second), an O(n) cache defeats the purpose of caching in the first place.
Step 2: Why the Obvious Approaches Fall Short
A plain HashMap gives you O(1) lookups, but no way to know order — you'd have no efficient way to find "what hasn't been used in the longest time" without scanning everything.
A plain array or list could track order easily, but finding and moving an item to "most recently used" would require O(n) search first.
We need both fast lookup and fast reordering. That's the combination that leads to the real solution.
Step 3: The Data Structure — HashMap + Doubly Linked List
The standard, production-grade solution combines two structures:
- A HashMap — maps each key directly to its node in the linked list, giving O(1) lookup
- A Doubly Linked List — maintains items in usage order, with the most-recently-used item at the head and the least-recently-used at the tail
Why a doubly linked list specifically? Because when we access a node, we need to remove it from its current position and move it to the front — and removing a node from a doubly linked list (where each node knows both its prev and next) is an O(1) operation. A singly linked list would force us to traverse from the head to find the previous node, which is O(n).
The flow:
- get(key): look up the node via the HashMap (O(1)), move it to the front of the list (O(1)), return its value
- put(key, value): if the key exists, update and move to front. If not, and the cache is full, remove the node at the tail (least recently used) — both from the list and the HashMap — then insert the new node at the front
Python Implementation
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> Node
# Dummy head/tail nodes simplify edge cases
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
"""Detach a node from the list — O(1)."""
node.prev.next = node.next
node.next.prev = node.prev
def _insert_at_front(self, node):
"""Insert a node right after head (most recently used) — O(1)."""
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._insert_at_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._insert_at_front(node)
if len(self.cache) > self.capacity:
# Evict least recently used (node just before tail)
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]Every operation here — lookup, move-to-front, and evict — is O(1), because the HashMap gives instant access to any node, and the doubly linked list lets us detach and reinsert a node without searching.
Step 4: Where This Shows Up in Real Systems
This exact pattern isn't just an interview question — it's the actual mechanism behind:
- API response caching — skip recomputing expensive responses (e.g. a search endpoint or aggregation query) for recently-requested inputs
- Database query result caching — reduce load on the primary database for repeated queries
- Mobile image caching (React Native, Flutter) — keep recently viewed images in memory, evict older ones as the user scrolls
- CDN and browser caching — conceptually similar eviction logic at a much larger scale
Trade-offs Worth Knowing
LRU isn't always the right policy. For some access patterns (e.g. data accessed in a strict cyclical pattern larger than the cache), LRU can perform worse than a simpler policy like FIFO. Variants like LFU (Least Frequently Used) exist for workloads where frequency matters more than recency.
At distributed scale, an in-process LRU cache like this one only helps a single server. Real production systems often pair this pattern with a distributed cache (like Redis, which implements similar eviction policies) shared across multiple servers — the core data structure logic is the same, but the "where it lives" question becomes a bigger architectural decision.
Why We Build This Way
The takeaway isn't "memorize this pattern for an interview" — it's that picking the right combination of data structures, driven by the actual performance requirement (O(1) here), is what makes a system hold up under real load. That's the same thinking we apply when deciding where to add caching layers in a client's actual product.
This is Week 2 of Brainy Blueprints. Next week: the Sliding Window pattern, and how it powers rate limiting.
📩 Want to talk through a performance or caching problem in your product? [email protected]