Art of Codeartofcode
Lesson 8 of 16

12. Caching: The Basics

1
The picture to keep in your head
2
12.1 What is a cache, and what are a hit, a miss and the hit rate?
3
12.2 Why is a cache faster than the database?
4
12.3 Where does a cache physically live?
5
12.4 On a miss, who fetches the data?
6
12.5 When the data changes, what gets written where?
7
12.6 What happens when the real data changes, and why add jitter?
8
12.7 What happens when the cache is full?
9
12.8 How do you invalidate safely, and what's the race everyone hits?
10
12.9 When should you cache, what should you never cache, and how do you name keys?
11
Memory card and where the analogy breaks
12
Practice: five levels
13
Interview questions
14
Solutions
15
Sources
16
Code lab
12. Caching: The Basics

12.7 What happens when the cache is full?

3 min read+10 XP

In the kitchen: The fridge is packed and you just bought groceries. You throw out the thing you haven't touched in the longest time, the jar at the back from last month.

In the system: The cache evicts (removes) something to make room. Which thing depends on the eviction policy.

a full fridge and a new item: LRU tosses the item touched longest ago, LFU the one used least, FIFO the oldest arrival.

Figure: three rules, three different victims.

12.7.1 LRU (least recently used)

In the kitchen: Toss what you haven't touched in the longest time.

In the system: Remove whatever hasn't been asked for in the longest time. If nobody has asked for it lately, nobody is likely to ask soon. It's simple, works well for most traffic, and is the usual default. Its weakness: a one-off scan (a report or a crawler that reads thousands of rare keys once) makes all of them "recently used" and pushes out the genuinely popular items.

12.7.2 LFU (least frequently used)

In the kitchen: Toss what you've used the fewest times, even if you touched it this morning.

In the system: Track how often each key is used and remove the least-used. It protects long-time favourites from one-off scans (in the chapter's code, a scan of 5 rare items pushed milk and bread out of an LRU cache, while LFU kept them). Its weakness: items that used to be popular can linger, so real implementations let old counts decay over time.

12.7.3 FIFO (first in, first out)

In the kitchen: Toss whatever went into the fridge first, used or not.

In the system: Remove the oldest-inserted key. The simplest policy, with no tracking of use, but it happily throws out popular items just because they arrived early. Rarely the best choice on its own.

Redis lets you choose among several policies (LRU-like and LFU-like ones, across all keys or only keys with a TTL), so you rarely build eviction yourself; you pick it.

Memory code: "Last touched, first tossed." That's LRU, the default; LFU protects favourites; FIFO just follows arrival order.