Code a Bloom filter

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

This is a library design question, not an algorithm question. The Bloom Filters lesson covers the math. Here the job is an API that other teams can use for years without reading that math: create from "expected items and target error rate", add, query, save, load, merge, and grow.
Make hashing a pluggable strategy with a stable identity. A filter is only meaningful with the exact hash function that built it, so the hasher's ID goes into the serialised header and loading with a different one fails loudly.
Version the binary format from day one: magic bytes, version, m, k, count, hasher ID, then the bit array in a defined byte and bit order. Filters outlive the processes that build them, and they cross languages.
Offer a scalable filter for callers who cannot predict n. It stacks plain filters, each larger and with a tighter error rate than the last, so the overall false-positive rate stays below the target however many keys arrive.
Bits only ever go from 0 to 1, which makes concurrent adds cheap: an atomic OR per word, no lock. Growing a scalable filter is the one step that needs real coordination.

Requirements

Functional:

Create a filter from expected insertions n and false-positive rate p, or from explicit m bits and k probes.
add(key) and mightContain(key) for byte strings, with an adapter (a "funnel") for application types.
Plug in the hash function; ship a fast, stable default.
Serialise to bytes and load from bytes, rejecting corrupt, truncated or incompatible data.
Merge two compatible filters by OR-ing their bits.
A scalable variant that keeps its error bound as it grows past the initial capacity.
Safe for concurrent use, or clearly documented when it is not.

Non-functional:

No false negatives, ever, including across save and load.
About 1.44 × log2(1/p) bits per key, so 1% costs under 10 bits per key.
Add and query in well under a microsecond for in-memory filters.
A byte format that a Go service can write and a Python job can read.

Out of scope: deletion (counting filters, covered in the sd lesson), a networked filter service, and exact set semantics.

Entities and relationships

Filter: the interface callers depend on: add, mightContain, count, serialise. Plain, scalable and synchronised filters all implement it.
BloomFilter: the core. It holds m, k, a bit array and a hasher, and turns each key into k probe positions.
BitArray: 64-bit words, swappable for an atomic or memory-mapped array without touching probe logic.
Hasher: the strategy that turns a key into two 32-bit hashes (h1, h2). Probes are derived as h1 + i × h2. It has an id that is persisted.
Funnel: an adapter from an application object to canonical bytes, because "hash this object" is ambiguous until field order and encoding are fixed.
FilterParams: a value object (capacity, m, k) computed from (n, p), so sizing logic lives in one tested place.
ScalableBloomFilter: an ordered list of BloomFilters with geometrically growing capacity and shrinking error rate.
Codec: reads and writes the versioned binary format.

Class diagram

classDiagram
    class Filter {
        <<interface>>
        +add(key) bool
        +mightContain(key) bool
        +count() int
        +toBytes() bytes
    }
    class BloomFilter {
        -int m
        -int k
        -BitArray bits
        -Hasher hasher
        +merge(other)
        +fromBytes(data, hasher)$ BloomFilter
    }
    class ScalableBloomFilter {
        -List~BloomFilter~ filters
        -double fpRate
        -int initialCapacity
        +filterParams() List
    }
    class SynchronizedFilter {
        -Filter inner
        -RWLock lock
    }
    class Hasher {
        <<interface>>
        +id() string
        +hash(bytes) pair
    }
    class Fnv1aHasher
    class Murmur3Hasher
    class BitArray {
        -long[] words
        +set(i)
        +get(i) bool
    }
    class FilterParams {
        +int capacity
        +int m
        +int k
    }
    Filter <|.. BloomFilter
    Filter <|.. ScalableBloomFilter
    Filter <|.. SynchronizedFilter
    SynchronizedFilter o-- Filter
    ScalableBloomFilter *-- BloomFilter
    BloomFilter *-- BitArray
    BloomFilter --> Hasher
    Hasher <|.. Fnv1aHasher
    Hasher <|.. Murmur3Hasher
    ScalableBloomFilter ..> FilterParams

Key flows

The interesting flow is an add to a scalable filter, because it may allocate a new layer.

sequenceDiagram
    participant C as Caller
    participant S as ScalableBloomFilter
    participant L as Last layer
    participant H as Hasher
    C->>S: add(key)
    S->>S: lock
    S->>S: mightContain(key) on every layer
    alt already present (or false positive)
        S-->>C: false
    else new key
        S->>S: last layer at capacity?
        opt full
            S->>S: append layer with 2x capacity, half the error rate
        end
        S->>L: add(key)
        L->>H: hash(key)
        H-->>L: h1, h2
        L->>L: set bits (h1 + i*h2) mod m
        S-->>C: true
    end

