6 — Caching

A cache keeps a copy of data somewhere faster than its source. Caches are everywhere: in CPUs, browsers, CDNs, application memory, and dedicated systems like Redis and Memcached. They’re among the most effective tools in system design, and among the most common sources of subtle bugs.

Why caches work

Caches rely on an uneven pattern in real workloads: a small share of data gets most of the requests. Web traffic often follows something like a Zipf distribution, where the second most popular item gets half the traffic of the first, the third a third, and so on.

A simulation with one million items, 600,000 Zipf-distributed requests and an LRU cache:

Caching one item in a thousand served 40% of requests. Going from 10% to 20% barely helped in this run, partly because there weren’t enough requests to fill the larger caches. The early items do most of the work.

Hit rate has an outsized effect on the database behind the cache. At 10,000 requests a second:

A drop from 99% to 95% looks minor, but it’s five times the database load. This matters when a cache restarts or a deployment changes key formats.

Where caches live

In-process caches are the fastest, but each server has its own copy, so they can disagree. A distributed cache is shared, but each read needs a network call. Large systems often use both.

Reading and writing

Cache-aside is the most common. In code:

def get_user(user_id):
    user = cache.get(f"user:{user_id}")
    if user is None:
        user = db.fetch_user(user_id)
        cache.set(f"user:{user_id}", user, ttl=300)
    return user

Eviction

Cache memory is limited, so something has to go when it’s full.

Redis offers approximate LRU and LFU, sampling a few keys rather than tracking everything, to save memory. Chapter 17 builds an exact LRU.

Invalidation

There’s a well-known saying that cache invalidation is one of the two hard things in computer science. The problem is keeping the copy consistent with the source.

TTL is the simplest approach: data expires after a set time. The time chosen is a direct trade-off between freshness and load.

Delete on write removes the entry when the data changes, and the next read repopulates it. Deleting is usually safer than updating, because of a race.

The stale-set race

Cache-aside can go wrong in these steps:

1. Reader A misses the cache and reads value 1 from the database.
2. Writer B updates the database to 2 and deletes the cache entry.
3. Reader A writes its stale value 1 into the cache.

The cache now holds an old value until it expires. Facebook’s memcache paper describes this exact problem, and fixes it with leases. On a miss, the cache hands out a token. If the key is deleted in the meantime, the token is invalidated, and the late write is refused.

Stampedes

When a popular key expires, thousands of requests can miss at once and all hit the database with the same query. This is a cache stampede, or thundering herd.

Leases made a large difference at Facebook: one report from the paper’s data shows peak database load falling from 17,000 to 1,300 queries a second.

Other failure modes

Cache penetration. Requests for keys that don’t exist always miss, and an attacker can use this to hammer a database. Caching “not found” for a short time, or checking a Bloom filter first, stops it.

Cold start. An empty cache sends all traffic to the database, which may not survive it. This is a real risk after a cache restart. Warming the cache in advance, or letting traffic back in gradually, avoids it.

Hot keys. One key can be so popular that it overloads its cache node. Fixes are a small local cache in each application server, or replicating that key.

Dependence. Over time, a system can come to rely on its cache to survive normal load. If the database can’t handle traffic without the cache, then the cache isn’t an optimization any more. It’s a critical dependency, and has to be run like one.

Big values. A large value can block a single-threaded cache and saturate the network. Splitting or compressing large values helps.

Consistency expectations

A cache means accepting some staleness. It’s worth deciding per item how much is acceptable. A like count can be a minute old, while a bank balance or a permission check generally can’t. A permission check served from a stale cache is a security problem.

Read-your-writes is a common requirement: a user who updates a profile expects to see the change. Options include reading from the source for a short time after a user’s write, or updating the cache as part of the write.

Negative effects on tail latency

A cache can hide a slow path. Most requests look fast, while cache misses are slow, so an average can look healthy while the p99 is poor. Measuring hit and miss latency separately gives a clearer picture.

The takeaway

Caches work because access is uneven. They reduce load and latency, and they create new failure modes: stale data, stampedes, and cold starts. Decide how stale each kind of data can be, and plan for the moment the cache is empty.