Skip to content
notes.vinhnq.com

Search

System DesignSenior21 min read

Cache failures: avalanche, breakdown, penetration, hot keys and big keys

Review 17 cards
On this page

Caching series: 1. Cache-aside and invalidation · 2. Cache failures: avalanche, breakdown, penetration · 3. Reviewing a Redis distributed lock

Post 1 was about the cache being wrong; this one is about the cache failing to absorb the load, so traffic lands on the database and it falls over even though the code has no bug. After reading, you can recognise six failures, fix each one and pick an eviction policy. Read post 1 first (cache-aside, TTLs); Redis internals (expiry, replication, Cluster) are in the Redis series.

1. Cache avalanche: the cache goes down under load

Key idea: if the cache dies at peak, a database sized for 1–5% of the load gets 100% and goes down with it. The fix has three layers: an HA cache, database protection, and recovering the cache before reopening traffic.

Causes: a node dies, a bad config, a network partition. The database pool drains, requests time out, and client retries add more load. When the cache comes back it’s empty, so the database keeps getting hammered until it refills.

flowchart LR
  U[10,000 req/s] --> App
  App -->|GET| R[(Redis cluster)]
  R -.-x|down| App
  App ==>|10,000 queries/s<br/>instead of 100| DB[(Database)]
  DB -.-> X[pool exhausted,<br/>timeouts, down]
  • An HA cache (high availability: keeps working when a node dies): Redis Sentinel (primary + replica, automatic failover) or Redis Cluster (shards with replicas). Losing a node costs part of the keyspace or a few seconds of failover.
  • Protect the database: a rate limit or a bulkhead (a partition that caps concurrent cache-miss queries to the database). A circuit breaker around Redis calls: while Redis is failing, error out immediately instead of waiting for a timeout. Degrade non-essential features (fail fast or return default data).
  • Recover the cache: enable persistence (RDB snapshots, AOF) so a restarted node comes back with data; warm up (preload) hot keys before opening traffic; add an L1 local cache to absorb the hottest data while Redis is away.

2. Cache avalanche: many keys expire at the same time

Key idea: the cache doesn’t need to die; it’s enough for a huge number of keys to expire in the same second. The fix is jitter: add a random offset to the TTL so expiry times spread out.

Example: a warm-up job loads a million keys at 00:00 with the same TTL = 3600, so at exactly 01:00 they all vanish. Or a deploy flushes the cache, every key reloads within a few minutes, and they keep expiring together from then on.

static long ttlWithJitter(long baseSeconds, double jitterRatio) {
    long spread = (long) (baseSeconds * jitterRatio);
    return baseSeconds + ThreadLocalRandom.current().nextLong(-spread, spread + 1);
}
// ttlWithJitter(600, 0.1) -> [644, 623, 553, 645, 651]: expiries spread over 540–660 seconds
Jitter with Spring Cache on Redis: TtlFunction and the sync = true trap

Spring Data Redis 3.2+ lets you compute the TTL per entry with a TtlFunction:

RedisCacheConfiguration.defaultCacheConfig()
    .entryTtl((key, value) -> value == null
        ? Duration.ofSeconds(30)                                        // empty entry: short
        : Duration.ofSeconds(600 + ThreadLocalRandom.current().nextLong(-60, 61)));  // 10 min ± 10%

3. Cache breakdown: a hot key expires

Key idea: just one key, but a hot one; when it expires, thousands of requests miss together and all run the reload query. Fix it by letting only one request reload (mutex, single-flight) or by never letting the hot key expire (background refresh).

Hot keys: the home page, a flash-sale product, config. A 200 ms query times 2,000 copies is enough to overload the database. Other names: cache stampede, thundering herd (a crowd of requests charging at one resource). I measured it with Caffeine and 100 virtual threads missing the same key, with a loader that simulates a 200 ms query:

naive check-then-put, 100 threads: DB calls = 100
cache.get(key, loader), 100 threads: DB calls = 1

