LRU Cache: The Pragmatist

The Story: The Stack of Papers

Imagine you have a messy desk with a single stack of papers.

• When you read a paper, you pull it out and put it on the very top of the stack.
• When you get a new paper, you put it on the top.
• When the stack gets too high and threatens to topple over, you pull a paper from the very bottom and throw it in the trash.

This is LRU (Least Recently Used). The paper at the bottom is the one you haven’t touched for the longest time. Logic dictates that if you haven’t looked at it in days, you probably won’t need it in the next 5 minutes.

LRU is the Default Policy for almost every caching system (from CPU caches to Redis) because it perfectly matches human behavior: we tend to focus on a few things at a time.

Why do we need it?

• Browsers: When you press the “Back” button, the browser shows the page instantly because it’s in the LRU cache.
• Operating Systems: Which pages of memory should remain in RAM? The ones the user is actively clicking on.
• Simplicity: It is easy to understand and surprisingly effective for 90% of workloads.

How the Algorithm “Thinks”

The algorithm needs to do two things fast ($O(1)$):

1. Find a key (Map).
2. Move that key to the “Top” (List).

This requires a hybrid structure: HashMap + Doubly Linked List.

1. Access (Get):

   • Look up the node in the Map.
   • Detach the node from its current position in the List.
   • Attach it to the Head (Most Recently Used).
   • Return value.

2. Insert (Put):

   • If key exists: Update value, move to Head.
   • If key is new: Create node, add to Head, add to Map.
   • Eviction: If the cache is full, look at the Tail (Least Recently Used). Remove it from the List and the Map.

Engineering Context: The Heavy Lifting

While LRU is great, it’s not perfect.

• The Scan Problem: If a user requests 1 million items once (a “Scan”), they will flush out your entire useful cache, replacing high-value items with one-hit wonders.
• Concurrency: To move items to the “Head,” you need to lock the list. In multi-threaded systems, this “lock contention” can slow everything down.

Implementation (Python)

Python’s collections.OrderedDict makes this trivial, but let’s build the internal logic to see the soul of the machine.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # Map: key -> Node
        # Dummy head and tail to avoid edge case checks
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # 1. Remove from current spot
            self._remove(node)
            # 2. Move to Head (Most Recently Used)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        
        node = Node(key, value)
        self._add_to_head(node)
        self.cache[key] = node

        if len(self.cache) > self.capacity:
            # Evict the LRU (Node before Tail)
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.cache[lru_node.key]

# Usage
lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
print(lru.get(1)) # Returns 1, moves 1 to head. Cache: [1, 2]
lru.put(3, 3)     # Evicts 2 (LRU). Cache: [3, 1]
print(lru.get(2)) # Returns -1 (Not Found)

Summary

LRU teaches us that time is the best filter. By assuming that the past predicts the future, we can make simple decisions that are correct most of the time. It reminds us that in a fast-paced world, “What have you done for me lately?” is not an insult—it’s an optimization.