Why LRU Wins: Competitive Analysis of Caching Strategies

When a cache has to decide which files to keep, the choice of eviction algorithm determines how often users wait for network calls instead of instant local access. Dropbox’s mobile clients split files into 4MB blocks and use least-recently-used (LRU) eviction across both Android and iOS. That choice is the mainstream one, but is it actually the best? To answer that rigorously, we need a formal model and a way to compare algorithms under worst-case conditions.

Formalizing the Cache Problem

We have a large collection of files, all assumed equal in size — a simplification that holds roughly for fixed-size blocks, and one we can relax later. At any moment the cache holds k files. When the user requests a file, the cache either serves it (a hit) or fetches it over the network (a miss), possibly evicting something to make room. We are forced into an online setting: the algorithm sees only past requests and cannot anticipate what comes next.

Two performance criteria matter. The hit rate — the fraction of requests served without network I/O — is the primary goal. But the cache must also be cheap to operate: membership tests and eviction decisions should add negligible overhead. The first concern is about algorithm design; the second is about data structures.

Measuring Worst-Case Performance with Competitive Analysis

The user drives cache behavior, so worst-case performance is defined against an adversarial user who maximally disrupts whatever eviction policy we choose. A purely adversarial analysis is meaningless, though: any cache can be forced to miss by requesting an unbounded number of distinct files. The fix is to compare against a benchmark that can see the future.

Competitive analysis compares our online algorithm’s number of misses A against the misses O of an optimal offline algorithm that knows the entire request sequence in advance. The competitive ratio is the worst-case value of A / O over all possible request sequences. If we can construct a sequence where our algorithm misses A times and the optimal algorithm must miss at least O times, we have a lower bound on the competitive ratio.

To show an algorithm is bad, we pick an adversarial sequence, count our algorithm’s misses precisely, then upper-bound the optimal algorithm’s misses by constructing some reasonable caching strategy for that same sequence. Since the optimal can do no worse than our constructed strategy, the ratio A / O is a lower bound on the true competitive ratio. Conversely, proving an upper bound requires a general argument that holds for every possible sequence.

The Candidate Algorithms

Three classic policies form the basis of comparison:

  • Most Recently Used (MRU): evict the file accessed most recently. This keeps older, less-frequently-touched files around. It shines for sequential access patterns — say, browsing a photo gallery — where each new request refers to a file we just saw and will likely never need again.
  • Least Recently Used (LRU): evict the file with the oldest last-access time. This requires only an access-order list. LRU adapts quickly to shifting interests but can falter when some files are consistently accessed at long, regular intervals.
  • Least Frequently Used (LFU): evict the file with the lowest access count. This needs a counter per file. LFU handles stable popularity distributions well but clings to files that were popular in the past and are now dead weight.

MRU Is Arbitrarily Bad

MRU fails spectacularly on a simple alternating pattern. Consider requests for files (1, 2, …, k, k+1, k, k+1, k, …). Each time k+1 arrives, MRU evicts k to make room; when k arrives next, it evicts k+1. Every request is therefore a miss. An optimal algorithm, by contrast, could evict file 1 once and then serve both k and k+1 indefinitely from cache, incuring at most k+1 misses to populate the cache initially. MRU’s miss count grows linearly with the sequence length N, while the optimal stays constant as N grows. The competitive ratio is therefore unbounded — MRU is ∞-competitive and effectively unusable for general workloads.

LRU Is Exactly k-Competitive

LRU handles the above pattern correctly, evicting files exactly as the optimal would. But LRU has its own weakness. If requests cycle through (1, 2, …, k, k+1) repeatedly, LRU misses every single time: by the time file k+1 arrives, file 1 is the least recently used and gets evicted, and the same happens to file 2 when the pattern restarts. Yet an optimal algorithm can evict the file that will be needed latest — evict k to make room for k+1, then k-1 for k, and so on — yielding one miss per k requests. Over N requests, LRU misses N times while the optimal misses roughly k + N/k times. For large N, the ratio approaches k, showing LRU cannot be better than k-competitive.

It turns out LRU is exactly k-competitive. The proof divides any request sequence into phases, each phase containing at most k distinct files. Within a phase, LRU can miss at most k times — once for each distinct file before it is cached. Meanwhile, the optimal algorithm, holding only k files, must miss at least once per phase, because the phase boundary guarantees a file is requested that was not in its cache. Since the same argument applies to any deterministic algorithm whose cache contents are predictable, k-competitiveness is the best any deterministic online algorithm can achieve. Randomized algorithms can occasionally do better in expectation, but they introduce unpredictability — a poor trade-off when cache behavior must be debuggable and reproducible.

LFU Sounds Smarter But Isn’t

LFU appears superior because it uses genuine popularity data rather than mere recency. The competitive analysis, however, reveals a fatal flaw. LFU performs terribly when usage patterns shift: files heavily used in one period remain in cache long after they stop being relevant, blocking files that are now hot.

Construct a sequence that first requests files (1, …, k-1) many times, until their access counters dwarf everything else, then alternates between files k and k+1. Since both have low counters, each alternation evicts one to make room for the other. LFU endures k-1 misses to load the first batch, then a miss on every alternation — 2N additional misses over N rounds. The optimal algorithm would simply evict one of the obsolete files (1, …, k-1) when the pattern shifts and then serve both k and k+1 from cache, incurring only k+1 total misses. The ratio (2N + k - 1) / (k + 1) grows without bound as N increases, so LFU is arbitrarily bad — worse than LRU in competitive terms.

