Caching — Cache-Aside, Write-Through, TTLs, Invalidation

Why this session exists

A cache buys less repeated work by keeping another copy of data. That copy has a key, a freshness policy, a capacity limit and a failure mode. The interesting question is not “can Redis return this quickly?” but “which answer may this caller safely reuse, and what happens when the copy is absent or wrong?” This lesson implements cache-aside, negative caching and coordinated fills, explains Redis lease ownership, and works through invalidation races instead of promising that a TTL makes every cache correct.

Prerequisites

Bring key/value operations, request/response basics, a database write boundary and the distinction between process-local synchronization and distributed coordination. Redis reference commands are not executed against a service here. The bounded lab uses Python dictionaries and a logical clock; no shared database is flushed, no container is provisioned, and no load generator is used.

Intuition: the librarian's photocopies

A librarian keeps copies of frequently requested pages at a desk. A desk hit avoids a trip to the shelves; a miss still needs the authoritative book. The copy can become old, the desk can fill, and a crowd arriving at once can cause many duplicate trips. Those are consistency, eviction and stampede problems, respectively.

Suppose a database lookup takes 200 ms and a cache lookup 2 ms in a hypothetical workload. At a 90% hit rate, with serial cache-then-database misses and negligible fill cost, expected lookup time is 2 + 0.1 * 200 = 22 ms, not 2 ms. This is arithmetic under assumptions, not a measured 100× speedup or proof about p99. A cache can also add latency when hit rate is low.

The familiar invalidation/naming aphorism is a reminder, not evidence that correctness is impossible. Name the authoritative state, derive the dependency/key mapping, and specify tolerated staleness before choosing machinery.

Vocabulary and historical context

CPU caches, Memcached and Redis share locality as a motivation but have very different coherence/durability contracts. The 2013 first-party paper Scaling Memcache at Facebook describes leases for stale sets and thundering herds plus a gutter pool for failure isolation. Redis documentation describes memory eviction and ownership-safe lock release. These sources support particular mechanisms; they do not establish universal adoption percentages, fixed latency figures or automatic two-tier coherence.

Three read/write patterns

Cache-aside: the application reads cache, reads the source on a miss and fills the cache. After an authoritative write it invalidates or updates affected keys. The app owns both paths and must handle partial failure and stale fills. Cache outage fallback is safe only if the origin and admission controls can support it.

Write-through: writes pass through a component that synchronously updates the backing store under a defined success contract. It can keep frequently read data warm at the cost of write latency and a dependency on that component. It does not inherently make every reader strongly consistent: bypass writers, eviction, replicas and dual-write failure still matter. Reads can miss after eviction even for previously written values. For a cart/session workload, require durable acknowledgement and specify behavior if cache update fails after the database commits.

Write-back/write-behind: acknowledge to a buffer/cache, then flush later. This can batch work but acknowledged updates can be lost if the buffering/durability contract is inadequate. AOF alone is not a universal zero-loss guarantee; fsync policy, replication, failover and replay idempotency matter. Counters/telemetry may tolerate losses that balances or permissions cannot. Decide from correctness requirements, not “fastest is best.”

Invalidation is an ordering problem

TTL expires an entry after insertion. It does not tell you how old the source snapshot was before insertion. A ten-minute TTL placed on a nine-minute-old replica read may already serve older data than intended. Repeated stale refills can extend wrong observations. Measure source/version age separately from cache residence.

Work this interleaving:

1. Reader R misses and reads source version 1.
2. Writer W commits version 2 and deletes the cache key.
3. R finishes late and stores version 1 after that delete.
4. Another reader hits version 1 although W already completed.

Deleting before the database commit is worse: a reader may immediately refill from the old database state. Deleting after commit is useful but does not eliminate the in-flight stale-fill race. “Double delete later” is not a proof unless timing and failure assumptions are explicit.

Five invalidation strategies and their failure boundaries

• TTL-only: simple residence expiry, appropriate when the end-to-end source-age bound is acceptable. It is not sufficient for immediate permission revocation.
• Write-invalidate: delete after authoritative commit; retry/reconcile invalidation failures. Pair with a stale-fill defense or an explicitly accepted stale window.
• Write-update: compute and install a new representation. Two separate systems do not magically share the database transaction; old writers can overwrite new values unless ordering/version checks are enforced.
• Versioned keys/values: include schema version and, where required, source version. Reject older fills using a generation/fencing rule. The current-version pointer must itself be obtained safely; a stale pointer is still a stale read.
• Events/CDC: carry durable changes from the source commit stream and apply them idempotently/in order or by version. Pub/Sub delivery, lag, disconnection, replay and retention differ by transport. CDC is not automatically “the strongest consistency” or an instantaneous invalidation channel.

