Skip to content

Caching Negative Results

A cache that stores only found values still sends every lookup for a missing key to the origin. Requests for deleted products, mistyped IDs, users who have not created a profile yet, and scanners probing random IDs all miss, every time. Caching the absence — a negative entry — stops that, with its own trade-off: a key created after its absence was cached stays invisible until the negative entry expires. Measured on Python 3.14 with an async cache in front of an origin taking 50 ms, 2,000 requests per second for 8 s, and 15% of requests for 200 IDs that did not exist: without negative caching, lookups for missing keys made 2,223 origin calls; with a 5-second negative TTL, 390; total origin calls fell from 3,524 to 1,689. A key created right after its 404 had been cached became visible after 1.05 s with a 1-second negative TTL and 5.06 s with a 5-second one. An origin error during a lookup was raised to the caller and not cached as a negative. And 50,000 lookups for random never-repeating missing IDs got no benefit from negative caching — 49,998 origin calls either way — but left 49,998 negative entries in the cache unless they were confined to a bounded LRU of 1,000. This guide implements negative caching with those limits.

Prerequisites

1. Measure how much traffic asks for things that do not exist

Before adding negative entries, count origin calls by outcome. A cache whose hit rate looks fine can still send most of its origin traffic for keys that are never there:

class CountingOrigin:
    async def get(self, key):
        result = await self._fetch(key)
        ORIGIN_CALLS.labels(outcome="found" if result is not None else "missing").inc()
        return result

Measured with 15% of requests for missing IDs: 2,223 of the 3,524 origin calls — 63% — were for keys that did not exist, while only 1,299 fetched real data, because found values were cached for 5 s and absences were not cached at all. Popular missing keys are typical: a deleted item still linked from old pages, a mobile app asking for a feature flag that was never set. The measurement tells you whether negative caching is worth its staleness cost.

Verify: origin call metrics are split by found and missing outcomes.

2. Store a marker for "not found", with a short TTL

Represent absence with a sentinel distinct from any real value, and give it its own TTL, usually shorter than for found values:

MISSING = object()

class Cache:
    def __init__(self, origin, ttl: float = 300.0, neg_ttl: float = 30.0):
        self.origin, self.ttl, self.neg_ttl = origin, ttl, neg_ttl
        self.data: dict = {}
        self.inflight: dict = {}

    async def get(self, key):
        now = asyncio.get_running_loop().time()
        hit = self.data.get(key)
        if hit and hit[1] > now:
            return None if hit[0] is MISSING else hit[0]
        fut = self.inflight.get(key)
        if fut is None:
            fut = asyncio.ensure_future(self._load(key))
            self.inflight[key] = fut
            fut.add_done_callback(lambda _: self.inflight.pop(key, None))
        return await asyncio.shield(fut)

    async def _load(self, key):
        value = await self.origin.get(key)            # exceptions propagate, nothing stored
        now = asyncio.get_running_loop().time()
        if value is None:
            self.data[key] = (MISSING, now + self.neg_ttl)
        else:
            self.data[key] = (value, now + self.ttl)
        return value

Measured: missing-key origin calls fell from 2,223 to 390 with a 5-second negative TTL — roughly one call per missing key per TTL period, instead of one per request. The sentinel keeps None free for callers — the cache returns None for a cached absence, exactly as the origin did — and the in-flight map coalesces concurrent misses for the same missing key into one origin call, as covered in preventing cache stampedes in asyncio.

Verify: repeated lookups of a missing key reach the origin once per negative TTL.

16,000 requests over 8 s, 15% for 200 missing IDs A grid of 3 rows by 4 columns. 16,000 requests over 8 s, 15% for 200 missing IDs negative TTL origin calls for missing keys total origin calls p99 none 2,223 3,524 51.1 ms 1 s - 2,270 51.0 ms 5 s 390 1,689 51.0 ms Origin latency 50 ms; found values cached for 5 s.

3. Never cache errors as absences

"Not found" and "could not find out" are different answers. A timeout, a 503 or a dropped connection from the origin says nothing about whether the key exists; caching it as MISSING turns a brief outage into minutes of false 404s:

async def _load(self, key):
    try:
        value = await self.origin.get(key)
    except (ConnectionError, TimeoutError):
        raise                                     # the caller sees the failure; nothing is cached
    ...

Measured: with the origin failing during a lookup, the caller received ConnectionError, no entry was stored, and the next lookup after the outage returned the real value. Only an explicit "does not exist" from the origin — a 404, an empty query result — should become a negative entry. If you want to dampen load during origin errors as well, use a separate, much shorter error cache or a circuit breaker, as in Circuit Breakers & Bulkheads, so the two kinds of answer stay distinguishable.

