Eviction: LRU and LFU

The problem: the cache is full

A cache keeps copies of popular data in memory, in front of a slower database. Memory costs far more than disk, so a cache holds only a slice of the data. Sooner or later it's full, and every miss brings in a new copy that needs a slot, so one copy has to go. That's eviction, and the rule that picks the copy is the eviction policy.

The policy decides the hit rate. Throw out a copy that's about to be asked for again and the next lookup misses; throw out one nobody wants and nothing is lost. A good policy guesses, from what it has seen so far, which copies won't be needed soon.

Three policies on one request list

Take a cache with room for 3 copies and ten requests for products A to G:

A B C A D A E F G A

A is the favorite: it's asked for four times. Every other product is asked for once.

FIFO: throw out the oldest stored

FIFO (first in, first out) treats the cache like a queue: the copy stored first goes first. It needs no bookkeeping, but it ignores how copies are used. At request 5, D, the cache holds A, B and C, and A was stored first, so A goes, even though it was used at request 4. Request 6 is A again: a miss.

LRU: throw out the least recently used

LRU (least recently used) keeps the copies in order of their last use. Every use moves a copy to the front, and when the cache is full, the copy at the back, unused for the longest, goes. At request 5, B hasn't been asked for since request 2, so B goes and A stays: request 6 is a hit. The bet is that what was used lately will be used again soon, which holds for most real traffic.

LFU: throw out the least frequently used

LFU (least frequently used) counts each copy's uses since it was stored and throws out the copy with the fewest. Counts often tie, so LFU needs a tie rule; the common one, used here, throws out the tied copy used longest ago. At request 5, B and C tie at 1 use, and B was used longer ago, so B goes.

The whole run

All ten requests under each policy ("out B" means the miss threw out B):

request   FIFO          LRU           LFU
 1  A     miss          miss          miss
 2  B     miss          miss          miss
 3  C     miss          miss          miss
 4  A     hit           hit           hit
 5  D     miss, out A   miss, out B   miss, out B
 6  A     miss, out B   hit           hit
 7  E     miss, out C   miss, out C   miss, out C
 8  F     miss, out D   miss, out D   miss, out D
 9  G     miss, out A   miss, out A   miss, out E
10  A     miss, out E   miss, out E   hit
hits      1             2             3

Seven of the ten requests ask for a product for the first time, and those miss under any policy, so 3 hits is the most any rule could get. LFU gets all 3. LRU loses A at request 9: E, F and G, asked for once each, pushed it to the back one after another. FIFO loses A twice.

The ideal rule, Bélády's, throws out the copy whose next use is furthest away; it also gets 3 hits here, but no real cache knows the future. LRU and LFU guess it from the past.

LRU or LFU: when each one wins

• LRU follows interest as it moves: today's news, a user who's active right now, this week's sale. It adapts as soon as interest shifts and is simple, which makes it the usual default.
• LFU keeps long-time favorites: year-round best sellers, the common words in a dictionary app. A burst of one-off requests can't push them out, because each newcomer has a count of 1.
• LFU is slow to forget: last month's viral product has a huge count and keeps its slot long after shoppers move on. Real LFU caches let old counts fade over time; Redis's LFU does.
• A scan flushes LRU: a nightly report that reads every product once pushes every useful copy out of an LRU cache. Under LFU each scanned copy has 1 use and goes before the favorites.
• Random eviction needs no bookkeeping, but it ignores use: with 3 slots, each eviction throws out the favorite one time in three.

How LRU is built in O(1)

A plain list kept in order of use is too slow for a busy cache: finding a key and moving it to the front means walking the list, O(n). The standard design uses two structures together:

• A hash map from each key to its node, so a lookup finds the node at once.
• A doubly linked list of the nodes, most recent first. Links both ways let a node leave the middle of the list without a search for the node before it.

Before request 6 in the run above, the list is D, A, C:

hash map:  A → node A   C → node C   D → node D
list:      front  D ⇄ A ⇄ C  back

Request 6, A, is a hit: the map gives A's node, D and C are linked to each other, and A is linked in at the front, giving A, D, C. Request 7, E, is a miss: C, at the back, is unlinked and its key leaves the map, and E goes in at the front. Each step changes a few links, so hits and misses both take O(1) time (on average, as hash map lookups do). The LRU Cache coding lesson in this course builds an LRU cache with a map and a plain list; swapping in a doubly linked list is the step that makes it O(1).

Where eviction shows up in design interviews

Every cache you draw is smaller than the data behind it, so expect the follow-up: what happens when it's full? Answer in one sentence: "LRU: when it's full, the least recently used copy goes; interest in products moves, and LRU follows it." Name the policy together with the cache, as you name the hit rate and the TTL. Choose LRU unless there's a reason not to, and say what the reason would be: a steady set of favorites, or big scans, points to LFU.

Common interview questions on eviction

How would you implement an LRU cache?

A hash map from key to node, and a doubly linked list of the nodes in order of use. A hit finds the node through the map and moves it to the front; a miss on a full cache removes the node at the back and its key. Both take O(1) time.

LRU or LFU: which would you choose?

LRU by default: it adapts as soon as interest moves and is simple to build. LFU when popularity is steady and one-off requests or scans would push favorites out, with counts that fade so old hits are forgotten.

What happens when a scan runs through an LRU cache?

Every item it reads becomes the most recently used, so a scan bigger than the cache pushes out every useful copy. Keep bulk reads away from the cache, or use a policy that resists scans, such as LFU.

What does Redis do when its memory is full?

Redis, a popular cache server, follows its maxmemory-policy setting. The default, noeviction, refuses new writes; for a cache you set a policy such as allkeys-lru or allkeys-lfu. Redis approximates both by sampling a few keys rather than keeping an exact order, which saves memory.

Summary

• A full cache drops a copy for each new one: eviction. The policy decides the hit rate.
• FIFO drops the copy stored first, even one in use.
• LRU drops the copy unused the longest: move to the front on use, evict from the back.
• LFU drops the copy used the fewest times, ties to the one used longest ago. It keeps favorites but is slow to forget.
• LRU in O(1): a hash map plus a doubly linked list.