LFU vs LRU Cache: Which Eviction Policy Wins, and When

A cache is only as good as its guess about what will be needed next. LRU guesses "whatever was touched most recently". LFU guesses "whatever has been touched most often". Both guesses are reasonable, both are wrong on some workloads, and the interesting part is knowing which workload breaks which.

This article builds an LFU cache with constant-time operations, puts it next to an LRU, and runs two short traces where the winner flips.

The problem it solves

A cache holds at most capacity keys. When a new key arrives and the cache is full, one existing key must go. The eviction policy chooses which.

• LRU (least recently used) evicts the key whose last access is oldest.
• LFU (least frequently used) evicts the key with the fewest accesses. When several keys tie on count, the usual rule — and the one used here — evicts the least recently used among them.

Both must run get and put in O(1). For LRU that is a well-known pairing of a hash map and a doubly linked list. LFU needs one more idea.

The intuition

The naive LFU keeps a count per key and scans for the minimum at eviction time. That is O(n) per eviction, which defeats the point of a cache.

Instead, shelve keys by their count. Shelf 1 holds every key used once, shelf 2 every key used twice, and so on. Each shelf is ordered by recency: a key joins at the back, and the front is the oldest. Then:

• A hit moves a key from shelf c to the back of shelf c + 1. That is a delete and an append — constant time with an ordered hash map.
• An eviction takes the front of the lowest non-empty shelf.

The last question is how to find the lowest non-empty shelf without scanning. Keep one number, the floor, and maintain it on the only two events that can change it:

• A hit that empties the floor shelf raises the floor by exactly one, because the key that left went to the next shelf up.
• Inserting a new key sets the floor to 1, because a newcomer has been used once and nothing can be lower.

Eviction never needs to update the floor on its own: it is always immediately followed by an insert, which resets it to 1.

Watch it run

Three keys sit on shelves labelled by use count, with the floor shown as a readout. Watch a get hit and slide from shelf 1 to the back of shelf 2, then the eviction take b from the front of the floor shelf, and the floor rise to 2 without any search because shelf 1 is now empty.

The code

LRU on Python's OrderedDict, LFU with one OrderedDict per shelf, and two traces that score both:

from collections import OrderedDict, defaultdict

class LRUCache:
    def __init__(self, capacity):
        self.cap, self.data = capacity, OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)              # most recent at the back
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        elif len(self.data) == self.cap:
            self.data.popitem(last=False)       # evict the front: least recent
        self.data[key] = value

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.value, self.count = {}, {}
        self.shelf = defaultdict(OrderedDict)   # use count -> keys, oldest first
        self.floor = 0                          # lowest count that has a key

    def _touch(self, key):
        c = self.count[key]
        del self.shelf[c][key]
        if not self.shelf[c]:
            del self.shelf[c]
            if self.floor == c:
                self.floor = c + 1              # the floor shelf emptied upwards
        self.count[key] = c + 1
        self.shelf[c + 1][key] = None           # join the BACK of the next shelf

    def get(self, key):
        if key not in self.value:
            return None
        self._touch(key)
        return self.value[key]

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.value:
            self.value[key] = value
            self._touch(key)
            return
        if len(self.value) == self.cap:
            old, _ = self.shelf[self.floor].popitem(last=False)
            del self.value[old], self.count[old]
        self.value[key], self.count[key] = value, 1
        self.shelf[1][key] = None
        self.floor = 1                          # a newcomer is always the least used

def hit_rate(cache, trace):
    hits = 0
    for key in trace:
        if cache.get(key) is None:
            cache.put(key, key)
        else:
            hits += 1
    return hits

trace = []
for r in range(50):                             # three hot keys read twice a round,
    trace += ["h1", "h2", "h3"] * 2             # then five rows nobody reads again
    trace += [f"row{r}-{i}" for i in range(5)]
print(hit_rate(LRUCache(4), trace), hit_rate(LFUCache(4), trace))   # 150 297

old, new = ["a", "b", "c"] * 50, ["x", "y", "z"] * 50
trace = old + new                               # yesterday's favourites, then today's
print(hit_rate(LRUCache(3), trace), hit_rate(LFUCache(3), trace))   # 294 147

The first trace is a scan: a burst of keys read once. Five of them flush a four-slot LRU completely, so every round opens with three misses on the hot keys. LFU parks the scan on shelf 1, where the rows evict each other and never touch the hot keys on shelf 2.

The second trace is a shift in popularity. After fifty rounds, a, b and c have high counts. When x, y and z take over, each newcomer enters at count 1 and is the first thing evicted when the next newcomer arrives. The stale favourites keep two of the three slots. LRU adapts in three misses.

The shelf bookkeeping is easy to get subtly wrong, so it is checked against the definition written as plainly as possible — store a count and a timestamp per key, and scan for the smallest pair on eviction:

import random

class SlowLFU:                                  # the definition, with a linear scan
    def __init__(self, capacity):
        self.cap, self.items, self.clock = capacity, {}, 0   # key -> [value, uses, last]

    def _tick(self):
        self.clock += 1
        return self.clock

    def get(self, key):
        if key not in self.items:
            return None
        item = self.items[key]
        item[1] += 1; item[2] = self._tick()
        return item[0]

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.items:
            item = self.items[key]
            item[0] = value; item[1] += 1; item[2] = self._tick()
            return
        if len(self.items) == self.cap:
            victim = min(self.items, key=lambda k: (self.items[k][1], self.items[k][2]))
            del self.items[victim]
        self.items[key] = [value, 1, self._tick()]

random.seed(3)
ok = True
for _ in range(2000):
    cap = random.randint(0, 4)
    fast, slow = LFUCache(cap), SlowLFU(cap)
    for _ in range(40):
        key = random.randint(0, 6)
        if random.random() < 0.5:
            ok &= fast.get(key) == slow.get(key)
        else:
            v = random.randint(0, 99)
            fast.put(key, v); slow.put(key, v)
    ok &= set(fast.value) == set(slow.items)
print(ok)                                       # True

The complexity

Both caches do get and put in O(1) average time: every step is a hash lookup, an ordered-dict move, or a pop from the front of one shelf. Memory is O(capacity). LFU carries more per key — a count, a shelf entry — and more hash maps, so its constant factor is higher than LRU's.

Where it goes wrong

• Scanning for the minimum count. Correct, but O(n) per eviction. The floor exists so this never happens.
• Forgetting to reset the floor on insert. After an eviction the floor may point at a high shelf; the new key is on shelf 1, and the next eviction must look there.
• Joining the front of the new shelf. A promoted key is the most recent on its new shelf, so it goes to the back. Putting it at the front breaks the tie-break rule.
• Choosing LFU for a changing workload. Counts never decay in the plain version, so yesterday's popular keys squat. Practical variants often age or cap the counts; the plain structure does not.

For the LRU half built from first principles, see LRU cache design.

How to say it in an interview

"LRU evicts the oldest access; LFU evicts the fewest accesses, oldest first on a tie. For O(1) LFU I keep keys in buckets by use count, each bucket ordered by recency, plus the lowest non-empty count. A hit moves a key to the back of the next bucket; an eviction pops the front of the lowest bucket. The minimum only changes when its bucket empties on a hit, where it goes up by one, or on an insert, where it resets to 1."

Then say when you would pick each. LRU is robust to shifting popularity but a single scan flushes it; LFU shrugs off scans but holds on to stale favourites. Naming a trace that breaks each shows you understand the policies, not just the data structures.