Commentary: bloom-filter

A false positive is not a dice roll — it is a permanent property of a key. One key returns positive on all 10,000 lookups. A study guide for bloom_filter.py.

cd bloom-filter
python3 demo.py              # the aha (§6)
python3 test_bloom_filter.py # pins every number this page quotes

1. Orientation

A Bloom filter is a set that answers membership queries in constant time out of a few bits per key, and pays for it by sometimes saying yes when the answer is no. Everybody who has read about one can recite that. This toy exists because the recitation hides something, and the something is not subtle once you look at it:

Those two readings sound like restatements of each other. They are completely different engineering situations. The first is a tax spread evenly over all your users. The second is a small set of users for whom the system is permanently broken, who will never see it work, and who cannot fix it by retrying — while everyone else never sees a fault at all.

By the end you should be able to:

• derive the false-positive rate (1-e^(-kn/m))^k from scratch, and say which of its assumptions your filter actually violates;
• explain why raising k past the optimum makes the filter worse, with the fill ratio as the reason;
• predict which of two absent keys is poisoned by looking at the bit array;
• say what a false positive costs in a system with ten filtered segments, and why the answer is neither 1% nor 10%;
• recognise the one line in this file that would destroy the toy's reproducibility if written the obvious way.

2. The problem this mechanism exists to solve

Some lookups are expensive, and most of them are misses.

That sentence is the entire motivation. An LSM-tree storage engine like RocksDB keeps its data in dozens of immutable on-disk segments. A get(key) has to consult them newest-first, and for a key that isn't there, every one of those consultations is a disk read that returns nothing. A web cache deciding whether a peer holds an object, a browser checking a URL against a malware list, a database avoiding a join probe — same shape. The expensive operation is dominated by negatives, and negatives are exactly what a cheap in-memory filter can rule out.

So you want a set membership structure with three properties:

• It fits in RAM while the real data doesn't. A hash set of the keys themselves would work perfectly and defeat the purpose: it costs the size of the keys, and the keys are the thing you couldn't afford to hold.
• It never says "not present" about something that is present. A false negative would make the filter a correctness bug — you'd skip a segment that holds the key and return a wrong answer. A false positive costs only a wasted read.
• It answers in constant time, ideally in one cache line.

The competing goals that make more than one design defensible are space, accuracy, and deletability. A Bloom filter takes an extreme position: it gives up deletion entirely, gives up ever storing the keys, and in exchange gets down to ~9.6 bits per key at 1% error. Give up a bit of that space and you can have deletion (counting Bloom filters, cuckoo filters); insist on exactness and you're back to holding the keys.

The asymmetry in the second bullet is the design's whole personality. The structure is deliberately built so that its errors all fall on the cheap side. "Definitely not present" is a proof; "maybe present" is a rumour. Everything this toy shows follows from thinking hard about what that rumour is actually made of.

3. Background you need

None of this is deep, but the commentary below leans on it.

The two that carry the result are the first and the third. The e^(-kn/m) limit is where every number on this page comes from, and it is what makes §6.5 predictable rather than surprising. Hash randomization is the trap: get it wrong and nothing on this page reproduces, including the aha, because the identity of the poisoned keys would change on every run.

4. The mental model

Before any code. One bit array, shared by every key, with no key ever stored in it.

Three consequences fall straight out of the picture, and they are the whole toy:

• "NO" is a proof, "MAYBE" is a rumour. A clear bit is direct evidence: had the key been added, that bit would have been set. There is no such evidence in the other direction, because a set bit could have been set by anyone.
• add only ever writes 1s. There is no operation that clears a bit, so the array is monotonically filling and the set of keys it lies about only grows. A Bloom filter has an arrow of time.
• A key's k positions are fixed. "cow" hashes to 4, 8, 18 today, and to 4, 8, 18 on every query for the rest of the filter's life. So whether "cow" is a false positive is decided the moment the last of those three bits gets set, and it is decided permanently. That is §6.2, and it is the thing people get wrong.

5. Reading the source

108 lines. Read them in this order.

5.1 The determinism trap, decided in the docstring

