Bloom filters

How a Bloom filter works

A Bloom filter answers one question cheaply: is this key in the set? It is a bit array of m bits, all starting at 0, plus k independent hash functions that each map a key to one of the m positions. It stores no keys and no values, only bits, which is why it costs single-digit bits per key instead of the size of the keys themselves.

insert(x):  for i in 1..k:  bits[ hash_i(x) mod m ] = 1
query(x):   for i in 1..k:  if bits[ hash_i(x) mod m ] == 0: return "definitely not present"
            return "possibly present"

Insert sets the k bits for a key to 1. Query checks those same k bits: if any one is 0, the key was never inserted; if all k are 1, the key might be present.

Why a Bloom filter has no false negatives

The answer is one-sided. A query returns "definitely not present" or "possibly present", and only the first is certain. If a key was inserted, its k bits were set to 1 and a standard filter never clears bits, so a query for it always finds all k set. That is why a negative can be trusted to skip the real lookup.

A false positive happens when the k bits of a key that was never inserted were all set by other keys. The filter then says "possibly present" for a stranger.

Wrong "possibly present" means the key is in the set. Right it means maybe, so you still run the real lookup to confirm a positive. Only the negative answer is final.

Why you cannot delete from a Bloom filter

Bits are shared. To remove a key you would clear its k bits, but some of those bits are also the 1-bits of keys still in the set, and clearing them makes a later query for those keys find a 0. That is a false negative, which breaks the one guarantee the filter offers. A counting Bloom filter fixes this by storing a small counter per position that insert increments and delete decrements, at roughly 3 to 4 times the space.

Where Bloom filters are used

The classic case is the read path of an LSM-tree store like RocksDB or Cassandra. Each on-disk table carries a Bloom filter, and a point lookup checks it first: if the filter says "definitely not present", the engine skips reading that table and saves a disk seek for an absent key. The same pattern shows up in cache and CDN sharing, in deduplication gates, and in safe-browsing URL checks, always as a cheap in-memory front end to an expensive exact store.

Sizing a Bloom filter: m, k, and the false-positive rate

Three knobs drive the false-positive rate p: the bit count m, the item count n, and the hash count k.

P(a given bit still 0 after n inserts) = (1 - 1/m)^(kn) ~= e^(-kn/m)
false-positive rate                    p ~= (1 - e^(-kn/m))^k     # rises with n, falls with m
optimal hash count                     k* = (m/n) * ln 2 ~= 0.693 * (m/n)
bits per element for target p          m/n = -ln(p) / (ln 2)^2 ~= 1.44 * log2(1/p)

At k* about half the bits are 1, where each bit carries the most information. Past it, extra hashes set 1s faster and push p back up, so more hashing is not always better. As a rule of thumb, about 9.6 bits per key buys roughly 1% false positives, and each further 4.8 bits per key cuts the rate about 10x (so about 4.8 bits/key at 10%, 9.6 at 1%, 14.4 at 0.1%). That cost is per key and independent of key length, since only bits are stored.

Why deletion breaks the guarantee

Set operations on shared bits do not commute: clearing a deleted key's bits can zero a bit a present key still relies on, which turns a certain negative into a false negative. A counting Bloom filter replaces each bit with a small counter, usually 3 or 4 bits, so insert increments and delete decrements and the two commute. The cost is 3 to 4 times the space, plus a counter-overflow edge case. LSM engines dodge the whole problem by never editing a filter: compaction writes a new immutable table with a freshly built filter, and deletes ride the tombstone path instead.

Failure modes and limits

p is never zero for a non-empty filter, only tunable toward small. It also degrades under overload: a filter provisioned for n items shows a much higher rate at several times that load, because p tracks n/m, so size for the real peak. The (1 - e^(-kn/m))^k formula assumes bit independence and runs slightly optimistic for very small m. And a positive is unverified, so a Bloom filter is a gate in front of the exact store, never the store itself.

Where they pay off in real systems

RocksDB embeds a filter per SSTable and skips the data blocks on a "definitely not present" probe, at a default near 10 bits per key. Cassandra keeps a per-SSTable filter off-heap and skips whole tables, tuned by bloom_filter_fp_chance (default 0.1 for LeveledCompactionStrategy, 0.01 otherwise), where 0.01 costs about 3x the memory of 0.1. The shared pattern is a negative cache: an O(k) in-memory check that pays off wherever a negative answer is common and the exact check is a disk seek or a network round trip.