A dependency map can be maintained explicitly and some systems provide coherent/transactional caches. It is false that complete invalidation is structurally impossible in every real codebase. The honest boundary is that an ordinary database plus independent cache has no automatic atomic write/read contract.

Tiers, locality, eviction and admission

An in-process cache avoids a network hop but duplicates state and invalidation work per process. A shared Redis cache coordinates more consumers but adds a network/service dependency. A reverse-proxy or CDN cache can avoid invoking the app altogether but must preserve HTTP/privacy semantics. More tiers are not automatically better: each adds capacity, expiry and version interactions.

Hot data must be reused before eviction/expiry to justify a cache. Redis maxmemory and its eviction policy control behavior under pressure; different policies consider different key sets and recency/frequency approximations. A key can disappear before TTL. noeviction changes failure behavior to rejecting certain writes rather than providing unlimited memory. Monitor hit/miss, eviction, memory, fill latency and origin work, not only hit ratio.

A 95% hit rate at 20,000 requests/s still means 1,000 origin requests/s in the simple one-fill-per-miss case. If the origin can safely handle only 300, normal operation already exceeds its capacity. Cold-cache survival can involve admission, degraded/stale responses, staged warm-up and reserved origin capacity; it need not mean provisioning the DB for unrestricted peak demand with no protection.

Stampedes, negative caching and lease ownership

Single-flight coalesces concurrent misses for the same key. Waiters need a deadline and an explicit timeout fallback; “sleep 50 ms then all fetch anyway” does not guarantee one fill. TTL jitter spreads simultaneous expiry across keys but does not solve one hot key's concurrent misses. Choose jitter within the allowed maximum lifetime; adding 20% to a strict freshness ceiling violates that ceiling.

A negative cache stores a typed result meaning “not found under this lookup context,” with a usually shorter lifetime and invalidation on creation. It must not confuse unauthorized, temporarily failed and genuinely absent results. Repeated requests for the same absent key benefit; a million distinct absent IDs still consume work and memory. Bound entries/admission and rate-limit abusive workloads. Bloom filters introduce false positives and update requirements; they are not an authorization check.

For a Redis single-instance lease, SET key token NX PX duration acquires only if absent. Release must compare the stored token and delete atomically. Separate GET then DEL can delete a successor's lease after expiry. Random ownership tokens distinguish holders; expiry still does not stop the old worker from continuing. For strict sink writes, use a sink-enforced fencing/version contract, not just a lock TTL. Do not generalize a single-instance optimization lock into a universal distributed-consistency guarantee.

Hands-on: generation-safe cache-aside with a logical clock

This bounded model separates a fill's lease from its source generation. A writer increments the authoritative generation and clears the cached value; a delayed filler cannot install its old snapshot. Losing ownership rejects the fill too. The model returns wait instead of stampeding, uses typed negative results, and implements a real update/create path.

from dataclasses import dataclass
 
@dataclass
class Entry:
    value: object
    generation: int
    expires: int
 
class CacheModel:
    def __init__(self):
        self.now = 0
        self.source = {42: {'name': 'original'}}
        self.generations = {42: 1}
        self.cache = {}
        self.leases = {}
        self.serial = 0
        self.loads = 0
 
    def write(self, key, value):
        self.source[key] = value
        self.generations[key] = self.generations.get(key, 0) + 1
        self.cache.pop(key, None)
 
    def begin(self, key):
        entry = self.cache.get(key)
        if entry and self.now < entry.expires:
            return ('hit', entry.value)
        lease = self.leases.get(key)
        if lease and self.now < lease[1]:
            return ('wait', None)
        self.serial += 1
        token = self.serial  # deterministic unique model token, not production randomness
        self.leases[key] = (token, self.now + 5)
        self.loads += 1
        ticket = (key, token, self.generations.get(key, 0), self.source.get(key))
        return ('fill', ticket)
 
    def finish(self, ticket):
        key, token, generation, value = ticket
        lease = self.leases.get(key)
        owns = lease is not None and lease[0] == token and self.now < lease[1]
        current = generation == self.generations.get(key, 0)
        if owns and current:
            ttl = 3 if value is None else 10
            self.cache[key] = Entry(value, generation, self.now + ttl)
        if lease is not None and lease[0] == token:
            del self.leases[key]
        return owns and current
 
