Eviction policies
A cache is smaller than the data behind it. What it throws out when it is full decides how often it helps.
5 minute lesson
A full cache has to choose
A cache holds a small part of the data, in memory that is limited. When it is full, every new entry pushes an old one out. That is eviction. Which entry goes decides how many of the next requests still find what they need, and so the hit ratio.
- ExpiryThe entry is too olddecided by its TTL, whether or not there is room
- EvictionThe cache is fulldecided by the policy, however fresh the entry is
Least recently used
- Full
A cache has room for three entries and holds A, B and C. A was stored first.
- Aoldest
- Bstored second
- Cnewest
- A is read
A request reads A. With LRU, that makes A the most recently used entry. B is now the one that has gone unused the longest.
- Bunused longest
- Cin between
- Ajust used
- D arrives
A new entry D has to be stored. The cache evicts B. The bet behind it: what was used recently will be used again soon.
- Ckept
- Akept
- Dnew
An LRU cache has room for three entries. Requests arrive in this order: read P, read Q, read R, read P, and then a new entry S is stored.
Which entry is evicted to make room for S?
- P
- Q
- R
- S
Show the answer
- Q
After the four reads the order of last use is Q, then R, then P, since P was read again at the end. Q has gone unused the longest and is evicted. P was the first entry ever stored, but LRU does not care about age. It cares about the last use.
LRU evicts by last use, not by age. A read moves an entry back to safety.
Recent or frequent
LRU
least recently used
- It evicts
- What was unused longest
- It adapts
- Quickly to new interests
- Weak spot
- One large scan flushes it
LFU
least frequently used
- It evicts
- What was used least often
- It adapts
- Slowly
- Weak spot
- Old favourites never leave
An LRU cache holds the 100,000 most used products. A nightly job reads all 5 million products once, through the cache.
What state is the cache in when the shop opens in the morning?
- Full of products that the job read last, and cold
- Unchanged, as a job cannot alter what is cached
- Empty, as the job has deleted all the entries
- Larger, as the cache has grown to 5 million
Show the answer
- Full of products that the job read last, and cold
To LRU every read counts as interest. The job touched each product once, and the last 100,000 it read pushed out everything customers actually ask for. The morning starts with misses on all popular products. This is the known weakness of LRU. Bulk jobs should read past the cache, or the cache should weigh frequency as well.
One big scan can flush an LRU cache. Let bulk jobs bypass the cache.
What is eviction, how does it differ from expiry, and what does LRU bet on?
Show the answer
Eviction removes an entry because the cache is full and a new entry needs the room. Expiry removes an entry because its TTL has run out, whether or not there is room. LRU evicts the entry that has gone unused for the longest time, betting that what was used recently will be used again soon.
Recap
- A full cache evicts an entry for every new one. The policy decides the hit ratio.
- LRU evicts what was unused longest. LFU evicts what was used least often.
- Expiry is about age, eviction about space. A cache needs both.