Bloom filters

A Bloom filter is a set that answers one question: have I seen this before? It can say definitely not or probably yes. It never gives a false negative, sometimes gives a false positive, and uses a small, fixed amount of memory no matter how large the items are.

How it works

The filter is an array of m bits, all starting at 0, and k hash functions that each map an item to a position in the array.

• Add an item by hashing it k times and setting each of those bits to 1.
• Check an item by hashing it the same way. If any of its bits is 0, the item was never added. If all of them are 1, it probably was — or other items happened to set the same bits.

Try it

Add a few words, then check some you did and didn't add. Fill the filter up and false positives start to appear.

The k positions come from two hashes using double hashing: hi(x) = (h1(x) + i · h2(x)) mod m, with 32-bit FNV-1a for both. This is a common way to get k hashes for the cost of two.

False positives

After n items have been added, the chance that a new item is a false positive is about

p ≈ (1 − e^−kn/m)^k

The rate grows as the filter fills. For a target rate p, the best choices are m = −n ln p / (ln 2)² and k = (m/n) ln 2. A 1% false positive rate takes about 9.6 bits and 7 hashes per item, whether the items are 4-byte integers or long URLs.

No deletes

You can't remove an item, because its bits may be shared with other items and clearing them would create false negatives. A counting Bloom filter fixes this by storing a small counter instead of a bit in each position, at several times the memory.

Where they're used

Bloom filters belong in front of something expensive. Databases built on LSM trees, such as Cassandra and RocksDB, keep one per data file so a read can skip files that can't contain the key. CDNs use them to avoid caching content that has only been requested once. In each case a false positive costs one unnecessary lookup, and a true negative saves one.

❧