LRU cache: an interactive eviction policy simulator

An LRU cache (least recently used) holds a fixed number of items and, when it is full, evicts the one used longest ago. Every read or write moves an item to the most recent end, so the item at the other end is always next to go. Built from a hash map and a doubly linked list, both get and put take O(1) time.

The playground runs the same requests through an LRU, an LFU and a FIFO cache of four slots. Each scenario is a request pattern one of them handles better: play all three and compare the hit rates.

How an LRU cache works

1. A hash map finds any key’s entry in O(1).
2. A doubly linked list keeps the entries in order of use, most recent at the head and least recent at the tail.
3. On a get, look the key up in the map and move its entry to the head.
4. On a put, insert or update the entry at the head. If the cache is now over capacity, remove the tail entry and delete its key from the map.

The list is what makes it O(1): moving an entry or dropping the tail is a few pointer changes, with no searching. Both structures together are a few dozen bytes per entry on top of the data.

LRU vs LFU

LRU keeps what was used recently; LFU keeps what was used often. They disagree in two classic cases. A one-time scan (a batch job or a crawler reading many keys once) pushes every popular key out of an LRU cache, because the scanned keys are more recent; LFU keeps the popular keys because their counts are higher. A shift in popularity is the opposite: LRU forgets yesterday’s popular keys as soon as they stop being used, while LFU holds them for their old counts and has too little room left for what is popular now. Production caches blend the two: segmented LRU, ARC, and W-TinyLFU all keep a small recency area and a frequency filter.

LRU vs FIFO

FIFO evicts whatever went in first, however often it has been used since. It is simpler and cheaper, since a hit changes nothing, but it evicts hot keys on schedule. In the “hot keys and one-offs” scenario LRU keeps the two hot keys and hits 58% of requests; FIFO keeps evicting them and hits 42%.

Which to use

Redis evicts nothing by default (noeviction: writes fail when memory is full), so a Redis used as a cache needs maxmemory and a policy set; allkeys-lru is the usual choice, and allkeys-lfu suits workloads with scans.

An LRU cache in code

from collections import OrderedDict

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

    def get(self, key):
        if key not in self.items:
            return None
        self.items.move_to_end(key)         # now the most recently used
        return self.items[key]

    def put(self, key, value) -> None:
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)  # evict the least recently used

OrderedDict is itself a hash map and a doubly linked list, so this is O(1). In an interview that asks you to build one (LeetCode’s “LRU Cache”), write the list yourself: a node with prev and next pointers, sentinel head and tail nodes, and the map from key to node.

In a system design interview

Size it and name the policy in one breath: “A Redis cache in front of the database, sized for the hot 20% of items that serve most reads, with allkeys-lru and a TTL for freshness; we watch the hit rate and grow it if that drops.” Expect the follow-ups: what a scan does to it (LFU, or a separate cache for batch reads), a stampede of misses when a hot key expires (request coalescing), and keeping the cache consistent with the database on writes.

Watch a strong candidate design a distributed cache, or read the caching guide for cache-aside, write-through and invalidation.

Questions people ask