Checking before inserting stops duplicates from consuming the newest layer's capacity, so count approximates distinct keys, and it gives callers a free "was this new?" answer, which is what deduplication pipelines want. The price is that a false positive makes a genuinely new key look like a duplicate. For a crawler that is the documented trade-off; where skipping a new key is costly, a Bloom filter is the wrong tool.

Design patterns used and why

Strategy for hashing. FNV-1a is simple and portable, Murmur3 and xxHash are faster on long keys, and a filter facing attacker-chosen keys needs a keyed hash such as SipHash so nobody can craft colliding keys. The filter code does not change.
Adapter (Funnel) for keys. Guava's Funnel interface writes an object's fields into a byte sink. Without it, every caller invents a different encoding of the same object, and two services building "the same" filter disagree.
Composite for the scalable filter. A scalable filter is a filter made of filters and implements the same interface, so callers do not know or care whether their filter grows.
Decorator for thread safety. SynchronizedFilter wraps any Filter with a read-write lock. Single-threaded users pay nothing; concurrent users opt in. A lock-free bit array is the faster alternative for the plain filter.
Factory methods for sizing. BloomFilter.create(expected, fpp) hides the formulas, as Guava does; the explicit (m, k) constructor remains for loading and experts.
Value objects. FilterParams and the serialised header describe a filter immutably, so compatibility checks for merge or load are an equality test.

Concurrency and edge cases

Add is monotonic: it only sets bits. Two threads can OR bits into the same word, and as long as each OR is atomic neither loses the other's bit. Guava's LockFreeBitArray does exactly this with a compare-and-swap loop over an AtomicLongArray, and Go 1.23 added atomic.OrUint64. A reader racing with a writer may see some of a key's bits and not others, so mightContain can return false for a key whose add has not returned yet. That is fine: the guarantee is "no false negatives for completed adds". The count is a separate atomic and is approximate under races.

The scalable filter is harder. "Check every layer, maybe append a layer, add to the last" must be atomic, or two threads both append a layer, or both add the same key and count it twice. The simple answer is a read-write lock. A faster design publishes an immutable list of layers through an atomic pointer and locks only to grow: the classic contention fix of a lock-free common path and a serialised rare structural change.

Edge cases to cover:

Loading bytes written with a different hasher, different version, or truncated in transit. Fail with a specific error rather than returning a filter that silently gives wrong answers.
Merging filters with different m, k or hasher. OR-ing them is meaningless; reject it.
Built-in hashes. Python's string hash() is randomised per process, so a persisted filter built with it is garbage after a restart.
Overfilling a plain filter. The rate climbs steeply; expose count and an expectedFpp() estimate so callers can alarm on it.
Empty keys, long keys and non-ASCII text, which must be encoded to bytes one defined way (UTF-8).

Down the stack

Layer 1The contract

After add(x) returns, mightContain(x) is true forever, in this process and after any number of save and load cycles with the same hasher. For a key never added, a plain filter returns true with probability about (1 - e^(-kn/m))^k. A scalable filter with initial error p0 and tightening ratio r keeps the compound rate below p0 / (1 - r), so choosing p0 = P(1 - r) keeps it under the target P. fromBytes(toBytes(f)) produces a filter with identical answers, or an error.

Layer 2The mechanism

Each layer derives its probes from two hashes, (h1 + i × h2) mod m, the Kirsch and Mitzenmacher construction, so one hash call serves all k probes. The derived probes are only as good as their spread: if h2 mod m shares a factor with m, the k probes cycle through a few positions and the false-positive rate rises. Rounding each layer's m up to a power of two and forcing h2 odd makes them coprime, at a cost of up to 2x memory; the alternatives are a prime m or enhanced double hashing, which adds a cubic term to each probe. The Practice measures this: with arbitrary m the same keys gave about twice the target rate.

The scalable design follows Almeida, Baquero, Preguiça and Hutchison (2007). Layer i has capacity c0 × s^i (growth s, usually 2 or 4) and error p0 × r^i (tightening r, 0.5 to 0.9), with k_i = ceil(log2(1 / p_i)) probes and about c_i × k_i / ln 2 bits, half set at capacity. Layers grow geometrically, so growing from 1,000 to 1,000,000 keys adds only about 10 layers for queries to check. RedisBloom implements this behind BF.RESERVE key error_rate capacity EXPANSION 2.

The serialised form is a header plus the raw bits. Guava writes a strategy ordinal byte, the number of hash functions, the word count and then the 64-bit words. The format in Practice uses a magic string, big-endian m, k and count, a length-prefixed hasher ID, and bit j at bit j mod 8 of byte j / 8. Whatever you pick, write it down: endianness and bit order are the details that make a filter written by a Go service unreadable by a Python job.

