System Design Patterns

Bloom Filters

A database wants to know whether a disk file might contain a key before paying for a lookup. A cache wants to recognize items requested before, and a recommendation service wants a compact approximation of recently seen posts. A Bloom filter helps when a fast “definitely absent” answer avoids expensive work, while a “possibly present” answer is handled according to the application’s tolerance for false positives.

A is the tiny memory structure behind those "definitely not" answers: with rare when it says maybe.

Safe URL check

k positions in a bit array.

Check bits

Any 0 → definitely not listed.

Verify with full store.

Skip expensive I/O

Most negatives never hit disk.

Try it: insert, lookup, and estimate false positives

This teaching Bloom filter uses 64 bits and three hash functions. Insert keys to watch bits flip, then query keys that were never inserted to see occasional false positives.

Inserted keys: 0
Bits set: 0
Estimated FP rate: 0.0%
Load (n/m): 0.00

Query key

Bit array (highlight = query hash positions)

Insert a few keys, then query members and non-members. A zero bit means definitely absent; all ones means possibly present and needs a full store check.

Trust negatives. Query a key you never inserted until you get a definite absent answer (at least one zero bit). That is the filter saving I/O.

Verify maybes. When every bit is 1 for an unknown key, treat the result as a hint only and read the authoritative store before acting on money or access.

What actually happens

You allocate a bit array and . Adding an item sets those bits. Querying checks them: any zero means definitely absent (no ). All ones means possibly present: go to the real store because of possible .

In an , each carries a filter so missing keys skip most disk reads. In browsers, a compact filter file screens unsafe URLs before a server round-trip. In feeds and caches, filters power cheap membership and .

At billion-key scale an exact hash set can cost tens of gigabytes; a Bloom filter at ~1% false positives often fits in about a gigabyte: small enough to keep hot in memory.

How to choose a filter

1. Do you need deletes? Classic Bloom cannot delete cleanly. Use a or when membership churns.

2. What false-positive rate can you afford? More bits and hashes lower noise but cost memory and CPU. Size for planned n: overfilling destroys the rate.

3. Is the set mostly immutable? Compact static filters (ribbon-style) can beat Bloom on space for frozen tables; rebuild when the set changes.

Simple rule of thumb

Use Bloom filters as a pre-check to avoid expensive negatives. Aim near ~10 bits per item for ~1% false positives with ~7 hashes. Rebuild or rotate before you outgrow capacity. Never treat maybe-present as definitely-present.

How Bloom filters work

plaintext

Structure: bit array of m bits, k hash functions

Add element x:
  h1(x) → bit 3    (set to 1)
  h2(x) → bit 7    (set to 1)
  h3(x) → bit 15   (set to 1)

Query element y:
  h1(y) → bit 3    (is 1? yes)
  h2(y) → bit 7    (is 1? yes)
  h3(y) → bit 15   (is 1? yes)
  All 1 → POSSIBLY in set (may be false positive from collisions)

Query element z:
  h1(z) → bit 3    (is 1? yes)
  h2(z) → bit 9    (is 0? no)
  Any 0 → DEFINITELY NOT in set (zero false negatives)

Key properties:
  - No false negatives: if element was added, all bits are set
  - Possible false positives: other elements may have set same bits
  - Cannot delete elements (bits shared between elements)
  - Constant time: O(k) per add/query regardless of set size
  - Constant space: fixed bit array regardless of queries

Optimal parameters

Given: n elements, desired false positive rate p

plaintext

m = -(n × ln(p)) / (ln(2))² ≈ -1.44 × n × log₂(p)
k = (m/n) × ln(2) ≈ 0.693 × (m/n)
p ≈ (1 - e^(-kn/m))^k

Elements (n)	FP rate (p)	Bits (m)	Size	k hashes
1 million	1%	9.6M	1.2 MB	7
1 million	0.1%	14.4M	1.8 MB	10
1 billion	1%	9.6B	1.2 GB	7
1 billion	0.1%	14.4B	1.8 GB	10
10 billion	1%	96B	12 GB	7

~40 GB

HashSet for 1B elements

~1.2 GB

Bloom filter (~33× smaller)