Four fixes:

  • (a) No TTL, background refresh. Hot keys never expire (or have a very long TTL); a scheduled job reads the database and overwrites the value before it gets stale, so there’s never a miss.
  • (b) A mutex: only one request reloads. A request that misses tries SET lock:key token NX PX 3000. Whoever gets it reads the database and repopulates; the others wait briefly and re-read, or return the old value (how to write the lock correctly is in post 3).
  • (c) Single-flight inside the JVM. Collapse concurrent misses on the same key within one instance into one load. Caffeine does it for you: cache.get(key, loader) runs one loader per key; refreshAfterWrite reloads asynchronously while still serving the old value (stale-while-revalidate: serve the old copy, refresh in the background).
  • (d) Probabilistic early expiration (XFetch). Each request “rolls a die” to reload early, with odds that rise as expiry approaches, so usually only a handful reload, with no lock.
flowchart LR
  Job[Background job<br/>every 30 seconds] -->|read| DB[(DB)]
  Job -->|SET overwrite| R[(Redis<br/>hot keys, no TTL)]
  App[App: cache-aside] -->|GET| R
  App -->|write-around| DB
Writing single-flight yourself, and the XFetch formula

Single-flight: the other threads wait on a shared CompletableFuture.

final class SingleFlight<K, V> {
    private final ConcurrentHashMap<K, CompletableFuture<V>> inFlight = new ConcurrentHashMap<>();

    V load(K key, Supplier<V> loader) {
        var mine = new CompletableFuture<V>();
        var existing = inFlight.putIfAbsent(key, mine);
        if (existing != null) return existing.join();      // someone is already loading: wait for it
        try {
            V v = loader.get();
            mine.complete(v);
            return v;
        } catch (RuntimeException e) {
            mine.completeExceptionally(e);                   // waiters get the error instead of hanging
            throw e;
        } finally {
            inFlight.remove(key, mine);
        }
    }
}
// 200 virtual threads missing "product:1" at once -> loads = 1

XFetch: a request reloads early if now − delta × beta × ln(random()) ≥ expiry, where delta is how long the last load took. Because ln(random()) is negative, the left side is now plus a random amount, which crosses expiry more easily the closer it gets.

4. Cache penetration: keys that don’t exist

Key idea: a request for something in neither the cache nor the database is never populated by cache-aside, so it goes through to the database every time. Fix it with validation, short-TTL empty values and a Bloom filter.

Examples: GET /products/-1, random ids from a bot, a deleted product. Sending random ids goes straight through the cache (hence “penetration”).

  1. Cache an empty value: when the database finds nothing, still store a special value ("", 0, NullValue) with a short TTL (30–60 seconds), so it doesn’t hold memory for long and a record created later shows up soon.
  2. Validate requests: reject ids with the wrong format, negative or out of range, or with an invalid signature at the API, before touching the cache.
  3. Bloom filter: a probabilistic structure (a bit array + k hash functions) that answers “definitely not present” or “possibly present”. No false negatives, and false positives at a rate you choose. Put it in front of the cache: “definitely not present” means an immediate 404. A million ids at 1% false positives take only ~1.14 MB.
Sizing a Bloom filter, with real numbers

For n elements and false-positive rate p: bits m = −n·ln p / (ln 2)², hash functions k = (m/n)·ln 2. I implemented a simple BitSet-based Bloom filter with a million ids and p = 1%, then probed a million ids that don’t exist:

bloom m=9585059 bits (1.14 MB), k=7, false positive rate=0.0101, no false negatives=true

1.14 MB for a million ids: much cheaper than caching a million empty keys. On Redis, the RedisBloom module (BF.RESERVE, BF.ADD, BF.EXISTS) ships with Redis Stack and with Redis 8; on the JVM there’s Guava’s BloomFilter. A typical use: stopping bots that scan random codes in Designing a URL shortener, with a Bloom filter of every issued code.

5. Hot keys: a few keys pile onto one node

Key idea: Redis Cluster puts each key on exactly one node, so a hot key overloads one node while the others sit idle, and adding nodes doesn’t help. Fix it with a short-TTL local cache or by replicating the key.

