Command Palette

Search for a command to run...

Hectal
Phase 3Intermediate4 of 12 in Bloom Filters

Building a Production Filter

Implement a Bloom filter in Java with sizing, double hashing and tests; make it thread-safe; serialize and version it; and know when to use a battle-tested library instead.

Writing a Bloom filter takes fifty lines. Writing one you can trust in production takes more: configurable sizing, correct index arithmetic, concurrency, persistence with metadata, versioning and tests that prove the false-positive rate.

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

A Bloom Filter in Java, with Tests

Implement BloomFilter<T> sized from expected insertions and target FPR, backed by a long array, using MurmurHash3 double hashing, with add and mightContain. Test existing and missing items, duplicates, large inputs, saturation and the measured FPR.

10 min 2 code practice

2
3.2

Thread Safety for Concurrent Adds and Lookups

Concurrent add calls race when two threads set different bits in the same 64-bit word with plain read-modify-write. Use atomic compare-and-set on words (lock-free), an immutable filter swapped by reference, or striped/partitioned filters. Reads never need locks if writes are atomic.

8 min 1 code practice

3
3.3

Persistence, Serialization, and Versioning

An in-memory filter disappears on restart. Persist it with its metadata (m, k, hash algorithm and seed, encoding, format version, expected capacity, target FPR, build time), store it in Redis or object storage, and version it (filter:v1, filter:v2) so incompatible filters are never mixed.

9 min 2 code practice

4
3.4

Libraries: Guava, Redis, RocksDB, and Others

Use proven implementations: Guava's BloomFilter (Java, thread-safe, serializable, mergeable), RedisBloom's BF.* commands (shared, scalable), storage-engine filters in RocksDB, Cassandra and HBase, and libraries like bits-and-blooms (Go) or pybloom-live (Python). Know their parameters and limits.

7 min 2 code practice