Determinism: hashing is SHA-256 from `hashlib`, never Python's builtin
`hash()`. `hash()` is salted per process by PYTHONHASHSEED, so a filter built
on it would poison a different set of keys on every run and none of the
numbers on this page would reproduce. The salt here is an explicit constructor
argument instead of a global, which makes "rehash the filter" a visible
one-line change in the demo rather than an environment variable.

This is the most consequential decision in the toy, and it isn't in any function. It deserves a paragraph because it is the exact trap the rest of the page depends on avoiding.

Python's builtin hash() on a str is salted with a per-process random seed (since 3.3, as a defence against hash-collision denial-of-service attacks). Two runs of the same program hash "key:431" to two different numbers. A Bloom filter built on hash() is therefore still a correct Bloom filter — its false-positive rate is fine — but it is a different filter every time you start the interpreter, and which keys it lies about is re-rolled on every run.

That's fatal here, because the aha is a claim about a named key. I built the variant and ran it in three separate processes:

The SHA-256 line is byte-identical three times. The hash() line changes every number it prints — bits set, false positive count, and the identity of the first poisoned key (key:214, then key:238, then key:138). Note that its rate is fine, hovering around the same 0.8%. It is not a worse hash. It is a hash you cannot write a sentence about.

The second half of the trap is closed in demo.py:

MEMBERS = [f"key:{i}" for i in range(N)]
ABSENT = [f"key:{i}" for i in range(N, N + PROBES)]

The probe keys are enumerated, not sampled. The obvious way to measure a false positive rate is to generate 100,000 random strings, and it would work — but the measured rate would wobble by a few hundredths of a percent per run, and no individual key could be named. With range() there is no RNG anywhere in the toy: no seed to remember, no random import, and key:431 means the same string on every machine that will ever run this.

The combination is what makes §6.2 sayable at all. Determinism here isn't a testing convenience; it is the difference between "some keys are permanently poisoned" (a fact you must take on faith) and "key:431 is permanently poisoned, go check" (a fact you can verify in eight seconds).

5.2 __init__ — one bytearray, and a salt that isn't a global

    def __init__(self, m, k, salt="A"):
        self.m = m
        self.k = k
        self.salt = salt.encode()
        # One BYTE per bit. A production filter packs 8 bits into each byte
        # (or 64 into a machine word) and pays a shift and a mask per probe.
        # This is 8x more memory and 8x less code, and nothing about the
        # mechanism changes -- see the commentary, section 8.
        self.bits = bytearray(m)
        self.n = 0

Two things worth stopping on.

self.bits is a bytearray(m), not a bit-packed integer. This is an 8× space lie, and the comment owns it. Bit packing would mean self.bits[i >> 3] |= 1 << (i & 7) on write and a mask on read, which is three extra operators in the two places the reader most needs to see clearly. The toy is about which bits get set, not about how they're stored, and nothing in this page's arithmetic would change. §8 says what real implementations do.

salt is a constructor argument with a default, not module state. This looks like over-parameterisation for a 108-line file until §6.3, where the entire fix for a poisoned key is build(salt="B"). Because the salt is per instance, the demo can hold two filters over the same keys in memory at once and diff their poisoned sets. Had the salt been a module constant — or worse, implicit in hash() — "rehash the filter" would have been an environment variable and a second process, and the comparison could not have been printed side by side.

self.n counts add calls and is never read by the filter itself. It is bookkeeping for a human, and it is honest bookkeeping about the wrong thing: it counts calls, not distinct keys. Adding the same 100 keys twice leaves the bit array byte-identical but reports n = 200. I checked:

Which matters, because optimal_k(m, n) and predicted_fp(m, k, n) both take n — feed them a duplicate-inflated count and they will predict a disaster that isn't happening. A real filter fed a stream with duplicates has a better false positive rate than its own insert counter believes.

5.3 _indices — the load-bearing function

        digest = hashlib.sha256(self.salt + key.encode()).digest()
        a = int.from_bytes(digest[:16], "big")
        b = int.from_bytes(digest[16:], "big") | 1
        for i in range(self.k):
            yield (a + i * b) % self.m

Five lines, and everything else in the file is plumbing around them.

