LRU eviction isn’t about discarding data; it’s about intelligently making space by discarding the data you’re least likely to need soon.
Let’s watch an LRU cache in action. Imagine we have a small cache with a capacity of 3 items. We’re storing key-value pairs, where the keys are page IDs and the values are the page content.
class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.order = [] # Stores keys in order of access (most recent at end)
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
else:
# Move accessed item to the end of the order list
self.order.remove(key)
self.order.append(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# Update existing item, move to end
self.cache[key] = value
self.order.remove(key)
self.order.append(key)
else:
if len(self.cache) >= self.capacity:
# Evict the least recently used item (first in the order list)
lru_key = self.order.pop(0)
del self.cache[lru_key]
# Add new item
self.cache[key] = value
self.order.append(key)
# Simulation
cache = LRUCache(3)
print("Putting 1:10")
cache.put(1, 10) # cache: {1:10}, order: [1]
print("Cache:", cache.cache, "Order:", cache.order)
print("Putting 2:20")
cache.put(2, 20) # cache: {1:10, 2:20}, order: [1, 2]
print("Cache:", cache.cache, "Order:", cache.order)
print("Putting 3:30")
cache.put(3, 30) # cache: {1:10, 2:20, 3:30}, order: [1, 2, 3]
print("Cache:", cache.cache, "Order:", cache.order)
print("Getting 1")
print(cache.get(1)) # cache: {1:10, 2:20, 3:30}, order: [2, 3, 1] (1 is now most recent)
print("Cache:", cache.cache, "Order:", cache.order)
print("Putting 4:40 (evicts 2)")
cache.put(4, 40) # cache: {1:10, 3:30, 4:40}, order: [3, 1, 4] (2 was LRU)
print("Cache:", cache.cache, "Order:", cache.order)
print("Getting 2")
print(cache.get(2)) # Returns -1, 2 is not in cache
print("Cache:", cache.cache, "Order:", cache.order)
print("Putting 3:35 (updates value)")
cache.put(3, 35) # cache: {1:10, 3:35, 4:40}, order: [1, 4, 3] (3 is now most recent)
print("Cache:", cache.cache, "Order:", cache.order)
The core problem LRU eviction solves is managing finite memory resources when you need to store a potentially infinite stream of data, or at least more data than you can physically hold. Think of a web server caching frequently requested pages, a database caching hot rows, or an operating system caching recently used memory pages. Without a strategy, you’d either run out of space or, worse, discard data you’ll need again immediately. LRU provides a probabilistic guarantee: by keeping the most recently used items, you’re maximizing the chance that the next item you need is already in the cache.
Internally, a typical LRU implementation uses a combination of a hash map (for O(1) lookups) and a doubly linked list (for O(1) insertions and deletions at either end, and O(1) moving of nodes). The hash map stores the key and a pointer to the corresponding node in the linked list. The linked list maintains the order of access, with the head being the least recently used and the tail being the most recently used. When an item is accessed (get), its node is moved to the tail. When an item is added (put) and the cache is full, the item at the head of the list (the LRU item) is removed from both the list and the hash map.
The "levers" you control with LRU are primarily the capacity and how you define "recently used." The capacity is the hard limit on how much data the cache can hold. A larger capacity means fewer evictions but more memory usage. The definition of "recently used" is implicit in the access pattern. If your application accesses data in a very sequential, predictable way, LRU might not be optimal. If access is more random but with strong temporal locality (items accessed recently are likely to be accessed again soon), LRU shines.
A common misconception is that LRU always evicts the oldest item. It evicts the least recently used item. If you have items A, B, C, D in the cache, and you access A, then B, then C, then D, then A again, A is now the most recently used. If you then add E and the cache is full, D will be evicted, not A, even though D was added after A. The "age" of the data in terms of when it was first inserted is irrelevant; only the recency of its last access matters.
The next logical step after understanding LRU is exploring variations like LFU (Least Frequently Used) or ARC (Adaptive Replacement Cache), which offer different trade-offs for specific access patterns.