LRU Cache — Design & Implementation

Imagine a library with infinite space for books. You could keep every book ever borrowed, organize them however you wish, and never worry about running out of room. But in reality, libraries have finite shelf space, and the same constraint applies to computer memory.

Caching is one of the most powerful techniques in computer science — the practice of keeping frequently or recently accessed data close at hand to avoid expensive recomputation or retrieval. But caches have limited capacity, and when that capacity is exhausted, difficult decisions must be made. Which data do we evict to make room for new entries?

This decision — the eviction policy — determines the cache's effectiveness. Choose wisely, and your cache dramatically accelerates system performance. Choose poorly, and your cache becomes worse than useless, consuming memory while providing no benefit.

Before we discuss eviction policies, let's establish what caching is and why it's so critical to modern computing.

The fundamental asymmetry of modern computers:

Computers have multiple layers of storage, each with drastically different speed and capacity characteristics:

Notice the six orders of magnitude difference between L1 cache access (~1 nanosecond) and network access (~1 millisecond). This asymmetry creates the fundamental motivation for caching: keep hot data close, push cold data far away.

The cache abstraction:

A cache is simply a smaller, faster storage layer that sits between a slow storage layer and the component requesting data. When data is requested:

1. Cache Hit: The data is found in the cache — returned immediately
2. Cache Miss: The data is not in the cache — fetched from the slow layer, then stored in the cache for future requests

The effectiveness of a cache is measured by its hit rate — the percentage of requests served from the cache rather than the slow storage.

Here's the fundamental dilemma: caches have limited capacity. When a cache is full and a new item must be added, an existing item must be removed. Which item do we evict?

This is not a trivial decision. The choice of eviction policy can make or break your system's performance. Let's understand why with a concrete example.

Scenario: Web Application Cache

Imagine a web application with a cache that can hold 1000 user session objects. During peak traffic:

• 10,000 users are active
• Each user might make 5-50 requests per session
• Session lookup from the database takes 50ms
• Session lookup from cache takes 0.1ms

If your eviction policy is poor, you might evict sessions that are about to be accessed again. Each eviction of an active session costs 50ms in database access. With thousands of requests per second, bad eviction decisions cascade into seconds of cumulative delay.

The Oracle's Perfect Eviction:

If you could see the future, the optimal eviction policy would be simple: evict the item that will be used furthest in the future (or never used again). This is called the Optimal Replacement Policy or Bélády's Algorithm.

Unfortunately, predicting the future is impossible. We must use heuristics based on past behavior to approximate optimal eviction. This is where different eviction policies diverge.

Multiple eviction strategies have been developed, each with different trade-offs. Understanding these alternatives helps appreciate why LRU became dominant.

1. Random Replacement

The simplest possible policy: when eviction is needed, pick a random item to remove.

Pros: O(1) time, trivial implementation, no bookkeeping overhead Cons: Completely ignores access patterns — might evict the most frequently used item

2. First-In, First-Out (FIFO)

Evict the item that was added to the cache first, regardless of how often it's accessed.

Pros: O(1) time with a queue, simple mental model Cons: A frequently-accessed item added early will be evicted before a never-touched item added later

3. Least Frequently Used (LFU)

Evict the item that has been accessed the fewest times since entering the cache.

Pros: Keeps truly popular items around Cons: Historical bias — an item popular last week but cold now stays forever; new items are vulnerable to eviction before they can prove themselves

4. Least Recently Used (LRU)

Evict the item that was accessed longest ago.

Pros: Adapts to changing access patterns; recently accessed items stay Cons: A full-cache scan of all items (accessed once each) pollutes the entire cache

Temporal locality is the principle that if an item was accessed recently, it's likely to be accessed again in the near future. This isn't an arbitrary assumption — it reflects fundamental patterns in how humans and systems interact with data.

Why temporal locality exists:

The recency heuristic:

LRU makes a simple bet: the past is the best predictor of the near future. If you accessed something 5 seconds ago but haven't accessed something else in 5 hours, the first item is more likely to be needed again soon.

