Caching Strategies: Cache-Aside, Write-Through, Write-Behind and Cache Stampede

Version note: The code in this post was built and run with C# 14 and .NET 10; the examples ran with StackExchange.Redis 3.4.31 against Redis 7.4.

Guess First

Bookstore's book detail page is filled by an expensive query that combines the book, author, price, stock and review count; the query takes 50 ms. The team put a Redis cache in front with cache-aside: look in Redis first, otherwise read from the database and write to Redis with a 10-minute TTL (time to live). On campaign morning Dune's page is on the home page and gets opened hundreds of times a second.

At 10:00:00 Dune's cache entry expires, and at that exact moment 200 requests arrive for the same page. How many queries reach the database: 1 or 200? And if the team "warmed" 10,000 books into the cache with a single script before the campaign, what happens ten minutes later?

Where Does a Cache Live?

A cache keeps the result of expensive work in a cheaper and faster place so it can be reused. The latency table in the series' second post explained why caches work: reading from memory is orders of magnitude faster than the network and disk. There are six places a cache can sit on a request's path:

browser        Cache-Control: max-age         the user's own device
CDN            s-maxage, purge API            edge close to the user
gateway        output cache / response cache  in front of the app
application    IMemoryCache (in-process)      each instance's own memory
distributed    Redis                          shared by all instances
database       buffer pool, plan cache        inside the engine

How close to the source a request is answered decides how cheap it is. A request answered at the CDN (Content Delivery Network) never reaches the server; one answered from application memory never touches the network. The cost rises in the same order: a cache far from the source is harder to invalidate. You cannot recall a copy in a browser; you can only wait for it to expire.

The .NET APIs (Application Programming Interface), namely IMemoryCache, IDistributedCache, output caching and HybridCache, are covered in the ASP.NET Core Web API series posts "Caching in ASP.NET Core Web API: IMemoryCache, Redis and Response Caching" and "What's New in .NET 9: Built-in OpenAPI, Scalar and HybridCache in ASP.NET Core", and in the upcoming Caching series in the Backend category. This post looks at the strategies independently of any library, which is why the code uses StackExchange.Redis directly.

Read and Write Strategies

Depending on how you make the cache talk to the database there are five common strategies:

In web applications the most common is cache-aside; the Cloud Design Patterns catalog on Microsoft Learn also describes it under this name. Its advantage is that the cache is not required for the system to be correct: if Redis goes down the application gets slower but keeps working. Write-behind does the opposite and makes the cache part of the data path; it works for counters, view counts and other places where losing a few writes is fine, not for orders and payments.

Cache-Aside in Code

Cache-aside for Bookstore's book detail:

// cache-aside: cache first, otherwise the database, then write to the cache
public async Task<BookDetail> GetAsync(int id)
{
    RedisValue cached = await cache.StringGetAsync($"book:{id}");
    if (cached.HasValue)
        return JsonSerializer.Deserialize<BookDetail>(cached.ToString())!;

    BookDetail book = await db.FindAsync(id);
    await cache.StringSetAsync($"book:{id}", JsonSerializer.Serialize(book), Ttl);
    return book;
}

BookRepository.FindAsync is a fake that waits 50 ms, returns a BookDetail and counts how many times it was called. Three reads in a row:

read 1: Dune, db calls so far = 1
read 2: Dune, db calls so far = 1
read 3: Dune, db calls so far = 1

The first read went to the database, the next two came from Redis. So far so good; the problems start with concurrency.

TTL, Eviction and Invalidation

An entry leaves the cache in three ways. The TTL expires; that is the promise "I show data at most this old". Memory fills up and the eviction policy throws an entry out: LRU (Least Recently Used) evicts the one not read for the longest time, LFU (Least Frequently Used) the one read least often. Redis' default maxmemory-policy is noeviction; so when it reaches the maxmemory limit it evicts nothing and rejects writes with an error. In a Redis you use as a cache, don't forget to set it to allkeys-lru or allkeys-lfu. The third way is invalidation: deliberately deleting or updating the cached copy when the data changes.

The most robust form of invalidation is "write, then delete": when the price changes, update the database, then delete book:42 in Redis and let the next read load fresh data. Deleting is safer than updating; if two concurrent updates write to the cache in reverse order, the old price stays in the cache. But deleting has a race too: a read misses the cache and reads the old price from the database, at that moment a write updates the price and deletes the cache entry, then the read writes the old price it holds into the cache. The old price stays there until the TTL expires. The "Scaling Memcache at Facebook" paper published in 2013 solves this stale set problem with leases; in practice most systems accept the TTL as the upper bound of this race.

