study › DDIA › Chapter 4 · Storage and Retrieval

Ten Bits per Key Buys a 1% Miss Rate

A Bloom filter lets an LSM skip disk reads for keys that aren't there. The space people overestimate: not bytes per key — about 10 bits. A 1.25 MB filter over a million keys gives a 0.8% false-positive rate, matching (1 − e^(−kn/m))^k exactly — and its size is independent of how big the keys are.

Concept

An LSM storage engine confirming that a key does not exist may have to check many SSTables — slow. A Bloom filter per SSTable answers "is this key maybe here?" in a few bit tests, so most of those disk reads are skipped. It can say a false "maybe" (a false positive) but never a false "no." The number people get wrong is the space: you don't need bytes per key for a low miss rate — you need about 10 bits. You will guess it takes far more, and watch a 1.25 MB filter give a 0.8% false-positive rate over a million keys.

Provenance

Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 4 — Storage and Retrieval, §"Bloom filters":

a Bloom filter … provides a fast but approximate way of checking whether a particular key appears in a particular SSTable.

The book describes the structure and that it "takes a bit of extra space." Here you measure exactly how little space, and how the miss rate falls as you spend more of it.

Prerequisites

The surprise is a short probability calculation made concrete. These help; each line notes where it shows up.

Hash functions — a function mapping any key to a number; a good one spreads keys uniformly. A Bloom filter uses k of them (here, derived from one SHA-256 digest) to pick k bit positions.
Bits vs. bytes — the space unit here is bits per key, not bytes. 10 bits ≈ 1.25 bytes. Missing this is the whole surprise.
False positives vs. false negatives — the filter's error is one-sided: it may say "maybe" for an absent key (false positive) but never "no" for a present one. That asymmetry is what makes it safe as a skip-gate.
The false-positive formula — with n keys, m bits, k hashes, the FP rate is (1 − e^(−kn/m))^k, minimized at k = (m/n) ln 2. This is the curve you measure against.

