LRU caches
See how an LRU cache chooses what to remove, compare it with FIFO one request at a time, and separate a cache's size limit from the freshness of its values.
An LRU cache removes the entry that has gone longest without an access when it needs room. Reading an entry refreshes its position. This can help when recent use predicts future use, but it neither guarantees more hits than another policy nor keeps values fresh.
Your desk has room for two folders. When a third arrives, you put away the folder you have not opened for the longest time. That is not necessarily the oldest folder: you might have opened it a moment ago.
A cache is full. The next lookup needs an entry that is not there, so something has to leave. Choosing the oldest entry and choosing the least recently used entry sound similar, but one repeated read makes them disagree. That small difference is enough to change whether the following lookup hits.
What least-recently-used actually orders#
LRU means least recently used. Its ordering follows last access, not insertion time. An entry added an hour ago and read a second ago is more recent than one added a minute ago and untouched since. A hit refreshes the entry’s position. When a miss needs space in a full cache, the least recently accessed entry is removed.
Try it: which key gets evicted?
Read the keys A, B, C, A, D into a small cache. A hit moves a key to the front; a new key pushes the least recently used one out.
Read A to start.
Python’s functools documentation explains the workload assumption: recent calls should be useful predictors of upcoming calls. A repeated set of popular keys can suit that assumption. A scan through a much larger key space can defeat it. The cache still has bookkeeping costs even when it avoids few computations.
Two caches, five requests#
Compare LRU with FIFO, first in, first out. In this FIFO model, the entry inserted first leaves first; reading it again does not change its place. Both models insert the requested entry on a miss. All reads finish before the next begins, and there is no expiry or invalidation. These are deliberately small teaching examples, not measured workloads.
Both caches start empty and hold two equally sized entries. Read A, then B, then A again. Both have one hit. LRU now puts B first for eviction; FIFO still puts A first because it was inserted first.
Before opening the trace: which entry does each cache remove when C arrives? Will the following request for B hit or miss?
Show each step for A → B → A → C → B
| Request | LRU | FIFO |
|---|---|---|
| 1. A | AMiss | AMiss |
| 2. B | A → BMiss | A → BMiss |
| 3. A | B → AHit | A → BHit |
| 4. C | A → CMiss; removed B | B → CMiss; removed A |
| 5. B | C → BMiss; removed A | B → CHit |
LRU finishes with 1 hit and 4 misses; FIFO has 2 hits and 3 misses. The third request refreshed A in LRU, so B left at the fourth request. FIFO did not refresh A and kept B for the last request.
Change one condition: start again with empty caches, but replace the final B with A. Predict the two hit counts before opening the answer.
Check the answer for A → B → A → C → A
LRU now has 2 hits; FIFO has 1 hit. At the fourth request LRU kept A and FIFO removed it. Changing just the last request reverses the result. Neither trace establishes which policy is best for another workload.
A hit count answers only one question: was the value present? It does not include how expensive each missed computation was, how large its result is, or the cost of keeping the order. Our model uses arrays to make every state easy to inspect; it is not a constant-time production implementation. A size of two means two entries, not two bytes.
The model is not a Redis simulator either. Redis documents an approximated LRU policy that samples eviction candidates instead of maintaining this exact order. Use the simple trace to learn the rule, then check the implementation and workload you actually plan to use.
The key is the whole argument list#
Python’s lru_cache stores results under keys built from the function’s positional and keyword arguments. Those arguments must be hashable so that they can serve as keys in a hash table. Passing an unhashable list does not silently skip caching; it fails. A tuple can be suitable when its contents are also hashable and it represents the intended input.
Equivalent intent need not produce identical keys. Python documents that f(a=1, b=2) and f(b=2, a=1) may create separate entries. How much that matters depends on the calls. Inspect cache_info() for hits, misses and entry count rather than assuming a fixed penalty. The cache also keeps references to arguments and results until entries leave or the cache is cleared.
A cache that never forgets#
With maxsize=None, Python disables size-based eviction. If a long-running process continues to receive new keys, the cache can keep growing. A bounded entry count helps, but it is not a fixed memory budget: different keys and results can retain different amounts of memory. These are still reachable objects, so a garbage collector cannot free them while the cache retains them.
Freshness is a separate decision. Suppose a cached room price changes in the database. Reading the old cached price repeatedly refreshes its LRU position; it does not fetch the new price. A smaller cache is not a correctness rule. Define when a changed value invalidates an entry, whether a version belongs in the key, or how much staleness an expiry policy permits.
There is also a distinction between a coherent cache and one execution of the underlying function. Python documents that concurrent callers can both run a computation before its result has been cached. Its thread-safety guarantee does not make a cache an exactly-once mechanism. Caching a function with important side effects therefore needs a different design, not just a larger maxsize.
IF YOU REMEMBER ONE THING
LRU chooses what leaves when space is needed. Your workload decides whether that choice helps, and a separate freshness rule decides whether a retained answer is still valid.
Questions people also ask
4 QUESTIONSWhen is an LRU cache the wrong choice?
When recent use is a poor predictor of future use. A sequential scan through more distinct entries than the cache can hold can evict each entry before it is needed again. Compare policies against representative requests, and include the cost of misses and bookkeeping rather than looking only at hit counts.
Why do two identical-looking calls miss the cache?
Python's lru_cache builds keys from call arguments. Distinct argument patterns may produce separate entries: f(a=1, b=2) and f(b=2, a=1) may cache separately. The effect on hit rate depends on the actual calls; it does not automatically halve it.
Is setting maxsize to None a good idea?
Python then disables size-based eviction, so the cache can grow without bound. It can be reasonable when the possible keys and retained values are known and affordable. It is risky when a long-running process keeps seeing new keys.
Does LRU expire stale data?
No. Last access and freshness are different properties. An entry may be frequently read and still contain an outdated value. Define invalidation, versioning or an expiry policy separately from the eviction rule.