Here the two roles of the TTL separate: memory management and a consistency bound. For a book description, data 10 minutes old is fine; for a price maybe 1 minute; for stock a cache may not be appropriate at all. This is the cache's effect on consistency: every place you put a cache, you have answered the question "how stale is acceptable?". The theoretical framework for this question is in the consistency models post of the upcoming Distributed Systems Fundamentals series.

Cache Stampede

Back to the first opening question. 200 concurrent requests for the same book with an empty cache:

stampede, plain cache-aside: 200 db calls for 200 requests

200 requests, 200 queries. All of them looked at Redis, all of them missed, and all of them sent the same 50 ms query to the database. This is called a cache stampede, or thundering herd: the moment a popular entry expires, all the load the cache was protecting hits the database at once. Combine it with the connection pool math from the series' first post: 200 concurrent queries fill a pool of 100 on their own.

The first remedy is request coalescing (single-flight): only one load runs at a time for the same key, and the other requests wait for its result.

private readonly ConcurrentDictionary<int, Lazy<Task<BookDetail>>> _inFlight = new();

// only one load per key at a time; the others await its result
public async Task<BookDetail> GetCoalescedAsync(int id)
{
    RedisValue cached = await cache.StringGetAsync($"book:{id}");
    if (cached.HasValue)
        return JsonSerializer.Deserialize<BookDetail>(cached.ToString())!;

    Lazy<Task<BookDetail>> load = _inFlight.GetOrAdd(id, key => new(() => LoadAndStoreAsync(key)));
    try { return await load.Value; }
    finally { _inFlight.TryRemove(new KeyValuePair<int, Lazy<Task<BookDetail>>>(id, load)); }
}

stampede, request coalescing: 1 db calls for 200 requests

Lazy<Task> is insurance against GetOrAdd being able to run the factory more than once: whoever gets into the dictionary, only one Task starts. Know the limit too: this coordination is in-process. In three-instance Bookstore at worst 3 queries go out, not 200; that is usually enough. If you want to guarantee a single query for the whole cluster, you need a short-lived lock in Redis (SET key value NX PX 5000), with those that fail to get the lock waiting briefly and reading the cache again. HybridCache, which arrived with .NET 9, gives in-process stampede protection out of the box.

The second problem is the second opening question: entries filled at the same time expire at the same time. We write 10,000 books with a single script, once with a fixed 10-minute TTL and once with a TTL with ±10% jitter, and read the remaining time from Redis:

public static TimeSpan WithJitter(TimeSpan ttl, double spread, Random rng) =>
    ttl * (1 - spread + rng.NextDouble() * 2 * spread);

plain  expiry between 599 s and 599 s, busiest second: 10000 keys
jitter expiry between 539 s and 659 s, busiest second: 109 keys

With a fixed TTL all 10,000 entries expire in the same second: ten minutes later, right in the middle of the campaign, 10,000 separate stampedes start at once. With jitter the expiry is spread over two minutes and the busiest second has 109 entries. A one-line change.

The third technique is refreshing before expiry. In the XFetch algorithm from Andrea Vattani, Flavio Chierichetti and Keegan Lowenstein's 2015 paper "Optimal Probabilistic Cache Stampede Prevention", every read triggers a recomputation with a small probability before the entry expires; the probability grows as expiry gets closer and the longer the recomputation takes. The rule is one line: refresh if now - delta * beta * ln(rand()) >= expiry (delta is the computation time, beta a tuning factor). A simulation for an entry that gets 1,000 requests per second and takes 0.5 seconds to compute:

// Vattani et al.: recompute before expiry when now - delta * beta * ln(rand) >= expiry
bool expired = now >= expiry;
bool refreshEarly = early && now - delta * beta * Math.Log(rng.NextDouble()) >= expiry;
if (expired || refreshEarly)
{
    recomputations++;
    refreshedAt = Math.Min(refreshedAt, now + delta);  // the value is refreshed when the first computation ends
}

plain  recomputations around expiry: 500
xfetch recomputations around expiry: 1

