Definition
- Cache penetration – requests for non-existent keys bypass the cache entirely and hit the DB every time.
- Negative caching – cache an empty/sentinel value with a short TTL; subsequent requests for the same missing key are answered from cache.
- Bloom filter – a bit array + hash functions; NO false negatives ('not present' = definitely absent); false positives are rare and harmless.
- Layered defense – Bloom filter rejects most non-existent keys at the front door; negative caching absorbs the rest.
- Sync – add new keys to the filter on creation; use counting Bloom filter or periodic rebuild for deletions.
People keep asking for account numbers that were never issued. The teller checks the notepad (cache), finds nothing, and runs to the vault every time. Fix 1: write 'does not exist' on the notepad for a while. Fix 2: a doorman with a compact list of every account ever issued who instantly says 'that was never issued, do not bother the vault.'
Understanding the Concepts
What is cache penetration?
Requests for keys that do not exist at all always miss the cache (nothing to cache) and fall through to the database. Especially dangerous as an attack vector: an adversary floods with random non-existent IDs.
How is it different from stampede and avalanche?
| Problem | Cause | Data exists? |
|---|---|---|
| Penetration | Non-existent keys | No |
| Stampede | One popular key expires | Yes |
| Avalanche | Many keys expire together | Yes |
How does negative caching work?
package com.bank.cache;
import java.math.BigDecimal;
import java.time.Duration;
public class AccountBalanceCache {
private static final String NOT_FOUND = "__NOT_FOUND__";
private final StringRedisTemplate redis;
private final AccountRepository repo;
public BigDecimal getBalance(String accountId) {
String cached = redis.opsForValue().get("balance:" + accountId);
if (NOT_FOUND.equals(cached)) return null; // negative cache hit
if (cached != null) return new BigDecimal(cached);
BigDecimal balance = repo.findBalance(accountId);
if (balance == null) {
redis.opsForValue().set("balance:" + accountId, NOT_FOUND,
Duration.ofSeconds(60)); // short TTL for negatives
return null;
}
redis.opsForValue().set("balance:" + accountId, balance.toString(),
Duration.ofSeconds(300));
return balance;
}
}
How does a Bloom filter work?
package com.bank.cache;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;
public class AccountBloomFilter {
private final BloomFilter<String> filter;
public AccountBloomFilter(long expectedAccounts) {
filter = BloomFilter.create(
Funnels.stringFunnel(StandardCharsets.UTF_8),
expectedAccounts,
0.01); // 1% false positive rate
}
public void add(String accountId) { filter.put(accountId); }
public boolean mightExist(String accountId) {
return filter.mightContain(accountId);
// false = DEFINITELY does not exist → skip DB
// true = probably exists → proceed with lookup
}
}
Expected output: Bloom says "not present" for SAV-FAKE-999 → skip DB entirely Bloom says "might exist" for SAV2001 → proceed with cache-then-DB lookup
How do you use both together?
public BigDecimal getBalance(String accountId) {
if (!bloomFilter.mightExist(accountId)) {
return null; // Bloom says definitely not present → skip everything
}
return balanceCache.getBalance(accountId); // normal cache-aside with negative caching
}
What are common mistakes?
// WRONG: no defense against penetration
// Attacker floods with random IDs → every request hits DB → DB overloaded
// WRONG: negative cache with too-long TTL
// New account created but cache says "not found" for an hour → customer cannot log in
// CORRECT: short TTL (60s) for negatives + Bloom filter for broad defense
What about keeping the Bloom filter in sync?
When a new account is created, add it to the Bloom filter. Standard Bloom filters do not support deletion (deleted keys linger as harmless false positives). Use a counting Bloom filter for removals, or periodically rebuild.
What should a senior engineer know?
- Choose defenses by threat model: negative caching alone for benign workloads; add Bloom filter when facing wide-spread attacks.
- The Bloom filter must be cheap to check (held in memory or in Redis).
- Space: ~10 bits per element for 1% FP rate; millions of keys in a few MB.
- False positive = one wasted lookup (harmless); false negative = never (safe).
Visual Overview
Cache Penetration Defense
┌────────┐ request ┌────────────┐ not present ┌─────────┐
│ Client │ ────────► │ Bloom │ ─────────────► │ REJECT │
└────────┘ │ Filter │ (definitely │ (no DB) │
└─────┬──────┘ not in DB) └─────────┘
│ might exist
▼
┌────────────┐ sentinel hit ┌─────────┐
│ Redis │ ─────────────► │ Return │
│ (negative │ "not found" │ null │
│ cache) │ └─────────┘
└─────┬──────┘
│ cache miss
▼
┌────────────┐
│ Database │ (rare: only real queries reach here)
└────────────┘
Key Takeaway
Cache penetration is requests for keys that do not exist at all always missing the cache and hitting the database. Normal caching does not help because there is nothing to cache. It is especially dangerous as an attack where an adversary floods with random non-existent IDs to overload the database.
The first defense is negative caching: when a lookup finds nothing, cache an explicit sentinel with a short TTL so subsequent requests for the same missing key are answered from cache. The second defense is a Bloom filter, a space-efficient probabilistic set with no false negatives: if it says 'not present,' the key definitely does not exist, so you skip the DB entirely. Together they give layered protection: the Bloom filter rejects the vast majority of non-existent keys at the front door, and negative caching absorbs the few false positives.
At National Bank of India, Pankaj defended an account-lookup service that was being hit by random non-existent IDs. The Bloom filter of all valid account IDs shut down the flood without a single database hit, while legitimate accounts were served correctly because the filter never rejects a real ID.
Remember one sentence: defend against cache penetration with negative caching (short-TTL sentinel for missing keys) plus a Bloom filter (no false negatives, so 'not present' is always correct), giving layered protection that shields the database from non-existent-key floods.
---