Eviction: what to forget

A cache is small, so something must leave. LRU versus FIFO.

A cache has limited room because memory is more expensive than disk. When it is full and a new key arrives, it must evict an old one to make space. The eviction policy decides which. A good policy throws away the entry least likely to be asked for again, and the only evidence it has is the past.

Imagine the cache holds three restaurants and a fourth is requested. If it evicts the one people open all evening, the next request for that restaurant misses and hits the database. If it evicts one nobody has opened in an hour, nothing is lost. So the policy is a guess about the future, based on how entries were used.

Two common policies

Step 1 of 3

FIFO

Evict the entry that was inserted first, regardless of how often it is used. It is simple, but a popular key inserted early gets thrown out anyway.

def get(key):
    if key in cache:
        cache.move_to_end(key)  # now most recently used
        return cache[key]
    value = load_from_db(key)
    cache[key] = value
    if len(cache) > CAPACITY:
        cache.popitem(last=False)  # evict least recently used
    return value

Illustrative LRU lookup (not executed by the platform).

Replay a request sequence

Step through the requests, then change the capacity and policy. How does the hit ratio change?

Capacity: 3

Policy

TTL: none

Apending
Bpending
Cpending
Apending
Dpending
Apending
Bpending
Epending
Apending
Bpending

Cache (next to evict ← → most recent)

Press Step to begin.

So far: 0 hits / 0 misses

Your turn

Describe an access pattern where FIFO performs worse than LRU.

Stuck? Think about a key that is used constantly but was inserted early.

Question 1

A full LRU cache holds A, B, C (C most recent). A is requested, then D arrives. Which key is evicted?

Question 2

Which statement about FIFO eviction is true?

What to remember

The eviction policy decides what leaves a full cache.
FIFO ignores usage; LRU keeps recently used entries by refreshing them on every hit.
Which policy wins depends on the access pattern; scans can hurt LRU.
Eviction is forced by size; expiry (next lessons) is driven by age or change.