Part 3 of 6 · 3 min read
Least recently used, and its relatives
LRU, LFU, FIFO and random replacement, traced on a short example.
Think of a desk with room for three files. When a fourth file arrives, one of the three must go back to the cabinet. A tidy clerk puts back the file untouched for the longest time. Another clerk puts back the file used the fewest times. A third puts back the oldest arrival. These are three policies.
LRU (least recently used)
LRU evicts the entry that has gone unused for the longest time. Every read or write counts as a use.
Example: entries A, B, C are used in that order, then A is read again. B is now the least recently used.
LFU (least frequently used)
LFU evicts the entry with the fewest uses. Ties are broken by age.
Example: A was used 10 times, B 2 times, C 5 times. B is evicted.
FIFO (first in, first out)
FIFO evicts the entry that was added first, whatever its use.
Example: entries were added in the order A, B, C. A is evicted first.
The book "System Design Interview" calls LRU the most popular policy and names LFU and FIFO as alternatives for other uses. The book "Fundamentals of Software Architecture" adds more: most recently used (MRU), most frequently used (MFU) and random replacement, which it calls a good policy when there is no clear analysis of whether recency or frequency matters.
A worked example. A cache holds 3 entries. The request sequence is A, B, C, A, D, B, A.
LRU trace (the list shows least recent on the left):
| Request | Result | Cache after (least recent → most recent) | Evicted |
|---|---|---|---|
| A | miss | A | - |
| B | miss | A, B | - |
| C | miss | A, B, C | - |
| A | hit | B, C, A | - |
| D | miss | C, A, D | B |
| B | miss | A, D, B | C |
| A | hit | D, B, A | - |
LRU gives 2 hits out of 7 requests.
FIFO trace on the same sequence (oldest on the left):
| Request | Result | Cache after | Evicted |
|---|---|---|---|
| A | miss | A | - |
| B | miss | A, B | - |
| C | miss | A, B, C | - |
| A | hit | A, B, C | - |
| D | miss | B, C, D | A |
| B | hit | B, C, D | - |
| A | miss | C, D, A | B |
FIFO gives 2 hits out of 7 requests too, but for different requests. FIFO evicted A, which was read again right after. On other sequences LRU does better, because it keeps what was used just now.
LFU keeps frequent entries. Its weakness: an entry that was very popular last week keeps a high count and may stay long after it stopped being used. Many designs age the counts, so old popularity fades.
| Policy | Keeps | Good for | Weak spot |
|---|---|---|---|
| LRU | Recently used | Most workloads with repeat in time | A one-time scan of many items pushes out useful ones |
| LFU | Often used | Stable popularity, such as top products | Slow to drop items that were popular and are now cold |
| FIFO | Newest arrivals | Simple, cheap | Ignores use |
| Random | Anything | No clear pattern, very cheap | May drop a hot item |
A scan is a real danger for LRU. A job that reads 1,000,000 different rows once each fills the cache with entries that will never be read again, and pushes out the hot set. Some caches add a rule that an entry must be read twice before it joins the protected area, or they keep scans out of the cache.
Common mistake
Picking LFU because it sounds smarter. Under a shifting workload, LFU holds old favourites. Without a reason to prefer it, LRU is the safe choice.
Check yourself:
- Cache size 2, requests A, B, A, C. Which entry does LRU evict when C arrives?
- Which policy suffers most from a once-off scan over the whole database?