Skip to main content

Redis Cache Penetration, Breakdown, and Avalanche

· 5 min read
tanzhuo

Penetration, breakdown, and avalanche are three problems you can't avoid when using Redis as a cache. The names sound similar, but the causes and remedies are quite different. This post walks through them one by one.

Cache Penetration​

Cache penetration happens when the data a user requests exists neither in the cache (a cache miss) nor in the database. Every request for that data goes all the way to the database, which then returns nothing.

If a malicious attacker keeps requesting data that doesn't exist in the system, a flood of requests hits the database in a short time, putting it under heavy pressure and potentially bringing the whole database system down.

Solutions​

1) Bloom filter

A Bloom filter is essentially a very long binary vector plus a set of random hash functions, used to test whether an element is a member of a set. Its strengths are space efficiency and query time far better than typical algorithms; its weaknesses are a certain false-positive rate and difficulty with deletion.

To check whether an element is in a set, the usual approach is to store all the elements and compare against them — linked lists, trees, and similar data structures all work this way. But as the set grows, the required storage keeps increasing and lookups get slower (O(n) or O(log n)). A hash table, on the other hand, can map an element through a hash function to a single position in a bit array, so you only need to check whether that bit is 1 to know whether the element is in the set — and that is the basic idea behind a Bloom filter.

2) Cache empty objects

When the cache misses and the database query also comes back empty, you can write the empty result into the cache. The next request for that key gets the empty object straight from the cache instead of hitting the database. To avoid accumulating too many empty objects, you usually give them an expiration time.

This approach has two problems:

  1. If a large number of keys penetrate the cache, the cached empty objects take up memory.
  2. Until the key expires, there is a window where the cache and the database may be inconsistent.

Cache Breakdown​

Cache breakdown occurs when a hot key expires at the exact moment a large number of requests are accessing it. Because the cache has just been invalidated, all of those requests hit the persistent database simultaneously to query the data and write it back to the cache, putting the database under instant pressure.

This is where the difference between breakdown and penetration becomes clear:

Breakdown is about one extremely hot key. Massive traffic concentrates on that single key, and the instant it expires, every request slams into the database — punching a hole straight through, hence "breakdown." Penetration, by contrast, is about requesting data that doesn't exist at all: large volumes of requests for nonexistent data.

Solutions​

1) Use a mutex lock

Let the first thread that arrives query the database and write the result back to the cache; all other threads wait for the write-back to finish and then re-read from the cache.

2) Make hot data never expire

For extremely hot data, don't set an expiration time at all; instead, have the business side refresh the cached content asynchronously.

Cache Avalanche​

Cache avalanche happens when a large batch of hot keys in the cache expires at the same time while query volume is huge, so requests fall directly on the database, overwhelming it or even taking it down. Unlike cache breakdown, which is concurrent queries for the same piece of data, an avalanche means many different keys expire at once — lots of data becomes unavailable in the cache, so everything goes to the database.

Solutions​

1) Stagger expiration times

Set different expiration times so that cache invalidation is spread evenly over time. Common approaches are adding a random offset to the TTL, or planning expiration times centrally.

2) Add a mutex lock

Same idea as with cache breakdown: only one thread rebuilds the cache at a time, while the others block and queue.

3) Never expire the cache

Same idea as with cache breakdown: the cache physically never expires, and an asynchronous thread keeps it updated.

4) Two-tier cache strategy

Use a primary/backup pair of caches:

  • Primary cache: TTL set based on experience; this is the cache reads normally hit. When the primary cache expires, load the latest value from the database.
  • Backup cache: long TTL; used for reads when acquiring the lock fails. Whenever the primary cache is updated, the backup cache must be updated in sync.

Wrapping Up​

At their core, all three problems are requests bypassing the cache and landing on the database: penetration is querying data that doesn't exist, breakdown is a single hot key expiring, and an avalanche is a large batch of keys expiring at once. The remedies share common threads too — either intercept invalid requests at the cache layer (Bloom filters, empty objects), control the concurrency of requests going back to the source (mutex locks), or make expiration predictable (staggered TTLs, never-expiring keys, two-tier caching). In practice, combine them based on how hot the data is and how strict your consistency requirements are.

COMMENTS