What is a Bloom Filter? When is it used? (Cache penetration, Spell check)
Bloom Filter
A Bloom Filter is a probabilistic, space-efficient data structure used to test whether an element is possibly present in a set. It can produce false positives, meaning it may say an element exists when it does not, but a properly configured standard Bloom Filter does not produce false negatives for inserted items.
- 1
Very memory efficient compared with storing all keys directly.
- 2
False positive: possible.
- 3
False negative: not expected for correctly inserted entries in a standard Bloom Filter.
- 4
Cannot normally remove individual entries safely without a counting variant.
- 5
Useful as a cache-penetration guard before querying an expensive database.
- 6
Useful for spell checking, URL filtering, deduplication, and membership prechecks.
- 7
The false-positive rate depends on bit-array size, number of hash functions, and number of inserted elements.
Scenario Questions
0-2 years experience
- 1We need to quickly reject duplicate user IDs before processing them. How would you use a Bloom filter for this task?
- 2If we accidentally add more elements than the filter was sized for, what happens to the false‑positive rate?
- 3What would be the impact on our cache‑miss handling if the Bloom filter returns a false positive?
2-5 years experience
- 1Our spell‑check service uses a Bloom filter to filter out non‑dictionary words before hitting the DB, but latency increased after a data load. Walk me through how you'd debug the issue.
- 2Explain the trade‑offs between false‑positive rate and memory when sizing a Bloom filter to protect a high‑traffic API from cache penetration.
- 3We tried to delete entries from the Bloom filter after a TTL expires and started seeing unexpected false positives. Why does this happen and how would you handle it?
5-8 years experience
- 1Design a distributed caching layer that guards against cache penetration using Bloom filters. Discuss sharding, consistency, and scaling to billions of keys.
- 2After a rolling upgrade, our system saw a spike in Bloom filter false positives. What could cause this and how would you mitigate it?
- 3Compare using a Bloom filter versus a Redis set for deduplication in a streaming pipeline, focusing on latency, memory usage, and correctness.
8+ years experience
- 1We have a legacy monolith with a custom hash table for request deduplication and want to migrate to Bloom‑filter‑based guards across multiple microservices. Outline the migration plan, including backward compatibility, monitoring, and failure modes.
- 2At a company‑wide level, how would you decide whether to standardize Bloom filters for all cache‑penetration scenarios versus per‑service implementations? Discuss governance, observability, and technical debt.
- 3A global CDN wants to use Bloom filters to block malicious URLs before edge caching. What architectural challenges arise (e.g., synchronization, false‑positive impact on user experience) and how would you address them?
Follow-up Questions
- How would you choose the number of hash functions for a given false‑positive target?
- What are the implications of a false positive in a cache‑penetration guard?
- Can you discuss any strategies to handle deletions or expirations with Bloom filters?