Architectural Breakdown & AnalysisFAANG Aligned
A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set.
Key Properties
- No False Negatives: If the Bloom Filter returns
False, the item definitely does not exist in the database. - Possible False Positives: If it returns
True, the item probably exists in the database.
How It Works
- Consists of a bit array of $m$ bits initialized to 0 and $k$ independent hash functions.
- When adding an item, hash it $k$ times and set the bit positions to 1.
- To query an item, check if all $k$ bit positions are 1. If any bit is 0, skip the database lookup completely.
NOTE — Real-World Usage
Google Chrome uses Bloom Filters to check malicious URLs locally. Cassandra & RocksDB use Bloom Filters to skip reading SSTables for non-existent keys.
Key Architectural Comparison
| Bloom Filter Parameter | Mathematical Variable | Optimal Tuning Formula |
|---|---|---|
| Bit Array Size | $m$ | $m = -\frac{n \ln p}{(\ln 2)^2}$ |
| Number of Hash Functions | $k$ | $k = \frac{m}{n} \ln 2$ |
| False Positive Rate | $p$ | Typically configured at $1\%$ ($p=0.01$) requiring $\approx 9.6\text{ bits/item}$. |