Scalable Bloom Filters: Growing Without Knowing n

In one line

A scalable Bloom filter chains sub-filters: when the current one reaches capacity, a new, larger one is added with a tighter error rate. Inserts go to the newest; lookups check all. With geometric growth (s) and error tightening (r), total FPR stays below P0/(1 − r).

0/6 · 0%

Think of it like this

A notebook that fills up. Instead of cramming more writing onto full pages, you start a new, bigger notebook and write more carefully in it. To check if something was noted, you look through all the notebooks.

Key ideas

01
Structure (Almeida et al., 2007): filter i has capacity n0 × s^i (s = growth factor, usually 2 or 4) and error rate P0 × r^i (r = tightening ratio, usually 0.8–0.9).
02
Total error: the union of sub-filter false positives is at most P0 × (1 + r + r² + ...) = P0 / (1 − r). For a 1% overall target with r = 0.9, start at P0 = 0.1%.
03
Operations: insert into the newest filter (after checking it's not already present, if you want counts); lookup checks every sub-filter, so lookups slow down slightly as filters are added, logarithmic in growth.
04
Memory: tighter error rates for later, larger filters cost more bits per item than a single right-sized filter; the price of not knowing n. If you can estimate n, a right-sized filter is cheaper.
05
RedisBloom's default behaviour is scalable (EXPANSION), and NONSCALING turns it off, returning an error when full.

Code & diagrams

scalable.mermaiddiagram

Rendering diagram…

ScalableBloomFilter.javajava

public final class ScalableBloomFilter<T> {
    private final List<BloomFilter<T>> filters = new CopyOnWriteArrayList<>();
    private final Function<T, byte[]> enc;
    private final double r;           // tightening ratio, e.g. 0.9
    private final int s;              // growth factor, e.g. 2
    private long capacity; private double error; private long inCurrent;

    public ScalableBloomFilter(long initialCapacity, double targetFpp, double r, int s, Function<T, byte[]> enc) {
        this.enc = enc; this.r = r; this.s = s;
        this.capacity = initialCapacity; this.error = targetFpp * (1 - r);   // P0 so that total <= target
        filters.add(new BloomFilter<>(capacity, error, enc));
    }

    public synchronized void add(T item) {
        if (mightContain(item)) return;
        if (inCurrent >= capacity) {                     // current full: grow
            capacity *= s; error *= r; inCurrent = 0;
            filters.add(new BloomFilter<>(capacity, error, enc));
        }
        filters.get(filters.size() - 1).add(item);
        inCurrent++;
    }

    public boolean mightContain(T item) {
        for (BloomFilter<T> f : filters) if (f.mightContain(item)) return true;
        return false;
    }
}

Interview problem

The problem

Filter for an unknown number of URLs (10M to 1B)

You need a visited-URL filter but don't know whether you'll see 10 million, 100 million or 1 billion URLs. Design a scalable Bloom filter with a 1% overall false-positive target and estimate memory at each scale.

Explain it without notes

Why do later sub-filters need tighter error rates?

Practice

Compute the total FPR bound for P0 = 0.2%, r = 0.8, and the number of sub-filters needed for 500M items with n0 = 10M, s = 2.

Trade-offs

↔
Scalable filters handle unknown growth at the cost of extra memory and slower lookups than a right-sized filter.

Done when you can

I can design a scalable Bloom filter and bound its total error rate.

Command Palette