CS Fundamentals Trainer · Guides

Caching strategies

Where caches live, cache-aside and the other patterns, eviction, invalidation races, and how to survive stampedes.

23 min read

A cache keeps a copy of data somewhere faster or closer, so the next request does not repeat expensive work. It is the cheapest way to make a system faster and the easiest way to make it wrong: the day you add a cache you also add a second copy of the truth, and copies drift apart. This guide covers where caches live, the patterns for reading and writing through them, how to keep them correct, and how they fail.

1. Why cache, and what to cache

Caching pays off when three things hold at once:

If any of these is missing, a cache gives you little: unique results are never reused, cheap work is not worth the extra hop, and data that must be exact to the millisecond (an account balance during a transfer) should not come from a copy.

The numbers that matter

Two numbers describe a cache: the hit ratio (the share of requests answered from the cache) and the cost of a miss. Say a cache lookup takes 1 ms and the database takes 20 ms. A miss costs both (you look in the cache first), so 21 ms.

Hit ratioAverage latencyLoad on the database
0 % (no cache)20 ms100 %
90 %0.9 × 1 + 0.1 × 21 = 3.0 ms10 %
99 %0.99 × 1 + 0.01 × 21 = 1.2 ms1 %

Going from 90 % to 99 % cuts latency by 2.5 times (3.0 ms to 1.2 ms), but the bigger win is that the database load falls another tenfold. That is why the hit ratio is the first number to watch, and why a cache that goes cold (after a restart, or a bad deployment) can knock over the database behind it.

2. Where caches live

Requests pass through several layers, and each one can hold a copy. The closer to the user, the faster and the harder to invalidate.

Diagram: Layers of caching between a user and the data

A common and good combination is a tiny in-process cache (seconds of lifetime) in front of the shared Redis cache, for the few hottest keys.

3. Reading and writing: the five patterns

These names come up in every discussion, so it is worth knowing exactly what each one does.

PatternReadWriteGood forWatch out for
Cache-aside (lazy loading)App checks the cache; on a miss, loads from the database and fills the cacheApp writes the database, then deletes the cached keyThe default for most appsStale data after races; a cold cache is slow
Read-throughSame as cache-aside, but the cache library loads from the database itselfOften combined with write-throughSimpler app codeNeeds a cache that supports loaders
Write-throughn/aWrite goes to the cache, which writes to the database before answeringData read right after it is writtenSlower writes; caches data that may never be read
Write-behind (write-back)n/aWrite goes to the cache; the database is updated later, in batchesVery high write rates, countersData loss if the cache dies before the flush
Write-aroundn/aWrite goes straight to the database, skipping the cacheData written once and rarely readThe first read after a write is always a miss

Cache-aside, step by step

It is the pattern to know best, because it needs nothing from the cache but get, set and delete.

Diagram: Cache-aside: a miss, then a hit

The same function in four languages (pick a language on the tabs; your choice is remembered). Note the details: the time limit has a random part (explained in section 6), a cache that is down must not take the app down with it, in either direction (a failed SET and a failed DELETE are both survivable), and the Python version also caches "not found" for a short time, which section 6 explains. The other versions leave that out to stay short.

import json
import logging
import random

from redis.exceptions import RedisError

log = logging.getLogger(__name__)
# r is a redis.Redis client created with decode_responses=True


def get_user(user_id):
    key = f"user:{user_id}"
    try:
        cached = r.get(key)
        if cached is not None:                       # "null" is a cached "not found"
            return json.loads(cached)
    except RedisError:
        pass                                         # the cache is down: carry on without it

    user = db.fetch_user(user_id)                    # a miss: read the source of truth
    # the random part spreads out expiry; "not found" is cached too, but only briefly
    ttl = 300 + random.randint(0, 60) if user is not None else 30
    try:
        r.set(key, json.dumps(user), ex=ttl)
    except RedisError:
        pass
    return user


def update_user(user_id, fields):
    db.update_user(user_id, fields)                  # write the database first
    try:
        r.delete(f"user:{user_id}")                  # then drop the cached copy
    except RedisError:
        # the write is done; the old copy lives until its TTL runs out, so log it and go on
        log.warning("could not invalidate user:%s", user_id)

