Skip to content

16 · Bloom Filters — Probabilistic Check for Key Existence

Storage Internals · Topic 16 of 16


What is a Bloom Filter?

A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is in a set.

  • Returns "definitely not in set" or "possibly in set" (never a false negative)
  • False positives are possible — but tunable
  • Uses a fraction of the memory of a hash set

How It Works

A Bloom filter is a bit array of m bits plus k hash functions.

Adding an element: hash it with all k functions → set those k bits to 1

Querying: hash with all k functions → if ALL k bits are 1, element "possibly present". If ANY bit is 0, "definitely absent".

graph LR
    Key["Key: 'user:42'"] --> H1["Hash fn 1 → bit 3"]
    Key --> H2["Hash fn 2 → bit 7"]
    Key --> H3["Hash fn 3 → bit 12"]
    H1 --> BA["Bit Array\n[0,0,0,1,0,0,0,1,0,0,0,0,1,...]"]

False Positive Rate

p ≈ (1 − exp(−k × n / m))^k

Where:

  • n = number of inserted elements
  • m = number of bits
  • k = number of hash functions

At the optimal k ≈ (m/n) ln(2), a 1% false-positive rate needs about 9.6 bits per key, not bytes. For one million elements this is approximately 1.2 MB (decimal), with about 7 hash probes.


Why Databases Use Bloom Filters

In LSM-Tree storage engines (Cassandra, RocksDB, LevelDB):

  • SSTables may span many files
  • A read must check all SSTables for the key
  • Bloom filter per SSTable lets the engine skip files that definitely don't contain the key
graph TD
    Read["Read key K"] --> BF1["Bloom Filter SSTable 1\n→ Definitely absent, skip"]
    Read --> BF2["Bloom Filter SSTable 2\n→ Possibly present, read"]
    BF2 --> Data["Find or not find K in SSTable 2"]

Cloud Implementations

  • Each SSTable has a Bloom filter stored alongside it
  • bloom_filter_fp_chance per table (default: 0.01 = 1% FP rate)
  • Lower FP = larger filter = more memory
    CREATE TABLE events (id UUID PRIMARY KEY, ...)
    WITH bloom_filter_fp_chance = 0.001;
    
  • No user-configurable Bloom-filter interface is exposed
  • Do not assume an undocumented internal implementation when planning performance
  • Bloom filters are configured through table/filter policies; integrations and defaults vary
  • NewBloomFilterPolicy(bits_per_key) configures false positive rate
  • Uses semi-join reduction and runtime filters (similar concept) for join optimization
  • Not a user-configurable Bloom filter
  • No built-in Bloom filter index by default
  • bloom extension available: CREATE INDEX ON table USING bloom(col1, col2)
  • Useful for multi-column equality searches with high cardinality

Summary

Property Bloom Filter
Space complexity O(m) bits
Query time O(k) — constant
False negatives Never
False positives Tunable probability
Can delete elements? No (standard; counting Bloom filters can)

A Negative Result Is Useful Only Within Its Scope

An SSTable Bloom filter answers whether a key could occur in that file, not whether the logical database contains it. A positive still requires an exact lookup and version/tombstone reconciliation. The no-false-negative guarantee assumes correct construction, the same hashing rules, no unsafe bit clearing and inclusion of all relevant keys.

Overfilling the filter raises the false-positive rate. Filters optimize absent point lookups especially well; they are not ordered indexes for arbitrary range scans. Configure filters based on the engine's documented defaults rather than assuming every RocksDB integration enables identical policies.

Check Your Understanding

#

Question 1

Can a Bloom filter be the authority for rejecting duplicate payments?

#

Question 2

Why can't a standard Bloom filter safely delete a key by clearing its bits?