One hash, k positions. Hashing is the only expensive thing a Bloom filter does — the bit probes are a handful of loads. Computing k independent SHA-256 digests would make a query k times more expensive for no change in the interface. Kirsch and Mitzenmacher's result is that you don't have to: split one digest into two halves a and b, and generate position i as a + i·b (mod m). Whether that costs accuracy is a real question with a measured answer, and it gets §7.1 to itself.

| 1 is load-bearing, and cheaply proved so. b is the stride of an arithmetic progression mod m. If b shares a factor with m, the progression closes early and the key gets fewer than k distinct positions — which silently converts that key into a k'<k filter with a much worse error rate. Here m = 1000 = 2³ · 5³, so any even b, or any multiple of 5, degrades. Forcing b odd doesn't eliminate the problem (5 is odd), but it kills the common half of it. I deleted the | 1 and re-ran:

Without it, 825 of 100,100 keys (0.824%) get fewer than seven distinct positions — and the worst cases collapse all the way to one: key:12247 probes a single bit, seven times. The false positive rate rises from 0.751% to 0.989%, a 32% relative degradation, from deleting two characters. This is the single best argument in the toy for running your variants instead of reasoning about them: the failure is invisible, silent, correct-looking, and affects fewer than one key in a hundred.

The fingerprint is only (a mod m, b mod m). This is the part the docstring doesn't say and §7.1 turns out to need. Whatever SHA-256's 2²⁵⁶ outputs, the only thing that survives into the positions is the pair (a mod m, b mod m) — for m = 1000, at most 1000 × 1000 / 2 = 500,000 distinguishable fingerprints. Two keys that land on the same pair get literally the same seven positions and become indistinguishable to the filter forever. That is not hypothetical; key:431 is one, and test_key_431_is_an_exact_fingerprint_clone_of_member_key_45 pins it.

5.4 add and __contains__ — the asymmetry, in nine lines

        for index in self._indices(key):
            self.bits[index] = 1
        self.n += 1

        # all() short-circuits, so a true negative usually costs far fewer
        # than k probes: the first clear bit ends the query.
        return all(self.bits[index] for index in self._indices(key))

add writes 1, never 0. __contains__ is all(...), never any(...). The entire "no false negatives" guarantee is those two facts standing next to each other: if a key was added, each of its k positions was written to 1 and nothing can ever un-write it, so all() cannot fail. The guarantee is not probabilistic, and it doesn't depend on the hash being good. It's structural.

The comment claims short-circuiting saves probes. It does, and by more than I expected:

Swapping the generator for a list comprehension — all([...]) instead of all(...), one pair of brackets — takes the average query from 1.962 probes to 7.000, with identical answers. And the depth histogram is the fill ratio staring back at you: 50.47% of queries die on the first probe, which is just 1 - 0.492, the chance a bit is clear. 25.15% die on the second, which is 0.492 × 0.508 = 0.250. Each row is the last one times 0.492. The expected depth is the geometric sum (1 - 0.492⁷)/(1 - 0.492) = 1.955, against 1.962 measured.

The last row is worth a second look: 1,500 queries reach the seventh probe, but only 751 are false positives. The other 749 found all six of the first bits set and the seventh clear. They did the maximum work to earn a "no".

The thing short-circuiting doesn't save is the hash. digest is computed on line 51, before the loop, on every query — so a query costs one SHA-256 no matter how fast it bails. In a real filter that's the entire cost, which is why production implementations optimise the layout (all k bits in one cache line) rather than the probe count.

5.5 optimal_k — where the tension is written down

    return max(1, round((m / n) * math.log(2)))

The derivation is in the docstring above it (bloom_filter.py:77-85) and is worth doing on a whiteboard once. After n inserts of k bits each, a given bit survived kn independent chances to be set, so it is still clear with probability (1 - 1/m)^kn ≈ e^(-kn/m). A false positive needs all k of a key's bits set, so the rate is (1 - e^(-kn/m))^k. Differentiating in k puts the minimum exactly where half the bits are set, at k = (m/n) ln 2.

The max(1, ...) floor is not decoration. round((m/n) · ln 2) returns 0 whenever m/n < 1.44 — a filter with under 1.44 bits per key:

