Caching strategies and their pitfalls

Why cache, and what it costs

A cache keeps a copy of data somewhere faster or closer than its original home, so that repeated requests do not pay the full price each time. Section 0.2 introduced the idea as a trade of space for time. At architecture scale the trade is more interesting, because a cache changes three qualities at once. It lowers latency (a Redis lookup in the same data centre typically takes well under a millisecond; a database query that joins five tables may take tens of milliseconds). It raises throughput and protects the database, because every hit is a query the database never sees. And it can improve availability, because a cache that can serve slightly old data keeps working while the source is slow or down.

The price is paid in correctness and complexity. A cache is a second copy of the data, and two copies can disagree. Every cache therefore embodies a decision about how stale an answer is allowed to be, and for whom. A restaurant menu that is five minutes old is acceptable; a bank balance that is five minutes old, shown to a customer deciding whether they can afford a payment, is not. Caches also add a component that can fail, consume memory that costs money, and create new failure modes such as stampedes and cold starts that do not exist without them. The first question is therefore not which cache? but what may be stale, by how much, and what happens if it is?

The effectiveness of a cache is measured by its hit ratio: hits divided by all lookups. Hit ratio depends on how skewed the access pattern is. Read traffic in most consumer systems is highly skewed (a small fraction of restaurants, products or accounts receives most of the reads), so a cache holding a few per cent of the data can often answer most of the reads. Uniformly random access, by contrast, caches badly whatever you do.

The five classic patterns

Caching patterns differ in who loads the cache, when writes reach the source, and therefore how stale and how durable the data can be. The table compares them; the paragraphs after it explain where each fits.

Cache-aside is the default for good reason: it is easy to reason about and fails safe, because if the cache disappears the application simply reads the database (more slowly). Read-through moves the same logic into a cache library or product, which is tidy but no different in behaviour. Write-through suits data that is read soon after being written, such as a user's session or shopping basket. Write-behind is the risky one: it turns the cache into the temporary system of record, so it is appropriate only where losing the last few seconds of writes is acceptable (view counters, analytics events, game scores) or where the cache itself is replicated and durable. Never use write-behind for money. Refresh-ahead is an optimisation for a small set of very hot keys, such as the home-page restaurant list in a busy city.

import json, random

TTL = 300  # seconds