With plain expiry, all 500 requests arriving in the half second until the new value is ready attempt a recomputation. With XFetch a single request triggers the refresh before expiry and the entry is never empty. No lock, no coordination; the cost is that the entry gets refreshed a little before its TTL.

Hot Keys

A stampede is a momentary problem; a hot key is a lasting imbalance. Imagine all campaign traffic going to the same book: in a Redis cluster keys are spread across slots, slots across nodes, and a single key always lives on a single node. In a 10-node cluster, whichever node holds Dune's key, that node's CPU (Central Processing Unit) or network becomes the ceiling for the whole cluster.

When Redis runs with the allkeys-lfu policy it keeps an access frequency counter per key, and redis-cli --hotkeys can scan it. The summary of the real output after sending 50,000 reads to Dune and one read each to 1,000 other books (all the other lines are 6):

-------- summary -------

Sampled 21001 keys in the keyspace!
hot key found with counter: 110	keyname: "book:42"
hot key found with counter: 6	keyname: "book:1563"
hot key found with counter: 6	keyname: "book:1870"

The counter is logarithmic: Redis starts a new key at 5 and lowers the chance of incrementing as the counter grows. Books read once sit at 6, Dune read 50,000 times at 110. So the counter is not a request count but a signal for ranking.

There are three common remedies for a hot key. The first is a short-lived L1 (level 1, in-process) cache inside the application: keeping Dune in each instance's memory for 5 seconds cuts reads to Redis to one per second per instance; the cost is 5 extra seconds of staleness. The second is replicating the key: writing eight copies from book:42#0 to book:42#7 and picking one at random when reading spreads the load over eight slots; the cost is deleting eight keys on invalidation. The third is replicas for reads. Whichever you pick, measure first; you find a hot key with a counter, not a guess.

Bookstore's Book Detail Page: A Multi-Layer Design

Putting the pieces together gives a design like this for the book detail page:

layer        what                          TTL            invalidation
browser      cover image                   1 day          new file name per version (cover-v3.jpg)
CDN          cover image, static files     1 day          purge on change (rare)
CDN          GET /api/books/42 (JSON)      s-maxage=30    none, short TTL is the bound
app (L1)     hot books, in-process         5 s + jitter   none, short TTL is the bound
Redis (L2)   BookDetail                    10 min +- 10%  delete on BookPriceChanged
database     source of truth               -              -
stock        never cached on this page     -              read live at checkout

When a price changes, Catalog publishes the BookPriceChanged event and a handler deletes the entry in Redis; the copies in L1 and the CDN stay at most 5 and 30 seconds stale. That is the number to discuss with the marketing team: "a price change reaches everyone within 30 seconds at most". Stock is never cached on this page, because wrong stock information can turn into an order; checkout always reads it live. At Bookstore's 200 requests per second peak, almost all reads of Dune are served from L1 and the CDN, and Redis and the database see only the books at the edges.

Common Pitfalls

Making the cache part of correctness. When Redis goes down the system should slow down, not stop; with cache-aside there should be a code path that catches Redis errors and falls back to the database.

Giving every entry the same TTL. A cache warmed in bulk empties in the same second; add jitter to the TTL.

Not accounting for stampedes on popular entries. The expiry of the most-read entry is the most expensive moment; use request coalescing or early refresh.

Updating instead of deleting. If two concurrent writes reach the cache in reverse order the old value stays; delete after writing and leave loading to the next read.

Using Redis as a cache with noeviction. When memory is full new entries cannot be written and the application starts getting errors.

Caching everything. Writing data that is read once into the cache fills memory and lowers the hit rate; for values like stock and balances wrong data is more expensive than slow data.

A Small Experiment

★☆☆ Run the stampede example with 2,000 requests and raise BookRepository.FindAsync to 500 ms. How does the gap between plain cache-aside and coalescing change? Measure the total time too.

★★☆ In the XFetch simulation set beta to 0.5 and 2. How do the number of recomputations and how long before expiry the first refresh happens change? What is the cost of a larger beta?

★★★ Make GetCoalescedAsync work across several instances: take a short lock in Redis with SET NX PX, and let requests that fail to get the lock wait 20 ms and read the cache again. What happens if the instance holding the lock crashes during the query, and what do you base the PX duration on?

The cache took reads off the database, but writes and reads that don't fit in the cache still go to a single database. In the next post we scale the data layer itself: replication, the read-your-writes problem with read replicas, sharding, and the SQL (Structured Query Language) vs NoSQL question.