AI-narrated article. Prose is preserved with pronunciation adjustments; code and image cues refer to the written article.
Building an LRU Cache: Eviction Is Not Freshness or Isolation
This is the AI-narrated article. The prose follows the written post; pronunciation is adjusted, and code and images are announced separately.
Build a bounded LRU cache with explicit recency and invalidation, then review the freshness, tenant-key, memory and miss-path guarantees it does not provide.
TL;DR: An LRU cache combines direct lookup with recency ordering, promoting successful reads and writes and evicting the oldest entry when capacity is exceeded. That policy does not provide expiry, byte-level memory limits, authorization or duplicate-load suppression. This article builds a bounded Python implementation with atomic cache operations, an explicit miss result and targeted invalidation. It then demonstrates tenant and revision key separation, explains how hot data can stay stale, and connects eviction decisions to worker-local memory, cold misses and dependency protection. Use the implementation only within its stated key and value contract.
Eviction correctness is only one part of cache correctness
A platform API caches rendered service metadata to reduce dependency calls. The process stays healthy, yet a large tenant displaces everyone else's entries, a frequently read response remains stale, or a cache key accidentally shares tenant-specific content. These failures require different fixes. A correct least-recently-used queue solves only the eviction problem.
Build the cache around an explicit contract: what identifies a response, what makes it stale, how much it can retain, and what happens when it misses. Then choose the data structure. Otherwise a seemingly simple optimization becomes an undocumented source of operational and security behavior.
Combine direct lookup with an ordered eviction queue
An LRU cache keeps one entry per key and promotes successful reads to the most-recent position. A write also promotes its key. When capacity is exceeded, it removes the least-recent entry. A miss leaves recency unchanged.
Conceptually, a hash map locates entries while a doubly linked list maintains order. That avoids scanning all entries to choose an eviction victim. In this Python implementation, OrderedDict provides explicit reordering and removal from the oldest end. A plain insertion-ordered dictionary does not automatically become LRU when you read a value.
Image. Before and after LRU ordering for a hit and an insertion with eviction
The diagram shows logical order, not Python object layout. Reading A moves it behind C; inserting D then removes B. Every arrow represents a policy operation, not elapsed time.
A complete bounded implementation
Use CPython 3.11.3 for the reproducible example, with no third-party packages. The implementation supports trusted, immutable built-in keys such as strings and tuples. Custom objects with re-entrant hashing, equality or destructors are outside this example's contract. Values should be immutable snapshots, because returning a mutable object does not protect later mutations.
Save this as lru_cache_demo.py. The boolean in the return value distinguishes a miss from a cached None. The cache bounds entry count, not resident bytes, and its capacity cannot be changed through its public API.
Code example. Refer to the written article for the complete code.
Run it in a disposable directory containing only the example file:
Code example. Refer to the written article for the complete code.
The Lock API supports the critical sections protecting each cache operation. It does not make the sequence “get, fetch dependency, put” atomic. The diagnostic snapshot copies every key and should not sit on a high-volume request path. Cleanup requires only removing the example copy; it creates no persistent cache or infrastructure.
Decide whether a standard decorator is enough
For a pure synchronous function with hashable arguments, functools.lru_cache is usually a better starting point than maintaining custom eviction code. It exposes cache statistics and clearing, and retains argument/result references until eviction or clearing. Its internal coherence is thread-safe, but simultaneous cold requests can still execute the underlying function more than once.
Use a custom interface when the application needs explicit insertion or targeted invalidation. This example deliberately excludes expiry, load coalescing, persistence and cross-process sharing. A worker-local cache is replicated per process; adding workers also adds cache copies and cold starts.
If duplicate loads are expensive, add a separately designed per-key in-flight registry with bounded lifetime, failure propagation and cancellation policy. Do not solve this by holding the global cache lock across a network call: one slow dependency would block unrelated hits and writes. Coherent eviction and one load per key are separate guarantees.
Reproduce the policy failure: LRU does not expire hot data
Consider a service descriptor cached under ("tenant-a", "service-42"). Its owner updates the upstream document, but repeated reads keep the old value most recent. LRU has no clock or version check, so the old response can remain indefinitely. This is a realistic failure scenario, not a claim about a tested production incident.
Diagnosis starts with the response's source revision, cache key and invalidation path. A high hit ratio can coexist with stale data. Increasing capacity retains more stale entries; changing eviction order does not create a freshness guarantee.
Recovery can use explicit invalidation after a successful update, or immutable versioned keys when callers have a trustworthy current revision. Invalidation can race with an earlier in-flight load that subsequently repopulates old data; coordinate loading or reject an outdated revision when that violates the contract. TTL is another policy, with an acceptable stale interval and clear expiry semantics. Do not let a cached presentation snapshot become the authoritative permission check: enforce current authorization before returning sensitive data.
The following check demonstrates the key boundary and targeted recovery using the same class. Save it as key_contract_check.py alongside the implementation:
Code example. Refer to the written article for the complete code.
Run python key_contract_check.py. This verifies separation for these keys; it is not a proof that your application's identity or authorization model is correct. Include any other response-changing dimensions, such as locale or representation version, in the real key contract.
Budget memory and misses together
Entry count is a useful bound only when value sizes are controlled. A hundred large rendered documents can consume more memory than thousands of short strings. A byte-budget cache needs a defined size estimator, oversized-entry admission rule, update accounting and eviction loop; shallow object size alone misses referenced objects.
LRU also gives no preferential protection to a tenant's working set. A stream of one-time keys can displace reusable entries. Separate bulk-read workloads or introduce an admission policy and tenant budgets when this matters. Record hits, misses, evictions, retained size and dependency load by workload, without exporting sensitive keys as metric labels.
The AWS Builders' Library caching guidance highlights the dependency risk of cold caches and cache outages. Plan the miss path with timeouts and bounded concurrency. A cache that works only while warm has changed the service's reliability assumptions.
Frequently asked questions
Does LRU provide TTL? No. Recency decides eviction; expiry requires its own freshness policy.
Is a thread-safe cache enough to stop a stampede? No. Multiple callers can miss before any puts a result. Coalescing needs a separate per-key loading contract.
Does a tenant-aware key enforce authorization? No. It prevents a particular key collision; the request still needs a current authorization decision.