Caching Absence with Negative Entries and Bloom Filters

A cache normally holds answers. Absence is also an answer, and one that ordinary caches represent badly: a key that is not in the cache is indistinguishable from a key that does not exist in the source. That indistinguishability is harmless when misses are rare and expensive when they are the majority of traffic, because an attacker or a broken client can generate unlimited keys that all miss and all reach the source. The two mechanisms that fix it — a cached tombstone and a probabilistic membership filter — differ in what they can promise and in what they cost per key.

The lookup that finds nothing, repeatedly

Requests for identifiers that do not exist are not an edge case. A crawler following stale links, a client retrying with a corrupted identifier, a user enumerating sequential ids, or an API accepting arbitrary path parameters all produce them. The source answers each with a lookup that finds nothing, which is usually a full index probe plus a response — the same cost as a successful read, with no cached value to show for it. Because the answer is not cached, the next request for the same missing identifier repeats the work.

The failure is asymmetric. A missing positive entry costs one source read and is then cached. A missing negative entry costs one source read per request, forever, at whatever rate the traffic arrives. The cache’s hit ratio is unaffected — a key that was never cached cannot lower it — so the problem is invisible in cache metrics and visible only as source load that does not correspond to cached objects.

Negative entries and the danger of a wrong absence

The direct fix is to cache the absence: store a marker under the key with a short TTL, and treat the marker as a hit that returns “not found”. This costs the same memory as a small value and removes the repeated source reads.

The danger is the direction of the error. A stale positive entry serves an old value; a stale negative entry asserts that an entity does not exist, which downstream code often treats as a permanent condition — 404 responses cached by intermediaries, objects skipped in a reconciliation pass, rows treated as deleted. The TTL for a negative entry should therefore be short, and it should be shorter than the positive TTL for the same entity type, because the cost of being wrong is higher and the value of being right is lower.

The second hazard is entry creation for deleted entities. A delete that removes the positive entry leaves no tombstone, so the next read misses, hits the source, and repopulates the value if the source still has it — or caches absence if it does not. If the entity is later recreated with the same identifier, the negative entry suppresses reads until it expires. Versioned keys handle this naturally because the recreated entity gets a new address; with plain keys, a delete must write a tombstone rather than remove the key, and the tombstone must expire before any legitimate recreation is likely — the mechanism invalidation by deletion and versioned keys develops in detail.

A third hazard is memory exhaustion by adversarial keys. Caching absence for every nonexistent identifier lets an attacker fill the cache with entries for keys that will never be read again, evicting live data. Keys generated at random produce a distinct miss each time, so every request writes a new negative entry. The cure is either to bound the rate at which negative entries are created, or to use a structure whose size is a function of the legitimate key set rather than the request stream — which is where filters come in.

Bloom filters and the arithmetic of false positives

A Bloom filter answers “definitely not present” or “possibly present” using a bit array of m bits and k hash functions. Insertion sets k bits; a query checks the same k bits and rejects if any is clear. Nothing is stored per key, so the space cost is the array size, and the error is one-sided: false positives occur, false negatives do not, provided the filter is never rebuilt incorrectly or queried against a different hash seed.

The false-positive rate for n inserted keys is approximately (1 − e^(−kn/m))^k, minimised at k = (m/n) ln 2. At that optimum the relationship collapses to a simple rule of thumb:

• m/n = −log₂(p) / ln 2 ≈ 1.44 log₂(1/p) bits per key.

One percent false positives therefore costs about 9.6 bits per key with k ≈ 7; a tenth of a percent costs about 14.4 bits per key with k ≈ 10. A million keys at one percent fits in roughly 1.2 megabytes. For comparison, caching the keys themselves — even as 16-byte hashes — would cost 16 megabytes and require a hash table with its own overhead. The filter is a compression of the key set that is only useful for membership, not retrieval.

The cost side is the k hash computations per lookup and per insert. With k around 7 and a well-distributed hash, that is a handful of memory accesses into a bit array that may not fit in cache: for a large filter, each probe can miss L2, so the filter’s latency is dominated by random memory access rather than arithmetic. This is why implementations derive the k probes from two base hashes rather than computing k independent hashes, and why some use a blocked layout to improve locality at a small cost in false-positive rate.

Where the filter sits

The filter is not a cache. It sits in front of the source, and its false positives become source reads, so the system still needs the source to answer “not found” correctly. Its purpose is to make the common case cheap: for a stream of requests where most identifiers do not exist, a 1% false-positive rate reduces source load by a factor of a hundred.

Placement matters. A filter in the application process is rebuilt on every deploy and on every instance, and its memory is duplicated per instance. A filter in the cache tier is shared but needs a protocol operation to query it, which reintroduces a round trip — affordable when the alternative is a source read, not when the alternative is a local map lookup. The common arrangement is a read-only filter loaded from a snapshot at startup and refreshed periodically, accepting that new keys are invisible to it until the refresh. That staleness is safe only in one direction: a key added after the snapshot will be reported absent, causing false negatives, which is the error Bloom filters are supposed to be incapable of.

The fix is to make the filter advisory rather than authoritative: query it first, and on “possibly present” go to the source, which is the only authority. Then a stale filter costs extra source reads for recently created keys and never produces a wrong answer. That is the correct contract, and it is why Bloom filters in front of a database are described as a load-reduction mechanism rather than a correctness mechanism.

Deletion, counting, and rebuilding

Standard Bloom filters cannot delete, because clearing a bit would clear it for every key that hashed there. Three responses exist.

A counting Bloom filter replaces each bit with a small counter, incremented on insert and decremented on delete; the cost is typically 4 bits per slot instead of 1, and the counters can overflow in a hot slot, which must then be treated as permanently set. A cuckoo filter stores short fingerprints in a cuckoo hash table, supports deletion, and has better lookup locality, at the cost of a more complex insertion that can fail and require a rebuild. A partitioned scheme — a filter per time window, with old windows dropped wholesale — supports expiry rather than deletion and matches the common case where the entities are time-bounded.

In practice the simpler answer is usually to rebuild: the filter is derived state, and a rebuild from the source scans the key set once. Rebuild cost scales with the key set size, and the rebuild must be atomic from the readers’ perspective, which means building the new filter beside the old one and swapping a pointer.

Sizing against a key set that grows

A filter sized for n keys degrades as the set grows past n: the false-positive rate rises steeply, because the bit array fills. With m/n halved, the rate at a fixed k rises by roughly a factor of 2^k while the filter is still sparse, and climbs toward one as the array saturates. Systems that provision a filter for the current key count and never resize end up with a filter that passes almost everything, which is worse than no filter because it adds probes without reducing source load. The size must be chosen for the growth expected over the filter’s lifetime, or the filter must be rebuilt on a schedule with a growth factor — the same reasoning that applies to any structure sized by an estimated cardinality, and to cache capacity itself in hit ratio arithmetic and working-set sizing.