Verify: an origin failure during a lookup is raised to the caller and leaves no cache entry.

4. Choose the negative TTL from how fast keys appear

A negative entry hides a key for its whole TTL, even if the key is created a moment later:

await cache.get(500)          # None: cached as missing
create_record(500)            # the record now exists
await cache.get(500)          # still None until the negative entry expires

Measured: a key created right after its absence was cached became visible after 1.05 s with a 1-second negative TTL and 5.06 s with a 5-second one. Choose the TTL from the workflow: where a user creates something and immediately reads it back, either keep the negative TTL to a second or two, or delete the negative entry when the key is created — the write path knows the key, so cache.data.pop(key, None) on creation removes the staleness entirely. Across several workers, that deletion has to be broadcast, as in invalidating caches across async workers.

Verify: creating a key makes it visible to readers within the time your product requires.

A key created after its absence was cached A sequence of 6 messages between 4 participants. A key created after its absence was cached reader cache origin writer get(500) fetch: 404 store MISSING, neg_ttl create 500 get(500): None (cached) or: delete negative entry on create Measured: visible after 1.05 s (1 s TTL) or 5.06 s (5 s TTL).

5. Bound negative entries separately

Negative caching helps only when the same missing keys are asked for repeatedly. A client probing random IDs — an enumeration scan, a bug generating fresh IDs — never repeats a key, so every request still reaches the origin, and every answer adds an entry:

from collections import OrderedDict

class NegativeLRU:
    def __init__(self, max_entries: int = 10_000):
        self.max_entries = max_entries
        self.keys: OrderedDict = OrderedDict()

    def add(self, cache: dict, key, entry) -> None:
        cache[key] = entry
        self.keys[key] = True
        self.keys.move_to_end(key)
        if len(self.keys) > self.max_entries:
            old, _ = self.keys.popitem(last=False)
            cache.pop(old, None)

Measured with 50,000 lookups of random missing IDs: 49,998 origin calls with or without negative caching, and 49,998 negative entries held in the cache — until they were confined to a 1,000-entry LRU, after which the cache held 1,000. Keep negative entries in their own bounded structure, so a scan cannot evict the real values, and protect the origin from scans with rate limits rather than caching, as in per-tenant rate limits in async services.

Verify: a burst of random missing lookups leaves the number of cached entries bounded and found values still cached.

Should this absence be cached, and for how long? A decision on What did the origin say with 4 outcomes. Should this absence be cached, and for how long? What did the origin say? 404 / empty result cache MISSING, short TTL 2,223 to 390 calls timeout / 5xx raise; cache nothing no false 404s key may be created soon 1-2 s TTL, or delete on create hidden up to the TTL never-repeating keys (scans) bounded negative LRU + rate limit caching cannot help Absence is data, but cheaper to be wrong about.

Verification

Negative caching is in place and safe when:

  • Origin calls are measured by outcome, and missing-key traffic justified the change.
  • "Not found" is cached with its own, shorter TTL, using a sentinel distinct from real values.
  • Origin errors are never stored as absences.
  • Negative entries are bounded separately, and creating a key removes its negative entry where staleness matters.

Diagnostic Hook: count negative-cache hits per key and alert on keys that are both popular and missing for days. They are usually broken links, stale clients or a feature flag that was never created — cheaper to fix at the source than to keep caching their absence.

Pitfalls & edge cases

  • Caching origin errors as not-found. Turns an outage into false 404s.
  • Long negative TTLs on create-then-read flows. Measured: hidden for 5.06 s.
  • Expecting negative caching to stop scans. Measured: 49,998 origin calls either way.
  • Negative entries sharing the main cache's capacity. A scan can evict real values.

Frequently Asked Questions

What is negative caching?

Caching the fact that a key does not exist, so repeated lookups for it stop reaching the origin. In testing it cut origin calls for missing keys from 2,223 to 390 with a 5-second TTL.

How long should negative cache entries live?

Shorter than found values, and short enough for your create-then-read flows: a key created right after its 404 was cached stayed hidden for 1.05 s with a 1 s TTL and 5.06 s with a 5 s TTL.

Should I cache errors from the origin?

Not as not-found: an error says nothing about existence. Raise it to the caller and store nothing; use a circuit breaker to dampen load during outages.

Does negative caching protect against ID enumeration?

No: random never-repeating IDs all miss. 50,000 such lookups made 49,998 origin calls; bound negative entries and rate-limit the client instead.