“You have 1 billion usernames. On every keystroke, the signup page asks whether a name is free. How do you answer without hammering the database, and without keeping every name in RAM?”
A Bloom filter gives up a little certainty to save a huge amount of memory. This page starts with why the obvious answers hurt, then builds the filter bit by bit, works out its size, and covers what goes wrong in production. Every term is explained the first time it appears.
| Term | What it means |
|---|---|
| Set membership | The question “is this item in the collection?” Yes or no, nothing more. A Bloom filter answers only this. It cannot give the item back or list what's inside. |
| Bit array | A long row of bits, each 0 or 1. 8 bits take 1 byte, so 8 billion bits take 1 GB. |
| Hash function | A function that turns any input into a number that looks random. The same input always gives the same number. Here we use that number as a position in the bit array. Bloom filters use fast non-cryptographic hashes such as MurmurHash or xxHash. |
| False positive | The filter says “maybe present” for an item that was never added. |
| False negative | The filter says “not present” for an item that was added. A correctly used Bloom filter never does this. |
| n, m, k, p | n = items you add. m = bits in the array. k = hash functions per item. p = false positive rate. |
| Cache penetration | Requests for keys that don't exist anywhere. The cache never holds them, so every request falls through to the database. |
| LSM tree / SSTable | A storage design used by Cassandra and RocksDB. Writes collect in memory, then flush to immutable sorted files called SSTables. One read may have to look through many of these files. |
A user typing param_codes fires a check for p, pa, par… (debouncing, meaning waiting for a typing pause, cuts this down but doesn't remove it). Multiply by every signup, and this becomes a high-volume read.
Notice what the question needs. You don't want the user's row. You only want one bit of information: does this name exist?
IMPThe shape that suits a Bloom filter: a large set, an expensive lookup, and many lookups where the answer is “no”. A filter pays off by avoiding those “no” lookups.
SELECT 1 FROM users WHERE username = ? with a unique index is correct, and a single lookup is fast. The problem is volume: every check costs a connection and index page reads, and uncached pages mean disk reads. This traffic competes with the queries that actually run your product. Keep the unique index anyway, because it's the final authority.
Fast and exact, but it stores every name. We measured this: 1 million 17-character names in a Redis set took 72 bytes each (Redis 7.0.11). The name is only 17 of those bytes. The rest is hash table overhead. Scaled to 1 billion names, that's about 72 GB of RAM, plus replicas.
Each name someone tries gets cached with a short lifetime. Popular names benefit, but people type endless unique variations, so hit rates are low on exactly the traffic you wanted to absorb. Memory also grows with every attempt.
What we want: almost exact, and far smaller than the data. The trick is to stop storing the names at all.
Burton Bloom published this in 1970. There are only three steps.
Create a bit array of m bits, all 0. Choose k hash functions.
Hash “alice” k times to get k positions, say 3, 11 and 25. Set those bits to 1. The name itself is not stored anywhere, which is why this is so small.
Hash “bob” the same way and look at those positions.
IMP“No” is a guarantee. “Yes” is only a maybe. The filter never replaces the database. It only stops most “no” traffic from reaching it.
A tiny filter: 32 bits and 3 hash functions. Add a few names, then check others. Press “Find a false positive” to watch the filter get one wrong.
The app keeps the list of added names only to label this demo. A real filter stores nothing but the bits. A real one is also much larger: 32 bits is deliberately small so collisions show up quickly.
k bit reads, whether the filter holds a thousand items or a billion. A check for an absent item usually stops early at its first 0 bit. We measured an average of 2.06 reads out of 7.Choose how many items you expect (n) and what false positive rate you can accept (p). Two formulas give the rest:
bits needed m = -n · ln(p) / (ln 2)² hash functions k = (m / n) · ln 2 false positives p ≈ (1 - e^(-k·n/m))^k
m = 1,000,000,000 × 4.605 / 0.4805 ≈ 9.585 billion bits, which is 9.585 bits per name.k = 9.585 × 0.693 ≈ 7 hash functions.| False positive rate | Bits per item | Hash functions | 1 billion items |
|---|---|---|---|
| 1% | 9.585 | 7 | 1.2 GB |
| 0.1% | 14.378 | 10 | 1.8 GB |
| 0.01% | 19.170 | 14 | 2.4 GB |
IMPAbout 4.8 extra bits per item cuts false positives by 10×. Size depends on the item count and the error rate, not on how long the items are.
| Setup (9.585 bits per item unless noted) | False positives | Bits set |
|---|---|---|
| k = 7, filled to plan | 1.01% | 51.8% |
| 14.378 bits per item, k = 10 | 0.10% | 50.1% |
| k = 1 (too few hashes) | 9.92% | 9.9% |
| k = 20 (too many hashes) | 7.05% | 87.6% |
| k = 7, 2× the planned items | 15.75% | 76.8% |
| k = 7, 5× the planned items | 83.16% | 97.4% |
False negatives in every run: 0. Node.js, positions from split MD5 hashes. These match the formula to within about 0.02 percentage points.
Look at the “bits set” column. The best filter is about half 1s and half 0s. Below that, memory is wasted. Above that, too many checks find only 1s. And overfilling is not a gentle failure: double the items and 1% becomes nearly 16%.
Plan a filter, then drag “actually inserted” past 100% and watch the false positive rate climb. The DB meter assumes every check is for an absent name.
Redis set estimate = items × (55 + name length) bytes, fitted to our one measurement of 72 bytes at 17 characters. Treat it as a rough figure: the real overhead changes with encoding and table size.
import { createHash } from "node:crypto";
class BloomFilter {
constructor(n, p) {
this.m = Math.ceil(-n * Math.log(p) / Math.LN2 ** 2);
this.k = Math.round((this.m / n) * Math.LN2);
this.bits = new Uint8Array(Math.ceil(this.m / 8));
}
*positions(item) {
const d = createHash("md5").update(item).digest();
const h1 = d.readUInt32LE(0), h2 = (d.readUInt32LE(4) | 1) >>> 0;
for (let i = 0; i < this.k; i++) yield (h1 + i * h2) % this.m;
}
add(item) {
for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7);
}
mightContain(item) {
for (const p of this.positions(item))
if (!(this.bits[p >> 3] & (1 << (p & 7)))) return false;
return true;
}
}
const usernames = new BloomFilter(1_000_000, 0.01);
usernames.add("alice");
usernames.mightContain("alice"); // true
usernames.mightContain("bob"); // false, almost always
Compute two hash values and derive the rest: position_i = h1 + i × h2. Kirsch and Mitzenmacher showed this keeps the same false positive rate asymptotically. That's the loop above. | 1 forces h2 to be odd, so it can't be 0 and repeat one position. >>> 0 is needed because | in JavaScript returns a signed number, and a negative position would silently break the filter. MD5 keeps this demo free of dependencies. In production, use a faster non-cryptographic hash such as xxHash or MurmurHash.
BF.RESERVE usernames 0.01 1000000000 BF.ADD usernames "alice" BF.EXISTS usernames "bob"
These commands ship with Redis Open Source 8 and later. Older versions need the RedisBloom module. Guava's BloomFilter is a common in-process choice for Java.
In an LSM tree, one key could be in any of many SSTable files, and searching them all means disk reads. So each file gets its own filter in memory. If the filter says “not here”, the database skips that file. RocksDB's NewBloomFilterPolicy(10) uses about 10 bits per key for about 1% false positives. Cassandra's bloom_filter_fp_chance defaults to 0.01 (0.1 with leveled compaction). This is the classic senior-level answer, and it's probably where you already rely on a Bloom filter without knowing it.
An attacker requests random product IDs that don't exist. The cache misses every time, and the database takes every hit. Caching “not found” doesn't help much, because each random ID is new and fills the cache with junk. Put a filter of all valid IDs in front: a “no” returns 404 straight away, and the database is never touched.
Akamai studied one cluster over two days. 74% of about 400 million objects were requested exactly once, so caching them wasted disk. Their rule: cache an object only on its second request, using a Bloom filter to remember what's been seen. In a test on about 47 production servers, byte hit rate rose from about 74% to 83% and disk writes fell 44%.
Medium Engineering wrote in 2025 that they made a filtering step cheaper by removing Bloom filters in favour of direct per-user database queries. A Bloom filter is a tool for a specific shape of problem, not an automatic upgrade.
The guarantee holds only for items that actually reached the filter. Suppose the DB insert succeeds, then the app crashes before updating the filter. Now the filter says “definitely not present” for a real row. For usernames, the user sees “available” and signup fails. For cache penetration protection, a real product returns 404.
Fix: add to the filter first, then write to the DB. If the DB write fails, you only have a few extra stale bits, which means a tiny extra false positive rate. The wrong order creates missing data errors. The right order creates a small harmless cost.
Two people can see “available” for the same name in the same second. The filter can't settle that. A unique index in the database decides the winner, and the loser gets a “just taken” error.
A freshly restarted empty filter answers “definitely not present” for everything. If you trust it, every lookup is wrong. Persist the filter (Redis RDB/AOF, a snapshot to S3), and if it's not fully loaded, send all checks to the database. The same applies when a Redis call times out.
Build a new filter from a table scan while the old one keeps serving. New signups must go to both filters from before the scan begins, otherwise anything created during the scan is missing. When the scan finishes, swap them. Rebuilds are also how you size up and clear out deleted items.
A fixed filter can't be resized, because it no longer knows the items and can't rehash them. Options: size for several years up front, rebuild when it fills, or use a scalable Bloom filter, which stacks a new larger filter when one fills up. Redis does this by default, but each extra filter makes checks slower. Monitor the fill level: alert when bits set goes well past 50%.
Param, param and param produce unrelated hash values. If your uniqueness rule ignores case, lowercase and trim before you add and before you check, using the same rule in every service. Otherwise you get false negatives.
m, k and hashes can be combined by OR-ing their bits. The result is the same as adding all items to one filter.Only half. It can prove a name does not exist. “Maybe” still needs the database.
False positives only. Bits never go back to 0, so an added item always finds all its bits set, unless your code skipped the add or deleted bits.
Those bits may be shared with other items, so this creates false negatives. Use a counting or cuckoo filter, or rebuild.
Too many fill the array. In our run at the same memory, k = 7 gave 1.01%, while k = 20 gave 7.05%.
Item length doesn't matter. Size depends only on item count and target error rate.
The 1% applies only at the planned item count. At 2× the items we measured 15.75%.
Never. Two concurrent signups can both pass the check. Only the unique index closes that race.
500,000,000 × 9.585 bits ≈ 4.79 billion bits. Divide by 8: about 600 MB, with k = 7.
The app wrote to the DB but never updated the filter (crash, or wrong write order), or the filter restarted empty. Different normalization between add and check, or a rebuild that missed writes, are also valid answers.
The filter now holds about 2× the planned items. Rebuild it larger from the database, and alert on the fill level so that it doesn't happen again.
Probably not. It only saves lookups where the answer is “no”, and that's just 5% of traffic here, while all the others pay for an extra check.
A key could be in any file, and files are immutable. A small in-memory filter avoids a disk read on most files that don't hold the key. Immutability also means the filter never needs a delete.
Ticks are saved in this browser. Press “Copy my picks” and paste them in chat.