A k=0 filter sets no bits and, because all() over an empty sequence is True, admits everything. It is a function that returns True. The floor converts a catastrophically wrong filter into a merely bad one.

5.6 bits_per_key_for — the number to remember

    return -math.log2(target_fp) / math.log(2)

Substitute k = (m/n) ln 2 back into (1 - e^(-kn/m))^k and it collapses to fp = 2^(-(m/n) ln 2), so m/n = -log₂(fp) / ln 2. Run it:

Two facts to carry out of this file. Each additional factor of ten in accuracy costs a flat 4.79 bits per key — the cost is logarithmic, so precision is astonishingly cheap. And the requirement is per key, not a fraction of the data: a million keys at 1% costs 1,170 KiB whether the values behind them are 10 bytes or 10 megabytes. That ratio — filter size fixed, data size arbitrary — is the reason the structure exists.

6. The demo, and what it proves

demo.py builds one filter — m = 1000 bits, n = 100 keys, k = 7 — and runs five experiments on it. Run it twice; the output is byte-identical (I diffed it, §5.1).

6.1 The textbook result, and it checks out

Start with the arithmetic, because everything after this depends on it being sound.

Why 492 bits and not 700. 100 keys × 7 positions = 700 bit-writes, but only 492 distinct bits are set — 208 writes landed on a bit that was already 1. The prediction: a given bit escapes all 700 writes with probability (1 - 1/1000)^700 = 0.4966, so 1000 × (1 - 0.4966) = 503.4 bits should be set. This particular filter got 492, luckier than average by 11 bits. That is the entire content of the e^(-kn/m) approximation, and the fill ratio 0.492 is satisfyingly close to the theoretical optimum of exactly 0.5.

Why 0.751% and not 0.8194%. The formula (1 - e^(-kn/m))^7 = 0.8194% assumes 503 bits are set. Only 492 are, and 0.492^7 = 0.6978%. So the formula's error here is mostly not about the formula — it's that this filter happened to fill less than average. Observed 0.751% sits between the two, and above fill^k by a factor of 1.076. That 7.6% excess over what independence would predict is real, it is the double-hashing dependence, and §7.1 chases it down.

The guarantee holds: no false negatives: True, checked against all 100 members. It is the one line in the transcript that is not a statistic.

So: observed rate matches the textbook formula, within the slack you'd expect from a single filter of 1000 bits. Nothing surprising. Now the part that is.

6.2 What that rate actually means

The reason is in the next line of output: key:431's positions are [82, 171, 445, 534, 719, 808, 897], and they are that on every query, because _indices is a pure function of the key (§5.3). All seven were set by members. Nothing in the filter is ever going to change that, because nothing in the filter ever clears a bit.

So the rate is not a per-query probability. It is a partition of the key space. Of the 100,000 absent keys probed, 751 are in the poisoned class and 99,249 are in the clean class, and membership of those classes is determined. The right mental model isn't a die rolled on each lookup; it's a list, computed at construction time, of every key in the universe that this filter will lie about.

Restate the SLA and the difference becomes an operational one:

• What people hear: "every request has a 0.75% chance of a slow path." An even tax. Fine. Retry if it matters.
• What is true: "0.75% of keys take the slow path on 100% of requests, and 99.25% never do." If a user's key is key:431, every single one of their requests eats the wasted read. Forever. They will never see the fast path. Their retry hits the same seven bits.

This is why the failure is hard to find in production. It doesn't show up as a raised error rate; it shows up as a handful of users with permanently bad p99 latency and a support ticket nobody can reproduce, because the engineer investigating types their own key and it's clean.

How does a key get poisoned? Two ways, and I counted them:

key:431 is a fingerprint clone: it collides with member key:45 on both a mod m and b mod m, so it gets exactly key:45's seven positions (§5.3's 500,000-state fingerprint space). One member poisons it single-handed. But that's the rare case — 38 of 751. The other 713, like key:489, are poisoned by collective coverage:

Seven different members each independently happened to set one of key:489's seven bits. No single member is responsible; the filter as a whole is. That's the ordinary case, and it's why "which keys are poisoned" is a property of the entire member set, not of any pair of keys. Both routes produce the same permanence, which is the point.

