Caching strategies

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

17 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:

The work is expensive. A slow query, a call to another service, a rendered page, a computed ranking.
The same result is wanted again and again. A few popular items get most of the requests.
A slightly old answer is acceptable. Or you can tell exactly when the answer changes.

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 ratio	Average latency	Load on the database
0 % (no cache)	20 ms	100 %
90 %	0.9 × 1 + 0.1 × 21 = 3.0 ms	10 %
99 %	0.99 × 1 + 0.01 × 21 = 1.2 ms	1 %

Going from 90 % to 99 % barely changes latency but cuts the database load by another factor of ten. 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

Browser and CDN are controlled with HTTP headers: Cache-Control, ETag, Vary. They are great for static files and public pages, and the standard is RFC 9111 [1]. stale-while-revalidate lets a cache answer with an old copy while it fetches a new one in the background [2].
In-process cache (a map or LRU in your app's memory) is the fastest: no network. But each server has its own copy, so the copies disagree, and memory is limited to the server's.
Distributed cache (Redis, Memcached) is shared by all servers, so everyone sees the same entries. It costs a network hop (typically well under a millisecond inside one data centre) and it is one more system to run.
The database's own cache (the buffer pool) keeps recently read pages in memory. It helps, but it does not save you the query work or the connection.

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.

Pattern	Read	Write	Good for	Watch out for
Cache-aside (lazy loading)	App checks the cache; on a miss, loads from the database and fills the cache	App writes the database, then deletes the cached key	The default for most apps	Stale data after races; a cold cache is slow
Read-through	Same as cache-aside, but the cache library loads from the database itself	Often combined with write-through	Simpler app code	Needs a cache that supports loaders
Write-through	n/a	Write goes to the cache, which writes to the database before answering	Data read right after it is written	Slower writes; caches data that may never be read
Write-behind (write-back)	n/a	Write goes to the cache; the database is updated later, in batches	Very high write rates, counters	Data loss if the cache dies before the flush
Write-around	n/a	Write goes straight to the database, skipping the cache	Data written once and rarely read	The 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), and a cache that is down must not take the app down with it.

from redis.exceptions import RedisError

# r is a redis.Redis client


def get_user(user_id):
    key = f"user:{user_id}"
    try:
        cached = r.get(key)
        if cached is not None:
            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
    if user is not None:
        ttl = 300 + random.randint(0, 60)            # the random part spreads out expiry
        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
    r.delete(f"user:{user_id}")                  # then drop the cached copy

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 := 300*time.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
	}
	return rdb.Del(ctx, "user:"+id).Err() // then drop the cached copy
}

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
  await redis.del(`user:${id}`); // then drop the cached copy
}

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
    await _redis.KeyDeleteAsync($"user:{id}");           // then drop the cached copy
}

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]. 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]. 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.

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.
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.
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.
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:

Diagram: A stale value written back after the delete

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]. 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 failures account for most cache outages [6]. All are about many requests arriving at the database at once.

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.

Diagram: Without protection every waiting request runs the query

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]). 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]:

import math
import random
import time


def should_refresh_early(expiry, recompute_seconds, beta=1.0):
    # log(random) is negative, so this moves "now" forward by a random amount
    # that is larger when recomputing is slow
    return time.time() - recompute_seconds * beta * math.log(random.random()) >= expiry

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. 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.
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.

8. 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.

9. 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.
Say that the cache must be optional: if it fails, the system gets slower, not wrong.

Quick recap

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

Sources

IETF, RFC 9111: HTTP Caching.
IETF, RFC 5861: HTTP Cache-Control Extensions for Stale Content. stale-while-revalidate and stale-if-error.
Redis documentation, Key eviction. The policies, and the approximated LRU and LFU.
Nishtala et al., Scaling Memcache at Facebook, NSDI 2013. Leases against stale sets and thundering herds.
Vattani, Chierichetti and Lowenstein, Optimal Probabilistic Cache Stampede Prevention, VLDB 2015. The XFetch algorithm.
Amazon Builders' Library, Caching challenges and strategies.
Wikipedia, Cache stampede and Cache replacement policies.

Practise this topic: Resilience & Scalability Caching System Design

More guides