Caching

Why Caching Matters

A cache is a fast data store that sits between a requester and a slower data source. Instead of fetching the same data from a database or API on every request, you store the result once and serve it repeatedly from memory. The speed difference between storage levels is not incremental: it is orders of magnitude.

The memory hierarchy

The principle at the heart of caching is temporal locality: data accessed recently is likely to be accessed again soon. Most real workloads follow the Pareto principle, where 20% of the data handles 80% of the reads. A small cache covering the hot fraction of your data dramatically reduces load on your database.

Cache layers in a web system

A request can be served by any of several cache layers before it reaches your database. Each layer a request avoids saves both latency and infrastructure cost.

Eviction Policies

When a cache is full and a new item needs to be stored, something must be removed. The eviction policy determines which entry gets dropped. The choice significantly affects hit rate for the same cache size.

Use the explorer below to step through a 20-request sequence with a 5-slot cache. Switch between LRU, LFU, and FIFO to see how eviction decisions differ and how the hit rate changes at the end of the sequence.

# On access: move to front of list
# On eviction: remove from tail
cache = OrderedDict()
cache.move_to_end(key)      # hit
cache.popitem(last=False)   # evict

# Track access counts
# On eviction: find min-frequency key
counts = Counter()
counts[key] += 1        # hit
evict = min(counts, key=lambda k: (counts[k], last_used[k]))

# Queue: entries leave in insertion order
from collections import deque
queue = deque()
queue.append(key)       # insert
queue.popleft()         # evict oldest

Cache Invalidation

There is a famous quip in computer science: there are only two hard problems, cache invalidation and naming things. The reason cache invalidation is hard is not technical: it is a consistency problem. Your cache and your database can disagree, and every user who hits a stale cache entry gets wrong data silently.

Serving stale data is worse than a cache miss in most contexts. A miss is slow. Stale data is incorrect. Design your invalidation strategy before you design cache population, not after.

redis.set("user:42", json, ex=300)  # expires in 5 min

# On user update:
db.update(user)
redis.delete(f"user:{user.id}")
# or: publish("cache.invalidate", key)

# Cache key includes schema version
key = f"user:{user_id}:v{SCHEMA_VERSION}"
# Deploy with new SCHEMA_VERSION to bust all keys

Choosing a TTL

TTL is a correctness budget. Set it to the maximum staleness your users can tolerate for each resource. There is no universal answer: a product price and a static asset have completely different tolerances.

The cache stampede problem

When a popular cache key expires, dozens or hundreds of requests can simultaneously see a miss and all rush to the database to repopulate it. The database receives a spike of identical queries at once.

# XFetch algorithm
if now - computed_at > ttl - beta * log(rand()):
    recompute_and_cache()

if not cache.get(key):
    with cache.lock(key, timeout=2):
        if not cache.get(key):  # re-check
            cache.set(key, db.fetch())

Write Strategies

Eviction policies decide what leaves the cache. Write strategies decide how the cache is populated and kept in sync with the database. They are separate decisions that combine independently.

The central tension: you want fast reads (cache hits) but also fresh data (no stale reads) and safe writes (no data loss). No strategy gives you all three without trade-offs.