m = CacheModel()
kind, ticket = m.begin(42)
assert kind == 'fill'
assert all(m.begin(42)[0] == 'wait' for _ in range(20))
assert m.loads == 1 and m.finish(ticket)
assert m.begin(42) == ('hit', {'name': 'original'})
m.now = 10
_, old = m.begin(42)
m.write(42, {'name': 'renamed'})
assert not m.finish(old)  # stale fill rejected after source write
_, fresh = m.begin(42)
assert m.finish(fresh)
assert m.begin(42) == ('hit', {'name': 'renamed'})
_, missing = m.begin(999)
assert m.finish(missing)
assert m.begin(999) == ('hit', None)
m.write(999, {'name': 'created'})
_, created = m.begin(999)
assert m.finish(created)
assert m.begin(999) == ('hit', {'name': 'created'})
m.now += 10
_, expired_owner = m.begin(42)
m.now += 5
_, successor = m.begin(42)
assert not m.finish(expired_owner)
assert m.leases[42][0] == successor[1]
assert m.finish(successor)
assert 2 + (1 - 0.9) * 200 < 22.000001
assert 20000 * (1 - 0.95) > 999.999
print('coalescing, negative cache, stale-fill and lease ownership: PASS')

Anatomy and what the model does not prove

begin chooses hit/wait/fill; finish checks both ownership and generation. write actually changes the source rather than merely printing “imagined update.” Exact expiry uses a strict comparison, so an entry/lease is expired at its boundary. A stale owner cannot delete the successor lease. The independent oracle varies write, finish and expiry ordering, checks multiple absent keys and confirms the logical-clock boundaries.

This model reads authoritative generation atomically with local state. Implementing that across database and Redis requires an actual protocol; simply translating the dictionaries into independent remote GET/SET calls does not preserve the guarantee. It also omits bounded-memory eviction, durability, network failures and fair waiter scheduling. Those are explicit production requirements, not hidden properties of the test.

Redis reference: atomic release and bounded waiters

The following function accepts an already configured Redis client and a source loader. It uses public JSON values and a unique namespace chosen by the caller. It is a stampede-reduction reference, not a proof of linearizable DB/cache consistency. It does not contact Redis at import, flush a database or delete unrelated keys. The API contract uses Redis 7-compatible Lua rather than silently relying on newer DELEX syntax.

# Reference only: requires a configured redis-py client supplied by the caller.
import json
import secrets
import time
 
RELEASE = """
if redis.call('get', KEYS[1]) == ARGV[1] then
  return redis.call('del', KEYS[1])
else return 0 end
"""
 
def redis_cache_aside(client, namespace, entity_id, loader, wait_seconds=0.2):
    if type(namespace) is not str or not namespace:
        raise ValueError('explicit namespace required')
    if type(entity_id) is not int or entity_id < 0:
        raise ValueError('entity ID must be a nonnegative integer')
    key = namespace + ':user:v2:' + str(entity_id)
    lock = key + ':fill'
    deadline = time.monotonic() + wait_seconds
    while True:
        cached = client.get(key)
        if cached is not None:
            item = json.loads(cached)
            return item['value']  # explicit JSON null is a negative result
        token = secrets.token_hex(32)
        if client.set(lock, token, nx=True, px=5000):
            try:
                cached = client.get(key)  # another fill may have completed before acquisition
                if cached is not None:
                    return json.loads(cached)['value']
                value = loader(entity_id)
                ttl = 30 if value is None else 300
                # Strict freshness still requires the source-generation protocol described above.
                client.set(key, json.dumps({'value': value}), ex=ttl)
                return value
            finally:
                client.eval(RELEASE, 1, lock, token)
        if time.monotonic() >= deadline:
            raise TimeoutError('fill wait budget exhausted')
        time.sleep(min(0.01, max(0, deadline - time.monotonic())))

The loader and Redis client's I/O calls need their own time bounds; the waiter budget does not bound either one. This loop checks the budget after a failed acquisition, so a cache hit or successful acquisition can still be returned after the nominal deadline. It is a bounded polling policy when calls terminate, not a strict end-to-end deadline. A loader exceeding the five-second lease can still race a new owner, and its write is not fenced in this reference. That is why the generation-safe model and production version protocol remain separate from safe lease release. The code no longer claims one to three calls for every concurrent schedule or a fixed warm-cache millisecond latency. Testing it against a real disposable Redis and a transactional source belongs to a separately authorized integration run.

Scoped keys and typed absence: an executable collision check

