A trip planner caches each route-distance result by its pair of stops - why does that cache never go stale?
answer
- same arguments, same answer, forever
- invalidation exists to catch drift
- no drift, nothing to invalidate
- hidden inputs are unlisted key parts
- eviction costs time, never correctness
basics
~20 sA pure lookup returns the same distance for the same pair of stops every time, so a stored result can never disagree with a fresh call. Invalidation exists to catch drift between cache and source; purity removes the drift.
solid answer
~50 sBecause the lookup is pure: for one pair of stops it returns the same distance every time, and it reads nothing that can move underneath it. A cache goes stale when the stored answer and a recomputed answer disagree, and for a pure function they cannot - so there is no change event to subscribe to, no time-to-live to pick, no invalidation code at all. Keeping an entry can only save work and dropping it can only cost work; neither can change a result, which turns cache sizing into a performance decision instead of a correctness one. The catch is the word pure. If the distance quietly depends on live congestion or the current time, those are hidden inputs the key `(from, to)` never mentions, and the cache is not safe - only lucky until conditions move.
code
pseudocode · 6 linesfunction distance(from, to)
return path_cost(from, to) // depends on its two arguments only
function distance_now(from, to)
return path_cost(from, to) * current_congestion()
// current_congestion() is a third input the key never mentionsgo deeper
Be able to say the rule in one line: same arguments in, same result out, so a stored result cannot disagree with a fresh one. That is what removes the need to invalidate anything.
Explain the mechanics: invalidation closes a window between stored and recomputed answers, and a function of its arguments alone has no such window. Then name what would reopen it - a clock, a shared table, a random source.
Show that you audit the argument list before trusting a cache. Point at the hidden input in a real lookup, say whether you lift it into the key or cache only the stable part, and state that memory still needs bounding.
Frame it as a standard: caches over pure computations are reviewed for latency and memory, caches over impure ones for correctness. Deciding which functions a codebase keeps pure decides how much cache-invalidation risk the system carries at all.
## What invalidation is actually for A cache stores an answer computed earlier and hands it back instead of recomputing. It is correct only while the stored answer still equals what a fresh computation would produce now. Every piece of invalidation machinery - a time-to-live, a version stamp, a change notification, an eviction triggered by a write - exists to close the window in which those two can disagree. Hard cache bugs are that window, left open. ## Why a pure lookup has no window A function is **pure** when it returns the same result for the same arguments and changes nothing observable. That gives **referential transparency**: a call may be replaced by its result anywhere without changing what the program means. A memo table is exactly that replacement, performed once and then remembered. If the route-distance lookup is a function of `(from, to)` and nothing else, a recomputation is obliged to produce the value already stored. The disagreement window has width zero, so there is nothing to invalidate. Concretely: - there is no staleness event to subscribe to, because nothing the result depends on can move; - there is no time-to-live to choose, because the age of an entry carries no information about its correctness; - an entry may be dropped at any instant - the caller pays one recomputation and sees the same value; - an entry may be kept for the whole life of the process, for the same reason; - adding or removing the cache changes timing and memory use, never output. ## The safe cache and the lucky cache | question | lookup that is pure | lookup with a hidden input | |---|---|---| | can a stored answer go stale | no - the arguments fully determine it | yes - as soon as the hidden input moves | | cost of evicting one entry | one recomputation, same value | one recomputation, and the answer may visibly jump | | cost of a badly chosen time-to-live | some memory, or some extra recomputation | wrong answers for the whole width of the window | | what the key must mention | every argument | every argument, plus every hidden input | The second column is the lucky cache. It passes review because the hidden input happens to sit still while anyone is watching, and it begins lying the moment conditions change. ## Where a hidden input hides A hidden input is anything the result depends on that the argument list does not mention. In a planner the usual suspects are the current time, a live conditions table that another part of the system writes, a random source used to break ties, a configuration value read inside the function, a mutable stop object the caller edits after the call, and state the function accumulates between calls. A distance that folds in live congestion is not a function of two stops - it is a function of two stops **and** the conditions at the moment of the call. Keying it by the two stops answers a question nobody asked. There are two honest repairs: 1. **Lift the hidden input into an argument** so it appears in the key. The function is pure again and the cache is safe by construction; the price is a much larger key space and therefore a lower hit rate. 2. **Do not cache the whole thing.** Cache only the part that really is a function of its arguments - often the stable geometric or graph cost - and apply the moving factor to the cached value afterwards. ## What the property is worth to a team 1. Sizing the cache stops being a correctness review and becomes a latency-and-memory decision, which anyone can revisit without re-testing behaviour. 2. Tests do not have to clear the table between cases: a leftover entry can only hold the same value the test would have computed. 3. Two caches of the same pure lookup, sitting in different layers, cannot disagree with each other, so nobody has to reason about which one wins. ## The caveat worth stating out loud "No invalidation" is a claim about the function's results, not about memory: an unbounded table over an unbounded key space is still a leak, and bounding it is a separate decision. It also assumes the computation itself is fixed. A memo held inside the process dies with the process, so a code change that redefines how distance is computed takes the table with it - but a cache that outlives the process must mention the version of the computation in its key as well, or it will happily keep serving answers from the old definition.
- What could make that same route-distance cache unsafe without a single line of the cache changing?The lookup gaining a hidden input - live congestion, the current time, a shared table someone else writes. Two calls with the same key can then honestly disagree, and the stored answer is simply wrong. The repair is in the function: make the extra input an argument so it lands in the key, or stop caching the part that moves.
- If entries can be dropped at any moment without changing results, what is the cache's only failure mode?Cost. A miss buys back one full recomputation, so the worst case is the uncached latency; holding too many entries buys memory pressure for everything else in the process. Both are performance failures you can measure, which is why sizing a memo over a pure function is a benchmarking exercise rather than a correctness argument.
A printed multiplication table never needs reprinting, because nothing that decides its entries can change; a printed train timetable does, because the world it describes moves.
saying these in an interview costs you the question
- Claims every cache needs a time-to-live to stay correct.
- Says the cache is safe because entries are short-lived.
- Calls a lookup pure while it reads live congestion each call.
- Thinks evicting an entry can change the answer a caller sees.
- Assumes caching is safe whenever writes are rare.
- Treats an unbounded memo table as free because it never goes stale.