Cache penetration and avalanche: when the cache can no longer shield the database Intermediate

Symptoms

The GET /products/{id} API uses cache-aside on Redis, with PostgreSQL as the source of truth. Three incidents produce the same feeling of “there is a cache, yet the DB is still overloaded”:

Incident	Hit rate	DB QPS	Accompanying signs
Bot requests random nonexistent ids	Drops, stays low	Rises with bot traffic	Queries by id return 0 rows
Job warms 50,000 keys at 00:00, TTL 1 hour	Falls exactly at 01:00, 02:00…	Peaks repeat every TTL cycle	expired_keys jumps in the same minute
Redis restart	Near 0, recovers gradually	Spikes, then decays	uptime_in_seconds resets

Hit rate = keyspace_hits / (keyspace_hits + keyspace_misses) (INFO stats), computed from per-minute deltas.

What to choose? (summary first)

	Stampede	Penetration	Avalanche
Key	One hot key	Key that does not exist in the DB	Very many keys
Why it misses	Just expired, many requests load it at once	Nothing to cache	Expired together or the cache was wiped
Main remedy	Singleflight, lock, XFetch	Validation, empty-value caching, bloom filter, rate limiting	TTL jitter, spread-out warming, HA, DB load limits

Situation	Choose	Condition
Malformed or out-of-range id	Validate at the edge, return 400/404	Clear id rules exist
Same nonexistent id requested repeatedly	Empty-value cache, short TTL	DEL the empty key when the row is created
Random, non-repeating ids	Bloom filter + rate limiting	Update the filter when rows are created
Many keys loaded at once	TTL jitter, spread-out warming	Applies almost always
Redis loses all its data	Replica + failover, cap concurrency to the DB	The DB must survive an empty cache

Reproduction

The demo runs on Redis 7.4.9 and PostgreSQL 17 from examples/docker-compose.yml; the table demo_cache_penetration.products holds ids 1..10000.

npx ts-node src/cache-penetration-avalanche/penetration.ts   # run inside examples/
npx ts-node src/cache-penetration-avalanche/avalanche.ts

Penetration: 1,000 requests for nonexistent ids

The demo counts the real queries sent to PostgreSQL:

A. 1,000 requests, 1,000 distinct random ids (bot):
  plain                  DB query: 1000   empty keys in Redis: 0
  negative               DB query: 1000   empty keys in Redis: 1000
  bloom                  DB query:   19   empty keys in Redis: 0
  bloom+negative         DB query:   19   empty keys in Redis: 19

B. 1,000 requests, 50 nonexistent ids, each repeated 20 times:
  plain                  DB query: 1000   empty keys in Redis: 0
  negative               DB query:   50   empty keys in Redis: 50
  bloom                  DB query:   20   empty keys in Redis: 0
  bloom+negative         DB query:    1   empty keys in Redis: 1

Bloom filter (95851 bits, k=7, 11982 bytes in Redis):
  false negatives over 10000 real ids: 0
  false positives over 100000 missing ids: 958 (0.96%)

• Empty-value caching is useless against random ids: still 1,000 queries, plus 1,000 junk keys. It only helps when ids repeat (B: 1,000 → 50).
• What the bloom filter lets through are false positives (19/1,000, small sample). Combining both means a repeated false-positive id hits the DB only once.

Avalanche: 50,000 keys, fixed TTL vs. jitter

TTL is shortened: 10 seconds instead of 1 hour (a 1:360 ratio), and jitter of 0..5 seconds corresponds to 0..30 minutes. Every second the demo runs EXISTS on every key and counts the ones that vanished:

Fixed TTL 10 s: warming 50000 keys took 109 ms
  second 10–11:  50000 keys expired ##################################################

TTL 10 s + random jitter 0..5 s: warming 50000 keys took 113 ms
  second  9–10:     12 keys expired #
  second 10–11:   9692 keys expired ##########
  second 11–12:  10046 keys expired ###########
  second 12–13:   9991 keys expired ##########
  second 13–14:   9877 keys expired ##########
  second 14–15:  10013 keys expired ###########
  second 15–16:    369 keys expired #

Per-second counts vary between runs; the shape is stable: one bar of 50,000 versus five bars of ~10,000.

Root cause

Penetration: cache-aside only stores what it can read from the DB. A nonexistent id has nothing to store, so every request continues to the DB.

Avalanche: keys written within the same short window with the same TTL expire within the same window. The reload also lands at once, so the peak repeats every cycle.

Same 00:00 warm job: a fixed TTL packs 50,000 expirations into one minute, a jittered TTL spreads them over 30 minutes

◀ Prev▶ PlayNext ▶↺ RestartStep 1/5

The job writes 50,000 keys in about one minute, every key with a 3600 s TTL, so expirations cluster around 01:00.

Time	Redis A (fixed TTL)	Redis B (TTL + jitter)
00:00–00:01	50,000 keys, expiring 01:00–01:01	50,000 keys, expiring spread over 01:00–01:31
01:00–01:01	All expire, ~830 keys/s to reload	~1/30 of the keys expire
01:01–01:31	Reloaded, new expirations still coincide	~28 keys/s to reload