Where to learn the prerequisites The structure and formula (#1, #3, #4): the Wikipedia "Bloom filter" article derives (1 − e^(−kn/m))^k and the optimal k; DDIA §"Bloom filters" (Figure 4-4) is the intuition. The double-hashing trick (#1): search "Kirsch–Mitzenmacher less hashing" — why two hashes can stand in for k of them (what the script does). If only one is new, make it #4 — the formula is the prediction you're testing.

Environment these numbers came from Deterministic hashing, so the false-positive rates reproduce exactly. Captured on macOS 26.5.2 (Darwin 25.5.0), arm64, Python 3.15.0a8, standard library only (no Docker, no third-party packages). 1,000,000 keys inserted; 1,000,000 absent keys queried per configuration.

Mental model

A Bloom filter is m bits, all 0. To add a key, hash it to k positions and set those bits to 1. To test a key, check those same k positions: if any is 0 the key is definitely absent; if all are 1 the key is maybe present — maybe those bits were set by other keys (a false positive). We insert a million keys, then query a million keys we never inserted and count how often the filter wrongly says "maybe," sweeping the bits-per-key budget. The whole exercise is one script, code/bloom_filter.py.

Setup

cd study/ddia/ch04/code
python3 bloom_filter.py     # ~20 s, standard library only

Do not read the output yet — make each prediction first.

Step 1 · pick a budget (predict)

Predict. You want a ~1% false-positive rate over 1,000,000 keys. Roughly how much space do you think that takes — and phrase it per key. (Most people reach for bytes: "a few bytes per key?" — which would be megabytes to tens of MB.)

Step 2 · the false-positive curve (the surprise)

Do. Run the script. It builds the filter at several bits-per-key budgets, uses the optimal number of hashes for each, and measures the false-positive rate against the formula.

How much space gets you a 1% miss rate over a million keys?

Bloom filter: 1,000,000 keys inserted, 1,000,000 absent keys queried bits/key k size measured FP analytic FP 4 3 0.50 MB 14.68% 14.69% 6 4 0.75 MB 5.61% 5.61% 8 6 1.00 MB 2.14% 2.16% 10 7 1.25 MB 0.83% 0.82% 12 8 1.50 MB 0.32% 0.31% 16 11 2.00 MB 0.05% 0.05%

10 bits per key — a 1.25 MB filter — gives 0.83%. Not bytes: bits. And each extra ~2 bits/key roughly halves the miss rate (5.6% → 2.1% → 0.83% → 0.32%). The measured rate sits right on the analytic (1 − e^(−kn/m))^k at every row — this is a formula you can trust, not a lucky run.

Step 3 · key size doesn't matter (the second surprise)

Predict. Those keys were short strings. If the keys were 5 KB blobs instead, how much bigger would the filter need to be for the same 0.8%?

How much bigger a filter do 5 KB keys need?

note: the filter size depends only on the NUMBER of keys, not their length -- 1,000,000 keys at 10 bits/key is ~1.25 MB whether keys are 5 bytes or 5 KB.

No bigger at all. Every key is hashed down to the same handful of bit positions, so the filter's size is set by the key count, never the key length. A filter guarding a million 5 KB records is the same 1.25 MB.

What you should see

~10 bits/key → ~1% false positives (0.83% here); ~16 bits/key → ~0.05%.
Measured rate matches (1 − e^(−kn/m))^k at every budget.
Filter size depends only on key count, not key length.

Why

A Bloom filter trades a small, tunable error for enormous space savings. Adding n keys with k hashes into m bits, the chance a given bit is still 0 is (1 − 1/m)^(kn) ≈ e^(−kn/m). A false positive needs all k bits checked for an absent key to happen to be 1, which is (1 − e^(−kn/m))^k. Choosing the optimal k = (m/n) ln 2 makes that (1/2)^k = 0.6185^(m/n) — an exponential decay in bits-per-key. That is why the rate falls so fast: 0.6185 to the 10th power is already 0.8%, and every extra couple of bits per key halves it again. Ten bits buys you 1% because the math is exponential, not linear.

The reason it works at all — and the reason an LSM can lean on it — is the one-sided error. A present key set its k bits when it was added, and bits are never unset, so those bits are still 1: the filter never gives a false "no." So a "no" from the filter is the truth ("this SSTable definitely lacks the key, skip the disk read"), and only a "maybe" needs a real lookup. Wrong "maybes" cost one wasted read, at a rate you dial in with bits-per-key; wrong "nos" — which would be catastrophic, dropping real data — cannot happen.

The boundary — cheap "no," and no deletes A Bloom filter is a negative cache: it turns "is this key definitely absent?" into a bit test, and that is exactly the expensive question for an LSM point lookup of a missing or long-cold key. It does not tell you where a present key is, only that it might exist. And you cannot delete from a plain Bloom filter — clearing a bit could unset one a different key still relies on, reintroducing false negatives — which is why LSM engines build a fresh filter per SSTable during compaction rather than mutating one in place. Spend bits to match your read mix: heavy missing-key traffic justifies more bits/key; if lookups are almost always hits, the filter earns little.

Go deeper

Use the wrong k. Fix k = 3 for every budget instead of the optimal, and re-run. Predict how much worse the FP rate gets at 16 bits/key — the optimum matters most when you have bits to spend.
Blow the size estimate. Build a filter sized for 1,000,000 keys, then insert 5,000,000. Predict the new FP rate (put n = 5e6 into the formula with the old m) before measuring — this is what happens when an SSTable has more keys than the filter was sized for.
Count the reads saved. Model an LSM with 8 SSTables and a point-lookup workload that's 90% misses. Predict how many disk reads per lookup the Bloom filters remove versus checking all 8 segments.

Sources: DDIA 2e, Ch. 4, §"Bloom filters" (Figure 4-4) · the FP formula and optimal k are standard results (see "Bloom filter", Wikipedia) · Kirsch & Mitzenmacher, "Less Hashing, Same Performance."