The technique you used to optimise dynamic programming is the same technique running your Redis cluster. Both trade space for time. Both fail the same way.
Most engineers learn these as separate topics. One appears in an algorithms course. One appears in a systems course. They are not separate. The pattern is identical. The scale differs. One difference between the two produces every operational problem in production caching.
This article traces Thread 5 — Caching/Memoization — from a dictionary in a recursive function to a Redis cluster serving millions of requests per second. The tradeoff is AT4 — Precomputation vs On-Demand at every level. The signature failure mode is FM7 — Thundering Herd.
Level 1 — Memoization in dynamic programming
You have a recursive function. It computes the same subproblem more than once. The naive version recomputes from scratch every time. Memoization stores each result the first time it is computed. Every later call returns the stored result.
That is the entire algorithm. Check the dictionary. Return the stored value on hit. Compute, store, and return on miss.
def fib(n: int, memo: dict = {}) -> int:
if n in memo:
return memo[n] # cache hit
if n <= 1:
return n
result = fib(n-1, memo) + fib(n-2, memo)
memo[n] = result # cache fill
return result
The transformation is dramatic. Without memoization, fib(n) runs in O(2ⁿ) time. With memoization, it runs in O(n). The memo table pays memory for compute. This is AT4 in its purest form.
fib(n) is a pure function. The same input always produces the same output. The memo table never needs invalidation. This purity is what makes the algorithm-level cache trivial. Every complication in production caching comes from losing it.
Level 2 — Infrastructure caching against a mutable database
Move the same structure out of process memory. Put it in Redis. Point it at a database instead of a recursive function.
def get_user_profile(user_id: int) -> dict:
cache_key = f"user:{user_id}:profile"
cached = r.get(cache_key)
if cached:
return json.loads(cached) # cache hit
profile = db.query(f"SELECT * FROM users WHERE id={user_id}")
r.setex(cache_key, 300, json.dumps(profile))
return profile
The code is structurally the same as fib_cached. The key is the request. The value is the query result. The check-then-fill pattern is identical.
One property changed. The database is mutable. The user can update their profile at any moment. The cached value can become stale. That single change — mutability of the underlying data — creates the entire engineering discipline of cache invalidation.
Two new mechanisms appear at this level. TTL sets an expiration timestamp on every entry. Explicit invalidation deletes the key when the underlying write happens. TTL is simple and blunt. Explicit invalidation is precise and requires every writer to know every affected key.
Level 3 — The invalidation strategy decision
Four strategies occupy different positions on the consistency-complexity axis.
TTL-based sets an expiration on every write. Staleness is bounded by the TTL. A profile picture with a 300-second TTL can lag reality by five minutes. For an inventory count, that lag is not acceptable.
Event-driven invalidation listens for a change event and deletes the affected key. Staleness collapses to the event pipeline latency. A dropped event leaves stale data indefinitely unless a TTL sits underneath as a safety net.
Cache-aside fills the cache lazily on read miss. The application controls the fill. Writes bypass the cache and rely on TTL or invalidation to clear stale entries.
Write-through updates the cache inline with every database write. No staleness for the written key. Every write path must be routed through the same code. A write that succeeds in the database but fails in the cache leaves the two out of sync.
Production systems layer these. Write-through for high-value keys. Event invalidation for prices and availability. TTL underneath as the guarantee that no bug leaves data stale forever.
Level 4 — The thundering herd
This is FM7. It is the failure mode specific to caching. It has no equivalent at the algorithm level, because the algorithm level has no concurrent readers.
A popular cache entry expires. At the moment of expiry, thousands of requests are in flight for the same key. All see a miss. All hit the database at once. The database was sized for the traffic the cache was absorbing. It cannot handle the full uncached load. It slows down. Cache fills take longer. The overload persists.
The mutex-per-key pattern coordinates the recompute. Only one thread queries the database. Every other thread waits for the result.
def get_or_compute(self, key, compute_fn, ttl):
cached = self._store.get(key)
if cached and time.time() < cached[1]:
return cached[0]
with self._meta_lock:
if key in self._locks:
event = self._locks[key]
should_compute = False
else:
event = threading.Event()
self._locks[key] = event
should_compute = True
if should_compute:
value = compute_fn()
self._store[key] = (value, time.time() + ttl)
event.set()
return value
event.wait()
return self._store[key][0]
Simpler approximations exist. Probabilistic early expiration refreshes the entry slightly before it expires. Staggered TTLs add random jitter so mass expiry does not synchronise across keys. All three treat the same root cause: coordination between the cache tier and the database tier at the moment of miss.
The thundering herd is not a failure of the cache. It is a failure of the assumption that the cache will always be warm. Cold caches, node failures, and mass expiry all violate that assumption. The database must survive the moment when it does.
Level 5 — Capacity and eviction
A memo table grows forever. A production cache has bounded memory. When the cache is full, something is evicted. LRU is the default: evict the entry accessed least recently.
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self._store: OrderedDict = OrderedDict()
def get(self, key):
if key not in self._store:
return None
self._store.move_to_end(key)
return self._store[key]
def set(self, key, value):
if key in self._store:
self._store.move_to_end(key)
self._store[key] = value
if len(self._store) > self.capacity:
self._store.popitem(last=False)
LRU exploits temporal locality. Recently accessed items are likely to be accessed again. This assumption holds for social media profiles and hot product pages. It fails for batch processing, where each item is accessed once and never again. LRU evicts every item exactly as the next arrives. The hit rate collapses to zero.
The pattern generalises. Every cache is a bet on the access distribution. If the bet is right, the hit rate is high and the cache pays for itself. If the bet is wrong, the cache adds latency and memory cost with no benefit.
Where the same idea shows up at the largest scale
Redis stores key-value pairs in memory with optional TTL. It is the dominant infrastructure cache.
Memcached does the same job with fewer features and simpler operations.
CDN edge caches apply the pattern to HTTP responses. The URL is the key. The response body is the value. Cache-Control: max-age=300 is the TTL, expressed at the HTTP layer.
LLM KV cache is memoization at transformer inference. Each generated token depends on the K/V tensors of every prior token. Those tensors are a pure function of the prefix. Caching them turns per-step work from O(N) into O(1) amortised. Every production serving stack keeps this cache in GPU memory with LRU eviction.
The pattern is the same at every scale. What changes is the cost of a cache miss. In dynamic programming, a miss costs microseconds. In a web application, a miss costs a database query. In a CDN, a miss costs a transatlantic round trip. In an LLM, a miss costs a full attention recomputation.
The signal that tells you Thread 5 is running in your system
Your P99 latency is much higher than your P50. Your database receives fewer queries per second than your service serves requests per second. A hidden cache is already doing the work. A cold start, a node failure, or a mass expiry would expose the underlying fragility immediately.
If you can name the cache tier, you can reason about it. If you cannot, the system has one anyway — a page cache, a query planner cache, a JVM code cache, an OS filesystem cache — and it will fail the same way when it goes cold.
The harder question
The chapter this article draws from calls itself the most important chapter in Books 1 and 2. The claim is not about the algorithm. The claim is that every infrastructure component you will study — CDNs, read replicas, materialised views, precomputed feeds — is memoization with different failure modes bolted on. The engineer who understands the memo table understands them all.
Which raises the question the article does not answer. If mutability is the source of every complication, what is the cost of designing a system where the underlying data is never mutated at all? Event sourcing, immutable infrastructure, and content-addressed storage all take this bet. What do they trade to make it?
The full framework treatment — compression blocks, three-level exercises, and the complete AT/FM mapping — is in Book 2: Algorithm Engineering, Chapter 11 (Memoization Is Caching). Free chapter available at computingseries.com/books/book2.