A read arrives for a key. That key could be in any of a dozen files sitting on disk, and the database does not know which one.
It could open each file and look. Disk reads cost milliseconds — plural — and a database that spends milliseconds per read on files that do not contain the key spends most of its life waiting.
So it asks a cheaper question first.
Before touching disk, the database consults a structure that lives entirely in memory: has this key ever been inserted?
There are exactly two answers. “Definitely not” means the key was never inserted, and the disk read can be skipped. “Probably” means the key might be there, and the read proceeds.
The answers are not symmetric. One is a proof. The other is a guess. Everything else follows from that.
The structure is a Bloom filter. It answers set membership — is this item in the set? — in about one byte per item, regardless of how large the items are.
It is allowed to be wrong, but only in one direction. It never reports absent for an item that was inserted. It sometimes reports present for an item that was not. That one-sided error is what buys the space.
Burton Bloom published the idea in 1970, in a five-page paper titled “Space/Time Trade-offs in Hash Coding with Allowable Errors.” Memory then was measured in kilobytes and budgeted accordingly.
The last three words are the argument. Tolerate a bounded error rate and the space cost collapses. Those same five pages now sit inside RocksDB, Cassandra, Chrome, and most of the content networks delivering this page.
Bloom’s example was automatic hyphenation. A dictionary of roughly half a million words, of which ninety percent hyphenate by simple rules; the remaining ten percent need a lookup in the full dictionary.
The dictionary did not fit in memory. But the program never needed the words — only an answer to a cheaper question: could this word be one of the tricky ten percent? Accept an occasional wasted lookup on an ordinary word, and the memory cost falls from impossible to trivial.
Two parts. The first is an array of bits, all zero. The illustration shows thirty-two of them; a production filter has millions.
The second is a handful of hash functions. Each maps an item to a position in the array, deterministically: same input, same position, every time. Nothing else is stored.
Insert “cat”. Hash it three times; the functions return positions 5, 11, and 26. Set those three bits to 1. The insert is finished.
Note what did not happen. The letters c-a-t were never written anywhere — no string, no pointer, no list. “cat” now exists in this structure only as three set bits among twenty-nine zeros, and from those three bits the filter can recognise it later.
Insert “dog”: positions 3, 11, and 20. Position 11 is already 1, set by “cat”. A bit that is already 1 simply stays 1; the filter does not count how many items set it.
Insert “fish”: 8, 14, and 26. Position 26 is shared with “cat”. As items accumulate their fingerprints overlap and the array fills with ones. That overlap is where the false positives come from.
Query “bird”: positions 4, 14, and 22. Position 14 is set. Position 4 is zero.
Stop there. Inserting “bird” would have forced position 4 to 1. It is still 0, so “bird” was never inserted. A single zero among the checked positions is proof of absence, and the database skips the disk read on the strength of it.
Query “cat”: positions 5, 11, and 26, all set. The filter answers probably yes.
Why probably? “cat” is in the set, so this answer happens to be right. But the filter cannot distinguish bits set by “cat” from bits set by anything else — it sees only ones. To see why that matters, query something that was never inserted.
Query “cow”, which was never inserted. Its hashes are 3, 8, and 20.
Position 3 was set by “dog”. Position 8 by “fish”. Position 20 by “dog” again. All three checked positions are 1, and none of them was set by “cow”. The filter reports probably yes, and it is wrong.
This is a false positive. The database performs one unnecessary disk read and finds nothing. It is the cost agreed to in 1970.
The contract, from which everything else follows: no means no; yes means maybe.
A Bloom filter never returns a false negative. Bits are only ever set, never cleared, so an inserted item keeps all its bits and cannot be missed. The only error it can make is the false positive.
Two further consequences follow from bits only being set. The filter cannot enumerate its members — three set bits do not spell “cat”. And it cannot delete: clearing cat’s bit at position 11 would silently break “dog”, which still depends on it.
The error rate is not left to chance. Three parameters fix it before the first insert.
m is the number of bits in the array. n is the number of items to be inserted. k is the number of hash functions applied to each item. Choose those three and the false-positive rate is determined and calculable.
Why more than one hash function? A single hash gives each item one fingerprint bit, and single bits collide constantly. More hashes make each signature more specific: a false positive now requires k bits to coincide rather than one. Too many, and so much of the array is set that everything matches everything. The optimum is exactly k = (m/n) · ln 2.
The numbers worth memorising: ten bits per item, seven hash functions, about one percent false positives. A hundred million URLs fit in roughly 120 MB at that rate. The URLs themselves would run to gigabytes.
The most awkward limitation is the missing delete. The counting Bloom filter replaces each bit with a small counter: insert increments, delete decrements, and zero means genuinely clear.
Removal is now safe — “dog” leaving no longer breaks “cat”. The cost is roughly four times the memory, since a counter needs several bits where a flag needed one.
The next variant is about hardware rather than correctness. In a plain filter an item’s k bits land anywhere across millions of positions, so one lookup can trigger k separate trips to main memory, each a potential cache miss.
The blocked Bloom filter confines an item’s bits to a single 64-byte block, the size of a cache line. A query becomes one memory fetch instead of seven. It is slightly less accurate at the same size and substantially faster, which is why RocksDB ships it.
A classic filter needs n in advance. Scalable Bloom filters drop that requirement by stacking layers: fill one filter to capacity, freeze it, start a new one on top, each tuned tighter than the last so the total error stays bounded. A query walks the layers newest first.
The shape should look familiar. It is the same stack of frozen sorted runs an LSM tree keeps, queried the same way — which is no coincidence, since the two often live in the same codebase.
The cuckoo filter takes a different route: rather than setting bits, it stores a short fingerprint of each item inside a cuckoo hash table.
That buys two things a Bloom filter lacks — real deletes, and better space efficiency below roughly a three percent error rate. The cost is a more involved insert that may have to relocate existing entries to make room. Bloom remains the sensible default; cuckoo wins in specific weight classes.
The filter’s home is the storage engine: RocksDB, LevelDB, Cassandra, HBase.
These databases keep their data in many immutable files. A lookup for one key might otherwise probe file after file. Instead every file carries a Bloom filter of the keys it contains, and the engine consults the filter before touching the file. A “definitely not” skips it entirely, disk untouched. This is the largest single read optimisation in the LSM tree family, and the reason those databases stay fast as files accumulate.
Chrome once kept a Bloom filter of known-malicious URLs, checking every site you visited against it locally and doing the slow full lookup only when the filter said maybe. Most clicks resolved to an offline “definitely not”.
Content networks use it differently. Akamai measured that about three quarters of requested objects are requested exactly once. Their caches store an object only on its second request, so the endless parade of one-hit wonders passes through without evicting anything popular.
A Bloom filter stores none of its inputs, cannot list its contents, cannot delete, and is sometimes wrong. In exchange it answers membership in about one byte per item, and it is never wrong in the direction that would make a database miss data it actually holds.
That asymmetry is the design, not a side effect. The error was placed where it costs one wasted disk read — and nowhere else.