Cache Eviction: FIFO vs LRU vs LFU Compared, With Python Code

When a cache is full, an eviction policy decides which entry to throw out. FIFO evicts the entry that was inserted first, LRU evicts the one not used for the longest time, and LFU evicts the one used the fewest times. LRU is the default choice in most systems, LFU wins when some keys are popular for a long time, and FIFO is mostly a baseline or a fit for simple, time-ordered data.

This post shows how each policy works, gives a tested Python implementation of each (the LRU and LFU ones run in O(1) per operation, which is what interviewers ask for), and compares them on three small access patterns so you can see where each one wins and loses.

The cache interface used below

All three classes have the same interface, the one from the well-known LRU Cache and LFU Cache interview problems: a fixed capacity, get(key) returning the value or -1, and put(key, value) which inserts or updates and evicts one entry if the cache is over capacity. A cache lookup that finds the key is a hit, one that does not is a miss. The goal of a policy is to maximize the hit ratio: hits divided by total lookups.

FIFO: evict the oldest insertion

FIFO keeps entries in insertion order and removes the front one when space is needed. Reading a key does not change anything, so a key that is read constantly is still evicted as soon as it becomes the oldest.

from collections import OrderedDict


class FIFOCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()  # insertion order = eviction order

    def get(self, key):
        return self.data.get(key, -1)  # reads do not change the order

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key not in self.data and len(self.data) >= self.capacity:
            self.data.popitem(last=False)  # drop the oldest insertion
        self.data[key] = value  # updating an existing key keeps its place

Both operations are O(1). The code is short and there is no bookkeeping on reads, which is the whole appeal. The cost is that FIFO ignores usage completely.

A common mistake in hand-rolled versions is using a Python list as the queue and calling pop(0), which is O(n). OrderedDict (or collections.deque plus a dictionary) avoids that.

LRU: evict what has not been used for the longest time

LRU bets on temporal locality: something used recently is likely to be used again soon. Every get or put moves the key to the “most recent” end; eviction takes from the “least recent” end.

The classic O(1) design is a hash map pointing into a doubly linked list. The hash map finds a node in O(1); the linked list lets you unlink it and move it to the front in O(1). If you want to practice the pieces, the Hash Map and Linked Lists lessons cover them. Python’s OrderedDict is exactly that combination, so in Python (and in an interview, if the interviewer allows it) the implementation is short:

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()  # least recently used first

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

If the interviewer asks you to build it without OrderedDict, write the hash map plus doubly linked list with two sentinel nodes (a dummy head and tail) so you never handle empty-list special cases. Our deeper post on LRU goes through that version.

LRU’s weak spot is a scan: a loop over more distinct keys than the cache can hold, or a one-time pass over a big table, pushes out everything useful. Each key is evicted just before it is needed again, so the hit ratio can fall to zero.

LFU: evict what has been used the least

LFU counts accesses per key and evicts the key with the lowest count. When several keys share the lowest count, the usual tie-break is least recently used among them. This makes LFU good at protecting keys that are popular over a long period.

The O(1) design keeps three maps: key to value, key to count, and count to an ordered set of keys with that count. It also tracks min_freq, the lowest count currently present. When a key is used its count goes up by one and it moves to the next bucket; if its old bucket was the minimum and is now empty, min_freq goes up by one. A newly inserted key always has count 1, so min_freq resets to 1.

from collections import defaultdict