The failure mode is not merely theoretical. Consider finishing a large project: the files you worked on daily for months suddenly become obsolete, and LFU keeps them in cache while your new project’s files miss constantly. LRU avoids this trap by forgetting anything older than k accesses. Popularity information is useful, but only when it is recent; LRU implicitly tracks popularity over a sliding window of the last k requests, which is why it remains the robust default despite its theoretical ceiling.

Why LRU Still Wins in Practice

Combining the strengths of LRU and LFU sounds appealing, but the theoretical picture is more nuanced. Any deterministic caching algorithm—not just LRU—can be forced into k-competitive worst-case behavior: an adversary simply requests the one file that is never in the cache. On that front, no deterministic algorithm can do better.

In real workloads, however, more sophisticated schemes do shine. The ARC and CAR algorithms generally outperform LRU by balancing recency and frequency, despite sharing the same theoretical worst case. Their added complexity buys better typical-case hit rates. Randomized algorithms, by contrast, can achieve O(log k) competitiveness in expectation—a result due to Fiat et al.—but they are rarely used in production. Their behavior can be surprising to users, who expect a file they just accessed to load quickly, not to be evicted by chance.

There is a more subtle reason deterministic algorithms like LRU remain attractive. Von Neumann's Minimax Theorem frames cache design as a game between the algorithm and an adversary. If the algorithm is deterministic and known, the adversary can always pick a worst-case sequence. But if the algorithm is randomized, the adversary's optimal response is itself deterministic—and the expected number of misses is bounded by O(log k). The same logic works in reverse: for a pre-determined, non-adversarial input sequence—which is what a human user effectively provides—a good deterministic policy is optimal in expectation. LRU is exactly such a policy: its worst-case competitive ratio is k, but its expected performance is much better.

Another useful comparison relaxes the cache size constraint. An LRU cache is at most twice as bad as an optimal cache half its size. Viewed this way, a 200-file LRU cache is within 2x of a theoretical best 100-file cache—a far more palatable bound than the raw k-competitiveness result.

For most systems, LRU is the right choice: theoretically sound, simple to implement, and fast in practice. Dropbox's iOS and Android clients use LRU caches, and the Linux kernel relies on segmented LRU, a variant designed for its access patterns.

A Constant-Time LRU Implementation

An efficient LRU cache needs two operations to complete quickly: lookup by key and determination of recency order. A hash table provides O(1) lookup, while a doubly linked list tracks recency. The trick is to let the hash table map each key directly to its node in the list, so rearrangement is also constant time.

class DoubleLinkedNode:
    def __init__(self, prev, key, item, next):
        self.prev = prev
        self.key = key
        self.item = item
        self.next = next
 
class LRUCache:
    """ An LRU cache of a given size caching calls to a given function """
 
    def __init__(self, size, if_missing):
        """
        Create an LRUCache given a size and a function to call for missing keys
        """
 
        self.size = size
        self.slow_lookup = if_missing
        self.hash = {}
        self.list_front = None
        self.list_end = None
def get(self, key):
    """ Get the value associated with a certain key from the cache """
 
    if key in self.hash:
        return self.from_cache(key)
    else:
        new_item = self.slow_lookup(key)
 
        if len(self.hash) >= self.size:
            self.kick_item()
 
        self.insert(key, new_item)
        return new_item

Looking up an existing item requires only moving its list node to the head of the list.

def from_cache(self, key):
    """ Look up a key known to be in the cache. """
 
    node = self.hash[key]
    assert node.key == key, "Node for LRU key has different key"
 
    if node.prev is None:
        # it's already in front
        pass
    else:
        # Link the nodes around it to each other
        node.prev.next = node.next
        if node.next is not None:
            node.next.prev = node.prev
        else: # Node was at the list_end
            self.list_end = node.prev
 
        # Link the node to the front
        node.next = self.list_front
        self.list_front.prev = node
        node.prev = None
        self.list_front = node
 
    return node.item

Evicting the least-recently-used item means removing the node at the tail of the list.

def kick_item(self):
    """ Kick an item from the cache, making room for a new item """
 
    last = self.list_end
    if last is None: # Same error as [].pop()
        raise IndexError("Can't kick item from empty cache")
 
    # Unlink from list
    self.list_end = last.prev
    if last.prev is not None:
        last.prev.next = None
 
    # Delete from hash table
    del self.hash[last.key]
    last.prev = last.next = None # For GC purposes

Inserting a new item is a matter of linking it at the head of the list and adding it to the hash table.

def insert_item(self, key, item):
    node = DoublyLinkedNode(None, key, item, None)
 
    # Link node into place
    node.next = self.list_front
    if self.list_front is not None:
        self.list_front.prev = node
    self.list_front = node
 
    # Add to hash table
    self.hash[key] = node

That yields a working LRU cache with linear-space overhead and constant-time operations.

Handling Variable-Size Files and Stale Data

The analysis so far assumes uniform file sizes, which rarely holds in practice. Dropbox sidesteps this by splitting files into fixed 4MB blocks; caching operates on blocks rather than whole files. The same effect can be achieved by evicting files repeatedly until enough space is available for the requested item.

Cache invalidation is the other real-world concern. When cached files change on the server, the client must detect staleness. A practical approach is to download a per-directory index containing each file's revision number, without the file data itself. When a file is found in the cache, its modification time is checked against the server's. These directory indices can themselves be cached and validated with the same logic. This is the scheme used by Dropbox's Android and iOS clients.

Caching is most valuable in front of slow operations—network round trips, disk reads, or expensive computation—and especially on mobile, where bandwidth is constrained. For those scenarios, LRU remains the best balance of performance and simplicity.