We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningAdvanced · Distributed Systems Core
A space-efficient probabilistic data structure that tells you if an element is 'possibly in the set' or 'definitely not in the set.' Used by databases to avoid expensive lookups.
In short
A Bloom filter is a space-efficient probabilistic data structure that answers one question about set membership: an element is either "definitely not in the set" or "possibly in the set." It can return false positives but never false negatives, which lets systems skip expensive disk reads or network calls for items that are guaranteed to be absent.
In short
A Bloom filter is a space-efficient probabilistic data structure that answers one question about set membership: an element is either "definitely not in the set" or "possibly in the set." It can return false positives but never false negatives, which lets systems skip expensive disk reads or network calls for items that are guaranteed to be absent.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Bloom Filter across a run of lessons, not one page. These 4 alone are about 82 minutes of step-by-step reading, every one with a quiz.
A space-efficient probabilistic data structure that tells you if an element is definitely NOT in a set.
A probabilistic data structure that provides O(log n) search with the simplicity of a linked list.
Let consumers receive only the messages they care about, filter at the broker, not in code.
Caching a result set freezes it, and the deep pagination it is usually bought to fix disappears when you change the question instead.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Bloom Filterspay once,
yours for life
A Bloom filter is a bit array of fixed size paired with a handful of hash functions. Every bit starts at 0. The structure does not store the elements themselves, only a fingerprint of which bits each element touches. That is why it is so small: a filter holding 1 million items at a 1 percent false positive rate needs about 1.2 MB, while storing the actual keys would take tens of megabytes or more.
Because it stores no keys, a Bloom filter cannot list its contents, cannot delete an element from a standard implementation, and cannot tell you exactly which items are present. It only answers membership questions, and it answers them with a deliberate asymmetry. A "no" is always trustworthy. A "yes" means "probably, go check the real source."
The whole point is to act as a cheap front gate. You ask the filter first. If it says no, you stop and save the cost of a real lookup. If it says yes, you do the expensive lookup as a fallback.
To add an element, you run it through k independent hash functions. Each hash produces an index into the bit array, and you set those k bits to 1. Adding the string "alice" with three hash functions might set bits 4, 19, and 88.
To test for membership, you hash the element the same way and check whether all k of those bits are 1. If even one of them is still 0, the element was never added, so the answer is a definite no. If all k bits are 1, the answer is "possibly yes" because those bits could have been set to 1 by a combination of other elements.
That collision risk is the source of false positives. As you add more elements, more bits flip to 1, and the chance that an unrelated query happens to hit all-ones rises. The false positive rate is tunable: pick the array size m and the hash count k for your expected element count n. The optimal number of hashes is roughly k = (m/n) times ln(2), and adding more memory drives the error rate down fast.
Standard Bloom filters do not support deletion, because clearing a bit might undo bits shared with other elements. Variants exist to handle this. A counting Bloom filter replaces each bit with a small counter so items can be removed, and a scalable Bloom filter grows new layers as the dataset expands beyond the original sizing.
Reach for a Bloom filter when a definite "no" is cheap to act on and the real lookup is expensive. The classic case is avoiding disk seeks: before reading a large file on disk or a remote object, ask the filter whether the key could possibly be there. Most negative queries get rejected in memory in nanoseconds.
The trade-off is that you accept a small rate of false positives in exchange for huge memory savings and constant-time queries. You must size the filter up front against your expected element count. Overfill it and the false positive rate climbs toward useless; oversize it and you waste memory you were trying to save.
Do not use a Bloom filter when you need exact answers, when you need to enumerate or delete elements freely, or when the underlying lookup is already cheap. In those cases a plain hash set or the database itself is simpler and correct. A Bloom filter only pays off when the cost of the avoided work dwarfs the cost of the occasional wasted check caused by a false positive.
Consider a log-structured merge tree, the storage engine behind Cassandra, RocksDB, and LevelDB. Data lives in many immutable files called SSTables, sorted on disk. To read a key the engine may have to check several SSTables, and each check is a disk read.
Each SSTable carries a Bloom filter of the keys it contains, held in memory. On a read, the engine asks each filter first. If a filter says the key is definitely not in that SSTable, the engine skips the file entirely and never touches the disk for it. Only when a filter says "possibly" does the engine pay for the actual seek.
For a key that does not exist at all, which is common in write-heavy systems, this turns a multi-file disk scan into a few in-memory bit checks. The occasional false positive costs one needless seek, which is a tiny price next to the disk reads avoided on every true negative.
Apache Cassandra
Keeps a Bloom filter per SSTable so reads skip on-disk files that cannot hold the requested key.
Google Bigtable
The original LSM design that popularized per-SSTable Bloom filters to cut disk seeks on negative lookups.
RocksDB and LevelDB
Embedded key-value stores that attach Bloom filters to data blocks to avoid reading blocks that lack a key.
Medium
Uses Bloom filters to quickly skip articles a user has already seen when serving recommendations.
Only in one direction. It can produce a false positive, saying an element might be present when it is not, but it never produces a false negative. If it says an element is absent, that is always correct.
Each element sets several shared bits, and different elements can set the same bit. Clearing a bit to remove one element might also remove bits another element depends on, breaking it. A counting Bloom filter, which uses small counters instead of single bits, supports deletion.
By sizing the bit array and the number of hash functions against the expected number of elements. More memory and a well-chosen hash count lower the error rate. A common target is 1 percent, which needs about 9.6 bits per element.
A hash set stores the actual keys, gives exact answers, and supports listing and deletion, but uses far more memory. A Bloom filter stores no keys, uses a fraction of the space, and trades exactness for the occasional false positive.
No. Lookup and insert time stay constant at k hash computations regardless of how many elements you add. What degrades is accuracy: the false positive rate rises as more bits get set to 1.
Caching
Storing frequently accessed data in a faster storage layer so you don't have to fetch it from the original (slower) source every time.
Index
A data structure that speeds up database lookups. Like the index at the back of a book that lets you jump to the right page instead of reading every page.
Database
An organized collection of data that can be easily accessed, managed, and updated. The backbone of almost every application.
CAP Theorem
When a network failure splits a distributed data store, each node must either refuse requests to stay consistent or keep answering with possibly stale data. It cannot guarantee both during the partition.
Consensus
The process of getting multiple nodes in a distributed system to agree on a single value. The foundation of distributed databases and coordination services.
Paxos
A family of protocols for solving consensus in unreliable networks. Famously difficult to understand but mathematically proven correct.
This page explains the idea. The "Bloom Filters" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Bloom Filters lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Bloom Filter in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
