Caching

A cache keeps a reusable copy of a result so a later request can avoid fetching or computing it again. Its value comes from work avoided: database queries, remote calls, serialization, or repeated computation. The authoritative source still decides what the data means. Losing a disposable cache should lose an optimization; the resulting load can nevertheless overwhelm a source sized for mostly cached traffic.

Caching introduces three decisions: which requests may share a value, how old that value may be, and how much capacity to spend keeping it. A fast wrong answer is still wrong. Product descriptions may tolerate seconds of staleness; permission revocations and inventory reservations need a stronger correctness path.

A hit saves work when the copy is usable

An application can cache objects inside one process or use a shared cache service. A local copy avoids a network round trip but consumes each process's memory and may disagree with other instances. A shared cache adds a network dependency and centralizes copies. Database buffer caches and CPU caches operate at other layers. HTTP freshness and CDN cache keys are covered in DNS and CDN; here the application owns its cached values.

With cache-aside, the application checks the cache, loads from the source on a miss, then fills the cache. Read-through moves that loading responsibility into a cache-facing abstraction. Write-through updates through the caching path, but needs an explicit answer for partial failure between source and cache. Write-behind acknowledges before the source write completes, introducing durability and ordering obligations. A cache name alone establishes no atomicity across two systems.

Download the complete runnable fixture. It requires Python 3.11+ and its standard library, with no services or packages. Extract it and run:

python3 cache_lab.py
python3 test_cache_lab.py

This is an application-cache teaching model, with a manually advanced clock and exact eviction. Its asyncio example does run real tasks, but does not implement a distributed cache. The excerpts below belong to four experiments in the fixture.

The first sends ten identical reads through cache-aside, within a 30-second TTL. MISSING is a distinct sentinel, so a cached None can represent an absent source record:

clock, source = Clock(), {"product:7": "blue"}
cache, origin_calls = Cache(clock), 0
for _ in range(10):
    value = cache.get("product:7")
    if value is MISSING:
        origin_calls += 1
        value = source["product:7"]
        cache.put("product:7", value, ttl=30, payload_bytes=4)
    assert value == "blue"
assert (cache.stats["hits"], origin_calls) == (9, 1)

These are observed operation counts, not a latency benchmark. If a cache lookup costs more than a cheap computation and reuse is rare, caching can increase latency. Measure hit ratio together with source calls, load duration, errors, and eviction rate. Separate fresh hits, accepted stale responses, and negative hits.

A key must encode every input that changes the answer: tenant, record, locale, representation version, and relevant query parameters. A tenant-qualified key prevents accidental sharing only when authorization is also enforced. Cache access must not bypass permission checks.

Invalidation can lose to an older reader

A common write path commits the source change and then invalidates the cached copy. Invalidating before committing allows another reader to refill from the old source. Committing first avoids that ordering mistake, but still permits an older in-flight reader to refill afterward.

The second experiment forces that schedule. A reader captures the old value, a writer commits and invalidates, then the reader finishes its fill:

source, cache, generation = {"p": "old"}, {}, {"p": 0}
token, old_value = generation["p"], source["p"]

source["p"] = "new"       # writer commits
generation["p"] += 1
cache.pop("p", None)       # invalidation sees an empty cache

cache["p"] = old_value     # delayed reader resurrects old data
assert cache["p"] == "old" and source["p"] == "new"

The fixture's guarded variant accepts that last fill only if generation["p"] == token. Its next request reloads new. The comparison and fill must be atomic relative to invalidation, and every relevant writer must participate. A separate GET followed by SET across a network would recreate the race. The model retains generation state outside the evictable value; production designs also need safe lifetime and reclamation rules for that state.

This guard prevents this stale fill, not every stale response: the reader already captured old. Nor does it solve a source commit followed by failed invalidation. Depending on requirements, use coordinated versioning, durable invalidation delivery, or bypass the cache for reads that require authoritative state. Versioned keys help only if readers discover the correct version reliably.

A hard TTL limits a copy's residence since insertion, not its age relative to the latest committed source value. A delayed fill can start a fresh TTL on an already stale value. Sliding expiry can keep a frequently read stale copy alive indefinitely. State the freshness contract before choosing a duration.

A missing key needs bounded work

When many callers miss one popular key together, independent loads create a stampede. Single-flight coalesces those callers onto one in-flight load. It needs two bounds: distinct loads in progress and callers waiting for each load. Bounding only one leaves another path to unbounded memory or source traffic.

