The Problem
Imagine a malicious user (or a buggy crawler) knows that your User IDs go from 1 to 1,000,000. They start blasting your site with requests for User IDs that don't exist — like ID 999,999,999 or ID -5.
In a standard Cache-Aside setup:
1. App checks cache for key user:-5. Miss — it's not there.
2. App queries the database for User -5. The database reports "Not found."
3. Because the data doesn't exist, nothing gets written to the cache.
4. App returns a 404 to the user.
The next request for user:-5 repeats the exact same journey: cache miss → database query → nothing cached → 404. The cache provides zero protection because there is nothing to cache. If an attacker sends millions of requests per second for non-existent IDs, every single one pierces straight through the cache and hits your database. This is Cache Penetration, and it can crash your database under load.
The Solutions
1. Cache Null Results
When the database returns "Not found," explicitly store a sentinel value in the cache under that key with a short TTL (e.g., 60 seconds):
result = db.query("SELECT * FROM users WHERE id = ?", user_id)
if result is None:
cache.set(f"user:{user_id}", "NULL_SENTINEL", ttl=60)
return None
cache.set(f"user:{user_id}", result, ttl=3600)
return result
The next request for the same non-existent ID hits the cache, finds the sentinel, and returns immediately without touching the database. The short TTL ensures that if the user is later created, the sentinel expires quickly.
2. Bloom Filters
A Bloom filter is a probabilistic data structure that can answer the question "does this key definitely NOT exist?" with 100% certainty (no false negatives), while occasionally saying "this key might exist" when it doesn't (false positives are acceptable). You populate the Bloom filter with all valid keys that exist in the database. When a request arrives, you check the Bloom filter first. If it says "definitely not in DB," you reject the request immediately — before it touches the cache or the database.
Bloom filters are extremely memory-efficient (storing millions of keys in kilobytes of RAM) and are used in production by systems like Cassandra, HBase, and PostgreSQL internal operations.