System Design Primer · llms.txt
Written for this site, not part of The System Design Primer. The sources it draws on are listed under Further reading.
Putting an in-memory cache in front of a database is usually the first fix anyone suggests when queries get slow. The idea fits in one sentence: check Redis, and if the key isn't there, query the database and store the result in Redis with a one-hour TTL.
Most of the trouble comes later, in production. When a service takes 50,000 requests a second, one hot key expiring can send thousands of identical queries to the database at once (a thundering herd). A cache restart, or a batch of keys that all expire together, can do the same thing across the whole key space (a cache avalanche). Requests for IDs that don't exist skip the cache every time and land on the database (cache penetration). And two writers updating the cache and the database in different orders can leave the cache holding a stale value until its TTL runs out.
This chapter covers those three failure modes and their standard fixes, where caches sit in a system, how Redis is built and how it compares with Memcached, Redis Sentinel and Redis Cluster with its 16,384 hash slots, and how to keep a cache consistent with the database, ending with invalidation driven by change data capture (CDC). It's a companion to the primer's cache chapter and builds on reliability patterns.
All three failure modes end the same way: requests the cache was supposed to absorb reach the database instead, faster than it can serve them.
A cache stampede happens when a very popular key, such as the front-page story on a news site, expires or is evicted. Every request that arrives before someone puts the value back is a miss, and every miss runs the same query.
Some numbers, as an illustration. Say the key gets 10,000 reads a second and takes 200 ms to rebuild from the database:
There are three common fixes.
On a miss, a request tries to take a short-lived lock for that key before going to the database. In Redis that's one command, SET lock:<key> <random-token> NX PX 5000, which succeeds only if the lock doesn't exist yet and expires on its own after 5 seconds in case the holder dies.
This costs a lock round trip on every miss and makes waiting requests slower, but the database sees one query instead of 2,000. Facebook's memcache paper describes a similar idea called leases: the cache itself hands out a token to the first missing client and tells the others to retry shortly.
The 2015 paper Optimal Probabilistic Cache Stampede Prevention by Andrea Vattani, Flavio Chierichetti and Keegan Lowenstein describes an algorithm called XFetch. Instead of waiting for the key to expire, each reader decides at random whether to refresh it early, and the chance of refreshing goes up as expiry gets closer.
Store two extra things with the value: delta, how long the last rebuild took, and expiry, the time the value expires. On every read:
if now − delta × beta × ln(rand()) ≥ expiry:
recompute the value, store it with a new expiry and a new delta
else:
return the cached valuerand() is a uniform random number in (0, 1]. Its natural log is zero or negative, so −delta × beta × ln(rand()) is a positive amount of time. That amount follows an exponential distribution with mean delta × beta.expiry − now).beta defaults to 1. Larger values refresh earlier; smaller values refresh later.When expiry is far away, the head start almost never covers the time left, so nobody refreshes. In the last few multiples of delta before expiry, the probability climbs quickly. With many readers, one of them is very likely to refresh before the key expires, so most readers never see a miss. Scaling by delta matters: a value that takes 2 seconds to rebuild starts refreshing much earlier than one that takes 20 ms.
It's probabilistic, so it doesn't guarantee a single refresh. Two readers can both win the draw at nearly the same moment, which just means two queries instead of one. A key read only rarely may still expire before anyone refreshes it, but a rarely read key can't cause a stampede anyway. The paper shows this exponential rule is the best trade-off between refreshing too early (wasted work) and too late (a stampede). No locks or coordination are needed. Teams often combine it with a lock as a backstop.
For a handful of known hot keys, don't let them expire at all. A background job rebuilds them on a schedule and overwrites the cache entry. Readers never miss. This works well for a small, known set of keys and doesn't scale to millions of them.
A cache avalanche is the same problem across many keys: a large share of the key space misses at the same time. Two common causes:
redis.set(key, value, ex=3600). At 03:00 every one of those keys expires within the same second, and all their traffic hits the database.Don't give a batch of keys the same TTL. Add a random amount (jitter) to each:
import random
def cache_set_with_jitter(redis, key, value, base_ttl=3600, jitter_pct=0.15):
# ±15% of one hour: somewhere between 3,060 and 4,140 seconds
spread = base_ttl * jitter_pct
ttl = base_ttl + random.uniform(-spread, spread)
redis.set(key, value, ex=int(ttl))The keys now expire spread over about 18 minutes instead of in one second, and the database sees a steady trickle of rebuilds.
For the restart case, jitter doesn't help. What helps is replicas that can take over with their data intact (see Sentinel and Cluster below), warming a new node before it takes traffic, and putting a circuit breaker or rate limit in front of the database so a burst of misses gets shed instead of taking it down.
Cache penetration happens when clients ask for keys that don't exist in the database at all, for example GET /users/-9999, or a scanner trying random IDs. The usual cache-aside code does this:
The cache never helps. Someone sending 20,000 made-up IDs a second sends 20,000 queries a second straight to the database.
When the database returns nothing, cache a marker for that key with a short TTL:
redis.set("user:-9999", "__none__", ex=60)For the next 60 seconds, requests for that ID get a 404 from the cache. Keep the TTL short, because the ID might be created later. This works well for repeated misses on the same IDs. It does little against random IDs, since each new ID is a new miss, and it fills the cache with markers.
A Bloom filter is a compact data structure that answers "is this key in the set?" with either "definitely not" or "probably yes". It's an array of m bits and k hash functions:
You size it for the false positive rate you want. About 9.6 bits per key gives a 1% false positive rate, so 100 million keys fit in roughly 120 MB.
To use it against penetration, add every ID to the filter when the row is created, and check the filter before the cache:
Two caveats. A plain Bloom filter can't remove keys, so deleted IDs stay "probably yes" until you rebuild it periodically (or use a variant such as a counting Bloom filter or cuckoo filter). And the filter must learn about a new ID before anyone asks for it, so add to it in the same code path that creates the row, or a new user can briefly get a 404.
Caches appear at several layers. The two you design for most often in a back end are a cache inside each application process and a shared cache on the network.
| Local, in-process (Caffeine, Guava, a plain LRU map) | Distributed (Redis, Memcached) | |
|---|---|---|
| Where it lives | In the application's own memory | Separate servers, reached over the network |
| Read latency | Well under a microsecond: a hash lookup in memory | Typically a few hundred microseconds to about a millisecond, mostly network round trip |
| Throughput | Limited by the app's CPU, often millions of lookups a second | Roughly 100,000 or more simple operations a second per Redis node |
| Consistency | Each server has its own copy, and copies can disagree | One copy per key, shared by every app server |
| Size | Limited by the process's memory, usually a few GB | Can grow to terabytes by adding nodes |
| Survives a deploy | No, it's empty after a restart | Yes |
Large systems often use both, as a two-tier cache:
The L1 takes the hottest keys off the network entirely, which also protects the L2 from a single hot key overloading one Redis node.
A single Redis process commonly handles more than 100,000 simple operations a second. Keeping data in RAM is part of the reason, but there are three others.
Redis runs every command on one thread.
INCR from two clients can't lose an update.The cost is that one slow command blocks everyone. KEYS * on a large database, or deleting a set with millions of members, stalls every client for its duration. Use SCAN and UNLINK (which frees memory in the background) instead.
Redis stores typed values, and picks a compact encoding when a value is small:
STRLEN is O(1).| Redis | Memcached | |
|---|---|---|
| Values | Strings, hashes, lists, sets, sorted sets, streams and more, with server-side operations on them | Opaque byte strings |
| Threads | One thread runs commands (I/O can use more) | Multi-threaded, so one process uses all cores |
| Persistence | Optional snapshots (RDB) and append-only log (AOF) | None, memory only |
| Replication and failover | Built in, plus Sentinel and Cluster | None; clients spread keys across servers with consistent hashing |
| Typical use | Cache plus counters, queues, rate limits, leaderboards, locks | A large, simple, fast key-value cache |
If all you need is a big cache of serialized objects, Memcached is simple and scales well on many-core machines. Most teams choose Redis because the data structures, replication and persistence let one system cover several jobs.
Redis offers two ways to run more than one node. They solve different problems: Sentinel keeps one dataset available, and Cluster splits the dataset across nodes.
Replication is asynchronous, so writes acknowledged by the old primary just before it failed can be lost in a failover.
Redis Cluster splits the key space across several primaries, each with its own replicas.
The key space is divided into 16,384 hash slots. Each key belongs to one slot:
slot = CRC16(key) mod 16384Each primary owns a set of slots. With three primaries, a default setup gives node A slots 0–5,460, node B slots 5,461–10,922 and node C slots 10,923–16,383.
Moving data between nodes means moving slots. Adding a node is a matter of handing it some slots from the others; keys never need to be rehashed.
Hash tags keep related keys together. If a key contains {...}, only the part inside the braces is hashed. {user:100}:profile and {user:100}:orders both hash user:100, so they land in the same slot. That matters because multi-key commands (MGET, MULTI/EXEC transactions, Lua scripts) only work when all their keys are in one slot; otherwise Redis returns a CROSSSLOT error.
Clients route requests themselves. A cluster-aware client keeps a copy of the slot-to-node map and sends each command straight to the right node. If the slot has moved, the node replies with a redirect such as -MOVED 3999 10.0.0.2:6379, and the client updates its map and retries there. While a slot is mid-migration, a node can answer -ASK instead, which redirects just that one request.
Why 16,384? The Redis author's explanation is about message size: nodes gossip a bitmap of the slots they own, and 16,384 bits is 2 KB, which keeps heartbeat messages small while still allowing far more slots than any realistic cluster has nodes (the recommended maximum is about 1,000 nodes).
When data changes, two questions come up: update the cache or delete the key? And touch the database first or the cache first? The wrong answers leave a stale value in the cache that nothing will correct until the TTL expires.
Two writers change the same user at nearly the same time:
The database says "Bea" and the cache says "Ann", and every reader sees "Ann" until the TTL expires. The two writes reached the two systems in different orders, and nothing ties them together.
The usual pattern is cache-aside (also called lazy loading), with deletes instead of updates:
Deleting has no ordering problem between writers: two deletes in any order leave the same result, an empty slot. The next read loads whatever the database holds at that moment.
Deleting before the database write has a wide race window:
user:1 from the cache, then starts its database transaction to change "Alice" to "Bob".user:1.The database says "Bob", the cache says "Alice", and nothing will fix it before the TTL. The window is the whole length of A's transaction, which can be many milliseconds, so this happens regularly under load.
Delete-after-commit still has a race, just a much narrower one. A reader misses, reads the old value from the database, and then stalls. Meanwhile a writer commits and deletes the key. Then the reader wakes up and writes the old value into the cache. For this to happen, the reader's database read has to happen before the commit and its cache write after the delete, which means the reader was slower than the whole write. It's rare, but it does happen at scale. Common defenses:
Delete-after-commit has one more gap. If the app server crashes, or loses its connection to Redis, after the commit but before the DEL, the key is never deleted. You can retry, but a crash loses the retry too.
Change data capture (CDC) moves invalidation out of the application. The database already records every committed change in its log (the PostgreSQL write-ahead log or the MySQL binlog). A CDC tool reads that log and turns each change into an event.
How it works:
<prefix>.<schema>.<table>. The event carries the row's key, and the before and after values.DEL user:42 in Redis.What you get:
DEL succeeds. If it crashes, it restarts from the last committed offset and replays some events. Delivery is at least once, and since deleting a key twice is harmless, the duplicates don't matter.What it costs: a pipeline (Kafka, Kafka Connect, Debezium) you have to run and monitor, and invalidation that lags the commit by the pipeline's delay, usually milliseconds to a second or two. During that lag readers can see the old value, so CDC gives you eventual consistency, not read-your-writes. It also doesn't close the stale-fill race described above, so keep TTLs. The event streaming chapter covers Kafka in more depth.
Every reader runs the check now − delta × beta × ln(rand()) ≥ expiry. Because −ln(rand()) is exponentially distributed, each reader draws a random head start whose average is delta × beta, where delta is how long the last rebuild took. If the head start reaches past the expiry time, that reader refreshes the value early and resets the expiry. Far from expiry the chance is close to zero; in the last few multiples of delta it rises quickly. With a hot key, many readers draw every second, so one is very likely to refresh before the key expires, and the rest never see a miss. No coordination is needed, though two readers occasionally refresh at once.
Scaling by delta matters because the refresh has to finish before the key expires. A value that takes 2 seconds to build needs to start refreshing seconds ahead; one that takes 20 ms only needs a few tens of milliseconds.
At 03:00 all 5 million keys expire within about a second. Every request for any of them misses at once, and the database gets the whole read load the cache was absorbing: a cache avalanche. The fix is jitter: set each key's TTL to the base value plus a random offset, for example 3,600 s ± 15%, so the expirations spread over about 18 minutes and the database sees a steady stream of rebuilds instead of a wall.
If you delete first, any reader that arrives while the write transaction is still open misses the cache, reads the old committed value from the database, and puts it back in the cache. When the writer commits, the cache holds the old value and nothing will remove it before the TTL. The window is the whole transaction, so this happens often.
If you update first and delete after the commit, the only race needs a reader that read the old value before the commit and then wrote it into the cache after the delete, meaning the reader was slower than the entire write. That's much rarer. TTLs, a delayed second delete, or leases handle what's left.
Redis Cluster computes CRC16(key) mod 16384 to get one of 16,384 hash slots, and each primary owns a set of slots. Clients cache the slot map and follow MOVED redirects when it changes. By default, user:42:profile and user:42:orders hash to unrelated slots, probably on different nodes, and a multi-key command across them fails with a CROSSSLOT error. Name them {user:42}:profile and {user:42}:orders: when a key contains braces, only the text inside is hashed, so both keys land in the slot for user:42 and MGET works.
Delete-after-commit only works for writes that go through your code. The batch job and the other service don't know about your cache, so their changes never trigger a delete, and the cache serves stale users until TTLs expire. CDC reads the database's own log, so every committed change produces an invalidation event no matter who wrote it. It also survives crashes: the worker resumes from its last Kafka offset, and repeating a DEL is harmless. The cost is running the pipeline and accepting a short lag before invalidation.
MOVED and ASK redirects.Previous: Cache · Next: Asynchronism