Pointer Walk

Cache Eviction Policies

The cache is full. LRU, LFU, FIFO and Random each throw out a different item, and no policy wins on every workload.

System DesignBeginner10 min read

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.

  1. A request arrives for a key

    A key is the name of the thing being asked for, such as user:42 or /home.

  2. Look in the cache

    If the key is there, that is a hit. The answer comes straight from memory.

  3. 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.

  4. 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.

LRU · steady favouritesInteractive
Policy
Requests

Requests

HABCCHNCBNJCCB

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.

LRU · favourites changeInteractive

Requests

CCCCBBCCBCJGBC

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:

python
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 used

Good 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.

LFU · steady favouritesInteractive

Requests

HABCCHNCBNJCCB

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:

LFU · favourites changeInteractive

Requests

CCCCBBCCBCJGBC

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.

FIFO · steady favouritesInteractive

Requests

HABCCHNCBNJCCB

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.

Same requests, four policies · round and roundInteractive
LRU
....
0 hits · 0%
LFU
....
0 hits · 0%
FIFO
....
0 hits · 0%
Random
....
0 hits · 0%

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:

Same requests, four policies · steady favouritesInteractive
LRU
....
0 hits · 0%
LFU
....
0 hits · 0%
FIFO
....
0 hits · 0%
Random
....
0 hits · 0%

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:

Same requests, four policies · favourites changeInteractive
LRU
....
0 hits · 0%
LFU
....
0 hits · 0%
FIFO
....
0 hits · 0%
Random
....
0 hits · 0%

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.

No limit · always something newInteractive

Requests

HNRJCEWDJABEYR

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 thisA good first choice
You are not sureLRU
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 flatFIFO 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress