The Bloom Filter

A database may need to locate a key across many files on disk. Checking every file is correct but inefficient because most reads return no result.

A compact in-memory index can eliminate many of these unnecessary disk reads.

Before reading a file, the database checks whether the key may be present.

A negative result proves that the key is absent, so the file can be skipped. A positive result indicates only that the key may be present and requires a normal lookup.

A Bloom filter provides this membership check. It typically uses about one byte per item, independent of the size of each item.

It can return a false positive for an item that was not inserted, but it does not return a false negative for an inserted item. This one-sided error allows the compact representation.

Burton Bloom introduced the structure in the 1970 paper “Space/Time Trade-offs in Hash Coding with Allowable Errors.” The design addressed systems with limited memory.

Allowing a bounded false-positive rate significantly reduces space usage. Bloom filters are now used in storage engines, browsers, and content-delivery systems.

Bloom’s example was automatic hyphenation. About ninety percent of words followed simple rules; only the exceptions needed a dictionary lookup.

The full dictionary would not fit in memory. A compact test could instead ask whether a word might be an exception. An occasional unnecessary lookup was harmless, and the memory savings were enormous.

The filter has two ingredients: an array of bits, initially all zero, and a handful of hash functions.

Each hash maps an item to a position in the array. The same input always lands in the same places. The filter stores nothing else — not the item, not a pointer to it, only the bits those hashes select.

To insert “cat,” apply three hash functions. If they return positions 5, 11, and 26, set those bits to 1.

The filter does not store the string or a pointer to it. It represents the insertion only through the selected bits.

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.

For “bird,” suppose the hashes return positions 4, 14, and 22. Position 14 is set, but position 4 is zero.

Insertion would have set every selected bit. The zero therefore proves that “bird” was not inserted, and the database can skip the disk read.

For “cat,” positions 5, 11, and 26 are all set. The filter therefore reports that “cat” may be present.

The result is not conclusive because the filter cannot identify which item set each bit. Other inserted items may have produced the same combination.

Suppose “cow” was never inserted, but its hashes return positions 3, 8, and 20.

Those positions may already have been set by “dog” and “fish.” Because all three bits are 1, the filter reports that “cow” may be present.

This is a false positive. It causes one unnecessary disk read but does not affect correctness.

A negative result is conclusive, while a positive result is probabilistic. Bits are set but not cleared, so an inserted item retains every bit required by its hashes.

A standard Bloom filter cannot enumerate its members or safely delete individual items. Clearing a shared bit could create a false negative for another item.

Three parameters determine the false-positive rate before insertion begins.

m is the number of bits, n is the expected number of items, and k is the number of hash functions applied to each item.

Using multiple hashes reduces collisions because a false positive must match several bits. However, too many hashes set a large fraction of the array and increase the error rate. The optimal count is k = (m/n) · ln 2.

A common configuration uses about ten bits per item and seven hash functions for a false-positive rate near one percent. One hundred million URLs require roughly 120 MB at that rate.

A counting Bloom filter supports deletion by replacing each bit with a small counter. Insertion increments the relevant counters, deletion decrements them, and zero indicates an unused position.

This variant typically requires about four times as much memory as a standard Bloom filter.

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 standard filter requires an estimate of n. A scalable Bloom filter removes this requirement by adding layers as capacity is reached. Each new layer uses a lower error rate so the combined rate remains bounded.

Queries check the layers from newest to oldest. This organization is similar to the sorted runs in an LSM tree, and the two structures are often used together.

A cuckoo filter stores short item fingerprints in a cuckoo hash table instead of setting bits.

It supports deletion and can use less space when the target error rate is below approximately three percent. Insertion is more complex because it may relocate existing fingerprints.

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 previously used a Bloom filter for known-malicious URLs. It performed a full lookup only when the local filter reported that a URL might be present.

Content-delivery networks use Bloom filters to guide caching. Akamai reported that about three quarters of requested objects were requested only once, so admitting an object after its second request can reduce cache pollution.

A Bloom filter reduces memory use and disk I/O by allowing false positives. A false positive causes an unnecessary lookup, while a negative result reliably rules out the item.

This error model is appropriate when unnecessary lookups are acceptable but missed data is not.