Topic 1.3
Saturation: What Happens Past Capacity
In one line
A Bloom filter sized for n items keeps working when you insert more, but its false-positive rate climbs fast: 1.5× capacity turns 1% into ~5.8%, 2× into ~15.7%, 10× into ~99.5%. At that point nearly every lookup says "maybe" and the filter is useless.
Think of it like this
A car park with a "FULL" sign that never lights up. Past capacity, cars keep squeezing in, the lot gets jammed, and eventually every space looks occupied even when you're looking for a specific empty one.
Key ideas
- 01
Why: n appears in the exponent. More items → more bits set → higher fill → p = fill^k rises steeply. The filter never errors or refuses inserts; it just silently degrades.
- 02
Numbers for a filter built for 10M items at 1% (m = 95.85M bits, k = 7): 1× → 1.0%, 1.2× → 2.3%, 1.5× → 5.8%, 2× → 15.7%, 3× → 43.6%, 5× → 83%, 10× → 99.5%.
- 03
Detect it: track inserted count (or estimate it from the fill ratio: n ≈ −(m/k) ln(1 − fill)), compute estimated p = fill^k, and alert when fill passes ~55% (at design capacity with optimal k it's ~50%).
- 04
Remedies: rebuild a larger filter from the source of truth (Phase 7), use a scalable Bloom filter that adds sub-filters as it grows (Phase 4), or rotate time-windowed filters so each stays within capacity.
Code & diagrams
Filter designed for 10M items at 1% (m = 95.85M bits = 12 MB, k = 7)
inserted fill false-positive rate
10M 0.518 1.00%
12M 0.584 2.31%
15M 0.666 5.79%
20M 0.768 15.7%
30M 0.888 43.6%
50M 0.974 83.2%
100M 0.999 99.5% <- almost every lookup says "maybe"Interview problem
The problem
Built for 10M, received 100M; observed FPR 0.5% → 5% → 25%
A filter was designed for 10 million items and has received 100 million. What happens? Separately, a production filter's observed false-positive rate climbed from 0.5% to 5% to 25% over months. What happened and how do you remediate?
When it breaks
Filter sized once at launch and never revisited
What you see
Months later the dataset has tripled; FPR is ~40%, database load is back near the unprotected level, and nobody connects it to the filter.
Fix & prevent
Monitor fill ratio and estimated FPR, alert early, and automate rebuilds or use scalable filters.
Explain it without notes
How can you estimate how many items are in a Bloom filter from its bits alone?
Practice
A filter has m = 1B bits, k = 7, and 620M bits set. Estimate n and the current FPR.
Trade-offs
- ↔
Over-sizing wastes memory; under-sizing silently destroys the filter's value. Size for projected growth and monitor.
Done when you can
I can predict FPR past capacity, detect saturation from the fill ratio, and plan remediation.