Bloom Filter

Designing the class: config, hashing, bits, locks, bytes

Design a Bloom filter as a reusable class: sized from an item count and a false positive rate, with pluggable hashing, a compact bit array, thread-safe adds, merging and a byte format.

Overview

A Bloom filter answers 'have I seen this item?' with a certain no or a probable yes, using a bit array instead of storing the items. Adding an item sets k bits chosen by hashing it; a lookup checks those same k bits. If any is 0, the item was never added. If all are 1, it probably was, but other items may have set those bits between them. So there are false positives, and never false negatives, as long as no bit is ever lost.

As a low level design question, the math is the easy part; the interviewer wants a class other teams can use safely. That means five decisions: how callers size it (they know an item count and an error rate, not bits), where the hash functions come from, how the bits are stored, what happens when two threads add at once, and how a filter is saved, loaded and merged. Each decision is one small class.

Scoping the problem

Ask these questions before you write code; each answer changes the design.

How many items, and what false positive rate is acceptable? — Sets the size m and the hash count k — For example 1,000 items at 1%
Must items be removable? — A plain bit filter cannot forget — No; removal is a follow-up (counting filter)
What if more items arrive than planned? — The error rate climbs past the target — Report it; a scalable filter is a follow-up
Many threads, or one? — A lost bit update is a false negative — Many threads add and check
Saved to disk or sent between services? — Needs a byte format that records m, k and the hash scheme — Yes
Built in parts and combined? — Union needs the same m, k and hashing — Yes, shards are merged

Sizing from what the caller knows

Callers know how many items they expect (n) and what false positive rate (p) they can live with. BloomConfig.for_items(n, p) turns those into bits and hashes with the standard formulas: m = -n ln p / (ln 2)², rounded up, and k = (m / n) ln 2, rounded to the nearest whole number.

1,000 — 1% — 9,586 — about 1.2 KB — 7
1,000,000 — 1% — 9,585,059 — about 1.2 MB — 7
1,000,000 — 0.1% — 14,377,588 — about 1.8 MB — 10

The config is a frozen value, so two filters with equal configs can be compared and merged. Invalid input (n of 0, p outside 0 to 1) is refused at construction, not discovered later.

Where the k positions come from

Computing k unrelated hash functions is slow and error-prone. Kirsch and Mitzenmacher showed that two hash values are enough: position i is (h1 + i × h2) mod m, with the same false positive rate asymptotically. The code takes h1 and h2 from one SHA-256 digest and keeps the step h2 between 1 and m - 1, so it is never 0 mod m and the k positions cannot all collapse to one. SHA-256 is chosen because it is in the standard library and gives the same positions on every machine and every run, which a saved filter needs; Python's built-in hash() of a string changes between processes.

The hashing sits behind a small strategy object with a name. The name goes into the saved bytes, so a filter written with one scheme is never read with another.

Storing the bits

A Python list of booleans spends a full object reference per bit. A bytearray stores 8 bits per byte: bit i lives in byte i >> 3 at offset i & 7. For 9,586 bits that is 1,199 bytes. The same bytes are the body of the saved format.

magic 'BLM1' — 4 bytes — refuse files that are not filters, and version the format
hash scheme name — 4 bytes — refuse a filter built with other hashing
m, k — 8 and 4 bytes — rebuild the config exactly
items added — 4 bytes — keep expected_fp_rate meaningful after a reload
bit array — (m + 7) / 8 bytes — the filter itself; a short body is refused

Two error estimates

The filter reports its error rate two ways. expected_fp_rate uses the item count: (1 - e^(-kn/m))^k. observed_fp_rate uses the fraction of bits actually set: (ones / m)^k. They agree when the count is honest. They drift apart when the same item is added many times (count too high) or after a union of filters that shared items. The demo adds 1,000 items to the 1% filter and measures 20,000 absent items: about 1% come back as false positives, as planned.

What you will be able to do

Size a filter from an item count and a target rate, and explain the table.
Explain double hashing and why the hash scheme is stable and named.
Store bits in a bytearray and design a small, versioned byte format.
Explain why a lost update under concurrency is a false negative, and lock correctly, including for union.
Answer the follow-ups: removal, overfilling, and merging shards.

Functional requirements

BloomConfig.for_items(n, p) computes bits m and hashes k; it refuses n <= 0 or p outside (0, 1)
add(item) records an item; might_contain(item) returns False only if the item was never added
expected_fp_rate() from the item count and observed_fp_rate() from the bits set
union(other) merges two filters with the same m, k and hash scheme, and refuses otherwise
to_bytes() and from_bytes() save and load a filter with a versioned header; a wrong header or short body is refused
Removal is not supported; say so (see the counting filter follow-up)

Non-functional requirements

add and might_contain are O(k); memory is m bits plus a small header, whatever the items are
Positions are the same on every machine and every run, so saved filters stay valid
Safe with many threads: bit updates happen under one lock, so no bit is lost
The hash scheme is a strategy object; replacing it does not change callers

Interview questions

Why does add need a lock? Setting a bit sounds atomic.
How would you support removing an item?
What happens when more items arrive than the filter was sized for?
Two services each built a filter. How do you combine them?
Why not use Python's built-in hash() for the positions?