How caching works
A cache answers repeated requests from a faster, nearer copy of the data. This guide follows one request through the browser, a CDN, an application cache and the database, then covers HTTP caching headers, keeping copies correct, stampedes and what to measure.
What caching is
A cache keeps a copy of data somewhere faster or nearer than its original source, so that later requests for the same data can be answered without going back to the source. When a request finds what it needs in the cache, that is a hit; when it does not, it is a miss, and the data has to be fetched from the source, which is usually slower or more expensive.
Caching works because most systems ask for the same things repeatedly: the same images and scripts on every page view, the same popular products, the same user profile on every request in a session. It trades two things for speed: memory to hold the copies, and the risk that a copy is out of date.
The gaps it closes are large. Reading from a computer's main memory takes on the order of 100 nanoseconds; a network round trip inside a data centre about half a millisecond; a round trip across an ocean more than 100 milliseconds. A cache that turns a cross-ocean round trip into a memory read is a million times faster for that request.
One request, four caches
A request for a web page can be answered by any of several caches on the way to the database. Each one that hits saves the trip through every layer behind it.
| Cache | Where it lives | What it holds | Controlled by |
|---|---|---|---|
| Browser cache | The user's device | Responses for that one user: scripts, styles, images, some API responses | HTTP headers sent by the server |
| CDN | Servers near users, run by a CDN provider | Responses shared by many users | HTTP headers and CDN rules |
| Application cache | An in-memory store such as Redis or Memcached, or the application's own memory | Results of database queries or computations | Application code |
| Database buffer pool | The database server's memory | Recently used pages of tables and indexes | The database itself |
Take a product page. On a repeat visit, the browser already has the page's script and style files and does not ask for them at all. The product image is not in the browser cache but is in the CDN's server in the same city, so it arrives in a few milliseconds. The page itself is generated by the application, which finds the product's details in Redis instead of querying the database. If Redis misses, the database answers from its buffer pool in memory, and only if that misses too does it read from disk.
HTTP caching
Browsers and CDNs decide what to cache, and for how long, from headers in the server's response. The rules are standardised in RFC 9111.
- Cache-Control: max-age=3600 means the response can be reused for an hour without asking the server. s-maxage sets a different lifetime for shared caches such as CDNs.
- private means only the user's own browser may store the response, never a shared cache. Any response containing personal data needs it; a shared cache that stores one user's account page can show it to another user.
- no-cache does not mean "do not cache". It means the cache must check with the server before each reuse. no-store is the one that forbids storing the response at all.
- immutable tells the browser the content will never change at that URL, so it need not check even when the user reloads.
When a cached response has expired, the cache does not have to download it again. It can revalidate: send the request with the response's ETag in an If-None-Match header (or its date in If-Modified-Since). If nothing has changed, the server answers 304 Not Modified with no body, and the cache keeps using its copy.
The usual pattern for static files is to put a hash of the file's contents in its name, such as app.3f9a1c.js, and cache it for a year with immutable. A new version gets a new name, so nothing ever needs to be invalidated. The HTML page that refers to those files is cached briefly or revalidated every time.
The Vary header tells caches which request headers change the response, for example Vary: Accept-Encoding when compressed and uncompressed versions exist. Caches then store a separate copy per value.
How applications use a cache
Cache-aside
The most common pattern. To read, the application checks the cache; on a miss it reads the database and stores the result in the cache. To write, it updates the database and then deletes the cache entry, so the next read loads the new value. Deleting is safer than updating the cache, because two writers updating the cache in the wrong order can leave the older value there.
def get_product(product_id):
key = f"product:{product_id}"
cached = cache.get(key)
if cached is not None:
return cached # hit
product = db.query_product(product_id) # miss: go to the database
cache.set(key, product, ttl=300) # keep it for five minutes
return product
def update_product(product_id, fields):
db.update_product(product_id, fields)
cache.delete(f"product:{product_id}") # next read loads the new valueRead-through and write-through
In read-through, the cache itself loads missing values from the database, so the application only talks to the cache. In write-through, every write goes to the cache and the database together, so the cache is always up to date, at the cost of slower writes and of caching data that may never be read.
Write-behind
Writes go to the cache and are copied to the database later, in batches. Writes are fast, but data written to the cache and not yet copied is lost if the cache fails. It suits data such as counters, where losing a little is acceptable.
Keeping cached data correct
A cached copy is correct when it is stored and can become wrong at any moment after. There are three main ways to limit how long a wrong copy is served.
- Expiry. Give each entry a time to live (TTL). After it expires, the next request fetches a fresh copy. Simple and always works, but data can be stale for up to the full TTL.
- Explicit invalidation. When data changes, delete or update the cached copies, as in the cache-aside write above, or by sending a purge request to the CDN. Data is fresh sooner, but every code path that changes data must remember every cache that holds it. A common way to make this reliable is to listen to the database's change log and invalidate from there.
- New keys for new versions. Include a version in the key or URL, so that a change creates a new entry instead of altering an old one, as with hashed file names.
Even cache-aside has a race. A reader misses, reads the old value from the database, and is delayed; meanwhile a writer updates the database and deletes the cache entry; then the reader stores the old value it read, which stays until it expires. Facebook's 2013 paper on scaling Memcache describes leases to prevent this: on a miss, the cache gives the reader a token, and a delete cancels the token, so the late, stale write is refused. Most systems rely on a TTL as a backstop.
Cache stampedes
When a popular entry expires, every request that arrives before it is reloaded misses at once, and all of them go to the database together. For an expensive query this can overload the database, which makes reloading slower, which lets even more requests pile up. This is a cache stampede, a kind of thundering herd.
- Request coalescing. Let only one request reload a missing key while the others wait for its result. Go's singleflight package is a well-known example, and Facebook's leases also do this.
- Serve stale while refreshing. Keep serving the expired copy while one request reloads it in the background. For HTTP caches, the stale-while-revalidate directive (RFC 5861) does this.
- Refresh early, at random. Reload an entry a little before it expires, with a probability that rises as expiry approaches, so one request usually refreshes it before the crowd arrives. Vattani, Chierichetti and Lowenstein analysed this approach in 2015.
- Spread expiry times. Add a random amount to each TTL, so that entries written at the same time do not all expire at the same time.
When the cache is full
A cache has limited memory, so adding an entry to a full cache means removing another. The rule for choosing which is the eviction policy. Least recently used (LRU) is the usual default; the LRU cache simulator shows how it is built and where it fails, and the cache eviction simulator compares LRU with LFU, ARC and TinyLFU on the same requests. Redis, for example, lets you choose between several policies, and by default refuses new writes when memory is full instead of evicting anything.
Measuring a cache
The most important number is the hit rate: hits divided by all lookups. Its effect on average response time is larger than it looks, because misses are so much slower than hits. With a 1 ms hit and a 50 ms miss:
| Hit rate | Average time per request |
|---|---|
| 50% | 25.5 ms |
| 90% | 5.9 ms |
| 99% | 1.5 ms |
Going from 90% to 99% cuts average time by three quarters, and cuts the load on the database tenfold. Also worth watching: the eviction rate (a high rate means the cache is too small for the data in use), the number of distinct keys (a key that accidentally includes a timestamp or request ID creates entries that are never read again), and the time to answer a miss.
Common mistakes
- Personal data in a shared cache. Missing private on a response, or a cache key that leaves out the user, can show one user's data to another.
- Caching errors. Storing an error or an empty result with a long TTL keeps serving it after the problem is fixed. Errors, if cached at all, need short TTLs.
- Treating the cache as the only copy. Caches lose data on restart or eviction. Anything that must not be lost belongs in a durable store.
- A cold start. After a cache restart or a deployment that changes every key, every request misses at once. Warm the cache gradually, or change keys in stages.
- Caching what is cheap to compute. A cache adds a network hop, memory and a way to serve stale data. It is only worth it when the original is meaningfully slower or more expensive.
Further reading
- RFC 9111, 2022HTTP CachingThe standard that browsers and CDNs follow.
- MDNHTTP cachingA readable guide to the headers, with examples.
- Nishtala and others, 2013Scaling Memcache at FacebookLeases, invalidation and stampede control at a very large scale.
- Vattani, Chierichetti and Lowenstein, 2015Optimal Probabilistic Cache Stampede PreventionRefreshing entries early at random, with the analysis.
- RFC 5861, 2010HTTP Cache-Control Extensions for Stale ContentDefines stale-while-revalidate and stale-if-error.
- SemicolonyLRU cache simulatorHow an LRU cache is built, step by step.