Caching: Strategies, Invalidation and Pitfalls

A cache stores the result of expensive work so repeated requests are cheap. It is the single most effective performance tool and the most common source of subtle bugs: stale data, stampedes, inconsistency and memory blowups. Interviewers want to hear where you would cache, which pattern you would use, how you invalidate, and what happens when the cache fails. This chapter covers each, with runnable models.

1. Where caches live

Closer to the user means faster and cheaper, but harder to invalidate. A good design uses several layers, each for what it does best.

2. Caching patterns

Cache-aside (lazy loading)

The application controls the cache. Read: check the cache; on a miss, read the database, store in the cache, return. Write: update the database, then invalidate (or update) the cache entry. This is the most common pattern.

import time

class CacheAside:
    def __init__(self, db, ttl=60, clock=time.monotonic):
        self.db, self.ttl, self.clock = db, ttl, clock
        self.cache = {}                         # key -> (value, expires_at)
        self.db_reads = 0

    def get(self, key):
        hit = self.cache.get(key)
        if hit and hit[1] > self.clock():
            return hit[0]                       # fresh hit
        self.db_reads += 1                      # miss or expired
        value = self.db[key]
        self.cache[key] = (value, self.clock() + self.ttl)
        return value

    def update(self, key, value):
        self.db[key] = value
        self.cache.pop(key, None)               # invalidate: the next read reloads

now = [0.0]
store = {"price": 100}
c = CacheAside(store, ttl=60, clock=lambda: now[0])
assert c.get("price") == 100 and c.get("price") == 100
assert c.db_reads == 1                           # the second read came from the cache
c.update("price", 120)
assert c.get("price") == 120 and c.db_reads == 2 # invalidated on write, so the new value is visible at once
now[0] = 61
c.get("price")
assert c.db_reads == 3                           # a TTL expiry forces a reload

Read-through and write-through

• Read-through: the cache library loads from the database itself on a miss.
• Write-through: writes go to the cache and the database synchronously. Reads stay consistent, but writes pay both costs, and data never read still fills the cache.
• Write-behind (write-back): writes go to the cache and are flushed to the database asynchronously. Very fast writes, but data can be lost if the cache fails before the flush, and the ordering is trickier.
• Refresh-ahead: proactively refresh entries before they expire.

3. Eviction policies

When memory is full, something must go.

Redis offers several policies (allkeys-lru, volatile-ttl, allkeys-lfu and others) and does approximate LRU by sampling, to avoid the cost of exact tracking.

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity, self.d = capacity, OrderedDict()

    def get(self, k):
        if k not in self.d:
            return None
        self.d.move_to_end(k)                        # mark as most recently used
        return self.d[k]

    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.capacity:
            self.d.popitem(last=False)               # evict the least recently used

lru = LRU(2)
lru.put("a", 1); lru.put("b", 2); lru.get("a"); lru.put("c", 3)
assert lru.get("b") is None and lru.get("a") == 1 and lru.get("c") == 3

4. Invalidation

"There are only two hard things in computer science: cache invalidation and naming things." Choose from:

• TTL only: simple; accept staleness up to the TTL. Pick it from how stale the business can tolerate.
• Explicit invalidation on write: delete or update the key when the source changes. Precise, but every writer must remember to do it, and a crash between the database write and the delete leaves stale data.
• Versioned keys: include a version or hash in the key (product:42:v7); bumping the version makes old entries unreachable, and they age out. Static assets use content hashes for the same reason.
• Event-driven invalidation: publish change events (from the application, or database change data capture) and have cache consumers invalidate.
• Tag-based or group invalidation: associate keys with tags (category:5) and purge by tag.

Stale race (the classic bug): a reader misses, loads the old value from the database, a writer updates the database and invalidates the cache, and then the reader writes the old value into the cache. The cache is now stale until the TTL. Mitigations: short TTLs as a safety net, versioning, deleting the key again shortly after writes ("delayed double delete"), or using compare-and-set with a version.

# the stale-write race, step by step
db = {"x": "old"}
cache = {}

reader_loaded = db["x"]              # 1. a reader misses and reads "old" from the database
db["x"] = "new"                      # 2. a writer updates the database...
cache.pop("x", None)                 #    ...and invalidates the cache (nothing there yet)
cache["x"] = reader_loaded           # 3. the reader finally fills the cache with the old value
assert cache["x"] == "old" and db["x"] == "new"      # the cache is stale until its TTL runs out

5. Cache failure modes

Cache stampede (thundering herd)

A hot key expires; thousands of requests miss at once and all hit the database to rebuild it. Defences:

• Request coalescing / single flight: one request rebuilds, the others wait for its result.
• Locking the rebuild (a short-lived lock key).
• Staggered TTLs with random jitter so many keys do not expire together.
• Stale-while-revalidate: serve the stale value while refreshing in the background.
• Refresh-ahead for known hot keys.

import threading, time

class SingleFlight:
    """Concurrent callers for the same key share one computation."""
    def __init__(self):
        self.lock = threading.Lock()
        self.inflight = {}

    def do(self, key, fn):
        with self.lock:
            entry = self.inflight.get(key)
            leader = entry is None
            if leader:
                entry = self.inflight[key] = {"event": threading.Event(), "value": None}
        if leader:
            try:
                entry["value"] = fn()
            finally:
                with self.lock:
                    del self.inflight[key]
                entry["event"].set()
        else:
            entry["event"].wait()
        return entry["value"]

calls = []
def slow_rebuild():
    calls.append(1)
    time.sleep(0.1)                                   # an expensive database query
    return "fresh"