func GetUser(ctx context.Context, id string) (*User, error) { key := "user:" + id s, err := rdb.Get(ctx, key).Result() if err == nil { var u User if json.Unmarshal([]byte(s), &u) == nil { return &u, nil } } // redis.Nil is a plain miss; any other error means the cache is down. // Either way, go on to the database.

u, err := db.FetchUser(ctx, id) // the source of truth if err != nil || u == nil { return u, err } if b, err := json.Marshal(u); err == nil { ttl := 300time.Second + time.Duration(rand.Intn(60))time.Second // random part spreads out expiry rdb.Set(ctx, key, b, ttl) // best effort } return u, nil }

func UpdateUser(ctx context.Context, id string, f Fields) error { if err := db.UpdateUser(ctx, id, f); err != nil { // write the database first return err } if err := rdb.Del(ctx, "user:"+id).Err(); err != nil { // then drop the cached copy // the write is done; the old copy lives until its TTL runs out, so log it and go on log.Printf("could not invalidate user:%s: %v", id, err) } return nil }

async function getUser(id) { const key = user:${id}; try { const cached = await redis.get(key); if (cached !== null) return JSON.parse(cached); } catch { // the cache is down: carry on without it }

const user = await db.fetchUser(id); // a miss: read the source of truth if (user) { const ttl = 300 + Math.floor(Math.random() * 60); // the random part spreads out expiry redis.set(key, JSON.stringify(user), "EX", ttl).catch(() => {}); } return user; }

async function updateUser(id, fields) { await db.updateUser(id, fields); // write the database first try { await redis.del(user:${id}); // then drop the cached copy } catch (err) { // the write is done; the old copy lives until its TTL runs out, so log it and go on console.warn(could not invalidate user:${id}, err); } }

public async Task<User?> GetUserAsync(string id) { var key = $"user:{id}"; try { var cached = await _redis.StringGetAsync(key); if (cached.HasValue) return JsonSerializer.Deserialize<User>((string)cached!); } catch (RedisException) { // the cache is down: carry on without it }

var user = await _db.FetchUserAsync(id); // a miss: read the source of truth if (user is not null) { var ttl = TimeSpan.FromSeconds(300 + Random.Shared.Next(0, 60)); // random part spreads out expiry _ = _redis.StringSetAsync(key, JsonSerializer.Serialize(user), ttl, flags: CommandFlags.FireAndForget); } return user; }

public async Task UpdateUserAsync(string id, Fields fields) { await _db.UpdateUserAsync(id, fields); // write the database first try { await _redis.KeyDeleteAsync($"user:{id}"); // then drop the cached copy } catch (RedisException e) { // the write is done; the old copy lives until its TTL runs out, so log it and go on _log.LogWarning(e, "Could not invalidate user:{Id}", id); } }


### Why delete on write, not update?

On a write, delete the cached key instead of writing the new value into it. Two writers that finish in a different order than they started would leave the older value in the cache; a delete cannot leave a wrong value behind, only an empty slot that the next read refills. It also saves work for data that is never read again. Section 5 shows the one race that deleting does not fix.

## 4. Eviction: what to throw out when full

A cache has fixed memory, so something must go when it is full. The usual policies:

- **LRU (least recently used):** remove what has not been touched for the longest time. Simple and a good default, because recent use predicts future use.
- **LFU (least frequently used):** remove what is used least often. Better when a few items stay popular for a long time, and a one-off scan (a crawler, a big report) should not push them out.
- **FIFO and random:** cheap and sometimes good enough.
- **TTL (time to live):** not an eviction policy, but a deadline on each entry. It bounds how stale a value can get, and it cleans up by itself.

The trade-offs of each policy are summarised on Wikipedia [[7]](#sources). Redis lets you choose with `maxmemory-policy`: for example `allkeys-lru`, `allkeys-lfu`, or the `volatile-*` versions that only touch keys with a TTL. Redis does not keep an exact LRU list; it samples a few keys and removes the best candidate, which is much cheaper and close enough to the real thing [[3]](#sources). The default policy, `noeviction`, makes writes fail when memory is full. That is right for a database and wrong for a cache, so set it deliberately.

A tiny LRU in Python shows the idea. A dictionary that remembers the order of use does all the work:

from collections import OrderedDict

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

def get(self, key): if key not in self.items: return None self.items.move_to_end(key) # now the most recently used return self.items[key]

def put(self, key, value): self.items[key] = value self.items.move_to_end(key) if len(self.items) > self.capacity: self.items.popitem(last=False) # drop the least recently used


## 5. Staying correct: invalidation

> There are only two hard things in computer science: cache invalidation and naming things. (Phil Karlton)

There are four ways to keep a cache honest, and real systems mix them.

1. **Time limits (TTL).** Every entry expires after, say, 5 minutes. No code to write, and the staleness is bounded. The price: users can see old data for up to a full TTL.
2. **Explicit invalidation.** When data changes, delete the keys that hold it. Fresh, but you must find every key affected: the user, the list the user appears in, the page that shows the list.
3. **Versioned keys.** Put a version in the key (`user:42:v7`). A change bumps the version, and old entries are simply never read again and age out. Nothing to delete, and no race on delete.
4. **Event-driven.** Changes in the database publish events (a change stream, or the outbox pattern), and a consumer deletes or refreshes keys. Good when many writers touch the data.

Always combine explicit invalidation with a **TTL as a safety net**. Deletes will occasionally be lost (a crash between the database write and the delete, a network blip), and the TTL guarantees such a mistake fixes itself.

### The race that deleting does not fix

Even cache-aside with delete-on-write has a gap. A slow reader can put an old value back after the writer has invalidated:

%% title: A stale value written back after the delete sequenceDiagram participant A as Reader A participant C as Cache participant D as Database participant B as Writer B A->>C: GET (miss) A->>D: read, gets the OLD value B->>D: write the NEW value B->>C: DELETE the key A->>C: SET the OLD value Note over C: stale until the TTL runs out


It needs a slow reader and a write in exactly the wrong gap, so it is rare, but at enough traffic it happens. Defences, from simple to elaborate:

- **A short TTL.** The mistake heals itself.
- **Versioned writes.** Store the row version with the value, and only accept a cache write if its version is not older than the stored one (for example with a small Lua script on Redis).
- **Leases.** Facebook's memcache describes handing the reader a token on a miss; a delete invalidates the token, so the late `SET` is refused [[4]](#sources). The same mechanism also reduces stampedes.
- **Delayed second delete.** Delete again a second or so after the write, to wipe out a late fill.

Decide how much staleness each kind of data tolerates, write it down, and pick the cheapest tool that meets it. A product description can be five minutes old. A stock level at checkout probably cannot.

## 6. How caches fail

Four failure patterns come up again and again in cache incidents. All are about many requests arriving at the database at once. (The AWS Builders' Library article covers related ground: cold caches, request coalescing, and caching "not found" [[6]](#sources).)

### Stampede (thundering herd)

A popular entry expires, and in the next few milliseconds a thousand requests all miss, and all run the expensive query. The database, which was safe behind the cache, gets a thousand copies of the same work.

%% title: Without protection every waiting request runs the query sequenceDiagram participant R as Requests (1000) participant C as Cache participant D as Database R->>C: GET hot-key C-->>R: expired, miss (for all of them) R->>D: the same slow query, 1000 times


Defences:

- **Single flight (request coalescing).** Let the first request do the work, and make the others wait for its answer. One query instead of a thousand. This is the best first fix, and it fits in a few lines:

import threading

class SingleFlight: def __init__(self): self.lock = threading.Lock() self.calls = {} # key -> the call in progress

def do(self, key, fn): with self.lock: call = self.calls.get(key) leader = call is None if leader: call = self.calls[key] = {"done": threading.Event(), "value": None, "error": None} if leader: try: call["value"] = fn() # only the first caller does the work except Exception as e: call["error"] = e finally: with self.lock: del self.calls[key] call["done"].set() # wake everyone who waited else: call["done"].wait() if call["error"]: raise call["error"] return call["value"]

import "golang.org/x/sync/singleflight"

var group singleflight.Group

func LoadUser(ctx context.Context, id string) (User, error) { v, err, _ := group.Do("user:"+id, func() (any, error) { return db.FetchUser(ctx, id) // one call per key at a time; the rest share its result }) if err != nil { return nil, err } return v.(User), nil }

const inflight = new Map();

function singleFlight(key, load) { let promise = inflight.get(key); if (!promise) { promise = load().finally(() => inflight.delete(key)); // the first caller starts the work inflight.set(key, promise); } return promise; // everyone else shares the same promise }

private readonly ConcurrentDictionary<string, Lazy<Task<User?>>> _inflight = new();

public async Task<User?> LoadUserAsync(string id) { var key = "user:" + id; // Lazy makes sure the loader starts only once, even if two threads race to add it var call = _inflight.GetOrAdd(key, _ => new Lazy<Task<User?>>(() => _db.FetchUserAsync(id))); try { return await call.Value; // everyone shares the same task } finally { _inflight.TryRemove(new KeyValuePair<string, Lazy<Task<User?>>>(key, call)); } }


This works inside one process. With many servers, you still get one query per server; that is usually fine. For one query globally, take a short lock in Redis (`SET key token NX PX 5000`) and let the losers wait briefly or serve a slightly stale value.

- **Serve stale while refreshing.** Keep the expired value for a little longer and answer with it while one request refreshes it in the background (`stale-while-revalidate` [[2]](#sources)). Users never wait.
- **Refresh early, randomly.** The XFetch algorithm lets each request decide, with a probability that grows as the expiry approaches, to recompute early. Hot keys are renewed before they ever expire, with no coordination [[5]](#sources):

Where does the recompute time come from? You measure it, and store it with the value: when you load from the database, time the call and save `{"value": ..., "delta": seconds_it_took, "expiry": unix_time}` in the cache entry. Each reader then asks:

import math import random import time

def should_refresh_early(entry, beta=1.0):

log(random) is negative, so this moves "now" forward by a random amount,

larger when the last recompute (entry["delta"]) was slow

return time.time() - entry["delta"] * beta * math.log(random.random()) >= entry["expiry"]


With a 2-second recompute, a reader has about a 1 % chance of refreshing early 10 seconds before the expiry, 13 % at 4 seconds, 61 % at 1 second, and certainty at the expiry. Slow computations start earlier; fast ones barely at all. `beta` above 1 refreshes earlier.

### Avalanche

Many keys expire at the same instant, because they were all filled together (after a restart or a bulk load) with the same TTL. The cache empties in one moment and the database takes everything. **Add a random part to every TTL** (as in the code above), and warm the cache gradually after a restart.

### Penetration

Requests ask for keys that do not exist (random ids from a bot, or a bug). They always miss, so each one goes to the database, and the cache never fills. Fixes: cache the "not found" answer for a short time (30-60 seconds), validate ids before the lookup, or put a Bloom filter of valid ids in front.

### Hot key

One key receives so many requests that a single cache node cannot serve it, even with a perfect hit ratio. Fixes: an in-process cache on every app server for the hottest keys, or split the key into several copies (`hot:1` ... `hot:8`) and read a random one.

## 7. Personalised responses and shared caches

A shared cache (a CDN, a reverse proxy, or one Redis for all users) gives the same stored answer to everyone who asks for the same key. That is the point, and it is also the danger: **if the key does not include everything the answer depends on, one person's data goes to another.**

- **Put every input in the key.** User or tenant, language, currency, feature flags, device class. `GET /account` cached under the key `/account` is a leak waiting to happen.
- **Mark HTTP responses honestly.** `Cache-Control: private` means "only the user's own browser may keep this"; `no-store` means "keep it nowhere"; `public` allows shared caches. Use `private` or `no-store` for anything personal, and be careful with CDNs that cache by default [[1]](#sources).
- **Use `Vary` when the same URL gives different answers** by a request header (`Vary: Accept-Language`, `Vary: Accept-Encoding`). A missing `Vary` serves the English page to the French reader. Never `Vary` on `Cookie` for a CDN unless you accept almost no sharing.
- **Do not cache responses that set cookies or tokens** in a shared cache.
- **Cache the shared part, not the personal one:** the product page is cached for everyone, and the "hello, Ana" fragment is loaded separately.

## 8. Replicas, and caches on many servers

### Reading your own write

A user saves a profile and reloads. If reads come from a replica that is a second behind, they see the old profile, and cache-aside makes it worse: the miss fills the cache **from the lagging replica**, so the old value is stored and served to everybody until the TTL ends. Defences:

- **Read from the primary for a short time after a write** (a few seconds, remembered per user in a cookie or the session), or for the reads that matter most.
- **Fill the cache only from the primary** for data where staleness is not acceptable.
- **Write the new value into the cache** with the version number from the write (versioned writes, section 5) for the pages the writer is about to look at.

### In-process caches on many servers

A delete in Redis reaches everyone. A delete in one server's memory reaches nobody else, so the other servers keep the old value. The options, from simple to complicated:

- **A very short TTL** (1 to 10 seconds). The staleness is bounded and there is nothing to coordinate. This is the default answer for hot keys.
- **Broadcast invalidations.** On a write, publish the key on Redis pub/sub (or a message bus); every server subscribes and drops its local copy. Messages can be lost when a server reconnects, so keep the short TTL as well.
- **Version numbers in keys.** Keep one small "version" value per entity in Redis and include it in the local key; a change bumps the version and old local entries are simply never hit again.

## 9. Choosing a TTL and a size

- **TTL:** start from what the business can accept. Seconds for fast-changing data, minutes for typical content, hours or days for things that almost never change. Add the random part. If you use explicit invalidation too, the TTL can be generous.
- **Size:** measure the hit ratio against cache size. It rises steeply at first and then flattens: the first few percent of the data often serve most requests. Stop growing the cache when more memory buys little. A worked example: 10 million users with a 2 KB cached profile is 20 GB if you cache everyone. If the hottest 20 % of users make most requests, caching them takes about 4 GB. Add the per-key overhead of the cache itself (tens of bytes per key in Redis; measure with `MEMORY USAGE`), and leave headroom, because a full cache evicts or fails. At 20 000 requests per second and a 95 % hit ratio, the database sees about 1 000 per second.
- **What to store:** the smallest thing that saves the work. Store the finished result (the rendered fragment or the JSON), not the raw rows you must still assemble.
- **Serialisation:** compact formats and compression matter when millions of keys are stored; measure bytes per key.

## 10. Testing a cache

- **Hit, miss, fill:** the first call goes to the database, the second does not.
- **Invalidation:** after `update_user`, the next read returns the new data.
- **The cache is down:** stop Redis in the test (or point at a closed port) and check that reads still work, and that a write does not fail.
- **Stampede:** start 50 concurrent calls for one missing key and count the database calls. With single flight it must be one.
- **TTL and jitter:** many fills produce expiry times within the expected range, not all equal.
- **Not found:** a missing key is cached briefly, and the database is asked once.
- **Isolation of users:** two users asking for "their" page get two different answers (the leak test for section 7).
- **Cold start:** a load test with an empty cache. Does the database survive the first minute?

Run these against a real Redis (a throwaway container), not a mock: the interesting failures are in expiry, timeouts, and eviction, which a mock does not reproduce.

## 11. What to measure

- **Hit ratio,** per cache and per key prefix. A sudden fall means a deploy changed keys, an expiry cliff, or an attack.
- **Latency** of cache calls, with timeouts set short. A slow cache is worse than no cache, so give up quickly and use the database.
- **Evictions per second.** A steady stream means the cache is too small.
- **Memory use and key counts,** and how many keys have no TTL (they are the ones that stay forever).
- **Database load,** the number the cache exists to protect.

## 12. Things to mention in an interview

- Say why you cache (read-heavy, expensive, tolerant of staleness) and name the hit ratio.
- Describe cache-aside first, then say when you would pick write-through or write-behind and what each one risks.
- Name the layers: browser, CDN, in-process, distributed.
- Explain invalidation honestly: TTL as a safety net, delete on write, and the race you cannot fully remove.
- Cover stampede, avalanche, penetration and hot keys with one fix each.
- Mention personal data in shared caches, and replicas that fill the cache with old data.
- Say that the cache must be optional: if it fails, the system gets slower, not wrong.

## Quick recap

1. A cache is worth it when work is expensive, repeated, and may be slightly stale.
2. The hit ratio decides everything: 90 % cuts database load tenfold, 99 % a hundredfold.
3. Default to cache-aside: read the cache, fall back to the database, fill, and delete on write.
4. Always set a TTL, with a random part.
5. Plan for stampedes with single flight, stale-while-revalidate, or early refresh.
6. Cache "not found" briefly and watch for hot keys.
7. Measure hit ratio, latency, and evictions, and treat the cache as optional.

## Sources

1. IETF, [RFC 9111: HTTP Caching](https://www.rfc-editor.org/rfc/rfc9111).
2. IETF, [RFC 5861: HTTP Cache-Control Extensions for Stale Content](https://www.rfc-editor.org/rfc/rfc5861). `stale-while-revalidate` and `stale-if-error`.
3. Redis documentation, [Key eviction](https://redis.io/docs/latest/develop/reference/eviction/). The policies, and the approximated LRU and LFU.
4. Nishtala et al., [Scaling Memcache at Facebook](https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/nishtala), NSDI 2013. Leases against stale sets and thundering herds.
5. Vattani, Chierichetti and Lowenstein, [Optimal Probabilistic Cache Stampede Prevention](https://www.vldb.org/pvldb/volumes/8/paper/Optimal%20Probabilistic%20Cache%20Stampede%20Prevention), VLDB 2015. The XFetch algorithm.
6. Amazon Builders' Library, [Caching challenges and strategies](https://aws.amazon.com/builders-library/caching-challenges-and-strategies/).
7. Wikipedia, [Cache stampede](https://en.wikipedia.org/wiki/Cache_stampede) and [Cache replacement policies](https://en.wikipedia.org/wiki/Cache_replacement_policies).

Practise this topic: System Design System Design › Reliability and scale

More guides