When a scraper floods an item-lookup API with random, never-issued IDs, why does negative caching stop helping?

## When negative caching works A **negative entry** (tombstone) caches the fact that a key has no database row, so a repeated request for that key is answered from the cache. It works well when the set of missing keys is **small and repeated**: - deleted items still referenced by popular old links; - a buggy client asking for the same wrong ID in a loop; - a handful of IDs that pages request before the items are published. In each case the first request pays the database cost and later ones hit the tombstone. ## Why unique IDs defeat it A scraper, or an attacker, that generates **random, never-issued IDs** almost never repeats one. For each request: 1. The cache misses, because this key was never seen. 2. The database is queried and returns no row. 3. A tombstone is written, and it will never be read again. The database load is exactly what it would be with no negative caching, and the cache has gained useless entries. The hit rate on tombstones is close to zero, so the mechanism costs something and saves nothing. ## The memory bill At steady state, the number of live tombstones is about **arrival rate x negative TTL**, because each lives for one TTL and new ones keep arriving. Assuming roughly 100 bytes per tombstone (key, sentinel and per-entry overhead; an illustrative figure): | Unique misses per second | Negative TTL | Live tombstones | Approximate memory | |---|---|---|---| | 5,000 | 60 s | 300,000 | 30 MB | | 50,000 | 60 s | 3,000,000 | 300 MB | | 5,000 | 3,600 s | 18,000,000 | 1.8 GB | The last row shows why a long negative TTL is dangerous here: it multiplies memory without saving a single query. On top of the memory, the cache takes one useless tombstone write per request: 5,000 writes per second in the first row, each later expired or evicted. ## How it hurts real users In a shared cache with a fixed memory limit, tombstones compete with real data: - **Eviction pressure.** Under LRU, a constant stream of freshly written tombstones counts as recently used, so any positive entry touched less recently than the newest tombstones becomes an eviction candidate, including **warm entries** real users still need. - **Falling hit ratio.** Real items that were evicted now miss and reload from the database. - **Compounding load.** The database now serves the flood *and* the extra reloads for real traffic. So in this scenario negative caching can make things **worse** than not caching absence at all. ## Defences that stop the request earlier 1. **Key-format validation.** Before touching the cache, reject IDs with the wrong length, characters or prefix. For sequential numeric IDs, also reject values above the highest issued ID. This costs almost nothing and stops malformed and out-of-range floods. 2. **Signed or checksummed public IDs.** If the public ID carries a short keyed hash (a MAC) of the internal ID, a forged ID fails verification without any lookup. Opaque random 128-bit IDs make guessing a *real* item practically impossible, but on their own they do not stop a flood of well-formed fakes. 3. **Bloom-filter guard.** A filter of every existing ID rejects well-formed but never-issued IDs, letting through only a small false-positive fraction. 4. **Separate tombstone pool.** Keep negative entries in their own namespace or pool with a hard memory cap, or cap tombstone writes per time window, so a flood can never evict positive entries. If tombstones are dropped, the cost is only extra misses that the earlier guards should already absorb. 5. **Throttle the client.** Identifying and limiting the enumerating client belongs to rate limiting, not to the cache. ## Sequential versus random enumeration Sequential walks behave differently. A scraper walking IDs 1 to N over a mostly-issued range hits real items (which cache normally) and gaps left by deleted items. Tombstones help only if the walk is repeated within the TTL. Range validation stops the walk past the highest issued ID. A bloom filter stops the never-issued gaps, but not deleted IDs, which a standard filter still reports as possibly present. For random floods, validation and the filter do the real work, and negative caching should be capped so it cannot make things worse.