# DDIA Ch. 4: ten bits per key buys a 1% miss rate ## 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. 1. **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. 2. **Bits vs. bytes** — the space unit here is *bits per key*, not bytes. 10 bits ≈ 1.25 bytes. Missing this is the whole surprise. 3. **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. 4. **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 them - **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 Deterministic hashing, so the false-positive rates reproduce exactly: - 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. ## Steps ### 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. **Observe.** ``` 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%? **Observe.** ``` 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 1. **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. 2. **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. 3. **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.