Negative caching and Bloom filters

Why is caching absence so cheap yet rare, and how does a Bloom filter reverse the trade?

Negative caching: the cheapest entry on the dearest path

The absent-key read is the most expensive read path a system has. A lookup that misses must rule out every possibility before concluding that nothing is there: every LSM level (an LSM-tree is a write-optimized storage structure with several sorted files on disk, all of which a read may have to check), the full index, possibly a whole partition scan, and in a distributed store possibly a scatter to every shard with a wait on the slowest. Meanwhile the entry costs nothing to create (you learned the absence for free while paying for the miss) and occupies almost no space.

So S is maximal and P is about 0: negative caching passes the amortization inequality more easily than any other mechanism here, at almost any reuse rate. It is also the only derived cache with a perfectly known, single-key dependency set, so exact invalidation is trivially available: inserting key k invalidates exactly the negative entry for k and nothing else. Fan-in is one, and you know which key.

Given all that, it should be everywhere. Two things stop it, and neither is about hit rate.

Obstacle 1: the key space is unbounded

Existing keys are bounded by the data. Non-existing keys are bounded only by the key's type. A client retry loop, a scanner, a misconfigured integration or an attacker can generate negative entries without limit, and every one evicts a positive entry that was earning its place. In a single shared LRU this is fatal. The mitigation is structural, not a tuning knob: negatives need their own capacity partition with its own cap, so the unbounded population cannot compete with the bounded one. This is the first hard argument here for partitioned capacity, and Making it fit finds others.

Obstacle 2: its staleness has the worst user experience for the shortest-lived entries

A negative entry is invalidated by a create, which is exactly the write whose author most expects read-your-writes. ("I just registered and it says I do not exist.") The technical fix is free, because the dependency is one known key. People fall back to short TTLs anyway for an organizational reason: the write path often does not know the negative cache exists. That is a coupling cost, not a technical limit, and it is worth naming as such.

The Bloom filter is the same mechanism with the trade reversed

A Bloom filter is a compact bit-array structure that answers "definitely absent" or "maybe present". It uses O(bits) per key, not O(entry). It is a complete negative cache: it never forgets an absence it was told about, but it has a false-positive budget (sometimes it says "maybe present" for a key that is absent). An LRU negative cache is an incomplete one: it may have evicted the absence, but it has no false positives. Each trades away exactly what the other keeps.

That duality tells you which one to use without benchmarking.

When the absent set is enormous and you can tolerate a fraction of wasted lookups, take completeness and pay with false positives. This is why every LSM SSTable (a sorted immutable file) carries a filter.
When the absent set is small and hot and a wasted lookup is unacceptable, take exactness and accept that you will sometimes forget.

The LSM read path runs both at once: per-table filter, block cache and row cache. That is the derivation ladder built into a single read.

In one sentence: the cheapest entry on the dearest path, with one known dependency key. Exact invalidation is therefore free; the key space is unbounded, so capacity must be partitioned; and a Bloom filter is the same thing with completeness and exactness swapped.

Case, resolvedConstructed case · Ifeoma at Dawnpost

The result cache that stopped working

A result cache stopped working once a table moved to streaming ingestion with a commit every 10 seconds, a schema call took 200 ms through the catalog, and a crawler sent millions of lookups for articles that do not exist. Where it started: The derivation ladder →

Ifeoma computes the bound before touching any settings. The streaming table receives a new commit every 10 seconds. A dashboard that refreshes every 60 seconds sees a new snapshot id each time, so a byte-identical repeat within the inter-write interval is nearly impossible: h is close to zero. No setting can change that. The result cache was fine for the batch tables and useless for the streaming one.

She stops trying to cache the final answers over the streaming table. Instead she moves down the ladder. First, she caches file blocks on local NVMe (immutable files, content-addressed, nothing to invalidate). Second, she builds one materialized view for the editors' main dashboard. She stores (sum, count) pairs so that averages can be maintained on the delta, and she measures that the daily delta is about 3% of the base table, below the few-percent-to-20% crossover, so incremental refresh beats a rebuild. She avoids MIN/MAX columns that would need recomputation under deletes.

The 200 ms schema call is the easy one. It is a metadata cache problem: λ is every query and n is one. She caches the immutable manifests forever and puts a short TTL only on the snapshot pointer, so all cached listings agree with one another. She also marks the schema lookup with column IDs, so that a stale name-to-position mapping cannot misread bytes.

Last, the crawler. Millions of absent article IDs reach the database. She adds a negative cache in its own capacity partition, with a cap, so absent keys cannot push out real articles. For the larger absent set she puts a Bloom filter in front of the database, accepting a small false-positive rate. Inserts of a new article delete its negative entry directly, so a newly published article is never reported missing.