The third experiment uses one load slot and two follower slots. This is the admission logic from SingleFlight.get; the complete method first rejects calls after shutdown, then checks the cache:

flight = self.pending.get(key)
follower = flight is not None
if follower:
    if flight.followers >= self.max_followers:
        raise Overloaded("followers full")
    flight.followers += 1
else:
    if len(self.pending) >= self.max_loads:
        raise Overloaded("load slots full")
    task = asyncio.create_task(self._load(key, loader, ttl))
    task.add_done_callback(lambda t: None if t.cancelled() else t.exception())
    flight = self.pending[key] = Flight(task)
try:
    return await asyncio.wait_for(asyncio.shield(flight.task), caller_timeout)
finally:
    if follower:
        flight.followers -= 1

An event holds the loader open while tests admit three callers for p. A fourth caller for p is rejected, as is a load for another key. Releasing the event returns the same value to all three, after one source call. These checks assert admission and coalescing independently of elapsed speed.

shield lets one caller stop waiting without cancelling everyone's load. The loader has its own deadline and removes its registry entry in finally. Shutdown first closes admission, cancels and awaits owned loads, then clears entries even for tasks cancelled before starting. Later calls, including hits, are rejected. Tests verify both shutdown races, caller timeout, initiating-caller cancellation, shared source errors, retry after failure, and loader timeout. Cancellation requires a cooperative async loader; blocking code or suppressed cancellation can defeat that deadline. See Parallelism and Concurrency for execution lifetime.

This registry coordinates one process. Twenty service instances may still issue twenty loads for the same key. It also does not include the previous experiment's generation guard. All callers sharing a key must agree on the loader and freshness policy. A fleet needs source admission limits even when the cache is unavailable; unlimited fallback turns a cache outage into a database outage.

Expiration spreads demand; eviction spends memory

Expiration removes permission to reuse an old copy. Eviction removes a copy to reclaim capacity, even if still fresh. They solve different problems.

The fourth experiment assigns 1,000 entries a maximum TTL of 60 seconds. Uniform earlier-only jitter spreads their deadlines over 48–60 seconds without extending that maximum:

def jittered_ttl(max_ttl, spread, rng):
    return max_ttl * (1 - spread * rng.random())

rng = random.Random(7)
deadlines = [jittered_ttl(60, 0.2, rng) for _ in range(1000)]
buckets = Counter(int(deadline) for deadline in deadlines)
assert len(buckets) == 12 and max(buckets.values()) == 94
# Without jitter, all 1,000 deadlines occupy the same second.

This is a deadline histogram, not measured source requests/s. Jitter reduces synchronized expiry across different keys, sometimes called a cache avalanche. It does not split demand for one hot key, and it cannot prevent a fleet-wide flush. Coalescing, gradual warming, admission limits, and explicit stale-serving policy address those other paths. A soft refresh deadline can initiate refresh while an older value remains usable until a hard deadline; only use this when the response contract permits stale data.

Negative caching stores an authoritative absence with a short lifetime. The fixture caches None for five seconds and asserts a miss exactly at expiry. A newly created record remains hidden until invalidation or expiration. A source timeout is not proof of absence: the single-flight implementation propagates errors without caching them. Failure backoff or a circuit breaker can control repeated errors without inventing a successful empty result; Queues and Retries develops retry budgets.

For eviction, the fixture fits two entries and accesses a repeatedly, then b most recently, before inserting c. Exact LRU retains b,c; exact LFU retains a,c. LRU reacts to recent use but a scan can displace hot entries. LFU preserves repeated use but needs aging to adapt when popularity changes. This model has no frequency decay; Redis uses sampled approximations and decaying probabilistic LFU counters.

The model charges UTF-8 key bytes plus supplied payload bytes plus an invented 64 bytes per entry. Two one-byte keys with empty payloads exactly fill its 130-byte budget; an oversized entry is rejected. This tests accounting decisions, not Python heap usage. Real budgets include object metadata, allocator fragmentation, client buffers, in-flight loads, and operational headroom; Redis replication/persistence buffers can also sit outside its eviction accounting. Measure representative resident memory and large-value behavior. Use Back-of-the-Envelope Calculations to estimate the working set, then validate against actual traffic and cold-cache failures.