In a cache-fronted lookup service, what is cache penetration, and how does it differ from an ordinary cache miss?
answer
- Keys that exist nowhere
- Normal miss writes back
- Not-found path writes nothing
- Every repeat returns to the database
- Watch the database not-found rate
basics
~20 sCache penetration is traffic for keys that exist in neither the cache nor the database, so nothing ever gets cached and every repeat reaches the database. An ordinary miss loads the row once, and later requests hit.
solid answer
~50 sCache penetration is traffic for keys that do not exist in the database, so the cache never gets anything to store. In cache-aside, an **ordinary miss** loads the row, writes it to the cache, and later requests for that key are hits: the miss heals itself. A request for a nonexistent ID finds no row, a naive implementation writes nothing, and the next request for the same ID misses again and goes back to the database. For that traffic the cache might as well not be there, so a bigger cache or longer TTLs change nothing. Typical sources are enumeration scrapers, stale links to deleted items, buggy clients and deliberate random-ID abuse. You spot it by a high database not-found rate with recurring or patterned keys, and you defend with key validation, a bloom-filter guard and short-lived negative entries.
code
pseudocode · 9 linesfunction getItem(id):
value = cache.get("item:" + id)
if value != MISS:
return value
row = db.findById(id)
if row == NONE:
return NOT_FOUND // nothing cached: the next call repeats this query
cache.set("item:" + id, row, ttl = 3600s)
return rowgo deeper
Define cache penetration in one breath: requests for keys that exist nowhere, so the cache never stores anything and every repeat reaches the database.
Walk through the cache-aside read path, point to the exact step where a not-found result writes nothing, and name the three standard defences.
Explain how you would detect it in production from the database not-found rate and recurring keys, and why scaling the cache tier does not help.
Treat penetration as a cost the caller controls, and discuss which defences belong in the cache layer and which belong at the API edge of a public lookup service.
## What a cache miss normally buys you A **cache-fronted lookup service** keeps copies of database rows in a fast in-memory key-value cache. The most common read path, **cache-aside**, works like this: 1. Look the key up in the cache. 2. On a **hit**, return the cached value. 3. On a **miss**, query the database, write the row into the cache with a TTL (time to live), and return it. An **ordinary cache miss** therefore heals itself. The first request for `item:48213` pays the database cost, and every request for the same key after that is served from memory until the entry expires or is evicted. For a popular key, one database query absorbs thousands of reads. ## Why a missing key never heals **Cache penetration** is what happens when requests ask for keys that do not exist in the database at all. Step 3 finds no row, and a naive implementation has nothing to write, so it returns a not-found response and stores nothing. The next request for the same key finds the cache just as empty as before and goes to the database again. That creates a class of traffic the cache cannot see: - the **hit ratio for real items** can look healthy, because those requests still hit; - the database receives **one query per not-found request**, with no end; - adding cache memory or raising TTLs changes nothing, because nothing is being cached; - the traffic **passes straight through** the layer that was supposed to shield the database, which is where the name comes from. A single not-found query is usually cheap, especially on an indexed primary key. The problem is volume. When not-found requests arrive at thousands per second, the database carries all of that load itself, and an attacker can choose the volume. ## Where the traffic comes from Penetration rarely has a single cause. Common sources in a public item or profile lookup API: - **Enumeration scrapers** walking sequential or guessed IDs, many of which were never issued. - **Deleted items** still referenced by old links, bookmarks, search results or other services. - **Client bugs** that send a malformed or wrongly prefixed ID on every call. - **Deliberate abuse** with random IDs, chosen because they bypass the cache. The mix matters because each defence works differently against each source. A repeating set of deleted IDs is a different problem from an endless stream of unique random ones. ## How to recognise it | Signal | Ordinary miss traffic | Cache penetration | |---|---|---| | What the database returns | Rows, which then get cached | Mostly no row | | Repeat requests for the same key | Become hits | Stay misses | | Effect of a bigger cache | Fewer database queries | No change | | Typical cause | Cold start, expiry, eviction | Nonexistent or deleted IDs | The most direct signal is the **database not-found rate**. Count lookups that returned no row, sample their keys, and look for keys that keep coming back, or for keys that look sequential or random. Another sign is database query volume rising while the cache hit ratio for real items stays flat. ## The defences, in the order a request meets them 1. **Key-format validation** rejects IDs that cannot be valid (wrong length, characters or range) before any cache or database work. 2. A **bloom-filter guard** holding every existing ID answers "definitely absent" for most nonexistent keys, so they are rejected without a lookup. 3. **Negative entries** (also called tombstones or null sentinels) cache the fact that a key has no row, with a short TTL, so a repeated miss becomes a hit. Each one has limits. Negative entries help only when the same key repeats. A bloom filter must be kept in step with creates and deletes. Throttling the clients that enumerate is a rate-limiting job, not a caching one. ## Not to be confused with Penetration is about keys that **do not exist**. A different failure is many concurrent requests missing one **existing** popular key at the moment its entry expires. That is a stampede, and different tools fix it. Interviewers often ask about the two back to back to check that a candidate keeps them apart: a stampede is a short burst on one real key, while penetration is steady traffic on keys that are not there.
- If a not-found query on an indexed key is cheap, why is penetration dangerous at all?The cost is per request and the caller sets the volume. A cheap indexed lookup repeated thousands of times per second, with no cache absorbing it, still uses database connections and CPU that real traffic needs. Because the cache never engages, adding cache capacity does nothing to relieve it, and an attacker can simply raise the rate.
- How would you confirm that rising database load comes from penetration rather than ordinary misses?Instrument the miss path: count database lookups that return no row, and sample their keys. A high not-found share with recurring keys, or keys that look sequential or random, points to penetration. Ordinary misses return rows and then stop recurring, because the row gets cached.
A library help desk remembers where popular books are shelved but never notes which titles the library does not own, so every request for a book it lacks sends a clerk to search the stacks again.
saying these in an interview costs you the question
- A bigger cache or longer TTL will absorb requests for nonexistent keys
- Every cache miss eventually becomes a hit, so misses limit themselves
- Cache penetration is the same thing as a popular key expiring under load
- Not-found lookups are free, so their volume never matters
- A healthy hit ratio for real items proves the database is protected