What is a Bloom Filter?
A user wants a custom short link, short.ly/my-brand. Before you create it, you have to answer one question: is that slug already taken? With 365 billion existing links spread across 365 terabytes, you cannot scan the data on every keystroke, and even a database index lookup per attempt adds up fast at that scale. Gmail faces the identical problem when you pick a username: does this email already exist? across a billion accounts, instantly.
Both are the same question - have we seen this value before? - at a scale where the honest answer, "go look it up," is too slow to do every time. The tool built exactly for this is the Bloom filter. This post covers what it is, how it works down to the bits, how to size and implement one, the pattern that makes it useful, its limits, and where real systems use it.
Bloom filters are one of the reliability building blocks worth knowing cold.
What a Bloom filter is
A Bloom filter is a space-efficient, probabilistic data structure that answers set-membership with a deliberate asymmetry. Ask it "is X in the set?" and it gives one of two answers:
- "Definitely not in the set" - and it is always right about this.
- "Possibly in the set" - which is usually right, but has a small, tunable chance of being a false alarm.
The critical property: a Bloom filter never returns a false negative. If it says something is not present, it truly is not. It may occasionally say "possibly present" for something that was never added (a false positive), but it will never miss something you actually inserted. And it does all this in a tiny fraction of the memory that storing the real values would take - under 10 bits per element for a 1% error rate, no matter how large each element actually is.
How it works: a bit array and k hash functions
A Bloom filter is just two things: an array of m bits, all initialized to 0, and k independent hash functions, each of which maps any input to a position in that array.
Adding an element
To add a value, hash it with each of the k functions to get k positions, and set the bit at each of those positions to 1:
Querying: the "definitely not" case
To check membership, hash the value the same way and look at those k bits. If any one of them is 0, the value was definitely never added - because adding it would have set that bit to 1:
This is the guarantee that makes Bloom filters safe: a single 0 bit is proof of absence.
Querying: the false positive
If all k bits are 1, the value is possibly present. Usually that means it was added. But the bits could all have been set by other elements that happened to hash there - so a value you never inserted can look present. That is a false positive:
The more elements you add, the more bits become 1, and the higher the false-positive rate climbs - which is why sizing matters.
Implementing one
Here is a complete, working Bloom filter in TypeScript. The bit array is a Uint8Array (8 bits per byte), and rather than write k separate hash functions, it uses the standard trick of deriving all k positions from two base hashes (g_i = h1 + i * h2):
class BloomFilter {
private bits: Uint8Array;
private readonly m: number; // number of bits
private readonly k: number; // number of hash functions
constructor(expectedItems: number, falsePositiveRate = 0.01) {
// m = -(n * ln p) / (ln 2)^2 ; k = (m/n) * ln 2
this.m = Math.ceil(-(expectedItems * Math.log(falsePositiveRate)) / (Math.LN2 ** 2));
this.k = Math.max(1, Math.round((this.m / expectedItems) * Math.LN2));
this.bits = new Uint8Array(Math.ceil(this.m / 8));
}
// A fast, simple string hash (this is the well-known FNV-1a algorithm).
private hashString(key: string): number {
const FNV_OFFSET_BASIS = 0x811c9dc5;
const FNV_PRIME = 0x01000193;
let hash = FNV_OFFSET_BASIS;
for (let i = 0; i < key.length; i++) {
hash ^= key.charCodeAt(i);
hash = Math.imul(hash, FNV_PRIME);
}
return hash >>> 0; // coerce to an unsigned 32-bit integer
}
private positions(key: string): number[] {
const h1 = this.hashString(key);
const h2 = this.hashString(key + "#"); // a second, independent-enough hash
const out: number[] = [];
for (let i = 0; i < this.k; i++) out.push((h1 + i * h2) % this.m);
return out;
}
add(key: string): void {
for (const pos of this.positions(key)) {
this.bits[pos >> 3] |= 1 << (pos & 7); // set the bit
}
}
mightContain(key: string): boolean {
for (const pos of this.positions(key)) {
if ((this.bits[pos >> 3] & (1 << (pos & 7))) === 0) return false; // a 0 bit => absent
}
return true; // all bits set => possibly present
}
}
const seen = new BloomFilter(1_000_000, 0.01);
seen.add("my-brand");
seen.mightContain("my-brand"); // true
seen.mightContain("totally-new"); // almost always false
Both add and mightContain are O(k) - a handful of hashes and bit operations - regardless of how many items the filter holds.
Sizing it: how many bits, how many hashes?
That is the only practical question, and you choose just two numbers: m, the number of bits in the array, and k, the number of hash functions. Both fall out of a single decision - the false-positive rate you are willing to tolerate. Here is the whole recipe.
Step 1 - pick an acceptable false-positive rate. 1% is the usual default.
Step 2 - read the bits-per-item and the hash count off this table. These numbers depend only on the target rate, not on how many items you have or how big they are:
| Target false positive | Bits per item | Hash functions (k) |
|---|---|---|
| 10% | ~5 | 3 |
| 1% | ~10 | 7 |
| 0.1% | ~15 | 10 |
The two numbers worth memorizing: about 10 bits per item and 7 hash functions gives roughly 1% false positives. Each extra factor of ten in accuracy costs only about 5 more bits per item.
Step 3 - multiply. Total memory m = bits-per-item x your item count n. Done.
For the slug problem - 365 billion slugs at 1% - that is 10 bits each and 7 hashes:
| Items (n) | Memory at 1% (10 bits each) |
|---|---|
| 1 million | ~1.2 MB |
| 1 billion | ~1.2 GB |
| 365 billion | ~440 GB |
About 440 GB - large, but roughly 800 times smaller than the 365 TB of real data, and a flat array you can spread across a few machines. You went from "scan terabytes off disk" to "check seven bits in RAM."
The formulas, for reference
The table above is just these relationships evaluated at common rates. Keep them for when you need a custom rate or have to show your working:
n = number of items to store
m = number of bits in the array
k = number of hash functions
p = target false-positive rate
false-positive rate: p = (1 - e^(-k*n/m))^k
bits needed: m = -(n * ln(p)) / (ln(2)^2)
bits per item: m/n = -1.44 * log2(p)
optimal hash count: k = (m/n) * ln(2) (about 0.7 * bits-per-item)
Two things fall out of these worth stating: the bits-per-item depends only on the target rate p (not on n), and the optimal number of hash functions depends only on the bits-per-item. In an interview you quote the table; these are for deriving a rate that is not in it, or for explaining where the numbers come from.
The pattern that makes it useful
A Bloom filter is almost never the final answer - it is a fast, cheap negative filter placed in front of an expensive, exact check. It exists to avoid the slow lookup in the common case:
Walk it for the slug: the filter holds every slug ever created. When a new request comes in, you ask the filter first.
- It says "definitely not seen" - the slug is guaranteed free, so you create it immediately, with zero database reads. This is the overwhelming majority of requests, and they never touch the database.
- It says "possibly seen" - now, and only now, you do the real database lookup to be sure. Sometimes it confirms the slug is taken; sometimes it was a false positive and the slug is actually free.
Here is why this is safe, and it is the whole reason a Bloom filter fits: a false positive only costs you an occasional unnecessary database lookup - correctness is never violated, because the database is the source of truth on the maybes. A false negative, on the other hand, would be catastrophic: it would tell you a taken slug (or an existing email) is free, and you would hand out a duplicate. And a Bloom filter never gives a false negative. The one kind of error it can make is the harmless one; the dangerous kind is impossible by construction. That is the property that makes it the right tool here, not a lucky optimization.
Scaling a Bloom filter as it fills
A Bloom filter is sized for an expected number of items. Insert far more than you planned and more and more bits flip to 1, so the false-positive rate creeps up until the filter says "maybe" to nearly everything and stops being useful. And you cannot simply resize it: a bigger array would need every element rehashed into it, but a Bloom filter does not store the elements, so there is nothing to rehash. Three ways to handle growth:
- Over-provision up front. Bits are cheap - about 1.2 GB per billion items at 1% - so if you can estimate the maximum
n, just size for it and move on. The simplest answer, and usually the right one. - Rebuild and swap. If you still have the source data (the actual slugs sit in a database), periodically build a fresh, correctly-sized filter offline and atomically swap it in.
- Scalable Bloom filter. When you truly do not know
nahead of time, chain filters: fill the first to its target rate, then add a second, larger one with a tighter target so the combined error stays bounded, then a third, and so on. New inserts go to the newest filter, and a query is "present" if any filter in the chain says maybe.
The catch with the chain is that a lookup must check every filter, so reads slow down a little as it grows - which is why over-provisioning or rebuilding is preferable whenever you can estimate the size.
Can you distribute a Bloom filter?
Yes, and one property makes it clean: two Bloom filters of the same size, using the same hash functions, can be merged with a bitwise OR of their bit arrays, and the result is exactly the filter for the union of both sets. Independent machines can each build a partial filter, and you combine them with an OR - no coordination needed.
That property enables a few real designs:
- Shard it. Partition the keys the way you shard a database - by a hash of the slug - and give each node a Bloom filter covering only its shard. A check routes to the node that would own the key and asks its local filter. This scales the filter's memory horizontally, so no single machine has to hold all 440 GB.
- Replicate it. Keep one logical filter and copy the bit array to every node for fast local reads, OR-ing new insertions into every replica. Ideal when the set changes rarely - Chrome ships its Safe Browsing filter to every browser exactly this way.
- Share it in a store. Put the bit array in Redis (its RedisBloom module does this) so every node reads and writes one shared filter over the network - simplest and consistent, at the cost of a network hop per check.
- Build locally, merge globally. Each node builds a filter from what it sees, and you periodically OR them into a global filter and redistribute it.
This is why Bloom filters fit distributed systems so naturally: Cassandra and ScyllaDB already keep a Bloom filter per data file on every node, so the filters are distributed for free by the same partitioning that distributes the data. One caveat: OR-merging requires an identical size and hash functions across the filters, and counting Bloom filters merge by adding their counters instead.
Limitations, and the variants that address them
Standard Bloom filters buy their space efficiency with real constraints:
- You cannot delete. Clearing an element's bits could unset a bit another element depends on, breaking the no-false-negative guarantee. The fix is a Counting Bloom filter: replace each bit with a small counter, increment on add, decrement on remove, and treat a position as "set" while its counter is above 0.
- Fixed capacity. You size it for an expected
n, and over-filling degrades the false-positive rate - handled by over-provisioning, rebuilding, or a Scalable Bloom filter, as covered above. - You cannot list the contents or reliably count them - it only answers membership.
- Deletion plus low error at high load is better served by a Cuckoo filter, a close cousin that supports removal and often beats Bloom on space at low false-positive rates.
Where real systems use them
Bloom filters are quietly everywhere:
- LSM-tree databases - Cassandra, ScyllaDB, HBase, and Bigtable keep a Bloom filter per on-disk file (SSTable). Before doing an expensive disk read to look for a key, they ask the filter; a "definitely not here" skips the disk entirely. This is the single most common production use.
- Redis offers Bloom filters through its RedisBloom module for exactly the "have we seen this?" pattern.
- Browsers - Chrome's Safe Browsing used a Bloom filter to check URLs against a huge malicious-site list locally, only calling the network on a "maybe."
- CDNs and caches use them to detect "one-hit wonders" - items requested once and never again - so they are not cached wastefully.
The interactive demo at Jason Davies' Bloom filter is worth a few minutes to watch the bits fill in real time, and ScyllaDB's glossary entry has the math laid out cleanly.
When not to reach for one
- When you need an exact answer and have no cheap fallback for the maybes - use a real set or the database.
- When you delete often - use a Counting or Cuckoo filter instead.
- When the set is small enough to fit in a normal hash set - the Bloom filter's cleverness is not worth it.
Back to the slug
The custom-slug and email-existence problems looked like "search 365 terabytes on every request." A Bloom filter turns them into "check about seven bits in memory," and only falls back to the database for the small fraction of maybes - never for the common case of a genuinely new value. Because it can only ever err by saying "maybe" (never by missing a real match), it is not just fast here, it is correct here. That combination - near-free memory, constant-time checks, and an error that is always the safe kind - is why the Bloom filter is the standard answer whenever you need to ask "have we seen this before?" at scale.