Topic 4.4
Blocked and Partitioned Bloom Filters: Cache-Friendly Layouts
In one line
A standard lookup touches k random cache lines. A blocked Bloom filter hashes each item to one 512-bit block (a CPU cache line) and sets all k bits inside it, so a lookup costs one cache miss, at a slightly higher false-positive rate. Partitioned filters give each hash its own slice of the array.
Think of it like this
Fetching files from one drawer versus seven drawers scattered around a building. Keeping everything for one person in one drawer is much faster, even if the drawer gets a little crowded.
Key ideas
- 01
The cost of randomness: with k = 7 and a filter larger than CPU cache, a lookup can incur up to 7 cache misses (~100 ns each). Hashing dominates less than memory access at scale.
- 02
Blocked Bloom (Putze, Sanders, Singler, 2007): first hash picks a block of 512 bits (64 bytes); the other probes are within that block. One memory access per lookup; SIMD can test all bits at once.
- 03
Accuracy cost: items are unevenly spread across blocks (some blocks fuller than others), so FPR is somewhat higher for the same bits per item; add ~10–20% more bits to compensate at typical error rates.
- 04
Partitioned Bloom: split m into k slices, hash i sets a bit only in slice i. Same asymptotic FPR, simpler analysis, easier parallelism; locality isn't better by itself.
- 05
Production use: RocksDB's newer full filters are cache-local; Parquet uses split-block Bloom filters (256-bit blocks, 8 bits set per item), designed for SIMD.
Code & diagrams
Explain it without notes
Why can a blocked Bloom filter be faster even though it has a higher false-positive rate?
Practice
Benchmark lookups on a 1 GB standard vs blocked Bloom filter with random queries and report ns/lookup.
Trade-offs
- ↔
Blocked filters trade a little accuracy (or memory) for large lookup speedups on big filters.
Done when you can
I can explain blocked and partitioned layouts and when cache locality matters.