LRU chooses a victim by recency, not by popularity, age, or business importance. When a bounded cache needs space, an exact least-recently-used policy removes the entry whose last qualifying access occurred longest ago. That rule can exploit temporal locality, but it neither guarantees useful hits nor keeps cached data fresh.

Follow the access order

Imagine a three-entry cache, listed from oldest to newest. Loading A, B, and C produces A–B–C. Reading A moves it to the newest position, producing B–C–A. Loading D then evicts B, leaving C–A–D. A plain insertion-ordered dictionary does not automatically move an entry when it is read.

An implementation must define which operations count as touches. A common exact design combines a lookup table with a doubly linked recency order, supporting efficient lookup, promotion, and removal. Maintaining that order also consumes metadata and turns cache hits into state updates. Concurrent implementations must coordinate those changes.

Exact and sampled policies differ

Redis uses approximate LRU: it samples candidates and maintains a pool of good eviction candidates instead of keeping an exact order of every key. The configurable sample count trades additional CPU work for a closer approximation. It does not promise the exact victim sequence of the small model below or universally constant eviction latency.

Candidate eligibility matters too. Redis allkeys-lru can evict any key, while volatile-lru considers keys with expiration metadata. A TTL is not protection against eviction before its deadline. If no eligible expiring keys exist, a volatile policy behaves like noeviction for memory-pressure decisions.

Capacity is not freshness

A limit of three entries is not a limit of three kilobytes. Values, keys, and bookkeeping have different sizes; a count-bounded cache can still retain large objects. Python’s lru_cache retains references to arguments and results until eviction or clearing. Choose a capacity unit that matches the resource you need to control.

Recency also says nothing about whether a source value changed. Frequently reading an obsolete cached answer can keep it resident indefinitely. Expiration, explicit invalidation, and versioned keys address freshness separately. An eviction rule is neither a consistency protocol nor a backup policy.

When it breaks

A scan through one-time entries can displace a useful working set. Cycling through four distinct keys with capacity three can miss on every access, even though those keys are repeatedly requested. Historical popularity does not reserve space under LRU. LFU, admission filtering, or a different capacity may help particular workloads, but no policy follows automatically from “read-heavy.”

Measure hits, misses, evictions, retained bytes, and miss cost over representative intervals. A high hit ratio can hide expensive misses; an eviction counter alone does not reveal whether victims were useful. Reconstruct the access trace before changing policies.

A cache hit must also be safe to reuse. Avoid memoizing side effects or results that require a fresh mutable object on each call. Python’s lru_cache keeps its internal state coherent across threads, but simultaneous misses may still execute the wrapped function more than once. Thread safety is not duplicate-work suppression.

Check it quickly

Save the block as lru_check.py and run python3 lru_check.py with Python 3.10 or newer. It ran with Python 3.14.4. Only the standard library is used: an OrderedDict models exact recency, and the real functools decorator separately verifies memoization. No Redis server, network requests, or filesystem writes are involved.

from collections import OrderedDict
from functools import lru_cache


def access(cache, key, capacity):
    assert capacity > 0
    hit = key in cache
    evicted = None
    if hit:
        cache.move_to_end(key)
    else:
        cache[key] = key.lower()
        if len(cache) > capacity:
            evicted, _ = cache.popitem(last=False)
    return hit, evicted, tuple(cache)


cache = OrderedDict()
observed = [access(cache, key, 3) for key in "ABCAD"]
assert observed == [
    (False, None, ("A",)),
    (False, None, ("A", "B")),
    (False, None, ("A", "B", "C")),
    (True, None, ("B", "C", "A")),
    (False, "B", ("C", "A", "D")),
]
print("ABCAD: touching A makes B the victim; final oldest -> newest:", tuple(cache))

for key in "XYZ":
    access(cache, key, 3)
assert tuple(cache) == ("X", "Y", "Z")
assert access(cache, "A", 3)[0] is False
print("a one-time XYZ scan displaces the old working set")

cache.clear()
hits = sum(access(cache, key, 3)[0] for key in "ABCD" * 3)
assert hits == 0
print("capacity 3, repeated ABCD: 0 hits in 12 accesses")

origin = {"A": 1, "B": 2, "C": 3}
loads = []


@lru_cache(maxsize=2)
def read(key):
    loads.append(key)
    return origin[key]


assert [read(key) for key in "ABACB"] == [1, 2, 1, 3, 2]
assert loads == ["A", "B", "C", "B"]
assert tuple(read.cache_info()) == (1, 4, 2, 2)
print("functools trace:", read.cache_info(), "origin reads:", loads)
origin["B"] = 20
assert read("B") == 2
read.cache_clear()
assert read("B") == 20
assert tuple(read.cache_info()) == (0, 1, 2, 1)
print("a recent cached B stays stale until explicit invalidation")

The first assertion checks every intermediate order, not just the final size: touching A makes B the victim. A subsequent XYZ scan displaces the former working set. The repeated ABCD trace then produces zero hits in twelve accesses with capacity three.

The decorated function reads an in-memory origin mapping. Its ABACB trace records one hit, four misses, and two retained entries; the recorded origin reads identify which calls actually recomputed. Changing the origin’s B from two to twenty leaves the cached result at two until cache_clear runs. Clearing also resets the statistics.

These are deterministic correctness checks, not latency or memory benchmarks. They do not exercise Redis sampling, TTL processing, concurrent misses, byte-based capacity, or a production access distribution. Use the measured trace to understand the policy, then validate the actual cache implementation under its own workload.

Further reading

Sources

  • Python functools, LRU memoization, cache statistics, references, invalidation, and concurrent-call limits, checked 2026-09-08.
  • Python collections, OrderedDict reordering and endpoint removal, checked 2026-09-08.
  • Redis key eviction, approximate LRU, sampling, and candidate eligibility, checked 2026-09-08.