6.3 Retry never helps. Rehashing does.

Change one character in the constructor — salt="A" to salt="B" — and key:431 is clean. Not less likely to be a false positive: clean, because its positions moved to bits that no member sets.

But look at the third line. The poisoned sets under the two salts overlap in zero keys out of 10,000. Rehashing doesn't reduce the problem; it moves it. Salt B poisons 83 keys where A poisoned 59 (a worse draw — the per-salt rate wobbles; over 20 salts I measured 0.709% to 1.164% at this size). Three of the newly cursed are named: key:1023, key:1238, key:1501, all of them perfectly fine under salt A.

That's the honest shape of the fix, and it's a bleak one. You cannot make a Bloom filter stop lying about a specific key without making it lie about a different, equally arbitrary set of keys. The knobs you actually have are:

• Rebuild with a different salt — helps that user, hurts strangers, and requires you to have identified the victim in the first place.
• Spend more bits — the only real fix. §5.6: another 4.79 bits per key shrinks the poisoned class tenfold. It doesn't empty it.
• Verify after the filter says yes — which is what every production system does, and why a false positive costs latency rather than correctness.

6.4 Ten segments at p each: the rate you feel is not p

The reason this matters in a storage engine is that you don't have one filter. An LSM tree (see lsm-tree) has many on-disk segments, each with its own filter, and a get for an absent key consults all of them. Demo part 5 stands in ten dicts for ten segments — no SSTable, no compaction, just ten independently-salted filters:

The arithmetic. A lookup is clean only if all ten filters say no, so the chance of at least one wasted read is 1 - (1-p)^10. At the demo's measured p = 0.913%, that's 1 - 0.99087^10 = 8.764% predicted against 8.740% observed. At a round 1% it would be:

Not 1%, and not 10%. So a "1% filter" in a ten-segment tree means roughly one lookup in ten does at least one pointless disk read. The first-order approximation 10 × p = 9.13% overstates the real 8.764% by 0.37 points, because it double-counts the lookups unlucky enough to false-positive on two segments at once.

Two things follow, and both are visible in the transcript. The per-segment rate here is 0.913% rather than §6.1's 0.751% purely because the segments use different salts (S0..S9) and different key strings — same structure, different draw from the same distribution. And the gap between 913 wasted reads and 874 affected lookups is where the missing 0.37 points went. I broke it down:

835 lookups wasted one read, 39 wasted two, none wasted three. Those 39 double-hits are counted twice by 10 × p and once by 1 - (1-p)^10, which is exactly the 39-read discrepancy.

The design consequence is that your filter budget scales with your segment count. If you want a 1% effective miss cost across ten segments you need a 0.1% filter per segment, which by §5.6 costs 14.38 bits per key rather than 9.59 — a 50% larger filter to hold the same promise. This is exactly why RocksDB's default is ~10 bits per key and why level-based compaction, which reduces how many files a lookup must consult, is as much a filter-economics decision as an I/O one.

6.5 The boundary condition: more hashing is not more accuracy

Every result above is at k = 7. Here is where the effect vanishes, and where the intuition "more hash functions means more checking means fewer mistakes" dies:

The curve is a U, and the fill column is the whole explanation.

Going up from k = 1, each extra hash adds a condition a false positive must satisfy, and the rate falls hard: 9.236% → 3.293% → 1.719%. But each extra hash also sets one more bit per insert, and the fill ratio climbs in lockstep: 0.092 → 0.182 → 0.259. At k = 7 the array is 49.2% full, almost exactly the half-full point the derivation predicted, and the rate bottoms out at 0.751%.

Past that, saturation wins. At k = 20 the array is 86.1% full — the demo measured it. Asking twenty questions of a wall that is 86% solid is worse than asking seven of a wall that is 49% solid, because 0.861^20 = 5.013% while 0.492^7 = 0.698%. The observed rate at k=20 is 5.344%: k = 20 does 20/7 = 2.9× the hashing work for 7.1× the error rate. Both ends of the table are bad and the middle is good, which is the signature of an optimum rather than a monotone knob.

