Part 3 of 8 · 2 min read
Penetration: asking for what does not exist
Requests for missing keys that always miss and always reach the database.
Think of a library where readers keep asking for a book that was never printed. The assistant checks the shelf, then walks to the archive, then finds nothing, every time. Because nothing is ever put on the shelf, the next reader makes the same trip.
A cache stores items that exist. If a key has no value in the database, there is nothing to cache, so every request for it misses and goes to the database. This is cache penetration.
Cache penetration
Cache penetration is a stream of requests for keys that are not in the cache and not in the database, so every request reaches the database and no request is ever a hit.
Example: a client asks for user:9999999 thousands of times a second, and no such user exists.
It is harmless when rare, such as a user mistyping an id. It is dangerous when deliberate. An attacker can request random keys, each new, and the cache never helps. At 20,000 requests a second with a database limit of 2,000 reads a second, the database falls over within seconds.
Fixes:
- Cache the miss. Store a marker such as "not found" with a short TTL (30 to 60 seconds). The next request for the same key hits the marker. This does not help when every key is different.
- Check keys before looking. A Bloom filter (Level 2, module 4) built from all valid keys says "definitely not present" for most invalid keys, and the request is dropped before it reaches the database. A Bloom filter can say "maybe present" wrongly, but never says "absent" for a present key.
- Validate input. Reject ids with the wrong format or range. An id must be a positive number below the highest one issued.
- Rate limit by client (Level 1, module 7).
A worked example. A Bloom filter holds 10,000,000 user ids. An attacker sends 20,000 random ids a second. With a false positive rate of 1 percent, 200 of the 20,000 requests pass the filter and reach the database as "maybe". The database sees 200 a second, not 20,000.
Common mistake
Caching "not found" for too long. A user who signs up at 10:00:00 and is looked up at 10:00:05 may be told that the account does not exist for as long as the marker lives. Keep the marker short, or delete it when the record is created.
Check yourself:
- Why does a normal cache not help against requests for random keys that do not exist?
- A Bloom filter has a 2 percent false positive rate. Of 50,000 invalid requests, how many reach the database?