Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

LRU caches: couple keyed lookup to recency order

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A least-recently-used cache evicts the entry whose most recent access is oldest. It needs both keyed lookup and an order that changes on every hit. A hash map joined to a doubly linked list gives expected O(1) lookup, move, insertion, and eviction when each map value points directly to its list node. Python's OrderedDict packages that ordering behavior. Recency is a policy choice, not a measure of entry value or size. Reads that update recency are writes to shared cache state, so concurrency rules must cover them too.

Operational case

An in-process route cache holds only two depot summaries. North and East are loaded. A request for North makes it newest; loading West then evicts East. The result depends on access order even when the stored summaries never change. A process restart clears this cache, and the origin remains authoritative. If a summary changes upstream, the cache needs expiry or explicit invalidation; LRU alone cannot prove freshness. The two-entry capacity is deliberately small so the eviction is visible.

Working Python program

python
from collections import OrderedDict

route_cache = OrderedDict()
capacity = 2

def read_or_load(depot, summary):
    if depot in route_cache:
        route_cache.move_to_end(depot)
        return route_cache[depot]
    route_cache[depot] = summary
    if len(route_cache) > capacity:
        route_cache.popitem(last=False)
    return summary

read_or_load("North", 47)
read_or_load("East", 52)
read_or_load("North", 47)
read_or_load("West", 61)
print(list(route_cache.items()))

Output

Output
[('North', 47), ('West', 61)]

Time, space, and tradeoff

For c cached keys, storage is O(c). OrderedDict endpoint and key operations are O(1) on average under ordinary hashing assumptions, while the oldest-key eviction is an endpoint operation. This demonstration passes a known summary to the loader; a production loader would call the origin only on a miss and would not trust a caller-supplied replacement for an existing key. Capacity counts entries rather than bytes, so a real cache with uneven object sizes may require weighted eviction. Define behavior for zero capacity before accepting requests.

Common Mistakes

  • Do not treat a hit as read-only when it changes recency.
  • Do not assume LRU invalidates stale source data.
  • Do not evict by insertion age when the contract says last access.

Connected lessons

LFU caches: evict by frequency, then recency adds a related lifecycle choice.

CLOCK caches: revisit pages through reference bits extends the retention comparison.

Segmented LRU: separate probation from protected reuse extends the retention comparison.

Resident LRU-K: Evict by the Kth Recent Reference extends this operation comparison.

data structures
range-query-structures
Storage details