The cluster maps keys to 16,384 slots (CRC16(key) mod 16384), each slot on one node. If product:34 and product:88 get 80% of the traffic and both sit on node 1, node 1 is overloaded.

flowchart LR
  App -->|80% of traffic| N1[Node 1<br/>product:34, product:88]
  App -->|10%| N2[Node 2]
  App -->|10%| N3[Node 3]
  • Replicate hot keys: store product:34#1 … product:34#N (different suffixes land in different slots); the client reads a random suffix. In exchange, invalidation has to delete all N copies.
  • A local cache: keep hot keys in Caffeine on each instance with a 1–5 second TTL: Redis then gets a few requests per second per pod for that key.
Reading from replicas, detecting hot keys, Redis 6 client-side caching
  • Read from replicas: ReadFrom.REPLICA_PREFERRED in Lettuce. The course’s sample config picks ReadFrom.UPSTREAM (primary only) to avoid lagging data, at the cost of not spreading read load.

Detection: redis-cli --hotkeys (needs an LFU policy) or client-side per-key metrics; avoid MONITOR in production.

6. Big keys: values that are too large

Key idea: a multi-MB value slows down itself and every other command, because Redis runs commands on one thread. Fix it by splitting, compressing, or moving large data to another store.

Most values are 1–2 KB, but product:34 holds 5 MB (every review embedded in the JSON). Consequences:

  • Timeouts: reading 5 MB takes tens of milliseconds, and other commands queue behind it.
  • Bandwidth: 1,000 reads/s × 5 MB = 5 GB/s, more than the network card can carry.
  • A partial update rewrites the whole value: adding one review means sending 5 MB again.
  • Slow reloads after eviction or expiry.

Fixes: split (hash fields per part, or product:34:reviews:page:1), compress (gzip, zstd, Snappy), and pick the right store: large files belong in object storage (S3) or a CDN, with the cache holding only a pointer.

More fixes, finding big keys, and a summary table of all six failures
  • A longer TTL so it’s reloaded less often.
  • Limit big keys: code review, alerts when a value exceeds a threshold such as 100 KB.
  • Finding big keys: redis-cli --bigkeys (by element count) and --memkeys (by memory, using MEMORY USAGE); both use SCAN, so they’re safer than KEYS.

Summary of all six failures:

Failure What happens Main fixes
Avalanche (cache down) the whole cache cluster dies under high load HA cluster, circuit breaker, rate limiting, warm-up
Avalanche (mass expiry) a huge number of keys expire at the same moment TTL + jitter
Breakdown one hot key expires, thousands of requests miss at once no expiry + background refresh, mutex, single-flight
Penetration the key is in neither the cache nor the database cache empty values, validation, Bloom filter
Hot key a few keys get most of the traffic, all on one node replicate the key, local cache
Big key a multi-MB value causes timeouts and saturates the network compress, split, use a different store

7. Out of memory: replacement policies

Key idea: at maxmemory, Redis follows maxmemory-policy; the default noeviction rejects writes. For a Redis that is purely a cache, pick allkeys-lru or allkeys-lfu.

Policy Behaviour
noeviction (default) rejects writes with an OOM error
allkeys-lru / volatile-lru evicts the least recently used key (among all keys / only keys with a TTL)
allkeys-lfu / volatile-lfu evicts the least frequently used key
allkeys-random / volatile-random evicts at random
volatile-ttl evicts the key closest to expiring
  • LRU (Least Recently Used, evict what was read longest ago): suits cases where what was just read is likely to be read again.
  • LFU (Least Frequently Used, evict what is read least often): suits things that stay popular, like a hot tweet, which one scan over old data shouldn’t push out.
  • W-TinyLFU (Caffeine): combines the two, and its hit rate is usually close to optimal.
  • A preloaded allowlist (flash sales): load the known product list ahead of time, with no TTL and no eviction, instead of hoping LRU guesses right.