def get_menu(restaurant_id):
    key = f"menu:{restaurant_id}:v3"            # version the key with the data shape
    cached = cache.get(key)
    if cached is not None:
        return json.loads(cached)                # hit
    with cache.lock(f"lock:{key}", timeout=5):  # coalesce: one loader per key
        cached = cache.get(key)                  # someone may have filled it meanwhile
        if cached is not None:
            return json.loads(cached)
        menu = db.load_menu(restaurant_id)       # miss: go to the system of record
        jitter = random.randint(0, TTL // 10)    # spread expiry times out
        cache.set(key, json.dumps(menu), ex=TTL + jitter)
        return menu

def update_price(restaurant_id, item_id, price):
    db.update_price(item_id, price)              # 1. change the system of record
    cache.delete(f"menu:{restaurant_id}:v3")     # 2. invalidate, do not overwrite

Time to live and invalidation

There are two ways to stop a cache serving data that has changed. The first is a time to live (TTL): every entry expires after a fixed period, which bounds staleness without any coordination. A five-minute TTL on menus means a price change is visible everywhere within five minutes. The second is explicit invalidation: when the source changes, something deletes or updates the cached copy. Invalidation gives fresher data but requires every code path that changes the data to know every cache that holds it, which is exactly what goes wrong as systems grow. In distributed systems invalidation is often driven by events: the menu service publishes MenuChanged, and each service holding a copy deletes its entry. Most professional designs combine both: invalidate on change for freshness, and keep a TTL as a safety net for the invalidation that was missed.

The difficulty is captured in a quip attributed to Phil Karlton of Netscape: There are only two hard things in Computer Science: cache invalidation and naming things. It is hard because invalidation is a distributed-systems problem in disguise. The database write and the cache delete are two operations on two systems with no shared transaction, so one can succeed while the other fails, and operations from different requests can interleave.

Two rules avoid most problems. First, on a write, update the database and then delete the cache entry; do not write the new value into the cache. Two concurrent writers that each set the cache can finish in the opposite order to their database commits and leave the older value cached indefinitely, whereas a delete can only cause an extra miss. Second, accept that even delete-on-write leaves a narrow race, shown below, and bound it with a TTL. Facebook's 2013 paper on scaling memcache describes leases for this case: the cache gives a token to the client that missed, and refuses that client's later write if the key was deleted in the meantime.

Stampedes and the thundering herd

A cache stampede happens when a popular entry expires, or a cache node restarts empty, and hundreds of concurrent requests all miss at the same instant. Each one goes to the database to compute the same value, and the database, sized for the cache's normal miss rate, is overwhelmed. Slower responses mean more requests pile up, and the overload can cascade. The related thundering herd describes many waiting clients woken at once to compete for one resource. Facebook reported that, for a set of keys particularly prone to this, leases cut the peak database query rate from 17,000 to 1,300 per second.

The defences combine well. Request coalescing (also called single flight) lets only one request per key fetch from the source while the others wait for its result; within one process this is a map of in-flight futures, across processes a short lock in the cache, as in the code above. Jittered expiry adds a random amount to each TTL so that entries written together (after a deployment or a cache flush) do not expire together. Stale-while-revalidate serves the expired value to everyone while one background request fetches a fresh one, which removes the latency spike entirely when slight staleness is acceptable. Probabilistic early expiration (Vattani, Chierichetti and Lowenstein, VLDB 2015) has each reader decide at random, with a probability that rises as expiry approaches, to refresh early, so that one request usually refreshes before the entry actually expires. Finally, warming a new cache from a list of hot keys before it takes traffic avoids the cold-start stampede after a restart.

Levels of caching

Caches exist at every level between the user and the disk, and a request is answered by the first level that has a usable copy. The browser keeps a private cache controlled by HTTP headers. A content delivery network (CDN) keeps shared copies at edge locations near users, ideal for images, scripts and public API responses such as menus. A reverse proxy at the origin (Nginx, Varnish) can cache whole responses for a few seconds, which is called microcaching and can absorb a sudden spike. The application caches computed objects, either in-process (fastest, but each instance holds its own copy and they disagree) or in a shared cache such as Redis or Memcached. The database caches pages in memory (PostgreSQL's shared buffers, the InnoDB buffer pool) and can precompute expensive results in materialised views.

The further from the data, the larger the saving per hit and the harder the invalidation. You can delete a key from Redis in a millisecond; you can purge a CDN, more slowly; you cannot reach into a customer's browser at all, so whatever max-age you send is a promise you must live with. Long browser lifetimes are therefore used for files whose URL changes when their content changes (app.3f9a1c.js), and short ones, or revalidation, for anything else.

HTTP caching headers

HTTP has a complete caching model, defined in RFC 9111 (June 2022), and using it well can remove load before it reaches your servers. Cache-Control: max-age=60 lets any cache reuse a response for 60 seconds; s-maxage overrides that for shared caches such as CDNs; private forbids shared caches from storing it (use it for anything personal); no-cache confusingly means store it, but check with the server before every reuse; and no-store means never keep a copy, the right setting for bank balances and statements. The stale-while-revalidate and stale-if-error extensions (RFC 5861, 2010) apply the stampede and availability ideas above at the HTTP level.

When a cached copy is stale, the client need not download it again. A validator lets it ask whether anything has changed: the server sends an ETag (an opaque version identifier) or a Last-Modified date with the response, and the client later sends If-None-Match or If-Modified-Since. If nothing changed, the server replies 304 Not Modified with no body, saving bandwidth and often most of the server's work. These conditional requests are defined in RFC 9110. The Vary header tells caches which request headers (such as Accept-Language) produce different responses, so that a French menu is never served to an English request.

GET /restaurants/17/menu HTTP/1.1
Host: api.example-food.test

HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: public, max-age=60, s-maxage=300, stale-while-revalidate=30
ETag: "menu-17-v42"

... 18 KB of menu JSON ...

# 100 seconds later the copy is past max-age plus the stale-while-revalidate
# window, so the browser must revalidate before using it:
GET /restaurants/17/menu HTTP/1.1
If-None-Match: "menu-17-v42"

HTTP/1.1 304 Not Modified
Cache-Control: public, max-age=60, s-maxage=300, stale-while-revalidate=30
ETag: "menu-17-v42"

# A bank balance, by contrast, must never sit in any cache:
Cache-Control: no-store

Eviction, sizing and consistency risks

A cache is smaller than the data behind it, so when it is full it must evict something. Least recently used (LRU) evicts the entry untouched for longest and works well when recent use predicts future use. Least frequently used (LFU) evicts the entry used least often and resists one-off scans (a nightly report that touches every restaurant once would flush an LRU cache of its genuinely hot entries). Production caches approximate both: Redis, for example, samples a few keys and evicts the best candidate among them, and offers policies such as allkeys-lru, allkeys-lfu and volatile-ttl. Its default policy, noeviction, rejects writes when memory is full, which suits Redis used as a store but not as a cache, so set the policy deliberately.

Beyond staleness, caches introduce subtler consistency risks. A user who changes their delivery address and then sees the old one, because the read came from a cache another instance had not yet invalidated, experiences a broken read-your-writes guarantee (Section 7.4); a common fix is to bypass the cache for a user's own recent writes. In-process caches on many instances disagree with each other, so consecutive requests routed to different instances can show a value going backwards. Caching an error or an empty result without a short TTL turns a brief outage into a long one. Caching data that mixes users (a page with the customer's name, cached under the URL alone) leaks personal data to the next visitor, a well-known class of security incident. And cache keys must include everything that changes the answer: tenant, language, currency, permissions and the version of the data format.