Bloom filters
A bit array plus hash functions that answer "is this in the set?" with a definite no or a probable yes, in a fraction of the memory an exact set needs. A strong answer names what the "maybe" costs.
What it is
A Bloom filter is a probabilistic set: it tells you whether an item might be in a set, using far less memory than storing the items would take. It was proposed by Burton Bloom in 1970 for the case where an exact hash table of the data would not fit in memory. The structure is a bit array of m bits, all 0 at the start, and k different hash functions that each map an item to one position in the array. To add an item, run it through the k hash functions and set the k bits they point at to 1. To check an item, run the same k hash functions and look at the k bits: if any of them is 0, the item was not added, because adding it would have set that bit; if all are 1, either the item was added or other items happened to set those same bits. That second case is a false positive, and the plain filter has no way to tell it apart from a true hit.
Two consequences follow from the mechanism. First, the filter does not fill up the way a hash table does: an insert does not fail, but as items are added more of the bits end up set to 1, so the false positive rate climbs, until in the extreme all bits are 1 and each lookup says "maybe". Second, the array length m you need grows in proportion to the number of items n you plan to insert, while the number of hash functions k depends on the false positive rate you want and not on n. So you size a filter by estimating n and picking a rate.
| Target false positive rate | Bits per item (RocksDB's implementation) | Share of the benefit of 100 bits per item |
|---|---|---|
50% | 1.5 | 50% |
25% | 2.9 | 75% |
10% | 4.9 | 90% |
1% | 9.9 | 99% |
0.1% | 15.5 | 99.9% |
The table shows diminishing returns: the theory gives about 9.6 bits per item for a 1% rate with the best choice of k, and each further 4.8 bits per item divides the rate by ten. The cost does not depend on how large the items are, because the filter stores hashed positions, not the items. The RocksDB wiki notes a small, roughly constant CPU cost for hashing on each lookup, and recommends comparing a 3-bit filter against no filter at all when memory is tight, rather than assuming the 10-bit default is worth it.
Removal is not part of the plain filter. Clearing one of an item's k bits would also clear a bit that other items share, and the structure keeps no record of who set which bit, so a delete would introduce false negatives. Two variants restore deletes. A counting Bloom filter replaces each bit with a small counter: insert increments, lookup checks that all k counters are non-zero, delete decrements, at the price of several bits per position and a risk of counter overflow. A cuckoo filter keeps short fingerprints of items in a hash table of buckets, supports deletes and has better memory locality; one documented use is coupon validation, where a redeemed code is removed from the filter. Its false positive rate is set by the fingerprint size.
How products expose it. In Apache Cassandra 5.0, each SSTable file on disk carries its own filter so a read can skip files that definitely lack the partition; the per-table setting bloom_filter_fp_chance defaults to 0.01, or 0.1 for tables on leveled compaction, and the 0.01 filter takes about three times the memory of the 0.1 one. The filter lives off-heap, is built when the file is written, and a changed setting applies to new files, so existing files keep their old filter until they are rewritten. In Redis Open Source, BF.RESERVE (module version 1.0.0 and later) creates a filter from two numbers, the desired error rate and the expected capacity, with an optional expansion factor for automatic growth and a flag to forbid growth; BF.ADD returns 1 when the item was newly added and 0 when it may have existed already.
When to use it
The shape to look for has three parts: most lookups would find nothing, the real check is expensive (a disk seek, a database query, a network call), and a wrong "maybe" costs no more than doing that check for nothing. Storage engines fit it well: Bigtable, HBase, Cassandra, ScyllaDB and PostgreSQL use filters to avoid reading from disk for rows that do not exist. Akamai uses filters to keep "one-hit wonders", objects requested once, out of its disk caches, after finding that close to three quarters of the URLs its caches were asked for were requested a single time. Google Chrome once checked URLs against a local filter and did the full malicious-URL check on a hit; Medium uses filters to avoid recommending articles a reader has already seen.
Uniqueness checks are another fit. Redis describes the pattern for "is this username, slug or domain already taken?": a filter holds each name registered so far; a "no" lets you create the account and add the name, and on a "yes" the application either checks the main database or rejects the name outright. Lookup time stays flat as the set grows. The same shape serves a short-link service that must not hand out a code twice: the filter answers for the common case (a fresh code) without touching the codes table, and a "maybe" sends you to the table or, since codes are cheap, to the next candidate. Our advice: keep the unique index on the table as the real guard, because two writers can both get a "no" for the same code before either has added it; the filter saves lookups, the index decides. See Unique ID generation for how codes are made.
When not to
The set is small, or you need the members back. If the set fits comfortably in memory as a hash set, an exact structure gives exact answers and supports removal, listing and an exact count, none of which a plain filter does: it holds hashed positions, not keys or values, so it can at best estimate how many items it holds. When the universe of possible values is small and many of them are present, a plain bit array indexed by value beats a filter outright. Reach for a filter when the set is too big to hold cheaply, not as a default.
Items leave the set. Unsubscribes, redeemed coupons, deleted links: each needs a delete, and the plain filter has no way to give one without rebuilding from the source. Pick a cuckoo filter or a counting filter instead, or rebuild the filter on a schedule and accept that a deleted item reads as present until the rebuild. Also watch for a set that grows without a known bound: a filter built for n items drifts past its target rate as the count passes n, and growth schemes such as the optional expansion factor in Redis handle that by adding sub-filters. Our advice: estimate the capacity at creation and treat automatic growth as a safety net.
A false positive hurts a person, or correctness is the point. Rejecting a free username, denying a valid coupon or dropping a legitimate message on a "maybe" turns the filter's error rate into a user-facing error rate. Either verify each "maybe" against the real store, or do not use a filter there. And when a decision must be exact and safe under concurrent writers, a database unique index or a transaction is the tool; the filter is an accelerator in front of it. Finally, where almost all lookups hit (a workload that reads what it knows exists, or scans the whole data set), the filter adds hashing work and memory for little saving; Cassandra's documentation says such workloads can run with a much higher false positive chance.
Compared
| Option | What a lookup gives you | Removes items? | Memory | Pick it when |
|---|---|---|---|---|
Bloom filter | Definite no, or probable yes | No; rebuild from the source | About 10 bits per item at 1%, whatever the item size | Most lookups miss, the real check is expensive, and a wrong "maybe" costs one wasted check |
Counting Bloom filter | Same as a Bloom filter | Yes, by decrementing counters | Several bits per position instead of one; counters can overflow | Items leave the set and you can afford a few times the memory |
Cuckoo filter | Same, from stored fingerprints | Yes | Fingerprint size sets the error rate | You need deletes, as with coupons marked used, or better memory locality |
Exact hash set | Exact yes or no | Yes | Holds each key in full | The set is small enough to keep, or you must list, count or iterate the members |
Database unique index | Exact, and rejects a duplicate write | Yes | Stores the keys themselves, in the database | The answer must be correct and two concurrent writers must not both succeed |