An LRU trace you can run by hand

An LRU cache keeps the entries used most recently and discards the least recently used entry when it needs room. The word “used” matters: reading a cached value changes its position even when the value itself stays identical.

If you are a beginner implementing a small application cache, start with an explicit access trace rather than a hit-rate slogan. You need basic Python dictionaries and functions for this example. We will cache three profile values, follow every recency change, and test a workload that defeats the policy. The example is sequential and uses a synchronous loader; it does not coordinate concurrent requests.

Put the least recent entry on the left

Represent the cache as an ordered list of keys, least recent first and most recent last. After accesses A, B and C, the order is [A, B, C]. A is the next eviction candidate because B and C have both been used more recently.

Access A again. It is a hit, meaning the key is already resident, so no load is needed, but the order becomes [B, C, A]. A has moved to the newest position. When D then misses, admit D at the right and evict B from the left. The resulting order is [C, A, D].

This is not insertion order. An insertion-only queue would still treat A as the oldest entry after the hit and would evict it when D arrives. The difference occurs before any performance calculation: the two policies maintain different state. Always label which end of a diagram is least recent, because some descriptions draw the same LRU order in the opposite direction.

Operating Systems: Three Easy Pieces, section 22.5, introduces LRU as a policy based on recency and temporal locality. Recent use is evidence that another use may follow, not a guarantee. We apply the ordering rule to application entries here; this is not a simulation of a kernel’s page-replacement implementation.

View full-size image ↗

Make cache membership independent of the stored value

A cache needs to distinguish “this key is absent” from “this key stores a value that happens to be false-like.” A legitimate result can be None, zero or an empty string. Using if not cache.get(key) to decide whether to load would confuse those values with a miss.

Our implementation tests membership first. On a hit, it moves the existing key to the newest position and returns the stored value. On a miss, it calls the loader once, stores a successful result if capacity permits, and evicts the oldest entry only when necessary. Capacity zero deliberately means bypass storage while still calling the loader.

Python’s OrderedDict documentation specifies move_to_end and popitem(last=False), which provide the two ordering operations we need. A regular dictionary preserves insertion order, but a read alone does not make it an LRU cache. The recency update must remain explicit.

from collections import OrderedDict


class LRU:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity < 0:
            raise ValueError('capacity must be a nonnegative integer')
        self._capacity = capacity
        self._items = OrderedDict()

    def get(self, key, load):
        if type(key) is not str:
            raise ValueError('keys must be built-in strings')
        if key in self._items:
            self._items.move_to_end(key)
            return self._items[key]
        value = load(key)
        if self._capacity:
            self._items[key] = value
            if len(self._items) > self._capacity:
                self._items.popitem(last=False)
        return value

    def order(self):
        return tuple(self._items)  # Least recent first; no recency change.


calls = []
def load_profile(key):
    calls.append(key)
    return 'profile:' + key

cache = LRU(3)
trace = ('A', 'B', 'C', 'A', 'D', 'B', 'A', 'C')
expected = (
    ('A',), ('A', 'B'), ('A', 'B', 'C'), ('B', 'C', 'A'),
    ('C', 'A', 'D'), ('A', 'D', 'B'), ('D', 'B', 'A'),
    ('B', 'A', 'C'),
)
hits = []
for key, order in zip(trace, expected):
    hits.append(key in cache.order())
    assert cache.get(key, load_profile) == 'profile:' + key
    assert cache.order() == order
    print(key, 'hit' if hits[-1] else 'miss', order)
assert sum(hits) == 2 and len(calls) == 6
assert calls == ['A', 'B', 'C', 'D', 'B', 'C']

Keys are exact built-in strings; uppercase and lowercase identifiers are distinct. Capacity is a fixed nonnegative integer, with booleans rejected rather than treating True as one slot. Callers should use the public methods and leave the private state untouched. The loader accepts the missed key and may return any value; our main trace uses immutable strings.

The loader must not recursively access this same cache, and calls must not overlap. Otherwise a miss could become a hit while the original load is still running, changing the reasoning about admission and eviction. Supporting that behavior requires a separate coordination contract. Adding a lock around one dictionary operation would not by itself define the lifetime of the shared loading work.

order() returns a tuple snapshot for teaching and tests. Looking at that tuple does not count as another access. It copies the stored keys and therefore costs work proportional to the number of entries. The instrumentation should not be mistaken for the cost of an ordinary cache hit.

Count hits, misses and evictions separately

The trace contains eight accesses. Only the fourth and seventh accesses, both to A, hit. Six accesses therefore invoke the loader, giving a hit fraction of 2/8 for this particular initially empty run. Three of the misses fill unused slots; the remaining three require eviction. A miss does not automatically imply that an entry was evicted.