Redis’s approximated LRU/LFU, W-TinyLFU, and where the allowlist lives
  • Redis does approximated LRU: it samples maxmemory-samples keys (5 by default) and evicts the oldest, with no global linked list.
  • Redis’s LFU uses an 8-bit logarithmic counter that decays over time (lfu-decay-time), so once-hot keys don’t stay forever.
  • Caffeine’s W-TinyLFU: a small LRU window for new keys, a main area split into probation and protected segments, and a frequency sketch that decides whether a new key is admitted at all. That’s why a scan doesn’t flush the hot keys.
  • Keep the preloaded allowlist on a separate instance or in a local cache, so the shared cache’s eviction can’t touch it.

Exercises

The local-cache homework from this lesson (an airport list with Caffeine) lives in post 3, together with a review of the reference solution.

Exercise 1: a flash-sale product page

Task (paraphrased): tonight at 8 pm, 50 products go on sale, with an expected 30,000 req/s to their detail pages, and the database handles at most 2,000 queries/s. Design the caching so the database survives.

Solution 1: allowlist, local cache, single-flight, bulkhead
  • A preloaded allowlist: at 7:50 pm a job loads the 50 products into Redis with no TTL; the displayed price and stock are overwritten by a job every 5 seconds (background refresh), so a breakdown can’t happen.
  • Hot keys: 50 keys × 30,000 req/s pile onto a few nodes; add a Caffeine local cache with a 2-second TTL on each pod. 40 pods × 50 keys × 0.5 reads/s = 1,000 Redis reads per second instead of 30,000.
  • Stampede: Caffeine’s cache.get(key, loader) so each pod loads each key only once.
  • Penetration: validate that the id belongs to the allowlist; any other id gets a 404 without touching the database.
  • Avalanche: other pages use jittered TTLs; a bulkhead caps concurrent cache-miss queries to the database, for example at 50.
  • Stock decrements never rely on the cache: UPDATE ... WHERE stock > 0 or an atomic DECR, see transactions and locking.

Exercise 2: size a Bloom filter

Task (paraphrased): there are 50 million user ids, and you want to block non-existent ids with a 0.1% false-positive rate. How much memory and how many hash functions does the Bloom filter need?

Solution 2: ~90 MB, 10 hash functions

m = −n·ln p / (ln 2)² = 50·10⁶ × 6.908 / 0.4805 ≈ 719 million bits ≈ 90 MB; k = (m/n)·ln 2 ≈ 14.4 × 0.693 ≈ 10. Every new user needs a BF.ADD; deleted users remain “possibly present” until the next periodic rebuild. Compared with null caching: a fixed 90 MB that blocks even 10 million distinct random ids.

Remember

  • Tell avalanche, breakdown and penetration apart, and name the main fix for each.
  • Explain why a cache that restarts empty can take the database down a second time, and how to reopen traffic.
  • Know when to pick background refresh, a mutex, single-flight or XFetch, and why @Cacheable(sync = true) isn’t enough across pods.
  • Explain why adding nodes doesn’t fix a hot key, and what does.
  • Choose a maxmemory-policy for a pure-cache Redis, and know the volatile-* trap with keys that have no TTL.

Interview questions

Mid

How do cache avalanche, breakdown and penetration differ?

Avalanche is many keys (or the whole cache) gone at once, breakdown is one hot key expiring, penetration is a key that exists nowhere.

Avalanche: the cache goes down or a huge number of keys expire together, and load spills onto the database broadly. Breakdown: one hot key expires, and thousands of requests miss and reload it at once. Penetration: keys that exist neither in the cache nor in the database, so they always go through to the database. Fix them with HA + jitter + database protection; background refresh/mutex/single-flight; and null caching + validation + Bloom filters, respectively.

What is a Bloom filter and where does it fit in caching?

A probabilistic structure that answers “definitely absent” or “possibly present”; it sits in front of the cache to stop penetration.

A bit array plus k hash functions. Adding an element sets k bits; checking it says “definitely absent” if any bit is unset and “possibly present” if all are set. No false negatives, false positives at a chosen rate, and no deletion. Ids that definitely don’t exist get an immediate 404. A million ids at a 1% false-positive rate take only about 1.2 MB.

Senior

