DevPath
Tracks

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.

Register
0.3 ns
L1 cache
1 ns
L2 / L3
10 ns
RAM
100 ns
SSD
100,000 ns
Network
10,000,000 ns
Approximate access time on a log scale. Each layer down is orders of magnitude slower, which is why a hit in a nearby small cache is worth so much.

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.

get(key)
Key in cache?yes
Return valuefast, no source call
Cache hit: the answer comes straight from the cache and the source is never touched.
get(key)
Key in cache?no
Fetch from sourceslow
Store in cache
Return value
Cache miss: pay for the slow source once, then stores the result so the next lookup is a hit.

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.

a
MRU, LRU
null
put(a): a miss on an empty cache. a is inserted at the front.
step 1 / 7

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).

OperationTimeNotes
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 usedO(1)It is always the node before the tail sentinel
SpaceO(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()))

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

  1. 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).
  2. Why a doubly linked list? Unlinking a node needs its predecessor. With prev pointers you can do it without scanning from the head.
  3. 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.
  4. 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.
  5. 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?

Further resources

Related lessons