B and C each load twice. Their first visits do not guarantee residence until their second visits: intervening accesses can push them out. A loads only once because its hits move it to the most recent position at the necessary moments. D loads once but is evicted by the final C miss.

The hit fraction says nothing by itself about elapsed time. A loader might perform a cheap local calculation or an expensive remote request, and maintaining cache state has a cost too. These eight accesses are a worked trace, not measurements of a real service. A production comparison needs a representative request sequence and a separately measured miss cost.

A useful invariant is that the stored keys are unique, their count never exceeds capacity after a completed call, and the rightmost key is the latest successfully accessed resident entry. A successful miss counts as an access when its loaded value is admitted. A failed load does not enter the recency order at all in this implementation.

Preserve the cache when loading fails

The miss path loads before evicting. If the loader raises, the exception propagates and existing entries keep their values and order. Evicting first would discard a usable entry even though the requested replacement never arrived. The next block makes this behavior observable rather than merely describing it.

nullable = LRU(1)
none_calls = []
def load_none(key):
    none_calls.append(key)
    return None

assert nullable.get('optional', load_none) is None
assert nullable.get('optional', load_none) is None
assert none_calls == ['optional']

before = cache.order()
def fail(key):
    raise LookupError('upstream unavailable')

try:
    cache.get('E', fail)
except LookupError:
    pass
else:
    raise AssertionError('loader failure must propagate')
assert cache.order() == before

bypass = LRU(0)
assert bypass.get('optional', load_none) is None
assert bypass.get('optional', load_none) is None
assert len(none_calls) == 3 and bypass.order() == ()

scan_cache = LRU(3)
scan_calls = []
def scan_load(key):
    scan_calls.append(key)
    return key

for key in ('A', 'B', 'C', 'D') * 3:
    assert scan_cache.get(key, scan_load) == key
assert len(scan_calls) == 12
assert scan_cache.order() == ('B', 'C', 'D')

wide = LRU(4)
wide_calls = []
def wide_load(key):
    wide_calls.append(key)
    return key

for key in ('A', 'B', 'C', 'D') * 3:
    assert wide.get(key, wide_load) == key
assert wide_calls == ['A', 'B', 'C', 'D']
assert wide.order() == ('A', 'B', 'C', 'D')

The None example invokes its loader once across two accesses because membership is independent of value. The capacity-zero example invokes the loader on both accesses because it retains nothing. The failed E load leaves the main trace’s final [B, A, C] order unchanged.

This guarantee concerns the cache’s own state. It does not undo external side effects performed by the loader before raising. It also assumes the loader does not mutate the cache indirectly. Decide whether failures should be cached as results only after defining their meaning and lifetime; an arbitrary exception is not automatically a reusable negative answer.

A repeated scan can evict exactly what comes next

The final controls scan A, B, C and D three times. With three slots, every one of the twelve accesses misses. After the first pass, the order is [B, C, D]. The next A evicts B; the next B then evicts C; the next C evicts D; the next D evicts A. The same pattern repeats.

With four slots, the first four accesses miss and the remaining eight hit. The extra slot crosses this workload’s four-entry working-set boundary. That exact result does not mean a one-slot increase generally produces such an improvement. A trace with a much larger cold scan or changing key population can behave differently.

View full-size image ↗

OSTEP’s looping-sequential example discusses the same structural failure of recency when a cycle is larger than the cache. Our twelve-request calculation uses a separate small trace. Admission policies that refuse one-time entries, or policies that also consider frequency, can preserve useful entries under some scans. They add state and tradeoffs; they are not universal replacements justified by this one counterexample.

Decide what the capacity and the key actually mean

Three entries do not mean three equal amounts of memory. One profile might retain a tiny string while another retains a large object graph. This implementation limits entry count, not total bytes, loader allocations or references held by callers after eviction. A byte-budget cache needs a size definition and rules for oversized entries.

Returned values are not copied. If a caller changes a cached mutable object, later hits observe that same object. Choosing immutable values, copying on return or documenting shared mutation changes the application contract. Recency ordering does not solve ownership of the stored value.

The key must also include every input that determines the reusable result. If two users can receive different profile representations under the same identifier, a key that omits the relevant context can return the wrong value despite perfect LRU bookkeeping. Case folding or trimming keys likewise requires a deliberate identity rule; the example performs neither.

LRU also provides no freshness deadline. A frequently read entry can stay resident indefinitely even if its source changes. Expiration and invalidation require separate decisions. Eviction answers which resident entry to remove under pressure, while freshness answers whether a stored answer is still valid to serve.

As an exercise, remove move_to_end from the hit path and trace the first five accesses again. The faulty implementation evicts A instead of B at D. Then add empty-string keys, false-like values and loader failures to a direct list-based reference model. Compare the order after every successful access, not just the final hit count. A small trace that identifies the first wrong eviction is usually more useful than a larger unexplained percentage.