The filter stores evidence of membership, not the original strings. At a 1% false-positive target, the optimum is about 9.6 bits per planned element and seven bit positions per insertion. Ten million elements therefore need about 96 million bits, or 12 million bytes. The original records still live elsewhere; this is additional index memory whose purpose is to avoid expensive lookups. Hash quality, capacity, and the fraction of absent queries determine the benefit.

False-positive math worked example

Where the formula comes from

plaintext

After n inserts with k hashes into m bits:
Chance one specific bit is still 0:
  (1 - 1/m)^(kn) ≈ e^(-kn/m)

Chance that bit is 1:
  1 - e^(-kn/m)

False positive means all k checked bits are 1:
  p = (1 - e^(-kn/m))^k

10M planned keys at 1%

plaintext

n = 10,000,000 keys
p = 0.01
m = -(n × ln p) / (ln 2)^2
  ≈ 95,850,584 bits ≈ 11.4 MiB
k = (m/n) × ln 2 ≈ 6.64 → use 7 hashes

Backend savings:
1M negative lookups/sec × 99% definite misses
≈ 990K database or disk lookups avoided/sec

Planned keys	1% false positive	0.1% false positive	0.01% false positive
10M	11.4 MiB, 7 hashes	17.1 MiB, 10 hashes	22.9 MiB, 13 hashes
100M	114 MiB, 7 hashes	171 MiB, 10 hashes	229 MiB, 13 hashes
1B	1.14 GiB, 7 hashes	1.71 GiB, 10 hashes	2.29 GiB, 13 hashes

Bits per item (rule of thumb)

plaintext

bits_per_item = m/n ≈ -ln(p) / (ln 2)^2 ≈ 1.44 × log₂(1/p)

p = 1%    → ~10 bits/item
p = 0.1%  → ~14 bits/item
p = 0.01% → ~20 bits/item

Check: 100M keys × 10 bits ≈ 1e9 bits ≈ 125 MB
(table above uses ~9.6 bits/item at 1%, so ~114 MiB)

Overfilling trap

If a filter sized for ten million elements at roughly 1% false positives receives twenty million, many more bits become one. Using m/n≈9.6 and k=7 in the formula, doubling occupancy increases the approximate false-positive rate to about 16%. Previously inserted items remain present under correct operation, but the backing store now receives far more unnecessary lookups. Monitor inserted cardinality and measured false positives, then rebuild or add capacity before the planned load is exceeded.

Negative: trust it; skip backend lookup.

Positive: verify in source of truth.

Do not use: authorization, billing, or final correctness decisions.

Bloom filter variants

Counting Bloom filter

plaintext

Replace bits with counters (4-bit typical)

Add: increment counters at h1(x)...hk(x)
Delete: decrement counters only for a known inserted item
        whose outstanding insertion is being removed; guard overflow
Query: all counters > 0 → possibly in set

Pros: Supports deletion
Cons: 4× more space (4 bits vs 1 bit)
      Counter overflow possible (rare)

Use: Dynamic sets where elements come and go
     Session tracking, temporary blocklists

Cuckoo filter

plaintext

Uses cuckoo hashing with fingerprints

Pros vs Bloom:
  - Supports deletion (no counters needed)
  - Better FP rate for same space
  - Better lookup performance (2 locations)
  - Cache-friendly memory access

Cons:
  - Insert may fail at high load (> 95%)
  - More complex implementation

Use: When you need delete support
     Modern replacement for Counting Bloom
     In-memory filter module

Quotient filter

Cache-friendly, supports delete and merge. Stores fingerprint quotient/remainder. Better cache locality than Bloom (sequential memory). Used in storage firmware, deduplication, and database engines.

Ribbon filter

A compact static-filter design can use less space than a standard Bloom filter at the same false-positive rate. Slower construction but fast queries; optimized for immutable table-like data.

Bloom filters in databases (LSM trees)

plaintext

