System Architecture: The Anatomy of an O(1) LRU Cache

In modern computing, memory is a hierarchy of extreme contrasts. A CPU L1 cache register responds in 0.5 nanoseconds, while main system RAM takes roughly 100 nanoseconds, and fetching a database record from an SSD or network takes upwards of 10,000,000 nanoseconds.

To prevent high-performance operating systems, web browsers, and distributed databases from grinding to a halt, engineers rely on a foundational principle: The Principle of Locality.

Programs tend to reuse data and instructions they have referenced recently (Temporal Locality). Because fast memory is scarce and expensive, systems deploy a cache. But when the cache fills up, a critical question arises: Which record should be discarded to make room for new data?

The industry standard answer is the Least Recently Used (LRU) Cache: a design that evicts the item that has sat untouched for the longest time.

1. The Algorithmic Dilemma: Why Naive Approaches Fail

To build an LRU cache, we need two core operations:

1. get(key): Retrieve value and mark as most recently used.
2. put(key, value): Insert key-value pair, evicting the least recently used entry if full.

Both operations must execute in strictly constant time: $\mathcal{O}(1)$.

Why do single data structures fail?

• A Pure Hash Map: Provides $\mathcal{O}(1)$ lookups, but maps have no inherent order. Finding the oldest item requires scanning all entries: an unacceptable $\mathcal{O}(n)$ operation.
• An Array or Queue: Maintains order, but finding a key requires linear search $\mathcal{O}(n)$, and moving an item to the front requires shifting elements: $\mathcal{O}(n)$.
• A Singly Linked List: Allows fast insertion, but removing an arbitrary node requires finding its predecessor, which takes $\mathcal{O}(n)$ traversal time.

2. The Architectural Masterpiece: Hash Map + Doubly Linked List

The solution is an elegant hybrid of two data structures working in unison:

  [ Hash Map ]
  Key "A" ===> [ Node A ] <====== (Pointer Resolution in O(1))
  Key "B" ===> [ Node B ]
  Key "C" ===> [ Node C ]

  [ Doubly Linked List (Temporal Ordering) ]
  HEAD (MRU) <-> [ Node C ] <-> [ Node A ] <-> [ Node B ] <-> TAIL (LRU)
  (Most Recent)                                              (Next to Evict)

1. The Doubly Linked List stores the actual data nodes ordered by recency of use:
   • The Head always points to the Most Recently Used (MRU) item.
   • The Tail always points to the Least Recently Used (LRU) item.
2. The Hash Map maps each Key directly to the Node Pointer in the list.

Executing get(key) in $\mathcal{O}(1)$:

1. Query the Hash Map. If absent $\to$ return -1 (Cache Miss).
2. If present $\to$ retrieve the node pointer directly.
3. Splice the node out of its current position by updating its neighbors: \(\text{node.prev.next} = \text{node.next}, \quad \text{node.next.prev} = \text{node.prev}\)
4. Re-attach the node directly after the dummy Head (marking it as MRU). Return value.

Executing put(key, value) in $\mathcal{O}(1)$:

1. If the key already exists: update its value and promote it to Head.
2. If the key is new:
   • If cache.size == capacity: Extract the node at Tail.prev (the LRU node). Delete it from the list and delete its key from the Hash Map in $\mathcal{O}(1)$!
   • Instantiate a new node, insert it at Head.next, and register it in the Hash Map.

 Operation Complexity:
 get(key):        O(1)
 put(key, val):   O(1)
 Eviction:        O(1)
 Overall Space:   O(Capacity)

3. Real-World Systems Utilizing LRU Caches

• Linux Kernel Page Cache: Virtual memory management in the Linux kernel uses a variation of the LRU algorithm (the Active/Inactive list split) to decide which 4KB physical RAM pages to flush to swap space when RAM runs low.
• Redis & Memcached: The world’s most popular in-memory key-value stores provide explicit allkeys-lru and volatile-lru eviction flags, allowing distributed backend microservices to cache database queries without running out of RAM.
• Web Browsers: Your browser caches DNS resolutions, HTTP responses, CSS stylesheets, and image assets using an LRU cache so visiting back-pages loads instantaneously.