sf = SingleFlight()
results = []
threads = [threading.Thread(target=lambda: results.append(sf.do("hot-key", slow_rebuild))) for _ in range(20)]
[t.start() for t in threads]; [t.join() for t in threads]
assert results == ["fresh"] * 20
assert len(calls) == 1                                # twenty concurrent misses, one database query

Cache penetration

Requests for keys that do not exist always miss, so every one reaches the database (accidentally or as an attack). Defences: cache negative results (a short-lived "not found" marker), validate keys before querying, and use a Bloom filter in front (a compact probabilistic set with no false negatives: if it says "absent", the key is definitely absent).

import hashlib

class Bloom:
    def __init__(self, size=1 << 16, hashes=4):
        self.size, self.hashes, self.bits = size, hashes, bytearray(size // 8)

    def _positions(self, item):
        for i in range(self.hashes):
            yield int(hashlib.sha256(f"{i}:{item}".encode()).hexdigest(), 16) % self.size

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def might_contain(self, item):
        return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))

bf = Bloom()
for i in range(1000):
    bf.add(f"user-{i}")
assert all(bf.might_contain(f"user-{i}") for i in range(1000))                 # no false negatives, ever
false_positives = sum(bf.might_contain(f"ghost-{i}") for i in range(2000))
assert false_positives < 100                                                    # a few false positives are possible, and acceptable

Cache avalanche

Many keys expire together, or the cache cluster dies, sending a flood to the database. Defences: TTL jitter, replication and failover for the cache, graceful degradation (serve stale or reduced data), rate limiting and circuit breakers in front of the database, and pre-warming after restarts.

Hot keys

One key receives a huge share of traffic and overloads one cache node. Defences: replicate the key across several nodes (suffix it with a random shard number), add a small in-process L1 cache in front of the distributed cache, or use read replicas.

Inconsistency and staleness

The cache and the database can disagree. Decide per data type: financial balances and inventory at checkout need the source of truth; a product description can be minutes stale. Say so explicitly.

6. HTTP caching

• Cache-Control: max-age=N how long a response is fresh; s-maxage for shared caches (CDNs); private (browser only), public, no-cache (must revalidate before reuse), no-store (never store), immutable.
• Validators: ETag and Last-Modified with If-None-Match and If-Modified-Since; a 304 Not Modified reply saves the body.
• stale-while-revalidate and stale-if-error for resilience.
• Vary tells caches which request headers change the response (Accept-Encoding, Accept-Language); an incorrect Vary can serve one user's variant to another.
• Never cache personalised or authenticated responses in a shared cache without keying by user and using private.

7. Designing a cache: a checklist

1. What is expensive? Measure first; cache the real bottleneck.
2. What is the read/write ratio and hit rate? A cache helps most when reads dominate and the working set fits.
3. Key design: include everything that changes the result (user, locale, version, parameters); namespace keys; keep them short.
4. Value design: store compact serialisations; avoid caching huge objects or unbounded lists.
5. TTL and invalidation: choose staleness tolerance; add jitter.
6. Failure behaviour: what if the cache is down, slow or cold? The system must still work (with a timeout on cache calls and a fallback to the source), without a stampede.
7. Capacity and eviction: memory sizing, policy, monitoring of evictions.
8. Observability: hit ratio, latency, evictions, memory, key counts, per-endpoint cache effectiveness.
9. Security: do not cache secrets or other users' data under shared keys.

def hit_ratio(hits, misses):
    return hits / (hits + misses)

def effective_latency(hit, cache_ms, db_ms):
    return hit * cache_ms + (1 - hit) * (cache_ms + db_ms)        # a miss pays for the cache lookup and the database read

assert abs(hit_ratio(950, 50) - 0.95) < 1e-12
assert abs(effective_latency(0.95, 1, 50) - 3.5) < 1e-9           # 95 % hits turns a 50 ms query into about 3.5 ms on average
assert effective_latency(0.5, 1, 50) > effective_latency(0.95, 1, 50) * 5     # the hit rate matters enormously

8. Redis in interviews

Redis is an in-memory data-structure server: strings, hashes, lists, sets, sorted sets, bitmaps, HyperLogLog, streams, with TTLs, atomic operations, Lua scripts and pub/sub. Typical uses: caching, sessions, rate limiting (atomic counters or sliding windows), leaderboards (sorted sets), distributed locks (with care), queues and streams, counters and unique-visitor estimates. It is single-threaded for command execution, so each command is atomic. Persistence options (RDB snapshots, AOF logs) trade durability against speed. Scale with replication and Redis Cluster (hash-slot sharding).

Distributed locks are tricky: use a unique token, an expiry, and release only if you still hold the token; understand that a long pause can let the lock expire while the holder still believes it is held, so protect critical resources with fencing tokens where correctness depends on it.

9. Common mistakes

• Caching before measuring, or caching something cheap.
• No invalidation story, only hope.
• Same TTL for everything, causing synchronised expiry.
• Caching errors or empty results forever.
• Letting the cache become the source of truth without durability.
• Unbounded caches with no eviction or size limit, leading to memory exhaustion.
• Missing keys for user, locale or version, leaking one user's data to another.
• Not handling cache outages (no timeout, no fallback, a stampede on recovery).
• Treating a high hit rate as success while the misses are the slow, important requests.

10. Practice questions

1. Explain cache-aside, write-through and write-behind, with a use case for each.
2. How do you prevent a cache stampede on a hot key?
3. Describe the stale-write race in cache-aside and how to mitigate it.
4. What is cache penetration and how does a Bloom filter help?
5. LRU versus LFU: when would each be better? Implement LRU.
6. How do you decide TTL values? How do you invalidate on writes?
7. What happens to your system if Redis goes down?
8. Which HTTP headers control caching in browsers and CDNs, and what does Vary do?