Caching: LRU, LFU and page replacement

01Why it matters

One millisecond instead of a hundred

A database answers in about 100 ms. A copy of the answer kept in memory comes back in about 1 ms. Keep the answers people ask for most in that fast copy, a cache, and most requests never reach the database at all.

How much faster does it get? If 90% of requests hit the cache, the average is $0.9 \times 1 + 0.1 \times 100 \approx 11$ ms. At 99% it is about 2 ms. The misses dominate, so every point of hit rate counts.

Caches work because programs and people have locality: what was used recently is likely to be used again soon. Your browser, a CDN, the CPU and the operating system's virtual memory all bet on it. The hard part is what to throw out when the cache is full.

02Key parts

The pieces you will see

hit and miss: A hit finds the key in the cache; a miss doesn't, and pays for the trip to the slow store. Hit rate is hits ÷ lookups.
eviction: Removing an entry to make room for a new one when the cache is full. The policy chooses which.
LRU and LFU: Least recently used: evict what was used longest ago. Least frequently used: evict what was used fewest times.
page and frame: Virtual memory caches fixed-size pages of a program in physical frames. A reference to a page that isn't in a frame is a page fault.

03See it work

An LRU cache in O(1)

This cache holds A, B and C, and A was just read. It keeps two things in step: a hash map from each key to its entry, and a recency list with the least recently used entry at the head. A hit moves the entry to the newest end; a full cache evicts the head.

Try get B, then put D 4. get B is a hit, so B moves to the newest end. put D finds the cache full and evicts the head of the list: C, used longest ago.

The same choice appears in virtual memory, with pages and frames in place of keys and slots. Here a string of page references runs through 3 frames under LRU; each column shows memory after that reference.

LRU faults 9 times on these 13 references. The first three faults just fill the empty frames.

04Predict

Your turn: be FIFO

FIFO replaces the page that was loaded longest ago, however often it has been used since. Before each step, say whether the page hits, and which page FIFO throws out.

Make 6 predictions: step forward and answer each question before the next step plays.

05Try it

When the bets go wrong

Every policy is a guess about the future. OPT, Bélády's optimal policy, cheats by looking ahead: it replaces the page needed again furthest in the future. No operating system can run it, but it shows the fewest faults possible, so it is the yardstick: on the string above OPT faults 7 times, against 9 for LRU and Clock and 10 for FIFO. Clock is what real systems use: one use bit per frame instead of LRU's timestamps, with a hand that sweeps the frames and spares any page used since it last passed.

Now try giving FIFO more memory.

FIFO on 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames: 9 faults. Switch to the 4-frame example and count again.

Locality can also fail. A loop over one more page than fits is LRU's worst case, and so is a one-off scan through a cache full of popular keys.

Pages 1 to 4 in a loop, 3 frames: LRU always evicts the page needed next and faults on all 12 references. OPT faults 6 times.

An LFU cache: A was used 3 times, B twice, C once. Put a new key and see which goes.

Bigger isn't automatically better either. Give the loop a fourth frame and every policy faults just 4 times, once per page. A fifth or sixth frame adds nothing: once the working set (the pages in active use) fits, extra memory stops paying.

06Check yourself

Check yourself

Question 1 of 6
A cache answers in 1 ms and the database behind it in 100 ms. About how long does the average request take at a 90% hit rate?
Your answer comes back in Review in a few days, so it sticks.
Question 2 of 6
Why does an LRU cache need a doubly linked list as well as a hash map?
Question 3 of 6
FIFO on 1 2 3 4 1 2 5 1 2 3 4 5 faults 10 times with 4 frames. With 3 frames it faults…
Question 4 of 6
Which policy gives the fewest page faults possible on any reference string?
Question 5 of 6
A program loops over 5 pages again and again, with 4 frames under LRU. What helps most?
Question 6 of 6
What does the Clock policy keep for each frame, in place of LRU’s timestamps?

07Explain it back

Say it in your own words

Why does a cache with a high hit rate make a slow system fast, and how does an LRU cache choose what to evict in O(1)?

08Recap

What to remember

A cache keeps hot data close. Hit rate is what matters: at 1 ms against 100 ms, 90% hits average about 11 ms and 99% about 2 ms.
LRU evicts the entry used longest ago, in O(1) with a hash map and a doubly linked list; LFU evicts the least used.
Page replacement is the same problem for memory pages: FIFO, LRU, Clock (one use bit) and OPT, the unreachable ideal that sees the future.
FIFO can fault more with more frames (Bélády's anomaly); LRU fails on loops and scans; past the working set, more memory stops helping.