Bloom filters

Why it matters

Before reading a file from disk, calling another service or querying a database, it is worth asking: is the key even there? Answering that exactly needs a copy of all the keys. A Bloom filter answers it with about ten bits per key and no false negatives: when it says "not here", the key is definitely absent and the expensive lookup is skipped. That one trick removes most of the wasted reads in LSM storage engines, caches, CDNs and distributed databases, and it is the probabilistic structure every interviewer expects you to know.

The idea

A Bloom filter is a bit array of m bits, all zero, and k independent hash functions. To add an item, hash it k times and set the k resulting bits to one. To query an item, hash it k times and check the bits: if any is zero, the item was never added (definitely not); if all are one, the item was probably added (probably yes), because other items may have set those same bits. There are no false negatives and a tunable rate of false positives.

Sizing it

The false-positive rate depends on bits per item and the number of hashes. With about 10 bits per item and 7 hash functions, the rate is around 1 percent; with 15 bits per item it is about 0.1 percent. The optimal k is roughly 0.7 times the bits per item. So a filter for 100 million keys at 1 percent false positives is about 120 MB, versus several gigabytes to store the keys themselves. The filter is sized for an expected count; exceeding it raises the false-positive rate, so either size with headroom or use a scalable variant that adds filters as it grows.

What it cannot do

Delete: clearing a bit might also clear it for another item that shares it, creating false negatives, which the structure promises never to do. Counting Bloom filters replace bits with small counters to allow deletes at several times the space; cuckoo filters, next lesson, solve it differently. Enumerate: the filter does not store items, only bits. Guarantee presence: "probably" always means a real lookup must follow.

Where it earns its place

1. 1

   LSM storage engines

   Each sorted file carries a Bloom filter of its keys, so a point read skips every file that definitely lacks the key and touches disk only for the one or two that might. RocksDB, Cassandra, HBase and LevelDB all depend on this.
2. 2

   Caches and CDNs

   Before caching an object, check whether it has been requested before; cache only on the second request so one-hit wonders never evict useful content. Akamai reported this cut cache churn dramatically.
3. 3

   Avoiding remote lookups

   A filter of known usernames, seen URLs or existing row keys in front of a database or service turns most negative lookups into an in-memory check. Distributed databases ship filters between nodes to avoid cross-node reads.
4. 4

   Deduplication and safe browsing

   Web crawlers track visited URLs; browsers check URLs against a filter of malicious sites locally and only call the full service on a probable hit.

Operating one

Choose the false-positive rate from the cost of a wasted lookup: if a miss costs a disk read, 1 percent is fine; if it costs a cross-region call, spend bits to get 0.01 percent. Rebuild the filter when the underlying set changes substantially, since it only grows. Use fast, non-cryptographic hashes (MurmurHash, xxHash) and derive the k hashes from two base hashes to save CPU. Persist filters next to the data they describe so a restart does not need a rebuild.

Trade-offs

A Bloom filter trades a small, controllable false-positive rate and the inability to delete for a membership test in a few bits per item with no false negatives. It is a filter in front of a slower truth, never the truth itself, and it pays for itself whenever negative lookups are common and the real lookup is expensive.

In an interview

Name the numbers and the placement: "Each SSTable has a Bloom filter at 10 bits per key, about 1 percent false positives, so a read for a missing key touches no disk. In front of the user-service, a filter of existing usernames at 0.1 percent lets 'is this name taken' answer locally almost every time, with a real lookup only on probable hits." Saying "no false negatives, tunable false positives, no deletes" in one breath shows you know the contract.