It only ever says “definitely not” or “probably yes”
asha and ravi set 3 bits each. meera hits a 0: never added. kiran finds three 1s set by others: a false positive.
Trust its “yes”?
Bad: “Yes” means it’s there
Sometimes you’ll refuse a free username or block a real payment.
Good: Only “no” is certain
Bits never clear, so “no” is never wrong. Every “maybe” asks the store.
9.6
bits per key buys a 1% false-positive rate
With 7 hashes, whether the key is a 4-byte ID or a 2 KB URL. Each extra 4.8 bits cuts false positives about 10×.
A billion usernames in 1.2 GB, not 40
A Redis set stores every 16-byte handle plus overhead. A 1% filter stores no keys, just 9.6 bits each.
In an LSM store, a missing key checked against 8 SSTables costs 8 random disk reads.
The trick
Each SSTable keeps a Bloom filter in memory. At 1%, that miss costs 8 × 0.01 = 0.08 reads.
16%
false positives at twice the design load
Sized for n keys at 1%, it never refuses an add; the error just climbs. Size for growth, watch the bits set, rebuild or rotate.
When it’s the wrong tool
- Mostly hits: almost every check says “maybe”
- Range scans: no single key to test
- Deletes: clearing shared bits makes false negatives
- Counting: count-min sketch or HyperLogLog instead
Remember
Most lookups miss, so put a Bloom filter in front of the store. A zero bit means definitely absent; a “yes” still asks the store. 100 million keys at 1%? 120 MB.