Cache Penetration

The Problem

 stampede = real key, many requests at expiry.
 PENETRATION = nonexistent keys, requested endlessly:

 attacker/bot: GET /user/{random_id}   × 10k/sec
 every id: cache MISS (nothing to cache!) → full db query → empty

 the db answers EVERY request because "not found" was never cached.
 caching only successful results leaves a hole exactly where
 malicious traffic aims.

Defense 1: Negative Caching

 cache the EMPTY answer too:

 miss → db says "no user 123456"
        cache.set("user:123456", NOT_FOUND, ttl=60)

 next 60s of identical probes: answered by cache, ~free.

 caveats:
 - short TTL (new users must appear promptly)
 - memory: attackers with huge random spaces can fill cache
   with negatives → cap negative-entry count/size

Defense 2: Bloom Filter Gate

 a probabilistic set answering "DEFINITELY NOT PRESENT"
 using ~10 bits per key:

 [ bloom filter of ALL valid ids ]  ← built/rebuilt from db
      │
 request ──► might exist? ──yes──► normal cache path
      └──── no ──► reject instantly (404), never touches db

 false positive rate tunable (1% typical) — false positives
 just fall through to normal path. NO false negatives for
 present members... but NEW members need filter updates,
 or accept a brief wrong-404 window after inserts.

Defense 3: Validate Before It Reaches You

 shape-reject garbage at the edge, before cache logic:

 - id format check: uuid pattern? numeric range? → reject malformed free
 - authz: probing OTHER tenants' ids? → 403 early
 - rate limits per ip/key on miss-heavy endpoints specifically
 
 most penetration attempts die here; defenses 1–2 catch
 the sophisticated remainder.

The Combined Stack

 request flow with all layers:

 [edge: format+authz checks]     ← kills 95% of junk
        │ plausible id
 [bloom: could exist?]           ← kills known-nonexistent cheaply
        │ maybe exists
 [cache: hit?]                   ← serves repeats incl. negatives
        │ miss
 [db]                            ← sees almost nothing hostile

 each layer's cost is tiny; together they make penetration
 attacks economically pointless.

Distinguishing the Cache Attack Trio

Problem	Trigger	Signature
Stampede	Hot key expires	Spike AT TTL boundaries
Penetration	Nonexistent keys	Constant high miss rate, low hit rate
Breakdown	Mass simultaneous failure	Everything missing at once

Diagnose by miss-rate SHAPE before applying fixes — each problem has its own medicine.

Interview Framing

“Someone scripts requests for random user ids — what breaks?” expects: recognition that not-found is uncached by default, then the ladder — negative caching with capped TTLs, bloom filter with its false-positive semantics stated, input validation at edge. Mentioning the trio distinction (stampede vs penetration vs breakdown) shows systematic thinking about cache failure modes.