Bloom Filter Simulator: a set in a thousandth of the space.

A Bloom filter is a space-efficient probabilistic data structure that answers "is this element in the set?" with either definitely not or probably yes. Burton Howard Bloom introduced it in a 1970 CACM paper. It uses a fixed-size bit array and several hash functions; insertions set bits and lookups check them, which means false positives are possible but false negatives are not. Bloom filters power LevelDB and RocksDB SSTable lookups, Cassandra's read path, Bitcoin's SPV mode, and Chromium's malicious-URL check.

Imagine you operate a database with a hundred million users. Most lookups against this database are wasted effort. A web crawler asks "have we seen example.com/page42?" — and 95% of the time the answer is no, but the database has to do a full disk read to confirm that. Each wasted read costs a few milliseconds; multiplied across millions of queries per day, you are paying for a lot of disk activity to learn things are not there.

The natural reflex is to keep an in-memory index of every URL you have seen. Now lookups are fast — a hash table answers "yes/no" in nanoseconds. The problem is memory. A hundred million URLs at fifty bytes each is five gigabytes of RAM just for the index, and that index has to live in every server that wants to do the check. At a billion URLs (Akamai, Cloudflare, Google's safe-browsing list) the bill becomes prohibitive.

The trick is to relax the problem. You do not actually need an exact answer; you need an answer that is almost always right in one direction. Specifically: if the URL has never been seen, you want a quick, certain "no" — that lets you skip the disk read with no risk. If the URL might have been seen, you can afford to fall back to the slow path and check authoritative storage; you have not lost anything by doing the work that you would have done anyway. What you cannot afford is a "no" answer when the URL is in the set, because that would silently drop data.

This asymmetry — never wrong about absence, occasionally wrong about presence — is exactly what the Bloom filter provides. It uses a bit array of fixed size and a handful of hash functions. To insert a key, hash it through each function and set those bits to 1. To check a key, hash it the same way and read those bits; if any is 0, the key was definitely never inserted. If all are 1, the key was probably inserted — but it might just be that other keys happened to set those same bits. The chance of that confusion is the false-positive rate, and you can tune it by spending more bits per item.

The numbers are striking. For a hundred million keys at a 1% false-positive rate, a Bloom filter takes about 120 MB — roughly 10 bits per item, or one fortieth the size of an exact hash set. At that price, 99 of every 100 negative lookups skip the disk read. The other 1 falls through to authoritative storage and pays the full cost. Over a million queries, that is 990,000 disk reads avoided in exchange for ten thousand wasted reads — a 99x reduction in I/O for almost no memory.

The simulator above lets you set bits, query keys, and watch the false-positive rate climb as the array fills up. Start small, watch the math come out exactly as the formula predicts, then scale to production sizes in the next sections.

Burton Howard Bloom published Space/Time Trade-offs in Hash Coding with Allowable Errors in Communications of the ACM in July 1970. The paper is four pages long, has no benchmarks, and barely uses the word “filter.” Bloom was working at Computer Usage Company on a hyphenation-dictionary problem for the AED-1 typesetting compiler: how to decide cheaply whether a given word might need lookup in a 200,000-entry dictionary that lived on tape. A full hash table would have cost too much core memory; a linear scan would have been impossibly slow. Bloom proposed a bitfield with multiple hash probes, accepting a small chance of unnecessary tape lookups in exchange for storing the “is it worth checking?” predicate in roughly one byte per word.

The structural commitment that gave the data structure its longevity is the asymmetry of error: a Bloom filter can return a false positive but never a false negative. The hyphenation use case demanded exactly that property — an extra dictionary lookup costs a few milliseconds; a missed hyphen ruins a paragraph. Half a century later, every production use case still leans on the same asymmetry: an SSTable read-skip can wastefully consult an SSTable that does not contain the key, but it must never skip an SSTable that does.

The mathematical core is a clean exercise in independence: each of the k hash functions sets one of m bits, items are independent, so after inserting n items the probability that a given bit is still 0 is approximately (1 − 1/m)^kn ≈ e^−kn/m. The probability that all k bits checked for a non-member happen to have been set is therefore (1 − e^−kn/m)^k. Optimising over k, the minimum lies at k = (m/n) ln 2 ≈ 0.693 (m/n); plugging that back in gives an optimal false-positive rate of (0.6185)^m/n. The practical sizing rule of thumb that fell out: roughly 9.6 bits per element for a 1% false-positive rate, 14.4 bits for 0.1%, 19.2 bits for 0.01%. The bits-per-element cost grows linearly with each additional decimal place of precision.

For a 1-million-entry filter at 1% false-positive rate, that is 1.2 MB and seven hash probes per query — compared with perhaps 30–100 MB for a Java HashSet<String> over the same vocabulary. The space win is the entire reason the data structure exists; the rest of the family tree is engineering around the false-positive asymmetry, the lack of deletion, and the lack of cardinality information.

The paper itself was almost lost to citation rot for a decade. Its first major systems-paper citation came in Andrei Broder and Michael Mitzenmacher's 2003 survey Network Applications of Bloom Filters, which catalogued the data structure's then-recent rediscovery in distributed caches, web crawler URL frontiers, and IP-multicast routing. From that survey onward, the term “Bloom filter” passed into the standard systems vocabulary; today, every storage engine, every CDN, every browser anti-phishing pipeline ships at least one.

The three independent parameters — bit array size m, hash count k, expected insertion count n — jointly determine the false-positive rate. In practice you fix two and solve for the third. The most common shape: pick a target false-positive rate p and an expected n, then derive m from m = −n ln(p) / (ln 2)² and k from k = (m/n) ln 2, rounded to a small integer. The Guava BloomFilter.create(Funnel, expectedInsertions, fpp) API in Java does exactly this; so does Python's pybloom_live, Rust's bloomfilter crate, and the github.com/bits-and-blooms/bloom Go package.

Memorable sizing pairs: 9.6 bits/key gives 1% FP, 14.4 bits gives 0.1%, 19.2 bits gives 0.01%. Doubling the bits per key squares the false-positive rate, which is why you almost never see Bloom filters tuned for parts-per-million precision — the bit budget is better spent on a different data structure (HyperLogLog for cardinality, a hash set for exact membership) than on chasing two more decimal places.

The hash-count k is bounded in practice. Each probe is a memory access; on a modern CPU with 4 ns L2 latency and 80 ns DRAM latency, a Bloom-filter query at k=7 with a hot bit array runs in roughly 30 ns and at k=14 takes twice that. Empirical RocksDB benchmarks show that k=10 hash probes saturate the cache-miss budget; beyond that, falling false-positive rate is paid for in proportional latency. Most production Bloom implementations cap k at 10–15 and accept the small loss of theoretical optimality.

One implementation detail saves enormous CPU: instead of computing k independent hash functions, real systems use double hashing — two 64-bit hashes h1, h2 (typically MurmurHash3 or xxHash64), then derive the ith probe as h1 + i·h2 modulo m. Kirsch and Mitzenmacher proved in their 2006 paper Less Hashing, Same Performance: Building a Better Bloom Filter that the false-positive rate under double hashing is asymptotically identical to k independent hashes. The simulator on this page uses exactly this trick; so does Guava, RocksDB, and Cassandra.

A second implementation detail that matters at scale: the bit array is laid out for cache friendliness. The naive layout sprinkles the k probes uniformly across m bits, which means up to k cache misses per query on a large filter. The blocked layout (described in Part 03) constrains all k probes for any given key to one cache line. The cost is a slightly higher false-positive rate at the same memory budget — roughly 1.4× for a 1% target — and the win is that lookup latency drops from a smear of 50–300 ns to a tight 30–60 ns. RocksDB, ScyllaDB and Apache Parquet all default to a blocked layout because the throughput uplift on hot lookups dominates the small accuracy loss.

Counting Bloom filters (Fan, Cao, Almeida, Broder, SIGCOMM 2000) replace each bit with a small counter, typically 4 bits, so insertions increment and deletions decrement. The cost is a 4× memory blow-up; the win is that an LRU-evictable cache can actually update its filter rather than rebuilding from scratch. Cisco IOS routers used counting Bloom filters in IP-multicast group filtering throughout the 2000s, and Squid's cache directory used them for inter-cache lookup.

Scalable Bloom filters (Almeida, Baquero, Preguiça, Hutchison, IPL 2007) chain a sequence of filters with geometrically tightening false-positive rates, so the union remains bounded as the insert stream grows without an a-priori cap. Stable Bloom filters (Deng & Rafiei, SIGMOD 2006) cope with infinite streams by randomly decrementing counters on insert — gaining bounded memory at the cost of accepting false negatives, useful in stream-deduplication where occasional duplicates are tolerable.

Blocked Bloom filters (Putze, Sanders, Singler, JEA 2009) restrict each item's k probes to a single 512-bit cache line, trading a slightly higher theoretical false-positive rate for a single cache miss per query. Modern RocksDB ships them as the default since version 5.6 (2017) under the name full filters; the throughput uplift on hot lookups is roughly 2× over the classic per-bit layout.

Cuckoo filters (Fan, Andersen, Kaminsky, Mitzenmacher, CoNEXT 2014) store fingerprints in a cuckoo hash table; they support deletion, have lower false-positive rates per bit at moderate sizes, and beat Bloom on lookup throughput. The CMU group's reference implementation reports 3–5× faster lookups than a tuned Bloom filter at 1% FP. Xor filters (Graf & Lemire, JEA 2019) use a system of linear equations over a small finite field; they are immutable but pack 1.23× more efficiently than a Bloom filter at the same false-positive rate. Ribbon filters (Dillinger & Walzer, ESA 2021) refine the xor approach with a banded matrix construction; Facebook's RocksDB shipped them as an option in version 6.15 (2020) and they have since become the default for new SSTables on hot block-cache paths.

The dominant production use case is the SSTable read-skip. In an LSM-tree storage engine — Bigtable (Chang et al., OSDI 2006), HBase, Cassandra, LevelDB, RocksDB, ScyllaDB, Pebble — a point lookup must check the in-memory memtable, then potentially every immutable on-disk SSTable from newest to oldest until it finds the key or exhausts the levels. Each SSTable lookup is a disk read; without help the worst case is O(L) reads where L is the number of levels. Each SSTable carries a Bloom filter sized to its key count; consulting the filter costs a few nanoseconds and skips the disk read on a negative answer. Cassandra's default is 1% FP per SSTable; tuning down to 0.1% costs roughly 50% more memory and is standard for read-heavy workloads.

RocksDB, the embedded engine inside MySQL's MyRocks, CockroachDB, TiKV, YugabyteDB, MongoDB Realm, ArangoDB, and Kafka Streams' RocksDB-backed state store, exposes the Bloom-filter knob as bloom_filter_bits_per_key — default 10. The block-based and full-filter formats coexist; the full filter (one filter per SSTable file rather than per data block) saves an order of magnitude on memory at the cost of slightly more bits-per-key. Facebook's 2020 paper Optimizing Space Amplification in RocksDB reports that ribbon filters at the same accuracy save roughly 30% memory over full Bloom on Facebook's UDB workload.

PostgreSQL ships a bloom contrib extension since version 9.6 (September 2016) that creates Bloom-filter indexes for the “column equality on many columns” access pattern that a B-tree handles poorly. The extension lets you tune length and column counts per index; in practice it is a niche tool for wide composite-equality predicates that nothing else fits.

The non-database production catalogue is also extensive. Akamai uses Bloom filters in its CDN's deduplication of inter-cache requests (a 2009 Akamai engineering blog mentions a 1.5 MB filter per edge node). Google Chrome and Firefox historically shipped a roughly 2 MB compressed Bloom filter of malicious URLs from the Safe Browsing list, consulted before every navigation; Chrome moved to a hash-prefix scheme in 2016 but the filter itself is still part of the lineage. Bitcoin SPV clients (BIP-0037, 2012) negotiate a Bloom filter of addresses with a full node; Cloudflare's edge uses Bloom filters in its DNS resolver for negative-cache lookups. Squid, Varnish, Nginx's ngx_http_realip_module, Mailgun's spam pipeline, and Medium's recommendation feed have all been documented using Bloom filters at various points.

The first failure mode is oversaturation. The false-positive curve is roughly flat until the filter passes its design n; once you exceed the budget, the rate climbs steeply. A Bloom filter sized for 1 million entries at 1% FP reaches 50% FP after roughly 7 million inserts and approaches 100% asymptotically. Production systems guard this either with a hard cap (refusing to insert past n), a scalable Bloom filter chain, or a periodic rebuild from a fresh empty filter. Cassandra rebuilds Bloom filters during compaction precisely to avoid drift on large SSTables.

The second is deletion impossibility. A standard Bloom filter cannot un-set bits, because clearing a bit you set for item A might also clear bits set by items B and C, introducing the one error the data structure forbids: a false negative. The standard fix is a counting Bloom filter at 4× memory cost; the modern fix is a cuckoo or ribbon filter. The naive workaround — rebuild the filter from scratch — is fine for small filters and excruciating at scale.

The third is hash collusion under adversarial input. A Bloom filter built with non-cryptographic hashes (MurmurHash, FNV, xxHash) is vulnerable to attackers who choose inputs to collide on the same bit pattern. The 2003 USENIX Security paper Denial of Service via Algorithmic Complexity Attacks by Crosby and Wallach is the cautionary classic. For internet-facing filters — spam blocklists, abuse signals — either keyed hashes (SipHash with a per-deployment secret, default since Python 3.4 and Rust's HashMap) or full cryptographic hashes (BLAKE3, truncated SHA-256) are required.

The fourth is stale filter on a hot path. A Bloom filter must be re-published whenever the underlying set changes, or readers will return false negatives on newly inserted items. The 2018 Cloudflare blog post on their R2 cache layer documents an incident where a stale Bloom filter on an edge node caused new uploads to appear “missing” for several minutes after each cache flush. The fix in their case was to make the filter eventually-consistent with a known staleness bound and to fall back to authoritative storage on filter-miss. Every production Bloom filter ships with this fallback path; the Bloom filter is a hint, not the source of truth.

The fifth, often missed, is the composition of false-positive rates. A request that touches three independent Bloom filters in series — say, one per LSM level — multiplies its false-positive probability per filter. Three filters at 1% give a roughly 3% chance that any random non-member triggers a wasted disk read; on a million-QPS service, that is 30,000 wasted I/Os per second. The fix is to budget the per-filter rate against the cumulative target, not to trust the per-filter number in isolation. RocksDB documents this trade-off in its tuning guide as the “effective false-positive rate”.

Concrete numbers anchor the choice. For one billion 32-byte keys at 1% false-positive rate: roughly 1.2 GB of bits, seven hash probes per query, query latency 30–120 ns depending on whether the bit array is in L3 cache or DRAM, build throughput around 5–10 million inserts per second on a single core. The same set in a Java HashSet<String> would consume well over 80 GB of heap. Daniel Lemire's 2019 benchmarks on the FastFilter project clock xor filters at roughly 250 cycles per query and Bloom filters at 200 cycles per query for the same false-positive rate, with cuckoo filters around 220 cycles — differences that matter only if the filter is on a per-packet hot path.

RocksDB benchmarks from the Facebook Database Engineering team report that adding Bloom filters cuts read amplification on the Cassandra-style YCSB “workload C” (read-only, Zipfian) by 3–5× on workloads where the working set exceeds the block cache. The cost is roughly 10 bits/key in memory, which on a 100-million-key SSTable is 125 MB — a fraction of the disk footprint and well within typical cache budgets.

Cassandra's own documentation reports that increasing Bloom-filter precision from 1% to 0.1% (roughly 14.4 bits/key) typically halves cassandra-stress read latency p99 on disk-bound workloads — precisely the case where the saved disk seek dominates. Going to 0.01% rarely pays off in their internal numbers; the marginal disk seek saved is overshadowed by the larger filter blowing past the page cache.

For network-touching filters, the numbers shift: a Cloudflare engineering post on Workers KV reports per-request Bloom-filter check latency under 100 µs including a network round trip to the colo's filter cache, with hit rates of 92% on negative lookups (i.e., roughly 92% of “does this key exist” questions are answered without a primary-storage round trip). On the storage side, Apache Parquet writers ship Bloom filters per column chunk since version 1.12 (2020); empirical TPCH queries on selective predicates show 2–10× scan reductions when the predicate hits the filter.

Reach for a Bloom filter when the question is set membership and you can tolerate a controlled false-positive rate. Reach for something else when any of those conditions slips.

If the question is cardinality — “how many distinct values?” rather than “is X a member?” — use HyperLogLog (Flajolet, Fusy, Gandouet, Meunier, AofA 2007). HLL estimates distinct counts of arbitrarily large sets in roughly 1.5 KB of memory with about 2% standard error. Redis's PFADD/PFCOUNT ships a 12 KB HLL per key; BigQuery, Snowflake, and Druid all use HLL or HLL+ for approximate COUNT(DISTINCT) at scale.

If the question is top-K or frequency estimation, use a Count-Min sketch (Cormode & Muthukrishnan, J. Algorithms 2005). Bloom answers binary membership; CMS answers approximate counts. Apache Spark's DataFrame.stat.countMinSketch, Apache Flink, and Cassandra's read-repair statistics all use CMS variants.

If the question is exact membership on a small set, a perfect hash function (Belazzougui, Botelho, Dietzfelbinger, ESA 2009) gives lossless lookup at roughly 2–3 bits per key with no false positives. The CMPH C library and Daniel Lemire's BBHash implementation are the standard tools; the trade-off is that the structure is immutable — you build it once on a known set and re-build it when the set changes.

If the question is set membership with deletion, a counting Bloom or cuckoo filter solves the surface problem; for very high write rates, a small in-memory hash set in front of a slow authoritative store usually beats both. The Bloom filter is the right tool when memory budgets are tight, the working set is large, and the workload tolerates false-positive misroutes. It is the wrong tool when you need to enumerate the set, count occurrences, or guarantee that “not present” means “definitely not present” under all configurations of an evolving system.

A final adjacent primitive worth naming: the quotient filter (Bender et al., FAST 2012), an alternative to Bloom that stores a tagged remainder per bucket and supports merge, resize, and deletion. Quotient filters power some range-query accelerators in PMEM-tuned databases and beat Bloom on cache-friendliness for skewed data. Together with cuckoo, xor, and ribbon filters, modern approximate-membership data structures are far richer than Bloom alone — but Bloom remains the default for the same reason ASCII remains the default character set: it is good enough, it is everywhere, and the alternatives have to earn the migration.