A hot key expires and overloads the database. Which fix do you pick?

Single-flight in the JVM always on, plus background refresh or a per-key Redis mutex for the few truly hot keys.

Single-flight (Caffeine get(key, loader)) only collapses loads within one pod. For the few truly hot keys: no TTL plus background refresh, or stale-while-revalidate (refreshAfterWrite) so requests never wait. To limit loads across the whole cluster: a per-key mutex in Redis (SET NX PX with a token), with other requests serving the old value or waiting briefly. XFetch if you want no locks at all. Add a bulkhead to cap concurrent reloads hitting the database.

What are the downsides of caching nulls to stop penetration?

Every junk id costs a key, and a record created later can be reported missing until the TTL runs out.

An attacker using random ids can fill memory, and the first request for each id still reaches the database. The TTL must be short, or a record created later is reported missing until it expires. In Spring, disableCachingNullValues() plus unless = "#result == null" turns this protection off entirely. Combine it with validation and a Bloom filter.

A hot key on Redis Cluster: why doesn’t adding nodes help, and what do you do?

A key belongs to one slot and a slot lives on one node, so its traffic still hits one node; fix it with a local cache or key replication.

Fixes: a short-TTL local cache on each instance (or Redis 6 client-side caching with invalidation), replicating the key into N suffixed copies spread across slots (and deleting all N on invalidation), or reading from replicas if lagging data is acceptable. Detect it with --hotkeys under an LFU policy or with client-side metrics.

What problems do big keys cause and how do you deal with them?

A multi-MB value blocks Redis’s single command thread and eats bandwidth; split it, compress it, move it to another store, and delete it with UNLINK.

Commands get slow and block everything else, partial updates force whole-value rewrites, and reloads are slow. Deal with it by compressing, splitting into several keys or hash fields, using a longer TTL, enforcing size limits in review and alerts, and moving large files to object storage. Find them with --bigkeys/--memkeys; delete them with UNLINK instead of DEL.

How do LRU, LFU and W-TinyLFU differ, and which policy would you pick in Redis?

LRU goes by recency, LFU by frequency, W-TinyLFU combines both; a pure-cache Redis uses allkeys-lru or allkeys-lfu.

LRU evicts the key read longest ago, but one scan can flush hot keys. LFU evicts the least frequently read key and needs counter decay so once-hot keys don’t stay forever. W-TinyLFU (Caffeine): a small LRU window for new keys and a frequency sketch that decides whether a newcomer gets into the main area. Redis uses sampled, approximated LRU/LFU; the default noeviction only makes sense when Redis is a data store.

Your Redis cache cluster dies at peak traffic. How should the system behave?

Errors must come back fast and a bulkhead must shield the database; when Redis returns, warm it up first and ramp traffic back.

Short client timeouts, an open circuit breaker, no hanging threads. The cache-miss path to the database goes through a bulkhead or rate limit, and anything above it fails fast or returns degraded data (empty lists, defaults) for non-essential features. An L1 local cache carries the hottest data. When Redis recovers: reload from persistence or warm up hot keys first, then ramp traffic back. Long term: Sentinel or Cluster with replicas, and a load test of the “Redis is down” scenario to know how much the database can actually take.

Useful phrases for interviews

  • “A 99 percent hit rate means the database is only sized for one percent of the traffic, so losing the cache is an outage, not a slowdown.”
  • “We add jitter to every TTL so keys loaded together don’t expire together.”
  • “Single-flight collapses concurrent misses into one load per key, but only within a single instance.”
  • “For the handful of really hot keys, we don’t expire them at all; a background job refreshes them.”
  • “A Bloom filter in front of the cache answers ‘definitely not here’, which stops random-id attacks for about ten bits per id.”
  • “Adding nodes doesn’t fix a hot key, because one key always lives on one node; we put a short-lived local cache in front of it.”
  • “We delete big keys with UNLINK, so the memory is freed on a background thread.”
  • “For a Redis that’s purely a cache, I’d use allkeys-lfu; volatile policies can end in OOM errors if keys have no TTL.”

Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.