Layer 3The machine

A filter for 10 million keys at 1% is about 12 MB: larger than most L2 caches, so each probe that misses costs a DRAM access of roughly 80 to 100 ns, and a positive query pays all k of them. Blocked layouts that keep a key's probes in one 64-byte line cut that to one miss. An uncontended atomic OR on x86 is a lock or instruction costing on the order of 10 to 20 ns; under heavy contention on the same cache line it becomes a cache-line ping-pong between cores, which is why hot filters shard by key hash across several bit arrays.

Serialised, those 12 MB can be loaded with mmap and shared between processes through the page cache, but only if the file layout equals the in-memory layout: another reason to fix byte order. Hashing a 32-byte key with FNV-1a is one multiply and XOR per byte, around 30 to 50 ns; Murmur3 and xxHash process 4 or 8 bytes per step and are several times faster on long keys.

Why it's built this way

Filters are useful only when they are shared and long-lived, so they must be serialised, and a serialised filter is useless without the exact hasher, so the hasher's identity is part of the format.
Callers rarely know n in advance, so the library grows by stacking layers instead of rehashing, which a Bloom filter cannot do because it no longer has the keys.
Stacking layers adds up their error rates, so each new layer must be stricter, and a geometric series keeps the sum bounded.
Bits only go up, so plain adds can be lock-free atomic ORs, while the rare structural change of adding a layer takes a lock.
Different callers need different speed, portability and attack resistance from hashing, so hashing is a strategy rather than a constant.

Extensibility

Deletion. Swap the bit array for counters (the sd lesson's Practice) or move to a cuckoo filter behind the same Filter interface.
Faster lookups. A blocked bit array that confines a key's probes to one cache line is a new BitArray plus a probe strategy; the API does not change.
New hashers. Register Murmur3Hasher under a new ID. Old filters still load with the old hasher, and the mismatch error names the one needed.
Format evolution. Bump the version, keep a reader for every version shipped, and write only the newest.
Distributed use. Ship filters as files to readers (an LSM tree's SSTable filters), or put a scalable filter in Redis with BF.ADD when many writers share one set.

Leadership lens

Decide the format and hasher before the first filter is persisted. Changing either later means rebuilding every stored filter, which for a crawler or a storage engine can mean days of reprocessing.
In review, look for hash(), hashCode() or Math.random() near a filter. These produce filters that work in tests and fail after a restart or in another service.
Ask what a false positive costs the business, and put that number next to p. A 1% rate is cheap for "skip a disk read" and unacceptable for "skip charging a new customer".
Prefer a tested library (Guava, bits-and-blooms, RedisBloom). Build your own only for a cross-language format or unusual growth policy, and then own the compatibility tests.

Check yourself

Why must the hasher's ID be stored in the serialised filter?
Show answer
Probe positions depend entirely on the hash. Loading the bits with a different hasher probes different positions, so keys that were added may test absent, which breaks the no-false-negative guarantee without any visible error.
A scalable filter targets 1% overall with tightening ratio 0.5. What error rate should the first layer use, and why?
Show answer
0.5%. Layer rates form the series p0 + p0/2 + p0/4 + ..., which sums to 2 × p0, so p0 = 1% × (1 - 0.5) keeps the total under 1%.
Why can concurrent adds to a plain filter avoid a lock, while adds to a scalable filter usually cannot?
Show answer
Plain adds only OR bits into words, which atomic operations make safe and order-independent. The scalable add is a check, a possible structural change (a new layer) and an insert, which must happen as one step or layers and counts go wrong.
Why not just rehash into a bigger filter when a plain filter fills up?
Show answer
A Bloom filter does not store its keys, so there is nothing to rehash. You either rebuild from the source data or grow by adding layers.

Watch

Bloom Filters, Algorithms You Should Know #2 (ByteByteGo): the structure and where production systems use it.
What Are Bloom Filters? (Spanning Tree): an animated explanation of why false positives happen and how sizing controls them.

Free resources

Scalable Bloom Filters (Almeida, Baquero, Preguiça and Hutchison): the paper behind stacked layers, growth factors and tightening ratios.
Guava BloomFilter source: a mature API with funnels, create(expected, fpp), merge, a serialised form and a lock-free bit array.
bits-and-blooms/bloom (Go): a widely used Go library with estimation helpers and binary marshalling.
BF.RESERVE (Redis docs): a production scalable filter with error rate, capacity and expansion settings.
Less Hashing, Same Performance (Kirsch and Mitzenmacher): why two hashes are enough to derive every probe.
RocksDB Bloom Filter (RocksDB wiki): cache-local filter layouts and the format choices of a storage engine.

Open in the interactive app: practice, quiz, mock interview →