Command Palette

Search for a command to run...

Hectal
Phase 7Advanced8 of 12 in Bloom Filters

Consistency and Filter Lifecycle

Stale filters and the dangerous direction, keeping inserts in sync with the database, handling deletes, zero-downtime rebuilds with versioned filters, and building huge filters in parallel and merging them with OR.

A Bloom filter's guarantee ("absent means absent") holds only if every item in the source of truth is in the filter. In production, inserts fail, deletes happen, filters saturate and need rebuilding. This phase covers the lifecycle that keeps the guarantee true.

0/4 · 0%
4 topics ~34 min 7 code blocks & diagrams
Start with the first topic
1
7.1

Stale Filters and Insert Consistency

Staleness in one direction is harmless (the filter has extra items → false positives); in the other it breaks correctness (the database has an item the filter lacks → false negatives, valid requests rejected). Order updates so an item is in the filter before it's exposed, make updates reliable (outbox/CDC, retries), and give recent items a fallback path.

9 min 1 diagram 1 code practice

2
7.2

Handling Deletes

Deleting from the database leaves the item's bits in a standard Bloom filter, producing false positives that the database check absorbs. For frequent deletes, choose between tolerating them with periodic rebuilds, counting Bloom filters, cuckoo filters, or time-windowed filters that expire together.

7 min 1 code practice

3
7.3

Zero-Downtime Rebuilds and Versioned Filters

Rebuild a saturated or drifting filter without downtime: build v2 from a database scan, replay changes that happened during the build, validate it, switch readers atomically via a pointer or config, keep v1 until the switch completes, then retire it. Dual-write both versions during the transition.

9 min 1 diagram 1 code practice

4
7.4

Building Huge Filters in Parallel and Merging with OR

Bloom filters with identical m, k, hash function and encoding can be merged with bitwise OR: the result equals a filter built from the union of their items. Build a 10-billion-item filter by scanning shards in parallel into partial filters and OR-ing them; the merged filter's FPR is that of the full union, so size it for the total n.

9 min 1 diagram 1 code practice