SD5.3 · LESSON 3 OF 6

Freshness and invalidation

Design a cache key, freshness policy and miss path while calculating load and mean-latency effects.

THE IDEA

Freshness and invalidation

A TTL bounds how long an entry can be reused (cached at 0 with TTL 60, changed at 10: up to 50 seconds of staleness), but it does not give instant consistency. Invalidating on write (deleting the entry) shortens that window, though a read already in flight can still put the old value back. Versioned keys avoid the race by never reusing a key: the new version is a new entry and the old one just ages out.

TTL (s)60source changes at (s)10

entry cached at 0, TTL 60, change at 10: readers can see the old value for 50 s TTL bounds how long, it does not promise instant consistency

Compare the three strategies on a timeline.

Predict first. Does deleting a cache entry before a concurrent old read finishes guarantee it stays fresh?

Chapter context

A cache serves a previously obtained representation instead of repeating work. Its correctness depends on which requests can share a value and how long that value may remain useful. Fast retrieval of the wrong representation is still an error.

TRY IT YOURSELF

Part 1. Do it hands-on

Work out staleness windows by hand, then write TTL logic, versioned keys and the race.

TTL (s)60source changes at (s)10

entry cached at 0, TTL 60, change at 10: readers can see the old value for 50 s TTL bounds how long, it does not promise instant consistency

seconds stale (cached 0, TTL 60, change 10) origin loads after a version bump entries for the profile meanwhile delete-on-write guarantees freshness? (yes/no)

To do: An entry is cached at t = 0 with TTL 60 s. The source changes at t = 10 s and nothing invalidates the entry. For how many seconds can readers see the old value?
To do: With versioned keys (profile:v1 → profile:v2), the first read after the update finds no profile:v2 entry. How many origin loads does it cause?
To do: Until the TTL removes it, profile:v1 is still in the cache. Entries for this profile now?
To do: A writer deletes the cache entry while an old read is still in flight (it already fetched the old value). Does that guarantee the entry stays fresh? Type yes or no

Part 2. Do it in code

stale_window(cached_at, updated_at, ttl): how long (seconds) readers can see the old value when nothing invalidates the entry: 0 if the entry was cached after the update; otherwise cached_at + ttl − updated_at (never negative).
is_fresh(cached_at, now, ttl): now − cached_at < ttl.
versioned_key(resource, version): "resource:vN" for version N.
class VersionedCache with get(resource, version, loader): look up the versioned key; on a miss call loader(resource, version), store and return it. Track self.loads and self.entries (dict).
invalidate_race(events): events from "read_old" (a reader fetches the old value), "write" (the source changes), "delete" (the cache entry is deleted), "fill_old" (the reader stores what it fetched). Return "stale" if the cache ends up holding the old value, "empty" if nothing is cached, "fresh" if it holds the new value (only after a later fill_new).

def stale_window(cached_at, updated_at, ttl):
    pass

def is_fresh(cached_at, now, ttl):
    pass

def versioned_key(resource, version):
    pass

class VersionedCache:
    def __init__(self):
        self.entries = {}
        self.loads = 0

    def get(self, resource, version, loader):
        pass

def invalidate_race(events):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does deleting a cache entry before a concurrent old read finishes guarantee it stays fresh?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

If h is hit probability, t-hit hit-path time and t-miss complete miss-path time:

E[T]=h\,t_{hit}+(1-h)t_{miss},\quad R_{origin}\approx(1-h)R.

The miss time here already includes lookup overhead. Means do not establish tail latency, and background refresh can add origin traffic.

Worked example

At 90% hits, 2-ms hit paths and 50-ms complete miss paths, mean latency is 0.9×2+0.1×50=6.8 ms. For 1000 requests/s, nominal origin demand is 100 requests/s. During a complete cache outage, it could become 1000 requests/s rather than remaining at the normal miss rate.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
hit=.9
assert isclose(hit*2+(1-hit)*50,6.8)
assert isclose((1-hit)*1000,100)
assert 1000/100 == 10

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A hit ratio is not a correctness guarantee. Mean latency does not reveal p95. Shared caching requires a safe identity and privacy policy; TTL does not replace authorization.