Databases and CDNs handle billions of lookups a day where the honest answer is almost always “no” — this key isn’t cached, this partition doesn’t hold that row, this URL isn’t on a blocklist. Hitting disk, making a network call, or scanning a table just to confirm an absence is expensive at that scale. The Bloom filter is the classic fix: a compact, probabilistic structure that can say “definitely not in the set” instantly, and “probably in the set” the rest of the time — never the reverse. Invented by Burton H. Bloom in 1970 to cut down expensive dictionary lookups, it now sits quietly inside Apache Cassandra, a PostgreSQL index type, Akamai’s CDN caching logic, and (historically) Chrome’s malicious-URL checks. Here’s exactly how it works, the math behind tuning it, and where it’s verifiably used today.
At a Glance
| What it is | A fixed-size bit array plus k independent hash functions, used to test set membership |
| Guarantees | Zero false negatives — a “not in the set” answer is certain. False positives are possible, and their rate is tunable. |
| Typical use cases | Skipping unnecessary disk reads, network round-trips, or cache lookups for keys that almost certainly don’t exist |
| Space cost | About 9.6 bits per item for a 1% false-positive rate — independent of how large the items themselves are |
| Trade-offs | Can’t enumerate members, standard version can’t delete items, and accuracy degrades once more items are inserted than it was sized for |
| Origin | Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM (1970) |
How a Bloom Filter Works
A Bloom filter is just an array of m bits, all starting at 0, plus k independent hash functions that each map any item to one position in that array.
- Insert: run the item through all k hash functions and set each resulting bit position to 1.
- Query: run the candidate item through the same k hash functions. If any of those bit positions is 0, the item was definitely never inserted. If all of them are 1, the item is probably in the set.
The “definitely not” answer is airtight: a bit can only be set by an insertion, so a 0 means no insertion ever touched it. The “probably yes” answer is where the trade-off lives. Because many items share the same small bit array, two or more different items can collectively set all k bits that a third, never-inserted item would also hash to. That coincidence is a false positive — the filter claims membership for something that was never added. This is also why standard Bloom filters can’t support deletion: clearing a bit to remove one item might silently remove another item that happens to share that bit.
The Math: Choosing Size and Hash Count for a Target False-Positive Rate
Three numbers determine everything: m (bits in the array), n (items you plan to insert), and k (hash functions). For a filter with m bits holding n items and using k hash functions, the probability of a false positive is approximately:
p ≈ (1 − e−kn/m)k
For a fixed ratio of bits to items (m/n), there’s a value of k that minimizes this probability:
koptimal = (m/n) × ln 2
And working backward from a target false-positive rate p, the array size needed for n items is:
m = −(n × ln p) / (ln 2)2
Plugging in a 1% target (p = 0.01) gives m/n ≈ 9.6 bits per item and k ≈ 7 hash functions — and dropping the target rate by another order of magnitude costs only about 4.8 more bits per item, not ten times more space. This is a textbook result, and it checks out against a real deployed system: early Chrome Safe Browsing shipped a client-side Bloom filter sized at roughly 10 bits per URL hash with 7 hash functions, landing almost exactly on the formula’s 1%-false-positive point for a filter of that size — for a list of around 100 million malicious URLs, that compressed an ~8 GB blocklist into roughly 125 MB on-device.
Real-World Uses (Verified)
The mechanics above are standard computer science, but it’s worth separating the textbook idea from where it’s actually proven to run in production. Here are four uses confirmed against primary sources:
| System | How it uses a Bloom filter |
|---|---|
| Apache Cassandra | Every SSTable on disk carries a Bloom filter so a read can skip SSTables that provably don’t contain the requested partition, avoiding needless disk I/O. The target false-positive rate is a per-table setting (bloom_filter_fp_chance), defaulting to 0.01–0.1 depending on compaction strategy, per Cassandra’s own operations documentation. |
| PostgreSQL (bloom module) | The official bloom contrib extension is an index access method that stores a lossy multi-column signature per row so queries can quickly exclude non-matching rows before rechecking the actual heap row — useful for equality filters across many columns where building one B-tree per column would be wasteful. |
| Google Chrome (historical) | Early versions of Chrome’s Safe Browsing feature stored a Bloom filter of malicious-URL hashes on the device itself, so most page loads were cleared instantly with no network call; only a filter “hit” triggered a narrow server lookup. Chrome has since moved to a different hash-prefix design, but the original implementation is preserved in Chromium’s source history. |
| Akamai CDN | In the peer-reviewed “Algorithmic Nuggets in Content Delivery” paper, Akamai researchers Bruce Maggs and Ramesh Sitaraman describe using a Bloom filter to detect “one-hit wonders” — objects requested only once — and apply a cache-on-second-hit rule so first-time requests aren’t written to disk. Their traffic logs found over three-quarters of objects were one-hit wonders, and the filtering raised byte hit rate from about 74% to 83% while cutting disk writes by 44%. |
Cassandra’s SSTable Bloom filters work alongside two other structural decisions covered in more depth elsewhere on this site: the choice between B-tree and LSM-tree storage engines (Cassandra is LSM-based, which is exactly why unnecessary SSTable reads are worth avoiding), and consistent hashing, which decides which node a key lives on before a Bloom filter ever gets asked whether that node’s local data might contain it.
Variants: Counting Bloom Filters and Cuckoo Filters
Two well-known extensions address the standard filter’s biggest limitation — no deletions:
- Counting Bloom filters replace each single bit with a small counter, typically 3–4 bits. Inserting increments the relevant counters; deleting decrements them. A position only reads as “empty” once its counter hits zero, so one item’s removal doesn’t erase another’s. The cost is 3–4× the memory of a plain bit array.
- Cuckoo filters take a different approach: they store short item fingerprints in a cuckoo hash table instead of setting bits. They support deletion natively, often use less space than a Bloom filter at the same false-positive rate, and have better memory locality since a lookup touches only one or two table buckets instead of k scattered bit positions.
A Minimal Implementation
The core logic fits in about twenty lines. This version uses only the Python standard library, deriving k independent hash positions from SHA-256 with a different integer salt per round:
import hashlib
import math
class BloomFilter:
def __init__(self, n_items, false_positive_rate):
self.size = self._optimal_size(n_items, false_positive_rate)
self.hash_count = self._optimal_hash_count(self.size, n_items)
self.bits = bytearray(self.size)
@staticmethod
def _optimal_size(n, p):
m = -(n * math.log(p)) / (math.log(2) ** 2)
return max(1, int(math.ceil(m)))
@staticmethod
def _optimal_hash_count(m, n):
k = (m / n) * math.log(2)
return max(1, int(round(k)))
def _indexes(self, item):
data = item.encode("utf-8")
for i in range(self.hash_count):
digest = hashlib.sha256(data + i.to_bytes(4, "big")).digest()
yield int.from_bytes(digest[:8], "big") % self.size
def add(self, item):
for idx in self._indexes(item):
self.bits[idx] = 1
def might_contain(self, item):
return all(self.bits[idx] for idx in self._indexes(item))
bf = BloomFilter(n_items=1000, false_positive_rate=0.01)
bf.add("user:4821")
print(bf.might_contain("user:4821")) # True: definitely inserted
print(bf.might_contain("user:9999")) # False, almost always — never a false negativeThis stores one byte per bit for clarity; a production implementation would pack eight slots per byte to hit the real 9.6-bits-per-item target. Swapping SHA-256 for a faster non-cryptographic hash (MurmurHash3 is the common production choice) is the usual next optimization once correctness is confirmed.
Trade-offs
- No enumeration: you can ask “is X in here?” but never get the list of what was actually inserted.
- No deletion (standard version): requires switching to a counting or cuckoo variant if removal is needed.
- Sizing matters: a filter sized for n items degrades past that false-positive rate once significantly more items are inserted — it doesn’t fail outright, but accuracy quietly worsens.
- Hash quality matters: the independence assumption behind the math above breaks down with poorly distributed hash functions, inflating the real false-positive rate above the computed one.
Bottom Line
A Bloom filter isn’t a general-purpose set — it’s a narrow, specific tool for one job: cheaply ruling out “definitely not here” so an expensive lookup only runs when there’s actually a chance of a hit. That narrowness is the whole point. Cassandra uses it to skip SSTables, Postgres uses it to skip heap-row rechecks, Akamai used it to skip caching objects nobody will request again, and Chrome used it to skip network calls for safe URLs. If you’re weighing whether to add one to your own system, the real design question isn’t “should I use a Bloom filter,” it’s what false-positive rate you can tolerate and whether you’ll ever need to delete an entry — the first sets your memory budget via the formulas above, and the second decides whether you need the plain version or a counting/cuckoo variant.
FAQ
Can a Bloom filter ever produce a false negative?
No. If an item was inserted, every bit it set is still set, so a query for it will always find all relevant bits at 1. “Not in the set” is a guaranteed-correct answer.
Can I delete an item from a standard Bloom filter?
Not safely. Clearing a bit could un-set membership for a different item that happens to hash to the same position. Use a counting Bloom filter or a cuckoo filter if deletion is a requirement.
How is this different from just using a hash set?
A hash set stores the actual items (or their full hashes) and is always exact. A Bloom filter stores neither — only a shared bit array — which is why it can be an order of magnitude smaller, at the cost of occasional false positives.
What false-positive rate should I actually pick?
It depends on what a false positive costs downstream. Cassandra’s own defaults — 0.01 for most compaction strategies, 0.1 for leveled compaction — are a reasonable starting range: lower if a false positive means an expensive fallback check, higher if memory is tighter and an occasional unnecessary lookup is cheap.
Sources
- Apache Cassandra Documentation — Bloom Filters
- PostgreSQL Documentation — F.6, bloom module
- Maggs & Sitaraman, “Algorithmic Nuggets in Content Delivery” (ACM SIGCOMM CCR, 2015) — Section 4.2 on Bloom-filter cache admission at Akamai
- Stanford CS145, “How does Google Chrome protect users using Bloom Filters?” (with links to the historical Chromium Safe Browsing source)
- Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors” (Communications of the ACM, 1970)
- Wikipedia — Bloom filter (math derivations, counting and cuckoo filter variants)
Discover more from Software Online Review
Subscribe to get the latest posts sent to your email.