Note also where the (1-e^-kn/m)^k column stops tracking. At k = 14 the formula says 1.898% and reality is 2.422% — the formula is optimistic by 28% in a regime where the independence assumption it rests on is badly violated, because at 76% fill the bits are heavily shared. Trust the formula near the optimum; distrust it in saturation.

6.6 The numbers are pinned by tests

python3 test_bloom_filter.py

test_headline_false_positive_count asserts 751, 492, and fps[0] == "key:431", so §6.1 and §6.2 cannot rot silently. test_more_hashing_is_not_more_accuracy pins the two ends of §6.5's U. test_odd_b_gives_every_key_k_distinct_positions locks in §5.3's | 1.

7. Design decisions and roads not taken

7.1 Double hashing vs. k independent hashes — the penalty is real, and it is a small-m artifact

This is the toy's one genuine open question, and reading the code can't settle it. _indices derives all seven positions from one SHA-256 by a + i·b (mod m). The seven positions are therefore not independent — they lie on an arithmetic progression, and the formula in predicted_fp assumes independence. Does that cost accuracy?

Kirsch and Mitzenmacher's paper says no, asymptotically. §6.1 saw observed 0.751% sitting 7.6% above fill^k, which looks like it might say yes. So I built the counterfactual: the same filter with _indices overridden to compute k genuinely independent SHA-256 digests (one per i, salted with i), and ran both over identical keys.

The first attempt was inconclusive, and instructively so — a single salt gives a difference that bounces around in both directions (ratios of 0.957, 1.008, 0.929, 1.011 across four sizes), because one filter of 1000 bits is one sample. So I paired the two implementations over 20 salts each, holding m/n = 10 and k = 7 so the textbook prediction is 0.8194% at every scale, and let only m grow:

Both halves of the question get an answer.

Yes, there is a penalty. At m = 1000, double hashing costs +0.082 percentage points, a 10.2% relative degradation. That is not noise — it is a paired mean over 20 salts and it is consistent in sign.

And no, it does not survive scale. The penalty decays fast: 10.2% → 2.2% → 0.9% relative as m goes 1,000 → 10,000 → 100,000, with m/n and k held fixed so the textbook rate is identical at every row. At m = 100,000 — still a tiny filter by production standards — double hashing costs under 1% relative. It is a small-m artifact. Kirsch–Mitzenmacher's asymptotic claim is confirmed rather than contradicted, and this toy just happens to run at a size small enough to see the transient.

The clone rate column is the mechanism, and it's the one from §5.3. A key is reduced to (a mod m, b mod m) — about m²/2 states — so by the birthday argument an absent key matches some member's fingerprint exactly with probability around 2n/m². The measured clone rates (0.0396%, 0.0035%, 0.0006%) track that prediction (0.0200%, 0.0020%, 0.0002%) within a factor of two, falling as 1/m when m/n is held fixed. And the last column is the control: k independent hashes produce zero clones at every scale, because an exact seven-position match would need seven independent coincidences instead of two.

The clone rate accounts for roughly half the penalty at m = 1000 (0.0396 of 0.0820 points); the rest is partial correlation, keys sharing some but not all positions with a member.

So why keep double hashing? Because the cost it saves is the dominant one. A query does one SHA-256 instead of seven — and §5.4 showed the digest is computed on every query regardless of short-circuiting, so it is the query cost. Paying 7× on the only expensive operation, to recover under 1% relative accuracy at any size you'd actually deploy, is a bad trade. Every serious implementation does what this toy does.

7.2 Why no remove()

The obvious extension is to clear a key's k bits. It is one line, and it destroys the structure's only hard guarantee, because those bits belong to everyone. Clearing key:0's seven positions:

    assert len(absent_members) == 9, absent_members
    assert absent_members[:3] == ["key:0", "key:22", "key:41"]

