A public product API accepts a product ID and returns a record or 404. The cache is large enough for the popular catalog. A client now requests 30,000 randomly generated IDs per second. Almost all of them do not exist, and the database starts running out of connections.
Interview question. Why can a cache with excellent hit rates for legitimate users fail to protect this endpoint? Design a safe path for missing IDs, explain when a Bloom filter helps, and address what happens when a previously missing ID becomes valid. The endpoint also serves private tenant products, so you must not reveal their existence to unauthorized callers.
Think first
Anonymous clients query 30,000 random nonexistent product IDs each second. Design a bounded protection path, then explain what happens if a cached missing ID is created and if a Bloom filter missed its insert.
Take a few minutes to form an approach, then compare it with the worked explanation.
Reveal the worked explanation
An ordinary cache may never learn from a miss
A typical cache-aside implementation only inserts a value after the database finds a record. A missing key produces a database lookup, then a 404, and the cache remains empty for that key. The next request for the same nonexistent ID does the same work.
Unknown IDs flow through a validity check, scoped negative cache and guarded origin lookup
The attack here is worse than repeated access to one key. Random IDs are different every time. Per-key request coalescing has almost nothing to combine. Even a 99% overall cache hit rate on legitimate traffic says little about the cost of this new stream.
The first defense is ordinary admission control and input validation. Reject malformed IDs before database access. Rate-limit abusive principals or anonymous callers, and apply a global budget to expensive misses. Do not assume an algorithmic data structure can replace an abuse policy.
For valid-looking IDs, consider storing a negative result. An entry like not-found(product, tenant, id) can prevent repeated origin lookups during a short interval. It must be scoped to the appropriate visibility context, and it should have an explicit expiry. A missing public product is different from a record that exists but is inaccessible to the current caller.
If IDs can be created later, negative caching introduces a real freshness issue. Suppose a read caches not-found(p91) for five minutes, then a creator publishes p91 one minute later. A later read may incorrectly return 404 until the negative entry expires. The creation path should invalidate an affected negative entry where reliable, while the maximum negative TTL limits exposure when invalidation fails.
For a dynamic catalog, I would start with a short negative TTL and measure how often previously missing IDs become valid. Five minutes may be far too long for freshly uploaded products, while seconds may be acceptable. A TTL is a product decision, not a universal cache setting.
Would a Bloom filter solve the random-ID problem?
A Bloom filter is a compact membership summary for a set. If its answer is “definitely not present,” an origin lookup for that key can be skipped, assuming the filter accurately covers the authoritative key set for the relevant point in time. If it answers “maybe present,” the key may be real or a false positive, so a database read is still necessary. Bloom filters trade some unnecessary positive checks for compact storage. RocksDB uses them to avoid pointless searches through SST files.
The difficulty is not the formula for the bit array. It is maintaining the meaning of “definitely absent” while new products are created.
An old filter built yesterday may report that a newly created product is absent. That is a false negative relative to today's database, caused by stale membership data rather than the Bloom filter's normal probabilistic guarantee. You cannot safely reject a new legitimate product using a snapshot that has missed its insert.
A defensible design might build a complete published-ID filter for a fixed catalog generation, consult an authoritative recent-inserts path for newer generations, and only use a negative Bloom response when the request falls under a generation the filter covers. If that coverage is uncertain, fall back to an admitted origin lookup rather than confidently returning a false 404.
For a mutable set with deletion, either rebuild generations or use a data structure with well-defined deletion semantics. Clearing arbitrary Bloom bits can create false negatives for other keys. A counting Bloom filter is one alternative, but it has its own update and overflow risks.
Security changes the cache key and the response
Consider tenant A requesting tenant B's product ID. If our service puts a shared 404 or 403 value under the raw product ID, the same cached response may be delivered to a caller with different permissions. That could block legitimate access or reveal whether a private ID exists.
Authorization should happen under the endpoint's security contract before a cached result becomes observable. Often the simplest rule for private data is to use a tenant-scoped cache and a uniform user-visible “not found” response when the caller lacks permission. Keep authorization failures out of global negative caches. The filter may guide internal database work but must not become the final authorization decision.
I'd monitor negative-hit rate, unique invalid IDs, origin lookups per principal, false-positive candidates, and time to visibility for newly created records. A negative cache that improves CPU but delays every new product is not a successful design.
Interview takeaway: Positive caching protects repeated access to things that exist. Negative caching and membership summaries can protect absent-key lookups, but only with an explicit freshness model. Validation, admission, and authorization still belong in the design.
Now the endpoint serves real customers and real records. The next failure is not excessive load. It is a fast response returned to the wrong person.
Go deeper
If unknown IDs are uniformly random, caching each negative ID individually can itself become a memory-exhaustion problem. Use bounded admission for negative entries, a size-aware eviction policy, and limits on key cardinality. A Bloom filter is useful when there is a stable set of known valid identifiers and the cost of a database miss is high enough to justify maintaining the filter.
Distinguish false positives from stale-filter false negatives. A correctly built Bloom filter normally does not return “definitely absent” for an element inserted into the represented set. A distributed pipeline that loses insert updates invalidates the assumption that the represented set is current.
DNS negative caching is a useful analogy because it explicitly gives negative answers a lifetime, but its protocol semantics should not be copied blindly into a product API.
Check your reasoning
Explain why positive cache-aside and per-key coalescing do little for uniformly random absent IDs.
Validate and enforce admission limits before expensive origin queries.
Scope negative caching by visibility and expire/invalidate negative entries when objects appear.
Distinguish probabilistic false positives from stale-membership false negatives.
Avoid revealing private tenant data through 403/404 behavior or shared negative cache keys.
Common mistake: Treating a Bloom filter as permanently authoritative for a changing dataset or globally caching access-denied results by raw ID.
Read the answer explanation
No, stale membership data can reject records created after the filter snapshot. — The no-false-negative property applies to the set the filter accurately represents, not unpropagated inserts.
Apply it elsewhere
An account directory serves newly provisioned users. How would your negative-cache TTL affect their first sign-in?
Compare your approach
A recently created user must not remain “not found” indefinitely. Scope and invalidate negative results or use a very short bound.
One more constraint
What protects you if attackers request a new random ID on every request?
Quick revision
Positive caching does not help random nonexistent keys when the application never stores misses. Add validation, rate limits and bounded negative results scoped to the authorized visibility context. Negative TTL and creation invalidation govern how quickly a newly created key becomes visible. A Bloom filter can cheaply rule out membership in the set it accurately represents, but missing updates make its negative result unsafe for newer keys. Treat the filter as a lookup optimization, not authorization. Random distinct invalid IDs also need admission control because per-key coalescing cannot help.
