Bloom Filter

A Bloom filter is a fixed-size bit array of m bits combined with k independent hash functions. To insert an element, you hash it k times and set the corresponding bits to 1. To query membership, you hash the element the same way and check if all k bits are set: if any bit is 0, the element is definitely not in the set; if all bits are 1, the element is probably in the set. There is no deletion mechanism in a standard Bloom filter because clearing a bit can silently invalidate other elements sharing that bit position — this is why variants like Counting Bloom Filters (using small counters instead of single bits) exist for mutable sets.

In distributed storage engines, Bloom filters are the primary defense against read amplification. An LSM Tree-based store (Cassandra, RocksDB, HBase) may have dozens of immutable SSTables on disk for a single key range. Without a filter, a point read would require probing every SSTable file, incurring a disk seek or page-cache miss per file. Each SSTable instead ships with a per-file Bloom filter loaded into memory; a query first checks the filter and only performs the actual disk read if the filter returns a positive. This converts an O(n) disk-bound lookup into an O(1) memory-bound check for the common case of a miss.

The critical engineering tradeoff is the false-positive rate p, which is a function of m/n (bits per element) and k. The optimal k = (m/n) * ln(2), and doubling bits-per-element roughly halves the false-positive rate. Under-provisioning m under high cardinality growth (e.g., a compaction job merging many SSTables) causes filter saturation — false-positive rates climb non-linearly, silently degrading read latency because every query now falls through to disk. This is a classic gray failure vector: the system stays technically correct but throughput erodes without any hard error being thrown.

• Scalable Bloom Filters add filter layers as the dataset grows, avoiding a single monolithic re-sizing.
• Cuckoo Filters are a common alternative offering deletion support and better space efficiency at low false-positive rates.
• Bloom filters are also used at the network layer — e.g., in gossip-based anti-entropy to avoid re-transmitting already-seen data, and in CDN edge caches to filter cache-miss requests before hitting origin.

Operationally, Bloom filter sizing must be re-evaluated whenever key cardinality assumptions change; a filter tuned for 10M keys at 1% false-positive rate silently becomes a 50%+ false-positive filter at 500M keys, and most storage engines do not alert on this degradation — it only surfaces as unexplained p99 read latency regressions.