Nine members go missing — the one deleted, plus eight innocent bystanders including key:22 and key:41, each of which happened to have one of its seven positions shared with key:0. That converts false positives (cheap, wasted read) into false negatives (a correctness bug: you'll skip a segment that holds the key and return "not found" for data you have).

The standard fix is a counting Bloom filter: replace each bit with a small counter, increment on add, decrement on remove. It costs 3–4× the space and introduces counter overflow as a new failure mode. The modern answer is the cuckoo filter (§10), which stores small fingerprints in a cuckoo hash table and supports deletion at less space than Bloom for low false-positive targets. Neither is here: the toy is about the mechanism whose whole personality comes from bits never being cleared, and adding deletion would delete the arrow of time that makes §6.2 true.

7.3 Why optimal_k is a function and not a constant

k could have been hardcoded at 7. Making it computed buys §6.5: the demo sweeps k from 1 to 20 against the same members and prints the U-curve, with the optimal_k row marked. A hardcoded 7 would have made the optimum an assertion rather than a demonstration, and the boundary condition is half the value of the page.

7.4 Why a bytearray of 0/1 rather than an int bitmask

Python's arbitrary-precision int would make the filter a single number: self.bits |= 1 << index. It's shorter, and it's genuinely how you'd do it if you wanted the filter to be serialisable in one int.to_bytes. It loses on two counts: fill_ratio becomes bin(self.bits).count("1") / m (or int.bit_count), which reads as a trick, and each |= on a large int is O(m/64) because it copies the whole integer — so building the filter would be quadratic. The bytearray is O(1) per write and sum(self.bits) is an honest population count, since every element is 0 or 1.

7.5 Why not a plain hash set, or a perfect hash?

A set of the keys is exact and defeats the purpose: it costs the size of the keys, and the premise (§2) is that the keys don't fit. A minimal perfect hash over a known static set is exact and compact, but it must be constructed over the whole key set at once and cannot be added to — which is fine for a static malware list and useless for an LSM segment being built incrementally. The Bloom filter's niche is precisely: incremental construction, unbounded key universe, bounded space, errors on the cheap side.

8. What's simplified vs. the real thing

• No bit packing. self.bits is a bytearray of 0s and 1s — one byte per bit, 8× wasteful. Real implementations pack bits into machine words and pay a shift and a mask per probe (words[i >> 6] & (1 << (i & 63))). More than space, this is about cache lines: RocksDB's "full filter" format deliberately constrains all k probes for a key to a single 64-byte cache line, turning k random memory accesses into one cache miss. At production scale the filter is memory-bandwidth-bound, and locality beats probe count.
• No deletion, no counting filter. §7.2. Production systems that need deletion use counting Bloom filters (Summary Cache's protocol, §10) or move to cuckoo filters. Systems that don't need it — LSM segments are immutable — simply rebuild the filter when the segment is rewritten by compaction.
• Fixed m and n, chosen up front. The constructor takes m and you are expected to know n in advance. Get n wrong and §6.5's U-curve punishes you from whichever side you missed. Real systems use scalable Bloom filters (a chain of filters with geometrically tightening error rates, so the compound rate converges) or, in an LSM tree, sidestep it entirely: a segment's key count is known exactly at flush time, so the filter is sized after the data is assembled.
• No partitioning or sharding. One array, one lock's worth of contention if there were a lock. Production filters partition the array into k slices, one per hash — which bounds each hash to its own region, makes the filter parallelisable, and slightly changes the math.
• No concurrency control. add is a read-modify-write over a bytearray with no lock. In CPython the GIL happens to make each self.bits[i] = 1 atomic, but that is an implementation accident, not a design. In a real concurrent filter, add is naturally lock-free (setting a bit is idempotent and monotone — concurrent adds can't lose data, only race harmlessly), which is one of the structure's underrated production virtues.
• No serialisation. A filter lives and dies in one process. A real one is written into the SST file's footer, memory-mapped on open, and must therefore pin its hash function and its k in a format version — because a filter rebuilt with a different hash is a different filter (§6.3), and reading it with the wrong one silently produces false negatives.
• One filter, not a hierarchy. §6.4 stands ten dicts in for ten segments. A real LSM tree has levels with different sizes, a compaction policy that changes how many files a lookup consults, and per-level filter configuration. See lsm-tree.
• SHA-256 is far stronger than needed. A cryptographic hash costs ~100× a non-cryptographic one. Production filters use xxHash or MurmurHash, which are well-distributed but not collision-resistant. SHA-256 is here because it's in the stdlib and is stable across processes and platforms — which §5.1 shows is the property the toy actually needs.

9. Check yourself

Answer before expanding. Each answer is derivable from the source.

Q1. Your service reports a 0.75% Bloom filter false positive rate. A user complains every one of their requests is slow. Your colleague says "0.75% — they've just been unlucky repeatedly, tell them to retry." What's wrong with that?

Q2. Same m = 1000 bit array, same k = 7, but you insert 200 keys instead of 100. The false positive rate goes from 0.751% to what — roughly 1.5%? And can you fix it by re-tuning k?

Q3. In _indices, b is forced odd by | 1 (bloom_filter.py:53). The docstring says this stops positions collapsing onto a. But m = 1000 and 5 is odd — so b = 5 is still a multiple of a divisor of m. Does the | 1 actually accomplish anything, or is it theatre?

Q4. You have three load-balanced servers, each building its own Bloom filter over the same 100 keys but with its own salt (A, B, C). A user's key is poisoned. Does retrying help now?

Q5. You replace all(...) with any(...) in __contains__ (bloom_filter.py:67). The filter still returns True for every member — so the "no false negatives" guarantee still holds. Is the filter still useful?

Q6. §6.4 shows ten segments at ~0.9% each producing an 8.7% chance of a wasted read. Your architect proposes going from 10 segments to 100 to improve write throughput. What does that do to your filter budget?

10. Further reading

Every link below was fetched and confirmed live when this was written (2026-07-26).

• Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors" (1970, PDF) — the original, four pages, CACM 13(7):422. Worth reading for how carefully it frames the trade-off as three-way (space, reject time, allowable error fraction) rather than two-way. Note it does not contain the (m/n) ln 2 optimum — that came later. This is a scanned mirror; the ACM canonical copy at dl.acm.org/doi/10.1145/362686.362692 returns 403 to non-browser clients, which is why it isn't linked directly.
• Kirsch & Mitzenmacher, "Less Hashing, Same Performance: Building a Better Bloom Filter" (PDF) — the paper behind _indices, and the direct source for §7.1. It proves that g_i(x) = h₁(x) + i·h₂(x) costs nothing asymptotically. §7.1 is the empirical confirmation, including the small-m transient the asymptotic result is silent about.
• Fan, Andersen, Kaminsky & Mitzenmacher, "Cuckoo Filter: Practically Better Than Bloom" (PDF) — the modern answer to §7.2. Stores short fingerprints in a cuckoo hash table; supports deletion, and uses less space than a space-optimised Bloom filter for false positive rates below ~3%. If you are choosing a filter today rather than learning how one works, start here.
• Fan, Cao, Almeida & Broder, "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" — where counting Bloom filters come from, driven by a real problem: cache directories that must support eviction. Also the source of the "8 bits per entry" figure people quote. The "Bloom Filters — the math" section is a clean, self-contained derivation.
• RocksDB Bloom Filter (wiki) — the production system §2, §6.4 and §8 keep pointing at. Documents the ~10 bits/key default, the full-filter vs. block-based-filter change (the cache line argument from §8), and ribbon filters, which save ~30% of the space for 3–4× the construction CPU. Read this if you want to see which of this toy's simplifications actually get paid for.
• Wikipedia: Bloom filter — unusually good. Carries the full derivation of k = (m/n) ln 2, the (1-e^(-kn/m))^k rate, counting filters, and a survey of the variants (§8's scalable and partitioned filters). The best single starting point after this page.
• "Bloom Filters Debunked: Dispelling 30 Years of Bad Math" — the honest footnote to §6.1. The universally-cited (1-e^(-kn/m))^k assumes bit independence and is an approximation; Bose et al. (2008) corrected it 30 years later, and their correction had errors too, until it was mechanically proved in Coq. Read this before trusting the fourth decimal place of anything on this page.
• Bloom filter calculator (hur.st) — interactive: fix any two of n, p, m, k and it solves for the rest, showing the formulas. The fastest way to internalise §5.6's "each 10× on accuracy costs a flat 4.79 bits per key."
• Bloom Filters by Example — type a word, watch the bits light up in a live bit vector, then test membership. If §4's ASCII diagram didn't land, this is the same picture with the animation.