The keys/s figures are estimates (50,000/60 and 50,000/1,800), not measurements.

A Redis restart is the most severe variant: the entire keyspace is lost when persistence is off or on failover to an empty node (persistence RDB/AOF).

How to detect it

redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses|expired_keys"
redis-cli INFO server | grep uptime_in_seconds
redis-cli DBSIZE

• Penetration: misses stay high; many distinct ids from few IPs.
• With empty-value caching: the hit rate looks good again, because Redis counts a GET on an empty key as a hit. You need a separate “not found from cache” metric.
• Avalanche: the expired_keys delta has sharp peaks exactly at the TTL cycle, matching the DB QPS peaks.
• Restart: small uptime_in_seconds, unusually low DBSIZE.

Immediate mitigation

While the incident is happening

Penetration: rate limit by IP/API key, return 404 early for out-of-range ids. Avalanche/restart: cap concurrent queries to the DB, serve stale data or fail fast. Do not rerun the full warm job: it creates another wave of load.

Long-term prevention

Loading diagram…

Penetration

1. Validate at the edge: the id is a positive number within a sane range, or a valid UUID. This cannot block well-formed ids that don’t exist.
2. Rate limit by IP or API key (rate limiting): the only layer that caps the bot’s total request volume.
3. Cache empty values (negative caching), with a short TTL such as 60 seconds. Risks: junk ids fill memory, and an empty key hides a newly created row.
4. Bloom filter containing every real id. A “no” means definitely absent; a “yes” can be wrong at the chosen rate.

The demo reproduces the risk of an empty key hiding a new row:

Create product 10001 after this id was cached as empty:
  read again, key not DELeted : null
  read again, after DEL key   : { id: '10001', name: 'new product' }

Creating a product but forgetting the empty key

✕ Common

await db.insertProduct(p); // empty key product:{id} lingers until the TTL ends

✓ Prefer

await db.insertProduct(p);          // 1. commit
await redis.del(`product:${p.id}`); // 2. delete the empty key
await bloomAdd(p.id);               // 3. add to the bloom filter

Why

Write the DB first, then delete the cache entry and update the filter.

Operating a bloom filter:

• Sizing per Redis: m = n × −ln(p) / ln(2)² bits, k = ceil(−ln(p) / ln 2). With n = 10,000, p = 1%: 95,851 bits (~12 KB), k = 7.
• Redis Open Source 8 ships BF.ADD and BF.EXISTS; earlier versions need Redis Stack. Redis 7.4 OSS does not have them: the demo container returns ERR unknown command 'BF.ADD', so the demo implements it with SETBIT/GETBIT.
• Elements cannot be deleted: a deleted product still “may exist”. Rebuild periodically from the DB.
• Load every id before enabling blocking; any missing id gets a wrong 404.

Avalanche

• TTL jitter: ttl = base + random(0, spread). N keys written together expire at an average of N / spread keys per second. With 3600 + random(0, 1800): about 28 keys/s for 50,000 keys.
• Spread-out warming: split into batches with pauses, or warm only the top keys.
• Redis HA: replica + Sentinel or Redis Cluster to fail over to a node that already has the data (replication is asynchronous, so the most recent writes may be lost).
• Cap concurrency to the DB: a semaphore for loaders, a circuit breaker that opens when DB timeouts rise; the overflow gets stale data or fails fast.
• Stale fallback data: an old copy in a local cache or a stale: key with a longer TTL, used while the DB is throttled.
• A single hot key still needs singleflight or a lock: jitter does not coalesce requests for one key (stampede).

Production checklist

1. Validate ids before touching the cache or the DB; rate limit read endpoints.
2. Empty-value caching with a short TTL; the row-creation flow DELs the empty key.
3. Bloom filter (if used): n and p with headroom, updated when rows are created, with a rebuild job.
4. Every TTL has jitter; warm jobs run in batches.
5. Redis has replicas and failover; DB QPS with an empty cache has been measured in staging.
6. Loaders have a concurrency limit, timeouts, and a fallback.
7. Dashboard: hit rate, expired_keys delta, DB QPS, not-found from cache.

Self-check

1. Why does empty-value caching reduce queries in scenario B but not in A?
2. If the bloom filter is missing a real id, what does the user see?
3. With ttl = 3600 + random(0, 1800) and 50,000 keys written at once, how many keys expire per second?
4. Why can the hit rate look good while penetration is happening?

Summary

Key takeaways

• Stampede: one hot key loaded in duplicate; penetration: keys not in the DB; avalanche: very many keys lost at once
• Empty-value caching only helps when ids repeat; random ids need a bloom filter, validation, and rate limiting
• A bloom filter has no false negatives, has false positives, and cannot delete elements
• ttl = base + random(0, spread) spreads N expirations to about N / spread per second
• The DB must survive an empty cache: HA, concurrency limits, stale fallback data

References

• Redis — Bloom filter: sizing formula, false positives.
• Redis Open Source 8.0 release notes: Bloom filter built in since 8.0.
• Redis — Sentinel: failover.
• AWS Builders’ Library — Caching challenges: negative caching, cold caches.