LSM-tree storage:
  Data is stored in immutable SSTables on disk
  Read: must check multiple SSTables to find a key

  Without Bloom filter:
    GET key_123 → check SSTable_1 (disk read, 150μs)
                → check SSTable_2 (disk read, 150μs)
                → check SSTable_3 (disk read, 150μs)  ← found!
    Total: 3 disk reads = 450μs

  With Bloom filter per SSTable:
    GET key_123 → Bloom_1: "definitely not here" (skip, 0.1μs)
                → Bloom_2: "definitely not here" (skip, 0.1μs)
                → Bloom_3: "possibly here" → disk read (150μs)
    Total: 1 disk read = 150.2μs (3× faster)

  At scale (1000 SSTables),
    Without Bloom: up to 1000 disk reads per query
    With Bloom: about 10 false-positive file checks for an absent key
    if all 1000 files are candidates at 1% FP; caching may avoid disk I/O

Bloom filter config:
  bloom_filter_fp_chance: 0.01  (1% false positive)
  → Default for most tables
  bloom_filter_fp_chance: 0.1   (10% FP, less memory)
  → For tables with few reads
  bloom_filter_fp_chance: 0.0001 (0.01% FP, more memory)
  → For time-series with many SSTables

Distributed Bloom filters

Merging Bloom filters

plaintext

Filters can be OR-merged only with matching m, k, hash functions/seeds,
serialization, and key normalization
Result: contains all elements from both (union)

Node 1: Bloom_1 (local elements)
Node 2: Bloom_2 (local elements)
Global: Bloom_1 | Bloom_2 (all elements)

Use: Distributed deduplication
     Each node has local filter, periodically merge for global view

Scalable Bloom filters

plaintext

Problem: standard Bloom has fixed capacity
Solution: chain of Bloom filters with decreasing per-filter FP budgets
  Filter 1: 1M elements, 1% FP
  Filter 2: 1M elements, 0.5% FP (created when Filter 1 full)
  Filter 3: 1M elements, 0.25% FP
  Combined FP ≈ 1% + 0.5% + 0.25% ≈ 1.75%

Query: check all filters (any positive → possibly in set)
Add: only to latest filter

In-memory Bloom filter

python

BF.ADD  myfilter element1
BF.EXISTS myfilter element1 → 1 (possibly exists)
BF.EXISTS myfilter element2 → 0 (definitely not)
BF.RESERVE myfilter 0.01 10000000  (1% FP, 10M elements)

Common production uses at scale

Browser threat lookup

A threat-lookup service can use a compact local membership structure to avoid sending every ordinary URL to a remote backend. A possible match triggers an authoritative lookup instead of immediately blocking the URL. This is an illustrative design pattern, not a claim that a particular browser currently implements its threat database as a classic Bloom filter. Freshness is critical: a filter snapshot cannot reject lookups for newly added threats unless updates are also checked.

Wide-column store SSTable reads

An immutable sorted file can carry a filter built from exactly its keys. For a missing key, a negative result skips that file’s data lookup; a positive result still requires an index and possibly a disk read. If 1,000 candidate files each have a 1% false-positive rate, an absent key produces about ten false-positive file checks on average, not automatically one or two. File-range pruning and compaction further reduce the number of candidate files.

Feed duplicate detection

A feed can use a per-user filter as a compact approximation of recently seen item identifiers. A false positive means a genuinely unseen item may be suppressed; this is a product-quality trade-off rather than harmless extra work. If every unseen item must remain eligible, verify possible matches against an exact history store. Rotate filters by time window and bound retained history so the per-user memory budget remains manageable.

Content cache admission

Edge caches use Bloom filters to determine if content is popular enough to cache. First request adds URL to filter. Second request: filter says "seen before" → cache it. Prevents one-hit wonders from polluting cache.

Choosing and explaining Bloom filters

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

A Bloom filter answers definitely-not-present or maybe-present with much less memory than a set.

False positives are allowed; false negatives are not, unless the filter is misused.

It is a pre-check that reduces expensive lookups, not the source of truth.

When it belongs

You need to avoid cache penetration or disk lookups for definitely missing keys.

A datastore, crawler, or feed system needs cheap membership checks.

Memory is too expensive for an exact set at billion-key scale.

How it fails

False-positive rate grows as the filter becomes overfilled.

Deletes are impossible without a counting or partitioned filter.

Bad hash functions create uneven bit distribution.

Trade-offs to weigh

Less memory versus occasional unnecessary real lookups.

