Cache Penetration: Requests for Data That Doesn't Exist

Scenario

Example app: a public product API, GET /products/{id}, cached in Redis. A scraper starts enumerating ids 1 to 50,000,000; 98% of those ids don't exist.

What you see in production

The cache hit ratio drops from 97% to 40%, database QPS triples, and every one of those database queries returns nothing. Rate limiting per IP doesn't help — the scraper rotates through thousands of IPs.

The naive code

Only found values are cached, so every request for a missing id goes to the database:

def get_product(pid):
    if (hit := r.get(f"product:{pid}")) is not None:
        return json.loads(hit)
    product = db.fetch_product(pid)             # None for missing ids
    if product is not None:
        r.set(f"product:{pid}", json.dumps(product), ex=600)
    return product                              # missing → database every time

@Cacheable(value = "products", key = "#id", unless = "#result == null")   // nulls are never cached
public Product get(long id) { return repo.findById(id).orElse(null); }

Reproduce it

1,000 requests for random ids where only 2% exist; compare database queries with and without negative caching and a Bloom filter:

import random
random.seed(3)
existing = set(range(1, 20_001))                       # ids that exist
requests = [random.randint(1, 1_000_000) for _ in range(1000)] * 2   # scraper repeats ids

def bloom_contains(i):                                 # stand-in for a Bloom filter (~1% false positives)
    return i in existing or i % 100 == 0

def run(negative_cache, bloom):
    cache, db_queries = {}, 0
    for i in requests:
        if bloom and not bloom_contains(i):
            continue                                   # definitely missing: answer 404 without the database
        if i in cache:
            continue
        db_queries += 1
        found = i in existing
        if found or negative_cache:
            cache[i] = found                           # cache "not found" too (short TTL)
    return db_queries

for label, neg, bloom in (("no protection", False, False), ("negative caching", True, False), ("Bloom filter + negative", True, True)):
    print(f"{label:24} database queries: {run(neg, bloom)}")

no protection            database queries: 1988
negative caching         database queries: 1000
Bloom filter + negative  database queries: 26

Root cause

Cache-aside only stores results that exist. Requests for non-existent data — enumeration, bugs that generate bad ids, deleted content still linked from search engines — always miss and always reach the database. The cache gives no protection exactly when traffic is adversarial.

The fix

1. Negative caching: cache "not found" with a short TTL (e.g. 30–60 s).
2. Bloom filter of existing ids in front of the database: "definitely not present" answers skip the lookup entirely.
3. Validate input cheaply (id ranges, checksums in public ids, signed ids) and rate-limit by behaviour, not just IP.

NOT_FOUND = "__nf__"

def get_product(pid):
    hit = r.get(f"product:{pid}")
    if hit == NOT_FOUND:
        return None
    if hit is not None:
        return json.loads(hit)
    if not r.bf().exists("products:ids", pid):          # RedisBloom; add ids on create
        return None
    product = db.fetch_product(pid)
    if product is None:
        r.set(f"product:{pid}", NOT_FOUND, ex=60)       # negative entry, short TTL
        return None
    r.set(f"product:{pid}", json.dumps(product), ex=600)
    return product

@Cacheable(value = "products", key = "#id")             // cache Optional.empty() as a negative entry
public Optional<Product> get(long id) { return repo.findById(id); }
// and configure the "products" cache to allow nulls/empties with a short TTL for negatives

$product = Cache::remember("product:$id", 600, fn () => Product::find($id) ?? false);   // false = not found
if ($product === false) abort(404);

const hit = await redis.get(`product:${id}`);
if (hit === "__nf__") return null;
if (hit) return JSON.parse(hit);
const product = await prisma.product.findUnique({ where: { id } });
await redis.set(`product:${id}`, product ? JSON.stringify(product) : "__nf__", "EX", product ? 600 : 60);

Trade-offs

• Negative entries must be invalidated on create, or a newly created item stays "not found" until the TTL.
• Bloom filters have false positives (some missing ids still reach the database) but never false negatives; they can't delete entries (use counting/cuckoo filters or rebuild periodically).
• Negative entries for random ids can fill memory — keep their TTL short and the eviction policy on.

Detect it in production

• Track the share of cache misses that return "not found" from the database.
• Unusual id distributions (sequential scans, out-of-range ids) in access logs.

Key points

• Requests for missing data bypass naive caches and hit the database every time.
• Cache "not found" briefly; use a Bloom filter for existence checks; validate ids cheaply.
• Invalidate negative entries when items are created.