What a cache is, and why it fills up
Some answers are slow to get: a database query, a call to another service, a big calculation. A cache keeps recent answers in memory so the next request for the same thing is instant.
A request arrives for a key
A key is the name of the thing being asked for, such as
user:42or/home.Look in the cache
If the key is there, that is a hit. The answer comes straight from memory.
If it is not there, fetch it
That is a miss. The slow path runs, and the answer is stored in the cache for next time.
If the cache is full, something must go
Memory is limited, so the cache holds a fixed number of items. To add one, it has to throw one out. This is called eviction.
Which item to throw out is decided by the eviction policy. A good choice keeps the items that will be asked for again. A bad choice throws out something that is needed a moment later.
Try it first
The cache below holds 4 items. Pick a policy and a stream of requests, then press play. The item with the dashed red border is the one that will be thrown out next.
Requests
Cache (holds 4)
The rule: Throw out the item that has gone unused the longest. Three keys (A, B, C) get most of the requests, the whole time.
- Requests
- 0 / 48
- Hits
- 0
- Misses
- 0
- Hit rate
- 0%
The number to watch is the hit rate: the share of requests answered from the cache. Higher is better.
LRU: least recently used
The rule: throw out the item that has gone unused the longest.
The idea behind it: something used a moment ago will probably be used again soon. Something nobody has touched for a long time probably will not.
Picture a shelf. Every time an item is used, it moves to the front. Whatever ends up at the back falls off.
Example
A cache that holds 3
Requests arrive for A, B, C. The cache is now full. Then A is requested again: a hit, and A moves to the front. Then D arrives. The item unused the longest is B, so B goes. A survives because it was just used, even though it is the oldest item.
In the animation, items are ordered by how recently they were used. Halfway through, the popular keys change from A, B, C to X, Y, Z. Watch how quickly the old ones drift to the right and fall off.
Requests
Cache (holds 4)
The rule: Throw out the item that has gone unused the longest. A, B, C are popular at first. Halfway through, everyone moves on to X, Y, Z.
- Requests
- 0 / 48
- Hits
- 0
- Misses
- 0
- Hit rate
- 0%
LRU is short to write when the language has an ordered dictionary:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.items = OrderedDict()
def get(self, key):
if key not in self.items:
return None # miss
self.items.move_to_end(key) # mark it as just used
return self.items[key]
def put(self, key, value):
self.items[key] = value
self.items.move_to_end(key)
if len(self.items) > self.capacity:
self.items.popitem(last=False) # throw out the least recently usedGood at
- Adapts quickly when what is popular changes
- A sensible default for most caches
Where it bites
- One pass over many rarely used keys pushes out everything popular
- Every read has to update the order, which costs a little
LFU: least frequently used
The rule: throw out the item that has been used the fewest times.
The cache keeps a counter for every item. Each use adds one. When room is needed, the item with the lowest count goes.
Example
Counts decide
The cache holds A (used 5 times), B (used once) and C (used 3 times). D arrives. B has the lowest count, so B goes, even if B was the most recent request.
When the same few keys stay popular the whole time, LFU is hard to beat. It never throws out a favourite because of one unlucky quiet moment.
Requests
Cache (holds 4)
The rule: Throw out the item that has been used the fewest times. Three keys (A, B, C) get most of the requests, the whole time.
- Requests
- 0 / 48
- Hits
- 0
- Misses
- 0
- Hit rate
- 0%
Its weakness is the past. A key that was popular an hour ago still has a high count, so it keeps its place long after anyone asks for it. Run LFU on the stream where the favourites change, and watch A, B and C sit there while X, Y and Z fight over the one slot that is left:
Requests
Cache (holds 4)
The rule: Throw out the item that has been used the fewest times. A, B, C are popular at first. Halfway through, everyone moves on to X, Y, Z.
- Requests
- 0 / 48
- Hits
- 0
- Misses
- 0
- Hit rate
- 0%
Good at
- Best when popularity is stable
- One burst of unusual requests does not push out the favourites
Where it bites
- Slow to forget: old favourites linger
- A new item starts at 1 and is often thrown out before it can prove itself
FIFO: first in, first out
The rule: throw out the item that was added first. It does not matter how often or how recently it was used.
Example
Popular, and thrown out anyway
A, B and C are added in that order. A is then requested ten more times. D arrives. A was added first, so A goes, even though it is the most popular item in the cache.
Requests
Cache (holds 4)
The rule: Throw out the item that was added first, used or not. Three keys (A, B, C) get most of the requests, the whole time.
- Requests
- 0 / 48
- Hits
- 0
- Misses
- 0
- Hit rate
- 0%
Good at
- The simplest to build: a plain queue
- Reads do not have to update anything
Where it bites
- Ignores how items are used, so popular ones are thrown out regularly
Random
The rule: throw out any item, picked at random.
It sounds like giving up. But it needs no bookkeeping at all, and it has one real strength: no pattern of requests can fool it every time.
Here is a pattern that fools the others. Five keys are requested in a loop, and the cache holds four. With LRU, the item thrown out is always exactly the one that is needed next.
Request 0 of 40. Five keys requested in a loop: A, B, C, D, E, A, B, ... One more key than the cache holds. A green border means that cache had it.
LRU, LFU and FIFO never get a single hit. Random gets lucky more than half the time.
No policy always wins
Here are all four on the stream with steady favourites:
Request 0 of 48. Three keys (A, B, C) get most of the requests, the whole time. A green border means that cache had it.
And on the stream where the favourites change halfway:
Request 0 of 48. A, B, C are popular at first. Halfway through, everyone moves on to X, Y, Z. A green border means that cache had it.
The winner of the first race comes last in the second. The best policy depends on how your data is requested, which is why caches let you choose.
A cache with no limit
What if nothing is ever thrown out? Every miss adds an item and memory use only goes up. When the process runs out of memory it is killed. It restarts with an empty cache, so every request is a miss, exactly when the system is already struggling.
Requests
Cache (no limit)memory limit 12
The rule: Never throw anything out. Requests are spread over many different keys, so most of them are new.
- Requests
- 0 / 48
- Hit rate
- 0%
- In memory
- 0 / 12
- Crashes
- 0
Which one should you use?
| Your requests look like this | A good first choice |
|---|---|
| You are not sure | LRU |
| Recent items are the ones asked for again (sessions, feeds) | LRU |
| The same items stay popular for a long time (product pages, reference data) | LFU, with counts that fade |
| You need the cheapest possible cache and popularity is flat | FIFO or Random |
Key takeaways
- A cache has limited room, so adding an item to a full cache means throwing one out.
- LRU throws out what has gone unused the longest. It adapts quickly and is the usual default.
- LFU throws out what has been used least. It is best for stable favourites and slow to forget old ones.
- FIFO throws out the oldest item and ignores how it is used.
- Random needs no bookkeeping and cannot be fooled by a pattern.
- No policy wins on every stream of requests, and a cache with no limit ends in a crash.