Key construction is part of the protocol, not cosmetic naming. The reference accepts a nonnegative integer entity ID and an explicit namespace. Allowing an arbitrary string such as 42:fill would let one entity's data key collide with entity 42's lease key. The validation now rejects that input (and booleans, which Python otherwise treats as integers). This is a real key-space defect, independent of Redis latency.

Construct the namespace from separate trusted dimensions rather than an ambiguous delimiter join. In this example JSON array encoding distinguishes tenant a:b with scope c from tenant a with scope b:c. Authorization checks must run before choosing the representation; a key helper does not grant access. Use bounded, canonical tenant/scope identifiers and cardinality limits in a real service.

import json
 
def profile_namespace(tenant, scope):
    if any(type(v) is not str or not v for v in (tenant, scope)):
        raise ValueError('explicit tenant and authorization scope required')
    return json.dumps(['profile', tenant, scope], ensure_ascii=True, separators=(',', ':'))
 
assert profile_namespace('a:b', 'c') != profile_namespace('a', 'b:c')
assert profile_namespace('alpha', 'public') != profile_namespace('alpha', 'staff')
assert profile_namespace('alpha', 'public') != profile_namespace('beta', 'public')

The loader contract is equally important: None means an authoritative absence under that namespace's lookup context; a timeout, denied request or temporary dependency error must raise or use a separate typed error, not return None. This particular reference does not represent a legitimate JSON-null entity separately from absence. Its local model also assumes all mutations use write and callers do not mutate returned dictionaries in place. Neither assumption can be inferred from replacing local dictionaries with remote operations.

Worked negative-cache schedule: absent ID 999 is filled at logical time 0 with a three-unit lifetime. A lookup at time 2 is a negative hit; at time 3 it must refill. If creation occurs at time 1 through write, the negative entry is removed immediately and the generation advances; an old fill cannot reinstall the absence. Twenty lookups for that same missing key can share one fill, while twenty different missing IDs need twenty separate admissions unless another policy rejects them. This is why a negative cache is not sufficient abuse protection.

Choosing block, stale-while-revalidate or refresh-ahead

Blocking coalesced fills trade waiter latency for a new source read, but do not make a stale replica authoritative. Set waiter/admission limits. Stale-while-revalidate permits bounded stale serving while a refresh happens; define both a soft freshness threshold and a hard maximum age. RFC 5861 gives HTTP stale directives bounded durations; it does not authorize indefinite stale serving. Proactive refresh can reduce hot-key misses but wastes work on unused keys and needs failure/backoff policy. None is the universal default for balances, permissions and public feeds alike.

Failure analysis and safe cache keys

A stampede is many same-key misses; coalesce and bound waiting. Penetration is repeated absent lookups; negative cache helps repeated keys while admission handles unbounded novelty. An avalanche/cold restart exposes many origin reads; spread fills/expiry and use controlled fallback. A stale set installs an old result after a new write; enforce versions/leases at the correct boundary. A hot key can overload one cache shard; local replicas or deliberately replicated cache keys can distribute reads, but multiply invalidation/version obligations.

The Memcache paper's leases distinguish stale sets from thundering herds, and its gutter pool limits fallout from failed cache servers. Do not claim an ordinary Redis expiry lock reproduces the whole design. TTL jitter is a general mitigation here, not an attributed Instagram festival outage. Typed/scoped key construction addresses the hypothetical cross-user-key bug; no unsupported company anecdote is needed.

A key for a tenant-specific profile may include tenant, entity ID, representation/schema version and authorization scope where representations differ. Validate inputs and encode them unambiguously; using a helper is valuable, but string concatenation itself is not intrinsically unsafe and a helper is not proof of isolation. A short TTL cannot make a missing tenant dimension safe.

Versioned avatar URLs solve one distribution problem only if query/path version dimensions are respected by the cache key and references update. Purging an edge cannot erase copies already held in browsers. Security-sensitive material needs an access/revocation design, not merely a new image URL.

Recall and worked answers

1. Explain cache-aside

Read cache; on miss load the authoritative source and fill under the chosen race policy. On source write invalidate/update relevant representations and handle failed invalidation. The easy-to-miss part is ordering against in-flight fills, not just remembering DEL.

2. When write-through?

A cart service whose writes should synchronously persist and warm its read representation can fit, provided all writes follow the path and success/partial-failure behavior is specified. It does not automatically guarantee read-your-writes across bypasses, stale replicas or all cache tiers.

3. Stampede defense