This heuristic isn't always correct — sometimes old data becomes relevant again. But it's correct often enough that LRU significantly outperforms random or FIFO policies across nearly all real-world workloads.

Mathematical justification:

Assume access patterns follow an exponential decay in recency. The probability of accessing item X in the next time interval is proportional to e^(-λ × time_since_last_access), where λ is a decay constant. Under this model, LRU is provably optimal — it always keeps the items with the highest probability of near-future access.

LRU isn't just a theoretical concept — it's ubiquitous in production software. Understanding where LRU appears helps appreciate its importance.

CPU Caches:

Modern CPUs use LRU or pseudo-LRU policies to manage L1, L2, and L3 caches. When you access a memory address, the CPU keeps it in cache assuming you'll access it again. This hardware-level LRU is invisible to programmers but critical for performance.

Operating System Page Cache:

When your OS loads files into memory, it uses LRU-based policies to decide which file pages to keep in RAM. This is why opening a file the second time is faster — the pages stayed in the OS cache.

Database Query Caches:

MySQL, PostgreSQL, and other databases cache query results. LRU determines which query results stay in memory. Repeated queries execute instantly from cache.

Application Caches:

Redis and Memcached — the most popular caching systems — both support LRU eviction. Web applications worldwide depend on these caches for session storage, API response caching, and more.

Let's precisely define what an LRU cache does. This formal specification will guide our implementation in later pages.

The LRU Cache ADT (Abstract Data Type):

An LRU Cache with capacity C supports two operations:

get(key):

1. If key exists in the cache, return its value and mark it as most recently used
2. If key doesn't exist, return a sentinel value (null, -1, etc.)

put(key, value):

1. If key already exists, update its value and mark it as most recently used
2. If key doesn't exist:
   • If cache is at capacity, evict the least recently used item
   • Insert the new key-value pair as the most recently used

The key insight: access = recency update

Notice that both get and put update recency. This is crucial and often overlooked:

• get("A") returns A's value and makes A the most recently used
• put("B", value) inserts/updates B and makes B the most recently used

This means simply reading a value prevents it from being evicted soon. The cache automatically adapts to access patterns without any explicit hints from the caller.

Before designing our optimal solution, let's consider naive approaches and understand why they're insufficient. This analysis will reveal the specific requirements our final design must satisfy.

Naive Approach 1: HashMap + Timestamps

Store each item with a timestamp of its last access. On eviction, scan all items to find the one with the oldest timestamp.

get(key):
  if key in map:
    map[key].timestamp = current_time()
    return map[key].value
  return null

put(key, value):
  if key in map:
    map[key].value = value
    map[key].timestamp = current_time()
  else:
    if map.size >= capacity:
      // Find and remove item with oldest timestamp - O(n) scan!
      oldest = find_min_timestamp(map)
      map.remove(oldest)
    map[key] = {value, timestamp: current_time()}

Analysis:

• get: O(1) ✓
• put (no eviction): O(1) ✓
• put (with eviction): O(n) ✗ — must scan all items to find minimum timestamp

With a cache of 100,000 items, every eviction requires comparing 100,000 timestamps. Unacceptable.

Naive Approach 2: HashMap + Min-Heap

Use a min-heap ordered by timestamp to find the oldest item in O(log n).

Analysis:

• get: O(1) for map lookup, but updating the heap position requires O(n) search + O(log n) heapify → O(n) overall ✗
• put: Same problem — updating an existing key's position in the heap is expensive

The issue is that heaps support efficient insert and extract-min, but not efficient arbitrary-element update or delete.

Naive Approach 3: HashMap + Sorted Array

Keep items sorted by access time.

Analysis:

• Finding LRU: O(1) — it's at the end
• Updating recency: O(n) — must shift elements to move item to the front

Again, O(n) per operation is unacceptable.

We've covered substantial ground in understanding the LRU eviction policy. Let's consolidate the key insights:

What's next:

Now that we understand what LRU does and why it's valuable, the next page examines the specific requirements that make O(1) operations challenging. We'll analyze exactly what operations our data structure must support and establish the complexity requirements that any production-grade LRU cache must meet.