{"id":1935,"date":"2024-10-15T12:25:04","date_gmt":"2024-10-15T12:25:04","guid":{"rendered":"https:\/\/algocademy.com\/blog\/cache-algorithms-fifo-vs-lru-vs-lfu-a-comprehensive-guide\/"},"modified":"2026-10-15T10:34:48","modified_gmt":"2026-10-15T10:34:48","slug":"cache-algorithms-fifo-vs-lru-vs-lfu-a-comprehensive-guide","status":"publish","type":"post","link":"https:\/\/algocademy.com\/blog\/cache-algorithms-fifo-vs-lru-vs-lfu-a-comprehensive-guide\/","title":{"rendered":"Cache Eviction: FIFO vs LRU vs LFU Compared, With Python Code"},"content":{"rendered":"

When a cache is full, an eviction policy decides which entry to throw out. FIFO<\/strong> evicts the entry that was inserted first, LRU<\/strong> evicts the one not used for the longest time, and LFU<\/strong> 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.<\/p>\n

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.<\/p>\n

The cache interface used below<\/h2>\n

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

FIFO: evict the oldest insertion<\/h2>\n

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.<\/p>\n

from collections import OrderedDict\n\n\nclass FIFOCache:\n    def __init__(self, capacity):\n        self.capacity = capacity\n        self.data = OrderedDict()  # insertion order = eviction order\n\n    def get(self, key):\n        return self.data.get(key, -1)  # reads do not change the order\n\n    def put(self, key, value):\n        if self.capacity == 0:\n            return\n        if key not in self.data and len(self.data) >= self.capacity:\n            self.data.popitem(last=False)  # drop the oldest insertion\n        self.data[key] = value  # updating an existing key keeps its place\n<\/code><\/pre>\n
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.<\/p>\n
A common mistake in hand-rolled versions is using a Python list as the queue and calling pop(0)<\/code>, which is O(n). OrderedDict<\/code> (or collections.deque<\/code> plus a dictionary) avoids that.<\/p>\n
LRU: evict what has not been used for the longest time<\/h2>\n
LRU bets on temporal locality<\/em>: something used recently is likely to be used again soon. Every get<\/code> or put<\/code> moves the key to the “most recent” end; eviction takes from the “least recent” end.<\/p>\n
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<\/a> and Linked Lists<\/a> lessons cover them. Python’s OrderedDict<\/code> is exactly that combination, so in Python (and in an interview, if the interviewer allows it) the implementation is short:<\/p>\n
class LRUCache:\n    def __init__(self, capacity):\n        self.capacity = capacity\n        self.data = OrderedDict()  # least recently used first\n\n    def get(self, key):\n        if key not in self.data:\n            return -1\n        self.data.move_to_end(key)\n        return self.data[key]\n\n    def put(self, key, value):\n        if self.capacity == 0:\n            return\n        if key in self.data:\n            self.data.move_to_end(key)\n        self.data[key] = value\n        if len(self.data) > self.capacity:\n            self.data.popitem(last=False)\n<\/code><\/pre>\n
If the interviewer asks you to build it without OrderedDict<\/code>, 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<\/a> goes through that version.<\/p>\n
LRU’s weak spot is a scan<\/em>: 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.<\/p>\n
LFU: evict what has been used the least<\/h2>\n
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.<\/p>\n
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<\/code>, 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<\/code> goes up by one. A newly inserted key always has count 1, so min_freq<\/code> resets to 1.<\/p>\n
from collections import defaultdict\n\n\nclass LFUCache:\n    def __init__(self, capacity):\n        self.capacity = capacity\n        self.values = {}                          # key -> value\n        self.freq = {}                            # key -> use count\n        self.buckets = defaultdict(OrderedDict)   # count -> keys, oldest first\n        self.min_freq = 0\n\n    def _touch(self, key):\n        f = self.freq[key]\n        del self.buckets[f][key]\n        if not self.buckets[f]:\n            del self.buckets[f]\n            if self.min_freq == f:\n                self.min_freq = f + 1\n        self.freq[key] = f + 1\n        self.buckets[f + 1][key] = None\n\n    def get(self, key):\n        if key not in self.values:\n            return -1\n        self._touch(key)\n        return self.values[key]\n\n    def put(self, key, value):\n        if self.capacity == 0:\n            return\n        if key in self.values:\n            self.values[key] = value\n            self._touch(key)\n            return\n        if len(self.values) >= self.capacity:\n            victim, _ = self.buckets[self.min_freq].popitem(last=False)\n            if not self.buckets[self.min_freq]:\n                del self.buckets[self.min_freq]\n            del self.values[victim]\n            del self.freq[victim]\n        self.values[key] = value\n        self.freq[key] = 1\n        self.buckets[1][key] = None\n        self.min_freq = 1\n<\/code><\/pre>\n
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<\/code> to 1 on insert.<\/p>\n
LFU has two known weaknesses. First, stale popularity<\/strong>: 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.<\/p>\n
Same operations, three different victims<\/h2>\n
Capacity 2: put 1, put 2, get 1, then put 3. Which key gets evicted?<\/p>\n
for cls in (FIFOCache, LRUCache, LFUCache):\n    c = cls(2)\n    c.put(1, 1)\n    c.put(2, 2)\n    a = c.get(1)\n    c.put(3, 3)\n    print(cls.__name__, a, c.get(1), c.get(2), c.get(3))\n<\/code><\/pre>\n
Output:<\/p>\n
FIFOCache 1 -1 2 3\nLRUCache 1 1 -1 3\nLFUCache 1 1 -1 3\n<\/code><\/pre>\n
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.<\/p>\n
Hit ratio on three access patterns<\/h2>\n
Here is a small simulator: on each key, call get<\/code>; on a miss, put<\/code> the key. Three traces, all with capacity 3:<\/p>\n
def hit_ratio(cls, capacity, trace):\n    c = cls(capacity)\n    hits = 0\n    for k in trace:\n        if c.get(k) != -1:\n            hits += 1\n        else:\n            c.put(k, k)\n    return hits \/ len(trace)\n\n# Two hot keys used repeatedly, with three never-repeated keys in between\none_offs = []\nn = 100\nfor _ in range(50):\n    one_offs += [0, 1, 0, 1, n, n + 1, n + 2]\n    n += 3\n\nloop = [0, 1, 2, 3] * 25                        # cycle over 4 keys\nshift = [0, 1, 2] * 30 + [10, 11, 12] * 30      # popular keys change halfway\n\nfor name, t in ((\"one-offs\", one_offs), (\"loop\", loop), (\"shift\", shift)):\n    print(name, *(f\"{cls.__name__[:-5]}={hit_ratio(cls, 3, t):.2f}\"\n                  for cls in (FIFOCache, LRUCache, LFUCache)))\n<\/code><\/pre>\n
one-offs FIFO=0.29 LRU=0.29 LFU=0.57\nloop FIFO=0.00 LRU=0.00 LFU=0.00\nshift FIFO=0.97 LRU=0.97 LFU=0.48\n<\/code><\/pre>\n\n\n\n\n\n\n\n
Pattern<\/th>\nWhat happens<\/th>\nWinner<\/th>\n<\/tr>\n<\/thead>\n
Hot keys plus one-off keys<\/td>\nOne-off keys flush FIFO and LRU, but LFU keeps the two keys with high counts<\/td>\nLFU<\/td>\n<\/tr>\n
Loop larger than the cache<\/td>\nEvery key is evicted just before it is used again; all three score zero<\/td>\nNone (needs a bigger cache or a different policy)<\/td>\n<\/tr>\n
Popularity shifts<\/td>\nLFU keeps the old popular keys because of their high counts and misses the new ones for a long time<\/td>\nFIFO and LRU<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
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.<\/p>\n
Comparison<\/h2>\n\n\n\n\n\n\n\n\n\n\n
<\/th>\nFIFO<\/th>\nLRU<\/th>\nLFU<\/th>\n<\/tr>\n<\/thead>\n
Evicts<\/td>\nOldest insertion<\/td>\nLongest since last use<\/td>\nFewest uses (ties: least recent)<\/td>\n<\/tr>\n
Tracks on a read<\/td>\nNothing<\/td>\nRecency order<\/td>\nA counter per key<\/td>\n<\/tr>\n
Time per operation<\/td>\nO(1)<\/td>\nO(1)<\/td>\nO(1) with the bucket design<\/td>\n<\/tr>\n
Extra memory per entry<\/td>\nSmall<\/td>\nList links<\/td>\nCounter plus bucket membership<\/td>\n<\/tr>\n
Strong when<\/td>\nData ages out in insertion order<\/td>\nRecent items are reused<\/td>\nPopularity is stable<\/td>\n<\/tr>\n
Weak when<\/td>\nA hot item is old<\/td>\nScans and loops<\/td>\nPopularity shifts, one-time bursts of counts<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
What real systems use<\/h2>\n