Design a Bloom Filter Service
How to design Bloom filters for interviews: false positives, bit array sizing, k hash functions, counting/scalable variants, Redis bitmaps, and classic use cases.
A Bloom filter answers “have I maybe seen this key?” in tiny space. False positives happen; false negatives do not (for the classic non-deleting filter). Interviews love it because it shows up in caches, web crawlers, databases, and CDN origin shields.
Clarify with the framework: expected n inserts, target false positive rate p, whether deletes matter, and single-node vs distributed service.
Functional requirements
- add(key) set k bits.
- mightContain(key) → true/false (true may be wrong; false is certain absent).
- Optional: merge filters, create snapshot, expire / rotate generations.
- Optional: counting Bloom filter or Cuckoo filter if deletes are required.
Non-functional requirements
- O(k) bit ops per add/lookup; k usually small (5-10).
- Memory linear in n for a fixed p - size carefully.
- Thread-safe add under concurrency or shard the bitset.
Never treat true as proof
Bloom filters gate expensive checks (disk, remote API). On true, you still verify. On false, skip the expensive path. That sentence alone shows you understand the structure.
Sizing math (say it once)
- Bits m ≈ -n ln(p) / (ln 2)^2.
- Hashes k ≈ (m/n) ln 2.
- Example: n=1e9, p=1% → on the order of a few GB - call it “gigabytes, not terabytes.”
You will not be graded on deriving the formula from scratch. Quoting m and k and naming the trade-off (more bits → fewer false positives, more RAM) is enough.
Implementation sketch
- Allocate a bit array of m bits (or Redis SETBIT / BITFIELD).
- Derive k positions from 1-2 hash functions via double hashing to save CPU.
- add: set those bits. mightContain: return true only if all k bits are set.
- For multi-tenant service: one filter per (namespace, generation).
| Variant | When to use |
|---|---|
| Classic Bloom | Insert-only membership; cheapest |
| Counting Bloom | Need deletes; more memory |
| Scalable Bloom | n unknown; chain filters as load grows |
| Cuckoo filter | Deletes + better for some workloads |
Distributed design
A Bloom service can wrap sharded bitsets behind an API, or embed filters in each app process rebuilt from a daily key dump. Cross-host: broadcast adds over Kafka or rebuild from object storage snapshots. Merges work when filters share m and hash seeds - OR the bit arrays together.
Classic interview use cases
- Cache: miss filter avoids stampedes into a DB for never-seen keys.
- Crawler: URL seen filter before enqueueing.
- DB: SSTable / LSM bloom short-circuits disk reads (LSM design adjacent to KV stores).
- Username signup: cheap “probably taken” before authoritative lookup.
Worked example
- API cache sits in front of user service; Bloom holds 200M active user ids.
- Request for id 42: filter says false → return 404 without hitting DB.
- Request for id 7: filter says true → query DB; found; return profile.
- False positive on id 99 → DB miss once; still correct externally.
Interview summary
One-way errors, m/k sizing, bit array + k hashes, and a real use case (cache or crawler). Mention deletes need a different variant. That closes the Bloom filter round.