One owner fills while same-key waiters recheck/wait within a deadline. The offline model produces one load for twenty waiting calls. A short sleep followed by unrestricted origin fallback would defeat that guarantee. Redis ownership-safe release is necessary but does not fence a late loader's data write.

4. Why negative cache?

It avoids repeatedly loading the same absent entity. Use a typed result, short policy lifetime and creation invalidation. Do not cache transient source errors as “missing” or share permission-dependent absence across users. Bound distinct-key admission.

5. Ten million equal expiries

If entries are filled together and later demanded together, synchronized expiry can produce a large miss wave. Expiry itself does not automatically send ten million queries. Stagger warm-up, add bounded jitter and protect origin concurrency. Measure demand and eviction, not only TTL.

6. Invalidate versus update

Invalidate removes a representation so the next authorized fill rebuilds it. Update writes the new representation and must know its dependency/version semantics. Both can race and partially fail across systems; neither is automatically the database transaction.

7. Hot key mitigation

Use local caching or multiple deliberate replicas where freshness allows; distribute reads and update/invalidate every relevant replica. A Redis shard's capacity is finite, but no fixed single-threaded universal throughput number is assumed. More replicas make consistency and memory cost larger.

8. 300 versus 3600 seconds

A longer residence lifetime can increase reuse but permits older observations; a shorter one increases refill demand. Derive the actual source-age bound including replica lag and refill duration. A hard security freshness requirement may require a validated source/policy version rather than either TTL.

9. Old profile picture after a write

Inspect application cache invalidation, stale fills, CDN/browser caching and whether the URL/cache key changed. A versioned content URL plus refreshed references avoids replacing bytes at a supposedly immutable URL. Edge purge alone does not invalidate a browser's existing fresh copy.

10. Schema versioning stretch

Use a new representation namespace such as tenant:alpha:user:42:schema:v2; new readers/writers use v2, old rollout participants can continue v1 until retired. Ensure the source still supports both during rollout and budget the doubled cache footprint. A schema version is distinct from the data generation used to reject stale fills. No blanket company-adoption claim is required.

Explain-out-loud test

Recreate the v1-read/v2-write/stale-fill schedule, distinguish safe lock release from sink fencing, and explain why 95% hits can still overload an origin. State when not to cache: low reuse, excessive write churn, or a freshness/isolation requirement the cache protocol cannot meet.

Connections, sources and execution boundary

CDNs apply these ideas to HTTP; reverse proxies may add another tier; data stores provide origin semantics; SLOs require origin and cache metrics together. Feed and URL-shortener designs should explicitly budget misses, rather than being summarized as a hit-ratio slogan.

The exact offline model and independent scheduling/boundary oracles execute without network. The 2026-10-10 review also executes the Python reference against a finite fake client/logical clock, including the expected late-owner stale-write limitation and rejected key collision. Lua remains source-reviewed, not executed against Redis; no live Redis, deployment or benchmark is claimed. Captures dated 2026-10-08 distinguish mutable Redis docs (which also mention Redis 8.4 DELEX) from the Lua-compatible reference.

• Redis distributed locks and atomic ownership release
• Redis eviction
• Scaling Memcache at Facebook, NSDI 2013
• HTTP caching, RFC 9111
• Bounded stale extensions, RFC 5861

Original resource trail and reading purpose

The original session allocated 90 minutes for intuition, visuals, practice, production reasoning and recall. Treat that as optional pacing, not a completion or diagnostic-speed guarantee. Read the mechanisms here before attempting separately authorized service work.

These original companion destinations are retained for discovery, not used as reviewed claim evidence. Video identity, attribution, duration, playback and external reachability have not been verified in this pass; search links are searches, not specific videos. Historical promotional claims and inconsistent labels are not repeated as facts.

• Original video/search destination 1 — cache pattern overview.
• Original video/search destination 2 — Redis command and data-structure study.
• Original video/search destination 3 — cache implementation orientation.
• Caching Best Practices — TTL/eviction/consistency reading.
• EVCache · Ephemeral Volatile Caching in the Cloud — cache architecture; historical throughput claim not endorsed.
• Scaling Memcache at Facebook — leases and failure isolation; governing paper linked above.

For reviewed propositions use the primary sources above and the source-qualified mechanisms, not the optional resource labels. Previous: S062 load balancers. Next: S064 CDN. The original “S015 HTTP basics” label was incorrect; basic HTTP and Redis command knowledge are conceptual prerequisites, not evidence that S015 teaches HTTP. Hub: The 6-Month Learning Plan. Navigation indicates a route, not acceptance of another lesson.