Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 65 ยท Core Algorithms and Data Structures for Design

Bloom Filters

Learn Bloom filters for system design: how bits and hashes answer 'definitely not' or 'maybe', sizing for a false-positive rate, uses in databases and caches, with Python.

Imagine a database that holds billions of keys across many files on disk. A request asks for key x. Checking each file costs a disk read. Wouldn't it be nice to know cheaply that x is definitely not in a file, so you can skip it? A Bloom filter does exactly that. It is a compact, probabilistic data structure that answers a membership question with one of two answers:

  • "Definitely not in the set", which is always correct.
  • "Possibly in the set", which is usually right but can be a false alarm (a false positive).

It never gives a false negative. In exchange, it uses a tiny fraction of the memory a real set would need, often about 10 bits per element for a 1 percent false-positive rate, regardless of how large the elements are.

How it works

A Bloom filter is an array of m bits, all initially 0, plus k independent hash functions.

  • Add an element: compute its k hashes, each giving a position in the array, and set those k bits to 1.
  • Check an element: compute the same k positions. If any bit is 0, the element was never added: definitely not. If all are 1, it is possibly present, because other elements may have set those same bits.

Add and check

Add Hash k times, set k bits to 1.
Check Hash k times, look at k bits.
Any bit 0 Definitely not present.
All bits 1 Probably present.

Bits can be shared, so "probably" is never "certainly".

1 / 2
Python A Bloom filter in 25 lines

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four added names answer "possibly present" (no false negatives). The names that were never added are usually "definitely absent", though with a small array you may see an unlucky false positive.

False positives and sizing

The false-positive rate depends on three numbers: the number of bits m, the number of hash functions k and the number of inserted elements n. The approximate rate is:

p โ‰ˆ (1 - e^(-kยทn/m))^k

You can work backwards to size a filter for a target rate p:

  • bits needed: m = -n ยท ln(p) / (ln 2)ยฒ, about 9.6 bits per element for 1%.
  • best number of hashes: k = (m/n) ยท ln 2, about 7 for 1%.

Each extra 4.8 bits per element divides the false-positive rate by about ten. When the filter is overfilled (n much larger than planned), the rate climbs quickly, so size for the largest expected n.

Python Measure the real false-positive rate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The measured rates should land close to the targets, confirming the formulas. The memory difference is also striking: the filter stores no keys at all.

Where Bloom filters are used

  • LSM-tree databases (Cassandra, RocksDB, HBase): one filter per SSTable lets a read skip files that cannot contain the key, avoiding most disk reads for missing keys (see LSM Trees and B-Trees).
  • Caches and CDNs: avoid caching one-hit wonders by caching an object only the second time it is requested; a Bloom filter remembers "seen once" cheaply.
  • Preventing wasted lookups: check "does this username/URL exist?" in memory before a database call; a "no" answer is final.
  • Web crawlers and safe-browsing checks: remember billions of visited or malicious URLs in a small memory budget.
  • Distributed joins and sync: ship a small filter instead of a whole key list to filter rows early.
  • Spell checkers, password breach checks and many other membership tests.
Python A Bloom filter in front of a slow database

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This is why Bloom filters protect databases from floods of lookups for non-existent keys, a pattern called cache penetration.

Variants and limits

  • Counting Bloom filter: each position is a small counter, so you can remove elements, at several times the memory.
  • Cuckoo filter: supports deletion and often uses less space at low false-positive rates.
  • Scalable Bloom filter: adds new filters as the set grows, when n is unknown.
  • Limits: you cannot retrieve elements, and false positives grow if the filter is overfilled. If a false positive is costly or a "maybe" is unacceptable, you need an exact structure.

In a design, say it like this: "A Bloom filter in front of the store answers 'definitely not here' from memory, so only keys that might exist cost a disk read or database query."

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A Bloom filter says an item is NOT present. What does that mean?

    At least one of the item's bits is 0, which cannot happen if it had been added. There are no false negatives.
  2. 2. What can a Bloom filter produce that a hash set cannot?

    Different items can set the same bits, so a never-added item might appear present.
  3. 3. Why can't you delete from a standard Bloom filter?

    Shared bits make removal unsafe. Counting Bloom filters or cuckoo filters support deletion.
  4. 4. How do LSM-tree databases use Bloom filters?

    A per-file filter avoids disk reads for files that definitely lack the key.

Summary

  • A Bloom filter is a bit array plus k hashes that answers "definitely not" or "possibly yes".
  • It has no false negatives; the false-positive rate is tuned with bits per element (about 10 bits for 1%).
  • It cannot list, count exactly or delete elements; variants like counting and cuckoo filters add deletion.
  • It guards databases, caches, crawlers and LSM trees from useless lookups.
  • Size it for the maximum expected number of elements.

Next: Counting at Scale: HyperLogLog and Count-Min Sketch