Bloom Filters: Proving a Key Is Absent

A Bloom filter is a compact structure that answers whether a key might be in a set. Its answer "absent" is certain; its answer "present" means only "probably". That one-sided certainty is enough to stop requests for keys that exist nowhere from reaching the database at all.

The problem it solves here. A cache helps only with keys it has seen. Requests for keys that exist nowhere, such as user ids an attacker makes up, miss the cache every time and reach the database every time. This is called cache penetration. A Bloom filter holding every key that exists can answer "absent" before the cache or the database is touched.

How it works. The filter is an array of bits, all zero at the start. To add a key, several hash functions each turn it into a position, and those bits are set to one. To look a key up, the same positions are checked: if any is zero, the key was never added. If all are one, it may have been added, or other keys may have set those bits.

What a false positive costs. A "maybe" sends the request on to the cache and the database, which answer correctly; the filter has saved nothing on that request, but done no harm. A larger array and more hash functions make false positives rarer. The filter can never wrongly say "absent", so it never hides a key that exists.

Where else you meet it. Cassandra keeps a Bloom filter for each data file on disk, so a read can skip every file that cannot hold the key.

So trust a Bloom filter's "absent" and check its "present": the certainty runs in one direction only.