The Three Cache Brothers

Cache Penetration

What it is: a flood of requests querying data that doesn’t exist in the database. The cache has nothing, so it keeps hammering the database. Prevention:

  1. Cache null values
    1. Even when the database finds nothing, put an empty marker in the cache (with a short TTL, e.g. 2 minutes; only after that TTL expires can the database be queried again)
    2. The next time the same id comes in, it’s blocked directly
    3. Pros: effectively intercepts large numbers of penetration requests
    4. Cons:
      1. A malicious attack with many different non-existent keys fills the cache with useless data and wastes memory
      2. It delays data consistency; new data has to wait for the cache to expire
  2. Bloom filter (recommended)
    1. At startup, put all legitimate ids into the Bloom filter
    2. If the Bloom filter says no, it really doesn’t exist
    3. Pros:
      1. No high-memory-usage risk
      2. No data-consistency risk
    4. Cons:
      1. There’s a tiny false-positive rate
      2. Insertions and deletions need maintenance; when data updates, the Bloom filter must be updated in sync
  3. Rate limiting and validation at the interface layer
    1. Intercept at the API gateway or Controller layer
    2. Parameter validation, rate limiting, and degradation
  4. Mutex-based rebuild
    1. A mutex mainly solves cache breakdown (a hot key expiring), but in the cache-empty-object scenario, if there are many concurrent requests for a non-existent key, a lock can be used
    2. Each access lets one thread query the DB while the others wait

Big companies’ practice

  1. Gateway layer: validate parameter format, IP rate limiting (block script attacks)
  2. Filter layer: Bloom filter
  3. Cache layer

Cache Breakdown

What it is: a frantically accessed hot key whose TTL expires; at the instant it expires, a huge number of concurrent requests all miss simultaneously and all hit the DB to rebuild the same key.

Prevention:

  1. Mutex
    1. Let only the first thread that misses query the DB
    2. Other threads wait a moment and then read the cache
      1. High consistency: threads dutifully wait
      2. Low consistency: serve the old data first; the next query gets the new value
  2. Logical expiration
    1. The key never physically expires; store the expiration time inside the value
    2. If it’s found to be logically expired, spin up a thread to rebuild it asynchronously
    3. The current request returns the old value first

Cache Avalanche

What it is: a large batch of keys expiring collectively at the same moment. Scenarios:

  1. At system startup, a whole batch of cache entries is loaded at once, all with the same TTL
  2. Redis as a whole goes down, and a massive number of requests hit the DB at once

Difference from breakdown: breakdown is a single hot key; an avalanche is a whole swath of keys

Prevention:

  1. Add a random value to the TTL
  2. Redis high availability
    1. Master-replica
    2. Sentinel
    3. Cluster
    4. Don’t let a Redis single point of failure trigger an avalanche
  3. Multi-level cache + rate limiting/degradation
    1. Let a local cache take the first hit
    2. Finally, protect with circuit breaking and rate limiting

Cache-Aside

Applicable scenarios: all read-heavy, write-light cases Real business: user profile info, product detail pages, etc. Decision mnemonic: “If this data has to be queried every time a user refreshes the page, but the user only changes it once a day, then use Cache-Aside without a second thought.” How it works: populate on read, invalidate on write

Case 1: a chat room’s online list. Many people query the online list at the same time. They can’t all read from the database. Cache the online list in Redis. Queries go straight to Redis.

Chat room count increases/decreases -> triggers a DB write -> delete the cache At the same time, Query the chat room’s online list -> cache miss -> query the DB -> write the DB result into the cache