Bloom filters

Q: Can a bloom filter ever say "not present" about something that is present? Why does the answer decide where you are allowed to use one?

No. Adding an item sets its bits, and nothing ever clears them. So if it was added, all its bits are 1 and the test passes. The only error is a false positive. That one-sidedness is what makes it usable as a gate in front of expensive work. A "no" is trustworthy enough to skip the lookup completely, and a "yes" just means doing the work you would have done anyway. If it could produce false negatives you could not use it for anything real, because you would sometimes tell a user their data does not exist when it does. It also explains the deletion restriction. Clearing bits for a removed item would clear bits shared with items that are still there, and that is how you would create false negatives.

A tiny structure that says "definitely not here" or "probably here", and never the wrong way round.

What problem does bloom filters solve?

Sometimes the expensive part is finding out that something does not exist. Checking whether a username is taken, or whether a key is in a store, can mean a disk read or a network call for an answer that is usually "no".

A bloom filter answers that in memory, in a few microseconds, using a small fraction of the space the real data takes.

What bloom filters costs you

What it costs you

It can say yes when the answer is no. Those are false positives, so every yes has to be checked against the real store. It can never say no when the answer is yes, which is what makes it safe. You cannot delete from a standard bloom filter, and you cannot list what is in it. And the false positive rate rises as you add items, so a filter sized for a million entries gets bad at ten million.

Every concept in here states a cost. A technique with no price is a technique you have not understood yet — and naming the cost out loud is most of what separates a senior answer from a junior one.

When to reach for bloom filters, and when not to

Use it when

Avoiding pointless lookups for keys that mostly do not exist.
Stopping cache penetration, where requests for ids that do not exist hit the database every time.
Storage engines checking whether a key might be in a given file before reading it. This is standard in LSM-tree databases.
Removing duplicates from a huge stream, where an occasional wrong "seen this" is acceptable.

Do not, when

A false positive is expensive or unsafe. Never use one as the final word on anything.
The set is small enough to hold in a normal hash set. Then just do that.
You need deletion, counting, or a list of members. A counting bloom filter handles deletion, using more space.

How bloom filters actually works

Hash the key three ways. If any bit is 0, it is definitely absent, answered in memory with no disk touched. If all are 1, it is probably present, so go and check.

How it works. You have an array of bits, all zero, plus k different hash functions. To add an item, hash it k ways and set those k bits to 1. To test an item, hash it k ways and look. If any bit is still 0, it was definitely never added. If all bits are 1, it was probably added, or those bits happened to be set by other items. That second case is the false positive.

The size intuition worth remembering: about 10 bits per item gives roughly a 1% false positive rate. So a million keys cost around 1.2 MB. The real set of a million 20-byte usernames, plus index overhead, is tens of megabytes and lives on disk. That ratio is why the filter is worth having.

You get to choose two of three: how many items you expect, the false positive rate you accept, and the memory. Fix two and the third follows. Size it for the number you expect at the end of its life, not the number today.

The cache penetration case is the one to raise without being asked. Requests for ids that do not exist cannot be cached, because there is nothing to store, so each one reaches the database. Someone probing random ids drives your miss rate to 100%. A bloom filter of all existing ids stops almost all of them in memory. The cost is that the filter has to keep up with new inserts. A newly created id is briefly missing from the filter and gets wrongly rejected, which is why you add to the filter on write. Deleted ids stay in the filter and only cause false positives, so a common approach is to rebuild the filter now and then.

Relatives worth naming in one line each. Counting bloom filters support deletion by using small counters instead of single bits. HyperLogLog estimates how many distinct items you have seen, in about 12 KB. A cuckoo filter supports deletion and is often smaller at low error rates.

Common trap

Treating a positive as an answer instead of a hint.
Sizing for today's data, then watching the error rate climb.
Trying to delete from a standard filter and creating false negatives.

Say this

"A bloom filter of existing ids in front of the cache, about 1.2 MB per million keys at a 1% error rate, so lookups for ids that never existed die in memory instead of hitting the database. Cost: 1% of real lookups do a pointless query, and new ids must be added to the filter on write."

The bloom filters follow-up an interviewer will ask

"What happens when the bloom filter says yes but the item does not exist?"

What a strong answer sounds like

You do the lookup you were trying to avoid, find nothing, and return not-found. So it costs you one wasted query and nothing else. That is the deal: the filter is a speed-up, never an authority, and the code behind it has to be correct on its own. At a 1% false positive rate, I have removed 99% of the pointless lookups, and that is the win. The dangerous direction would be the other one, saying no about something that exists, and a bloom filter, by design, cannot do that, because an item that was added always has its bits set. That one-sidedness is the reason it is safe to put in front of a correctness-sensitive path at all.

Your turn

60-second self-check

Can a bloom filter ever say "not present" about something that is present? Why does the answer decide where you are allowed to use one?

Stuck? Take one hint at a time0 of 2 used

0 / 25 characters

Learn it from the source

This page gets you interview-ready. These take you to where the idea is actually specified or measured — read them when you want the real depth.

Redis — Bloom filters ↗A production implementation, with the error-rate and capacity knobs exposed.
Bloom filter ↗The maths for choosing size and hash count against a false-positive rate.

Related concepts

Caching Indexes and what makes a query slow Search indexing basics

Where you will use this

Web crawlercore Distributed key-value storehard