class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}                          # key -> value
        self.freq = {}                            # key -> use count
        self.buckets = defaultdict(OrderedDict)   # count -> keys, oldest first
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None

    def get(self, key):
        if key not in self.values:
            return -1
        self._touch(key)
        return self.values[key]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.values:
            self.values[key] = value
            self._touch(key)
            return
        if len(self.values) >= self.capacity:
            victim, _ = self.buckets[self.min_freq].popitem(last=False)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.values[victim]
            del self.freq[victim]
        self.values[key] = value
        self.freq[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1

A frequent bug is a heap-based LFU that re-heapifies on every access, which is O(n) per operation. Another is forgetting to reset min_freq to 1 on insert.

LFU has two known weaknesses. First, stale popularity: a key that was hot yesterday keeps a high count and stays even though nobody asks for it now, while new keys start at 1 and are the first to be evicted. Second, the extra bookkeeping: a counter per key and more work per access. Real systems usually fix the first problem by decaying the counts over time.

Same operations, three different victims

Capacity 2: put 1, put 2, get 1, then put 3. Which key gets evicted?

for cls in (FIFOCache, LRUCache, LFUCache):
    c = cls(2)
    c.put(1, 1)
    c.put(2, 2)
    a = c.get(1)
    c.put(3, 3)
    print(cls.__name__, a, c.get(1), c.get(2), c.get(3))

Output:

FIFOCache 1 -1 2 3
LRUCache 1 1 -1 3
LFUCache 1 1 -1 3

FIFO evicts key 1 even though it was just read, because it was inserted first. LRU and LFU evict key 2: it is both less recently and less frequently used than key 1. To separate LRU from LFU you need longer access patterns.

Hit ratio on three access patterns

Here is a small simulator: on each key, call get; on a miss, put the key. Three traces, all with capacity 3:

def hit_ratio(cls, capacity, trace):
    c = cls(capacity)
    hits = 0
    for k in trace:
        if c.get(k) != -1:
            hits += 1
        else:
            c.put(k, k)
    return hits / len(trace)

# Two hot keys used repeatedly, with three never-repeated keys in between
one_offs = []
n = 100
for _ in range(50):
    one_offs += [0, 1, 0, 1, n, n + 1, n + 2]
    n += 3

loop = [0, 1, 2, 3] * 25                        # cycle over 4 keys
shift = [0, 1, 2] * 30 + [10, 11, 12] * 30      # popular keys change halfway

for name, t in (("one-offs", one_offs), ("loop", loop), ("shift", shift)):
    print(name, *(f"{cls.__name__[:-5]}={hit_ratio(cls, 3, t):.2f}"
                  for cls in (FIFOCache, LRUCache, LFUCache)))

one-offs FIFO=0.29 LRU=0.29 LFU=0.57
loop FIFO=0.00 LRU=0.00 LFU=0.00
shift FIFO=0.97 LRU=0.97 LFU=0.48

Pattern	What happens	Winner
Hot keys plus one-off keys	One-off keys flush FIFO and LRU, but LFU keeps the two keys with high counts	LFU
Loop larger than the cache	Every key is evicted just before it is used again; all three score zero	None (needs a bigger cache or a different policy)
Popularity shifts	LFU keeps the old popular keys because of their high counts and misses the new ones for a long time	FIFO and LRU

These traces are tiny and chosen to show the failure modes, so do not read the exact numbers as typical. On real traffic, measure with a trace from your own system.

Comparison

	FIFO	LRU	LFU
Evicts	Oldest insertion	Longest since last use	Fewest uses (ties: least recent)
Tracks on a read	Nothing	Recency order	A counter per key
Time per operation	O(1)	O(1)	O(1) with the bucket design
Extra memory per entry	Small	List links	Counter plus bucket membership
Strong when	Data ages out in insertion order	Recent items are reused	Popularity is stable
Weak when	A hot item is old	Scans and loops	Popularity shifts, one-time bursts of counts

What real systems use

• Python: functools.lru_cache memoizes a function with an LRU policy; its default maxsize is 128, and functools.cache is the same thing with no size limit, so it never evicts (Python docs).
• Redis: when maxmemory is reached, the maxmemory-policy setting chooses the behavior. Options include allkeys-lru, allkeys-lfu, allkeys-random and the volatile-* variants that only touch keys with an expiry. Redis’s LRU and LFU are approximations: it samples a few keys and evicts the best candidate among them rather than tracking exact order. LFU is available since Redis 4.0 and uses a small probabilistic counter that decays over time, which addresses the stale-popularity problem. The Redis docs call allkeys-lru a good default if you have no reason to prefer another policy (Redis docs, as of October 2026).

The pattern is clear: production caches are usually LRU or LFU variants that trade exactness for lower memory and CPU cost, often with extras such as expiry times and scan resistance.

How to choose

1. Start with LRU. It matches most real access patterns and costs little.
2. Consider LFU if a stable set of popular keys is being pushed out by bursts of one-time keys, and you can decay counts so old favorites fade.
3. FIFO is fine when entries naturally expire in the order they were added, or when you need the cheapest possible policy and misses are cheap.
4. Measure. Log hits and misses, replay a real trace against each policy, and compare. A policy that wins on paper can lose on your traffic.

In interviews

“Design an LRU cache” is a standard question, and “LFU cache” is its harder sibling. Expect to be asked for O(1) get and put, and to explain why a hash map alone or a list alone cannot do it. Practice writing the doubly linked list version once by hand, then know the OrderedDict shortcut. The AlgoCademy app has step-by-step practice for the underlying hash table and linked list problems.