Building Huge Filters in Parallel and Merging with OR

In one line

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.

0/4 · 0%

Think of it like this

Several volunteers each ticking boxes on identical copies of a grid for their own neighbourhood. Laying the copies on top of each other and marking every box ticked on any copy gives the same result as one person doing the whole city.

Key ideas

01
Why OR works: a bit is set in the union filter if any item from any part sets it, which is exactly the OR of the partial filters' bits.
02
Compatibility requirement: same m, same k, same hash function and seed, same item encoding. Anything else produces garbage (and false negatives).
03
Sizing: each partial filter must be the full size (m for the total n), not n/workers, because the merged filter holds everything. Partial filters are therefore mostly empty until merged.
04
Scale limit: for 10B items at 0.1%, every full-size partial filter is ~18 GB, so 100 workers would each need 18 GB and the merge would move 1.8 TB. At that size, partition the key space instead: hash each key to one of P independent sub-filters (each sized for n/P), or keep per-shard filters and route lookups to them (Topic 8.2).
05
Intersection (AND) of filters approximates the intersection of sets but with a higher error than a filter built from the intersection; rarely used.
06
Merged FPR: equals that of a single filter with all n items (the same bits), so a merge can push you past capacity if parts overlap less than expected; check the fill ratio after merging.

Code & diagrams

merge.mermaiddiagram

Rendering diagram…

MergeFilters.javajava

// Guava: filters must be created with the same expectedInsertions, fpp and funnel
BloomFilter<CharSequence> global = BloomFilter.create(funnel, 3_000_000_000L, 0.001);
for (Path part : partialFilterFiles) {
    try (var in = Files.newInputStream(part)) {
        BloomFilter<CharSequence> p = BloomFilter.readFrom(in, funnel);
        if (!global.isCompatible(p)) throw new IllegalStateException("incompatible " + part);
        global.putAll(p);                         // bitwise OR
    }
}
System.out.printf("merged, expected fpp now %.5f%n", global.expectedFpp());

Interview problem

The problem

Workers built filters A, B and C: combine them

Three workers built filters A, B and C over different shards of the dataset. How do you combine them, what are the requirements, and what are the false-positive implications? Then: how do you rebuild a filter for 10 billion records that can't be built in one process?

When it breaks

Merging filters built with different expected sizes

What you see

m or k differs; OR-ing the arrays is meaningless and lookups miss inserted items (false negatives) or match everything.

Fix & prevent

Check compatibility (m, k, hash, seed, encoding) before merging; reject mismatches.

Explain it without notes

Why must partial filters be sized for the total n rather than each worker's share?

Practice

Design a Spark job that builds a hash-partitioned filter for 10B IDs into 64 sub-filters.

Trade-offs

↔
OR-merging is simple but needs full-size partials; hash-partitioned sub-filters scale builds horizontally at the cost of routing logic.

Done when you can

I can merge compatible filters and build very large filters in parallel.

Command Palette