Bloom filter: a tiny "definitely not here" test, bought with a few wrong "maybe"s

What it is for. Answering "is this thing in the set?" when the set is far too large to keep in memory, or when checking the real store costs a disk read. It is a pre-filter, never the final answer: it only saves you from asking the expensive question most of the time.

The idea. Do not store the thing itself. Store a few traces it leaves behind. A query computes the same trace positions: if any trace is missing, the thing definitely never joined. If all traces are present, the thing may have joined, or other things' traces may happen to cover those positions.

How it is built. A bit array, all zeros at first, plus a few hash functions. A hash function turns a key into a position, deterministically: the same key always gives the same positions. Joining a key means hashing it with each function and setting those bits to 1. Bits are shared: many keys may set the same bit.

How it is queried. Hash the query key with the same functions and check those bits. Any bit 0: the key definitely never joined. No false negatives, ever. All bits 1: the key may have joined. A false positive is possible.

Worked example: ten bits, two hashes. Join apple: sets bits 3 and 7. Join banana: sets bits 2 and 7. Query cherry: hashes to bits 3 and 5; bit 5 is 0, so cherry is definitely absent. Query grape: hashes to bits 3 and 7; both are 1, so grape is maybe present, but it is really apple's and banana's traces stitched together: a false positive.

The price of "maybe". A false positive costs one wasted real lookup each, nothing more. The rate is tunable: a bigger array lowers it, and more hash functions lower it up to a point, then raise it again, because too many functions set too many bits. The usual operating point is roughly 10 bits per key for about a 1% false-positive rate. Size the array for the largest set it will ever hold: at optimal load roughly half the bits are set, and well beyond that the false-positive rate climbs fast.

What it cannot do. It cannot delete: one bit may serve several keys, and clearing it would injure the others. Counting variants replace each bit with a small counter so deletes are possible, at several times the space. It cannot tell you the value, only membership. And it cannot prove presence: "maybe" is never a yes.

Where it is used. One filter per SSTable in LSM stores (Cassandra, RocksDB, HBase, ScyllaDB): the filter lives on disk with its table, is loaded into the database's one shared block cache, and skips whole tables before any data block is read. The same shape shows up wherever a cheap "definitely not" saves an expensive check: web crawlers skipping seen URLs, routers and caches skipping absent keys.

A semantic cousin, and why it is rarely used. Replace the hash functions with locality-sensitive hashes (similar vectors collide in the same bucket with high probability) and you get a distance-sensitive Bloom filter: "definitely nothing similar in the set". In practice false negatives do appear, because LSH does not guarantee collisions; the variant without false negatives costs storage exponential in the radius, and the near/far gap it needs is wide. So exact membership stays with the classical Bloom filter, and semantic neighbors stay with vector indexes.

Transfer. The read path of lsm-tree is where this filter earns its keep: it decides which table, and binary search decides where inside the table.

Kin. lsm-tree

Agent audit checklist: read this node, then check a filter deployment against every line, and report each item with evidence.

1. Query semantics: says absent means absent, says present means maybe; no caller treats "maybe" as a yes.
2. Sizing: bits per key and hash count stated, array sized for the largest set, false-positive rate measured not assumed.
3. Deletes: either absent by design (immutable tables) or a counting variant with its space cost stated.
4. Cache placement: filter lives with its data on disk and loads into a shared cache, not one cache per table.