Week 7: Cache Invalidation, Eviction & Content Delivery

1. Cache Eviction Policies: LRU, LFU & TTL

A cache has bounded memory, so once it's full, adding a new entry means removing an existing one — an eviction policy decides which one. The three policies that come up constantly in interviews each make a different bet about what "likely to be needed again" means.

LRU (Least Recently Used):
  Evict the entry that hasn't been accessed for the longest time.
  Bet: recent access predicts near-future access (temporal locality).
  Cheap to reason about; the default policy in most caches
  (e.g. Redis's allkeys-lru).

LFU (Least Frequently Used):
  Evict the entry with the fewest total accesses.
  Bet: overall popularity predicts future access better than
  recency alone -- protects a consistently hot item from being
  evicted by a short burst of one-off requests.
  Costlier to track (needs a running access count per key) and
  can let old, no-longer-popular items linger ("aging" is needed
  to let their counts decay over time).

TTL (Time To Live):
  Every entry expires automatically after a fixed duration,
  regardless of access pattern.
  Not a competitor to LRU/LFU -- it's usually layered on top of
  one of them, bounding how stale any entry can ever get.

A classic LRU implementation combines a hash map (for O(1) key lookup) with a doubly linked list ordered by recency (for O(1) move-to-front on access and O(1) eviction from the tail) — worth knowing conceptually even outside a coding-specific interview, since "how would you implement that efficiently?" is a common follow-up.

2. Cache Invalidation: The Hard Problem

There's an old programmer's joke that there are only two hard problems in computer science: cache invalidation, naming things, and off-by-one errors. It's a joke because it's true — invalidation is hard specifically because it requires the cache to find out about a change it didn't cause, fast enough that nobody reads stale data, without coordinating so tightly that the cache stops helping performance at all.

Three strategies handle this, usually layered together rather than used alone:

TTL-based: entries expire automatically after N seconds.
  + Simple, needs no coordination with writers
  - Guarantees a staleness window up to N seconds long, even
    when nothing actually changed during that window

Write-driven (explicit): the write path deletes (or updates)
the corresponding cache key as part of the write, as in Week
6's cache-aside pattern.
  + Tight staleness window -- invalidation happens right when
    the underlying data changes
  - Only works if every writer goes through the same code path;
    a direct DB write that bypasses the app misses the cache
    entirely and leaves it stale indefinitely

Event-driven: a write publishes a change event (via a message
queue or a database change-data-capture stream, Week 8) that
one or more caches subscribe to and invalidate on.
  + Works across multiple caches/services without every writer
    needing direct knowledge of every cache
  - Adds infrastructure and a small propagation delay

The trickiest failure mode isn't the staleness window itself, it's a race between a write and a concurrent read repopulating the cache:

t0: Reader A misses cache, starts reading OLD value from DB
t1: Writer updates DB to NEW value, deletes cache key
t2: Reader A finishes its DB read (still holds OLD value)
t3: Reader A writes OLD value into the cache
  -> cache now holds OLD value indefinitely, even though the
     DB already has NEW -- until the next write or TTL expiry

This race exists whether invalidation deletes or updates the
cache key; deleting doesn't eliminate it, but it does avoid a
second, worse race where two concurrent writers' cache-updates
land out of order and leave a wrong value cached with no
further write ever coming to correct it.

This is why real systems layer defenses rather than relying on any single mechanism: a short TTL as a backstop bounds how long any missed invalidation or lost race can persist, versioned cache keys (embedding a version number or timestamp in the key itself) let a reader detect it fetched a value older than the current write, and keeping the write-then-invalidate window as short as possible reduces how often the race above is even triggered.

3. Thundering Herd & Stampede Protection

Week 3 named thundering herd as a scalability failure mode; caching is where it shows up most concretely. When a popular ("hot") key expires or is invalidated, every concurrent request for that key misses the cache at once — and without protection, all of them independently query the database simultaneously, turning one expiring key into a sudden traffic spike the database wasn't sized for. This gets worse when many unrelated keys share the same TTL and expire in the same instant (a "cache stampede" across the whole cache, not just one key).

Without protection:
  1,000 concurrent requests for hot_key, cache just expired
  -> all 1,000 miss -> all 1,000 hit the database at once

Request coalescing ("singleflight" / mutex-per-key):
  function get(key):
      value = cache.get(key)
      if value is not null: return value

      if not lock.tryAcquire(key):        # someone's already
          wait_briefly()                   # fetching this key
          return cache.get(key)            # then reuse their result

      value = db.query(key)
      cache.set(key, value, ttl=300)
      lock.release(key)
      return value
  -> only ONE request reaches the database; the other 999
     wait briefly and reuse its result

Other common mitigations, often combined: jittered TTLs — adding a small random offset to each entry's expiration so a batch of keys set at the same time doesn't all expire in the same instant; stale-while-revalidate — serving the slightly-stale cached value immediately while asynchronously refreshing it in the background, so no request ever has to wait on a slow database read; and probabilistic early expiration — occasionally refreshing a hot key slightly before its TTL actually expires, spreading refreshes out instead of letting them all cluster at the expiry boundary.

4. CDNs: Caching at the Edge

A CDN (Content Delivery Network) is a globally distributed network of cache servers ("edge nodes" or "points of presence") positioned physically close to end users. It applies the exact same ideas as an application cache — hits, misses, eviction, TTLs, invalidation — but at a different point in the request path: instead of sitting between the app server and the database, it sits between the client and the origin server entirely, sometimes serving a request without the origin being involved at all.

[Client] --> [Nearest CDN Edge Node]
                    |
              (hit) returns immediately -- origin never touched
                    |
              (miss) --> [Origin: LB -> App Servers -> App Cache -> DB]
                          edge node caches the response, then
                          serves future nearby requests from itself

The value is almost entirely about Week 1's latency numbers: a round trip to a different continent can cost 100–150 ms, while a round trip to a nearby edge node costs a few milliseconds — for a user far from your origin data center, the CDN is often a bigger latency win than anything happening inside your architecture.

Static content (images, videos, JS/CSS bundles, anything identical for every user) is the easy case — it's essentially cache-aside at the edge, governed by Cache-Control headers the origin sets to tell the CDN how long a response can be reused. Dynamic content (a personalized feed, an API response scoped to one logged-in user) is much harder to cache at the edge, because caching it per-user at every edge location approaches caching almost nothing at all. Common approaches for dynamic content: cache only the pieces that are genuinely public and shared across users (a product price, not a personalized recommendation), use very short TTLs so staleness is bounded to seconds, or push logic to the edge itself (edge compute/serverless functions) so some personalization can happen without a full round trip to the origin.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.