Cache Penetration: Requests for Things That Don't Exist

In one line

Cache penetration happens when requests ask for keys that exist neither in the cache nor in the database, so every request reaches the database. Defend with input validation, negative caching, Bloom filters, and rate limiting.

0/7 · 0%

Think of it like this

A prank caller asking a pharmacy for medicines that don't exist, a thousand times an hour. Each time the pharmacist walks to the back to check. A sensible pharmacist keeps a list of "we don't stock that" names and answers at the counter.

Key ideas

01
Why the cache doesn't help: cache-aside only stores values it found. A missing product returns nothing to cache, so the next identical request misses again, and random IDs never repeat at all.
02
Negative caching: when the database returns not-found, cache a sentinel (SET product:999999999 __none__ EX 60) with a short TTL. Repeated requests for the same missing ID stop at Redis. Keep the TTL short so a newly created item appears quickly, or delete the sentinel when the item is created.
03
Bloom filter gate: keep a Bloom filter of all valid IDs (Topic 4.4); reject IDs that are definitely absent before touching the cache or the database. This handles random-ID attacks where negative caching can't help.
04
Input validation: reject impossible IDs (wrong format, negative, beyond the current max ID, invalid checksums) at the edge. It's the cheapest defence and often blocks most junk.
05
Rate limiting and anomaly detection: per-client limits on not-found responses, and alerts on a rising miss rate combined with a rising not-found rate.

Code & diagrams

negative-cache.pypython

NONE = "__none__"

def get_product(r, db, pid: int):
    if pid <= 0 or pid > MAX_KNOWN_ID:              # 1. validate
        return None
    if not r.execute_command("BF.EXISTS", "bf:products", pid):
        return None                                 # 2. definitely absent
    cached = r.get(f"product:v1:{pid}")             # 3. cache (incl. negative)
    if cached == NONE:
        return None
    if cached:
        return deserialize(cached)
    row = db.fetch_product(pid)                     # 4. database
    if row is None:
        r.set(f"product:v1:{pid}", NONE, ex=60)     # negative cache, short TTL
        return None
    r.set(f"product:v1:{pid}", serialize(row), ex=600)
    return row

Interview problem

The problem

1M requests for product:999999999

Attackers send 1M requests for non-existent products, some repeating the same ID and some random. Every request reaches the database. Design the defences.

You're given

Valid IDs are 1..20,000,000
Attack: 1M requests/min
Legitimate new products appear constantly

The interviewer follows up

What's the risk of negative caching with a long TTL?

When it breaks

Negative entries cached with the same TTL as real data

What you see

Newly created items are invisible for up to 10 minutes; support tickets say "my listing disappeared".

Fix & prevent

Short negative TTL (seconds to a minute) and explicit deletion on create.

Explain it without notes

Why does negative caching fail against random-ID attacks, and what works instead?

Practice

Add negative caching to the cache-aside code from Topic 6.1 and write a test proving the second lookup for a missing ID doesn't query the database.

Trade-offs

↔
Negative caching is simple but delays visibility of new items; Bloom filters handle random IDs but need rebuilds.

Done when you can

I can define cache penetration and layer validation, negative caching, Bloom filters and rate limiting.

Command Palette