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 elementsm= number of bitsk= 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_chanceper table (default: 0.01 = 1% FP rate)- Lower FP = larger filter = more memory
- 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
bloomextension 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.