More hash functions lower false positives until CPU cost dominates.

Counting filters support deletion but use more memory.

Common misunderstandings

Using Bloom filters for authorization or correctness decisions.

Forgetting to rebuild or rotate filters as data changes.

Confusing maybe-present with definitely-present.

Going deeper

Bloom filters

The mechanism and its boundary

A Bloom filter is a compact probabilistic set used to avoid expensive lookups. It never says an inserted item is absent, but it can say an absent item is probably present, so positives must be verified when correctness matters.

False-positive math

n items

m bits

k hashes

p false positives

Work through the sizing assumptions

False-positive rate: p = (1 - e^(-kn/m))^k, where n is inserted items, m is bits, and k is hash functions.

Optimal bits: m = -(n ln p) / (ln 2)^2. For n=100M and p=1%, m is about 958M bits, or 120 MB.

Optimal hashes: k = (m/n) ln 2. At 1% false positives this is about 6.6, so choose 7 hashes.

If 50,000 absent-key reads/sec hit storage and p=1%, only about 500/sec become unnecessary backend lookups.

When it belongs

Most reads are misses and the backing lookup is expensive. The set is large enough that exact in-memory membership is too costly. False positives are acceptable but false negatives are not.

Assumptions that matter

The capacity n is planned from peak cardinality, not current size. The bit array fits in memory near the read path. A false positive costs one backend lookup, not incorrect user state.

Easy mistakes

A filter built for yesterday’s cardinality becomes less selective as more distinct items are inserted, so measure its occupancy and plan rebuilds or rotation. Treating a positive result as exact membership turns harmless false positives into incorrect application decisions. Adding hashes beyond the useful range increases CPU work and can also worsen the false-positive rate for a fixed bit array, so size the array and hash count together.

How it fails

Overfilled filters drift from 1% to much higher false positives. Bad hash independence creates clustered bits. Deletes are modeled incorrectly and introduce false negatives.

Trade-offs to name

A Bloom filter uses much less memory than storing every full key, but a positive answer still needs an exact lookup when the application must establish membership. A lower target false-positive rate needs more bits per item and a suitable number of hashes, so compare the saved storage reads with the added memory and hashing cost. Immutable filters are easy to rebuild alongside immutable data files, while growing or deletable sets need explicit capacity management, replacement filters, or a structure such as a counting filter.

Wrap-up

You have sized bits-per-element, LSM negative lookups, and when to prefer cuckoo or counting filters. Keep the primary papers for the formulas and variants.

Primary sources

Bloom: Space/Time Trade-offs (CACM 1970) : original Bloom filter paper.
Apache Cassandra Architecture : LSM negative lookups in practice.
Fan et al.: Cuckoo Filter (CoNEXT 2014) : deletable approximate membership.

Key takeaway

Bloom filters trade a small false-positive rate for massive space savings. Size near ~10 bits/element for 1% FP with ~7 hashes. Essential in LSM databases to avoid disk reads. Prefer cuckoo or counting variants when you need deletes. At billion-user scale they turn expensive negative lookups into cheap memory checks: a building block, not a source of truth.

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Use probabilistic membership with explicit false-positive budget, sizing, hash count, saturation monitoring, rebuild, and deletion strategy.

Explain the decision

Why can a standard Bloom filter not safely delete one key?

Read the reasoning

Clearing a shared bit can create false negatives for other keys; use counting variants or rebuild from authority.

Apply it to a production scenario

False positives climb after data doubles. What do you do?

Read one approach

Measure fill ratio/observed rate, build a correctly sized version, dual-check during warm-up, atomically switch, and retire the saturated filter.

Work through the numbers

For n=10M and 1% false-positive target, estimate bits using m≈−n ln p/(ln2)^2.

Read the worked calculation

About 95.9 million bits, roughly 11.4 MiB, with about 7 hash functions.

Reason through a failure

What must a negative Bloom result guarantee?

Read the recovery reasoning

For keys represented by the current complete build, negative means definitely absent; partial/stale builds must not be trusted to skip authoritative lookup.

Sources and further study

Bloom — Space/Time Trade-offs in Hash Coding

Continue with B-Trees and Variants.