System designDeep dive11 min
Bloom filters
Answer is this one of them? for half a billion items in a few hundred megabytes. A no is always right; a yes is right almost always, and you choose how often.
1 · The problem
Every handle check costs a database read, even when the answer is no
A social app has 500 million accounts. On the sign-up form, a new user types a handle, and after each pause the form asks whether it is taken. At peak that is 20,000 checks a second, and each one is a read against the accounts database, whether the handle exists or not.
The obvious fix is to keep every taken handle in memory. But an exact set has to store the handles themselves. In Redis a set costs about 24 bytes per member plus the value, so 500 million handles of about 12 characters take 500,000,000 × 36 bytes = 18 GB, too much to copy onto every server that runs the check.
Memory to answer is this handle taken? for 500 million handles. The set stores every handle; the filter stores about 10 or 14 bits per handle, however long the handle is. 500,000,000 × 9.6 bits ≈ 0.6 GB.
A Bloom filter is the third option. It answers is this one of them? from a fixed row of bits, without storing the items at all. The price is that some of its yes answers are wrong. For the sign-up form that is a good trade, because a wrong yes only means one extra database read.
2 · How it works
A row of bits and a few hash functions
Start with m bits, all zero, and pick k hash functions, each mapping a handle to one of the m positions. With 16 bits and 3 hash functions:
- Add "mira"
Its three hashes point at bits 2, 7 and 11. Set them to 1.
- Add "sam"
Bits 4, 7 and 13. Bit 7 is already 1, and stays 1.
- Check "lena"
Bits 2, 9 and 13. Bit 9 is 0, so lena was never added: no added handle could have left it at 0.
- Check "omar"
Bits 4, 11 and 13: all 1, set by mira and sam. The filter says maybe, and it is wrong.
The 16 bits after adding mira and sam
position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bit 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0
↑ lena checks bit 9: it is 0A yes for an item that was never added is a false positive. It happens when other items have, between them, set every bit the new item checks. The more of the row is set, the more often it happens, which is why the size of the row and the number of hash functions are the whole design.
Adding and checking each touch k bits, whatever the number of items already in the filter. In practice nobody writes k different hash functions: two hash values h1 and h2 are enough, and position i is h1 + i × h2, with no loss of accuracy that matters.
A Bloom filter in a few lines
class Bloom {
private bits: Uint8Array;
constructor(private m: number, private k: number) {
this.bits = new Uint8Array(Math.ceil(m / 8));
}
private *positions(item: string) {
const h1 = hash(item, 1), h2 = hash(item, 2); // any good hash, two seeds
for (let i = 0; i < this.k; i++) yield (h1 + i * h2) % this.m;
}
add(item: string) {
for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7);
}
mightContain(item: string) {
for (const p of this.positions(item)) if (!(this.bits[p >> 3] & (1 << (p & 7)))) return false;
return true;
}
}3 · The guarantee
A no is certain, so use the filter where a wrong yes only costs a lookup
An added item always sets all its bits, and bits are never cleared, so a zero bit proves the item was never added. A Bloom filter has no false negatives. Its errors all go one way, and that decides how to use it: let a no settle the question, and send every yes to the real data.
The filter lives in the handle service's memory. A no answers at once; a maybe costs the same read as before the filter, and a false positive costs nothing worse.
If half the checks are for free handles, the filter answers those 10,000 a second from memory. At 1% false positives, about 100 of them a second still reach the database by mistake. The 10,000 checks for taken handles all go to the database, as before.
Two rules keep the guarantee true in a real service:
- The database stays the judge. Two people can check the same free handle at the same moment, so the account insert still relies on the database's unique index. The filter only makes the check on the form fast.
- A no is certain only if the filter saw every add. If each server keeps its own copy and a new handle reaches some copies late, those copies answer no for a taken handle. Add new handles to every copy, or keep one shared filter.
Rejecting a handle on a maybe, without the database read, is also possible, and some products do it. It turns away 1 in 100 free handles at a 1% rate: a choice to make knowingly, not by accident.
4 · The numbers
About 10 bits per item buys 1% false positives, whatever the items are
For n items in m bits with k hash functions, the false-positive rate is close to (1 − e^(−k·n/m))^k. Two results follow from it:
- the best number of hash functions is k = (m ÷ n) × ln 2, about 0.7 × the bits per item;
- with that k, a target rate p needs −ln p ÷ (ln 2)² bits per item, about 1.44 × log₂(1/p).
Wrong yes | Bits per item | Hash functions | 500 million handles |
|---|---|---|---|
1 in 10 | 4.8 | 4 | 300 MB |
1 in 100 | 9.6 | 7 | 600 MB |
1 in 1,000 | 14.4 | 10 | 900 MB |
1 in 10,000 | 19.2 | 14 | 1.2 GB |
Each tenfold cut in false positives costs the same 4.8 bits more per item. And the item's own size never enters the formula: a 12-character handle and a 2 KB URL cost the same bits. The filter stores bits set by hashes, not the items.
More hash functions are not always safer. Each one sets another bit per item, so beyond the best k the row fills up and false positives rise again. Here is a filter with 9.6 bits per handle and different values of k:
One hash function gives almost 10%; seven give 1%; twenty give 7% again. The curve is flat near the best k, so 6 or 8 cost almost nothing extra.
5 · The catch
A Bloom filter can't forget, and it degrades when you overfill it
The filter's size is fixed when you create it, from the number of items you expect. Keep adding past that number and nothing fails: adds still work, and no answers are still right. The yes answers just get worse, quickly.
4.8 billion bits and 7 hash functions, fixed. At twice the planned handles the rate is about 16%; at three times, about 44%, and the filter saves little.
Deleting is the other limit. When an account is closed and its handle freed, you can't clear the handle's bits: each of them may also belong to handles that still exist, and clearing it would make the filter say no for those, the one error it promises never to make. So freed handles keep answering maybe, and each check of one costs a database read that finds nothing.
Way out | How it works | Cost |
|---|---|---|
Rebuild it | Build a fresh filter from the database, for example nightly, and swap it in | A full read of the data each time; adds made during the build must go to both |
Counting Bloom filter | Small counters instead of bits; an add increments, a delete decrements | About 4 times the memory, for counters of 4 bits |
Cuckoo filter | Stores a short fingerprint per item, which a delete removes | Delete only what you added, or you may remove another item's fingerprint |
Stacked filters | When one fills, start a bigger one and check them all, as Redis's Bloom filter does | Each check costs more as filters stack up |
A cuckoo filter also takes less space than a Bloom filter when the target rate is below about 3%. And none of these structures can list the items they hold: if you need the handles back, they have to live somewhere else.
6 · Where they're used
Use one to skip work that would find nothing
The best uses share one shape: a lookup that is expensive, often finds nothing, and can tolerate an occasional wasted try. The biggest is inside databases built on LSM trees, which keep data in many sorted files on disk. A read for one key may have to look in many files, and most of them don't hold it.
Every file that can't hold the key is ruled out from memory. Only a maybe costs a disk read, and only a false positive costs one for nothing.
RocksDB adds a filter to each file at 10 bits per key by default, for about 1% false positives. Cassandra keeps one per data file, off the Java heap, with a default target of 1 in 100, or 1 in 10 for tables using leveled compaction; it notes that 1% takes about three times the memory of 10%. Storage engines: B-trees, LSM trees & WAL shows where those files come from.
Where | The question | What a no saves |
|---|---|---|
LSM storage engines | Could this file hold the key? | A disk read per file |
A cache in front of a database | Does this id exist at all? | A database read for ids that don't exist, as in Cache failure modes |
Web crawlers | Have we fetched this URL before? | Storing every URL seen, at billions of URLs |
Per-user features | Has this user already seen this ad? | Storing a full history per user |
The crawler row shows the one-sided error from the other side: a false positive there means a page is wrongly treated as seen and never fetched. Whether that is acceptable is a product decision, and Web crawling makes it.
Check yourself
5 questions
Takeaways
Remember this
- A Bloom filter's no is certain and its yes is probable, so let a no settle the question and send a yes to the real data.
- About 9.6 bits per item and 7 hash functions give 1% false positives, whatever the size of the items.
- Each tenfold cut in false positives costs about 4.8 more bits per item.
- Size it for the final count: past it, false positives climb fast, and a plain filter can't delete.
- Use one to skip expensive lookups that would find nothing: files on disk, ids that don't exist, URLs already seen.