Negative caching: the misses cost more than the hits

A product lookup endpoint has a healthy cache. Hit rate sits at 94 percent, latency is flat, and the database is comfortable.

Then a partner integration starts sending requests with SKUs from their own catalogue, most of which do not exist in yours. Hit rate stays at 94 percent, because the metric only counts lookups for things that were cacheable. The database goes from 200 queries per second to 4,000, all of them returning zero rows, all of them scanning an index and finding nothing, all of them repeating the same fruitless work forever.

The cache was never protecting that path. A cache that only stores what it found offers no protection at all against asking for what is not there.

The asymmetry nobody notices

Standard cache-aside logic has a gap that is easy to read past.

def get_product(sku):
    cached = cache.get(f"product:{sku}")
    if cached is not None:
        return cached

    product = db.query_one("SELECT * FROM products WHERE sku = %s", sku)
    if product:                                # <- the gap
        cache.set(f"product:{sku}", product, ex=3600)
    return product

That if product is doing something significant. It means the cache learns from every success and nothing from any failure. Ask for a SKU that does not exist a million times and the database answers a million times.

The natural objection is that lookups for missing things are rare. That holds until the caller is not your own frontend. Partner integrations, scrapers, stale mobile clients holding deleted ids, a migration replaying old identifiers, or somebody enumerating an id space all produce sustained misses, and none of them look unusual in a request log.

When the key is user supplied it becomes an attack

The security version of this has a name: cache penetration.

If the cache key derives from user input, an attacker does not need to find a slow endpoint. They need to find a cacheable one and then ask for things that do not exist.

GET /api/products/aaaaaaaa   -> miss, DB query, no cache write
GET /api/products/aaaaaaab   -> miss, DB query, no cache write
GET /api/products/aaaaaaac   -> miss, DB query, no cache write

Every request bypasses the cache by construction. The hit rate metric stays high because these lookups never become cacheable. The database absorbs the full request rate for an endpoint that was sized on the assumption that the cache would absorb 94 percent of it.

flowchart TB
    REQ["Request for a key<br/>that does not exist"] --> C{"In cache?"}
    C -->|"no, and never will be"| DB[("Database query<br/>returns zero rows")]
    DB --> SKIP["if product: cache.set(...)<br/>condition is false"]
    SKIP --> NOWRITE["Nothing cached"]
    NOWRITE -.->|"next identical request"| REQ

    style NOWRITE stroke:#ef4444,stroke-width:3px,color:#fff
    style DB stroke:#f59e0b,stroke-width:2px,color:#fff

I find this one genuinely underrated as a threat, because it needs no vulnerability. The application behaves exactly as designed. The design just assumed misses were rare and did not check.

Caching the absence

The fix is to store a marker rather than skipping the write.

MISSING = "\x00missing"      # a sentinel that cannot collide with real data

def get_product(sku):
    cached = cache.get(f"product:{sku}")
    if cached == MISSING:
        return None                       # known absent, no origin call
    if cached is not None:
        return cached

    product = db.query_one("SELECT * FROM products WHERE sku = %s", sku)
    if product:
        cache.set(f"product:{sku}", product, ex=3600)
    else:
        cache.set(f"product:{sku}", MISSING, ex=60)   # shorter, deliberately
    return product

Two details in there matter more than they look.

The sentinel has to be distinguishable from both a real value and a cache miss. Using None or an empty string collapses three states into two, and then a genuine value of empty string reads as absent. A byte that cannot appear in your serialised values, or a wrapper type, keeps the states separate.

The negative TTL is deliberately much shorter, and the reason is asymmetric risk.

Why negative entries expire sooner

Both directions of staleness are wrong. They are not equally likely or equally damaging.

A record that exists rarely stops existing. Deletion is uncommon in most systems, and when it happens a short window of serving a deleted record is usually tolerable.

A record that does not exist very frequently starts existing. Somebody creates an account, a webhook arrives, a product is published. If a reader looked microseconds before that write and cached the absence for an hour, the new record is invisible for an hour to every reader.

That failure mode is nasty because it is time dependent and unreproducible. The bug report says the record was created but does not appear, and by the time anyone investigates, the entry has expired and everything works.

The other half of the answer is to delete the negative entry at write time. If the code path that creates a product also invalidates product:{sku}, the TTL stops being the only defence. That is worth doing wherever the write path is known, and negative TTLs stay short anyway for the writes you do not control.

A short TTL also means a hot negative entry expires often, and each expiry lets concurrent misses stampede the origin, so a hot absence needs the same protection as a hot key.

A Bloom filter in front, when the key space is enumerable

If misses are not just possible but adversarial, caching each one still means one origin query per distinct key, and an attacker can generate unlimited distinct keys.

A Bloom filter containing every key that exists answers the question before any lookup happens.

# Populated from the source of truth, rebuilt periodically.
if sku not in product_filter:
    return None          # definitely absent, no cache and no database touched

A Bloom filter never produces a false negative, so “not in the filter” is authoritative and safe to act on. False positives fall through to the normal cache path and cost a lookup, which is the correct direction for the error to point.

This is the shape where keeping the filter small enough to stay in cache matters more than its theoretical false positive rate, because a filter that has spilled to main memory is adding a random read to the path it was supposed to make cheap.

Deletion is the awkward part, since a plain Bloom filter cannot remove entries, which is exactly the constraint that makes Cuckoo filters interesting for membership sets that change. For a set that mostly grows, periodic rebuilds are simpler than either.

What to measure

Hit rate alone is misleading, because it is computed over lookups that produced a cacheable result. Track misses separately, split into misses that found something in the origin and misses that did not.

That second number is the one that tells you whether you have this problem. If misses-that-found-nothing is a meaningful fraction of traffic, the cache is not covering your most expensive path. If it is growing while your traffic is flat, somebody is enumerating your key space.

I would also alert on the ratio rather than the absolute count. A steady background of genuine not-found lookups is normal in most systems. A ratio that moves is the signal, and it moves before the database does.