Bloom Filter
What it is
A Bloom filter answers one small question: could this item be here? It uses a fixed, small amount of memory, no matter how many items you add. It can say yes for an item that was never added. People call this a false positive. It must never say no for an item that really was added. Databases and web caches use it to skip a slow lookup when the answer is almost certainly no.
The core idea
The filter is a row of bits, all starting at 0. Adding an item picks k positions in that row (using k different hash functions) and sets each one to 1. Checking an item picks the same k positions and looks at them. If any of them is still 0, the item was definitely never added. If all of them are 1, the item was probably added, but maybe not: some other items could have set those same bits between them. With m bits, k positions per item, and n items added, the expected rate of a wrong yes is
p = (1 - e^(-k*n/m))^kMore bits bring this rate down. More hash positions can help too, but only up to a point, and each one costs more time per check.
Example
Add "cat". It sets bit 2 and bit 7. Checking "cat" looks at bit 2 and bit 7. Both are 1, so it answers yes, correctly. Now add "dog", which happens to also set bit 2 and bit 7. Checking some item that was never added, but which also lands on bit 2 and bit 7, still answers yes. That is the mistake from above: the bits are shared evidence, not a list of exact items.
Where you meet this
- Cassandra keeps a Bloom filter for each data file (SSTable). A read asks the filter first and skips the files that cannot hold the row. A wrong yes only means Cassandra looks in a file for nothing. (Cassandra Bloom filters)
- RocksDB, when a filter is turned on in its settings, stores a filter inside each of its files. When the filter rules a key out, a lookup skips that file's data blocks. (RocksDB Bloom filter)
- PostgreSQL has a
bloomindex type. Because it can say yes by mistake, PostgreSQL rechecks every row it returns against the real values. (PostgreSQL bloom)
When to choose it: a "no" saves expensive work, like a disk read or a network call, and a rare wasted check is fine. You also need it to be small: Cassandra notes that a 1% wrong-yes rate needs about three times the memory of a 10% rate.
When not to: you need an exact answer, the set is small enough to keep in a normal hash set, or you need to remove items. A plain Bloom filter cannot remove anything, because clearing a bit could also clear it for other items.
Common bugs
- Checking only one position, or saying yes as soon as any one bit is set, instead of checking all
k. - Using hash functions that are not really independent, so they often land on the same positions.
- Mixing up bits and bytes when you store or look up a position.
- Stopping one bit short of the end of the array.
- Replacing the filter with an exact set, or quietly using far more bits than asked for. Both avoid ever being wrong, which means they are not really being a Bloom filter anymore.
Keep it fast
Checking an item should only ever touch k bits, never the whole array. Picking those k positions should be cheap, usually two hash values combined into more, not k separate full hashes.
Learn more
Bloom's 1970 paper first described this trade of memory for the occasional wrong answer. Databases, web crawlers, and content delivery networks all use it to skip expensive lookups most of the time. A counting Bloom filter keeps a small counter at each position instead of a single bit, so items can be removed again too.