Caches and LRU Eviction
Why keeping hot data close makes programs fast, from CPU cache lines to application caches, and how to build an LRU cache with a hash map plus a doubly linked list.
intermediate40 min#cache#lru#locality#eviction#hash-map
Prerequisites: Hash Tables, Linked Lists
Why it matters
Almost every fast system is fast because of a cache: a small, quick store that holds a copy of data from a big, slow one. Your CPU does it with registers and L1/L2/L3 memory, your browser does it with downloaded files, your web service does it with Redis, and a database does it with its buffer pool. Knowing how caches behave explains why a loop over an array beats one over a linked list, and "design an LRU cache" is one of the most common interview questions.
Intuition
Think of a desk, a bookshelf, and a library across town. The desk holds a few books, the shelf holds hundreds, the library holds everything. You keep the books you are using on the desk. When the desk is full and you need a new one, you send back the book you have not touched for the longest time. That is Least Recently Used (LRU) eviction.
This works because real programs show locality of reference:
- Temporal locality: data used just now is likely to be used again soon (a loop counter, a popular product page).
- Spatial locality: data near what you just used is likely to be used next (the next array element).
How it works
Rough access times show why the layers exist.
registers ~0.3 ns tiny
L1 cache ~1 ns tens of KB
L2 / L3 ~4-40 ns MBs
RAM ~100 ns GBs
SSD ~100 us TBs
network ~1-100 ms unlimited
The numbers are approximate, but each step down is roughly 10 to 100 times slower and far bigger.
CPU caches move memory in fixed chunks called cache lines (commonly 64 bytes). Reading a[0] of an int array pulls in a line that also holds a[1], a[2] and more, so scanning an array is mostly cache hits. A linked list scatters nodes across memory, so each hop can be a miss. Both are O(n), but constants differ a lot.
Application caches follow one pattern, often called cache-aside: look in the cache; on a hit return it; on a miss fetch from the slow source, store it, then return it. Quality is measured by the hit rate, hits divided by total lookups.
The two paths look like this.
Because a cache is smaller than the source, it must evict something when full:
- LRU: drop the least recently used entry. Good default for most workloads.
- LFU: drop the least frequently used. Protects long-term favorites but reacts slowly when popularity changes.
- FIFO: drop the oldest inserted. Simple, ignores usage.
- TTL: entries expire after a set time, which also bounds how stale data can get.
Building LRU in O(1). We need two things at once: find an entry by key quickly, and know which entry is oldest. A hash map gives O(1) lookup. A doubly linked list keeps entries ordered from most to least recently used, and unlinking a node you already hold is O(1) because it knows both neighbors. The map points to the nodes.
head <-> [c] <-> [a] <-> tail map: a -> node, c -> node
most recent least recent
Sentinel nodes at both ends remove special cases for empty lists.
Here is a capacity-3 LRU cache (front is most recent). Step through a sequence of operations and watch the order change.
Every get or put moves the key to the front, and the entry at the back is always the one evicted. The map (not drawn) finds any node in O(1).
| Operation | Time | Notes |
|---|---|---|
| get(key) | O(1) | Map lookup, then move node to front |
| put(key, value) | O(1) | Insert at front; evict tail if full |
| Evict least recently used | O(1) | It is always the node before the tail sentinel |
| Space | O(capacity) | One map entry and one node per item |
Code: an LRU cache
class Node:
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {}
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, n):
n.prev.next, n.next.prev = n.next, n.prev
def _push_front(self, n):
n.prev, n.next = self.head, self.head.next
self.head.next.prev = n
self.head.next = n
def get(self, key):
if key not in self.map:
return -1
n = self.map[key]
self._unlink(n)
self._push_front(n)
return n.value
def put(self, key, value):
if key in self.map:
n = self.map[key]
n.value = value
self._unlink(n)
self._push_front(n)
return
if len(self.map) == self.capacity:
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
n = Node(key, value)
self.map[key] = n
self._push_front(n)
def keys(self): # most recent first
out, n = [], self.head.next
while n is not self.tail:
out.append(n.key)
n = n.next
return out
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # a is now most recent
cache.put("c", 3) # evicts b
print(cache.get("b"), cache.get("a"), ",".join(cache.keys()))class Node {
constructor(key = null, value = null) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
this.head = new Node(); // sentinels
this.tail = new Node();
this.head.next = this.tail;
this.tail.prev = this.head;
}
#unlink(n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
#pushFront(n) {
n.prev = this.head;
n.next = this.head.next;
this.head.next.prev = n;
this.head.next = n;
}
get(key) {
if (!this.map.has(key)) return -1;
const n = this.map.get(key);
this.#unlink(n);
this.#pushFront(n);
return n.value;
}
put(key, value) {
if (this.map.has(key)) {
const n = this.map.get(key);
n.value = value;
this.#unlink(n);
this.#pushFront(n);
return;
}
if (this.map.size === this.capacity) {
const lru = this.tail.prev;
this.#unlink(lru);
this.map.delete(lru.key);
}
const n = new Node(key, value);
this.map.set(key, n);
this.#pushFront(n);
}
keys() { // most recent first
const out = [];
for (let n = this.head.next; n !== this.tail; n = n.next) out.push(n.key);
return out;
}
}
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a"); // a is now most recent
cache.put("c", 3); // evicts b
console.log(cache.get("b"), cache.get("a"), cache.keys().join(","));Both versions print -1 1 a,c.
Common pitfalls
- Stale data: a cache is a copy. If the source changes, readers see old values until you invalidate or the TTL expires. "There are only two hard things: cache invalidation and naming things" is a joke for a reason.
- Forgetting to update the map on eviction: removing the node but leaving its key in the map causes ghost hits and memory leaks.
- Not refreshing on
get: in LRU a read counts as a use. Skipping the move-to-front makes it FIFO. - Cache stampede: when a hot key expires, hundreds of requests miss at once and hammer the database. Use jittered TTLs or let one request refill while others wait.
- Caching without a size bound: an unbounded dict is a memory leak with extra steps.
Practice
Hit rate easy
Hint
Count hits and total lookups, then divide.
Show solution
Given a capacity of 2 and the access sequence 1 2 1 3 2, LRU gives: 1 miss, 2 miss, 1 hit, 3 miss (evicts 2), 2 miss (evicts 1). That is 1 hit out of 5, a 20 percent hit rate. Track hits in get and divide by lookups.
LRU with TTL medium
Hint
Store an expiry time in each node. When should you check it?
Show solution
Add an expires_at field. In get, if the entry exists but the clock is past expires_at, unlink it, delete it from the map, and report a miss. Inject the clock as a function so tests can control time. Expired entries that are never read still occupy space, so optionally sweep the tail on each put.
Row-major versus column-major medium
Hint
Think about which loop touches neighboring addresses.
Show solution
A 2D array is stored row by row. Looping for i: for j: a[i][j] walks adjacent memory and uses every byte of each cache line. Swapping the loops jumps a whole row between accesses, so many accesses miss. Same O(n*m) work, often several times slower for large matrices.
LFU cache hard
Hint
You need to find the least frequent key, and among ties the least recent. One list per frequency helps.
Show solution
Keep a map from key to value and count, plus a map from count to an ordered list of keys (LRU order within a count) and a variable min_count. On access, move the key from list c to list c + 1; if list min_count becomes empty, increment min_count. On insert into a full cache, evict the oldest key in list min_count, then set min_count = 1. All operations are O(1).
Interview questions
- Design an LRU cache with O(1) get and put. Hash map from key to node plus a doubly linked list ordered by recency. Explain why a singly linked list would make removal O(n).
- Why a doubly linked list? Unlinking a node needs its predecessor. With
prevpointers you can do it without scanning from the head. - When is LRU a bad policy? A large one-time scan (reading a whole table once) pushes out hot entries. Variants like LRU-K or segmented LRU resist this.
- What is the difference between write-through and write-back caching? Write-through updates the cache and the source together, so it is simpler and safer but slower on writes. Write-back updates only the cache and flushes later, so it is fast but can lose data on a crash.
- How does a cache fit in a distributed system? See the caching strategies lesson: placement, invalidation, and consistency become the hard parts.
Interviewers look for: sentinel nodes or careful null handling, updating both structures on every operation, handling capacity of 1 and updating an existing key, and naming trade-offs such as staleness and eviction choice.
Quick check
An LRU cache holds a and b (b is most recent). You call get(a) and then put(c) on a full cache of capacity 2. Which key is evicted?
Finished this lesson?