Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive)

Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR

Every number in a Bloom filter's spec sheet — 9.6 bits/element, k≈7 hash functions, a 1% false-positive rate — falls out of one probability calculation: the chance a single bit is still 0 after n inserts. This page derives that calculation end to end and verifies it with real numbers, then covers three dimensions the sizing story alone never answers: what happens when many threads touch the filter at once, what happens when the set it describes changes underneath it, and what happens when an attacker chooses the keys going in.

The insert/query mechanics, the SSTable read-shield example, and the variant family (Counting, Cuckoo, Scalable) are covered in depth elsewhere in this guide; this page assumes that picture and goes one level deeper into where the sizing numbers actually come from, and where a real deployment can silently degrade or be attacked.

Deriving m/n and k* from first principles

Fix a bit array of m bits, k hash functions, and n items to insert. Every part of the sizing formula falls out of tracking the fate of one specific bit.

1. Step 1 — probability a specific bit is still 0. Each hash function fires once per insert, so n inserts × k hashes means kn independent "shots" at the m positions (treating the hashes as close enough to uniform and independent, which the Kirsch–Mitzenmacher construction makes true enough in practice). Each shot misses a given bit with probability (1 − 1/m). After kn independent shots: P(bit = 0) = (1 − 1/m)^(kn). For large m, (1 − 1/m)^m → e^(−1) (the limit definition of e), so P(bit = 0) ≈ e^(−kn/m).
2. Step 2 — the false-positive rate. A query for an absent item reports "possibly present" only if all k of its bits happen to be 1. Each bit is 1 with probability 1 − e^(−kn/m), and treating the k bits as approximately independent: p ≈ (1 − e^(−kn/m))^k.
3. Step 3 — minimise p over k. For a fixed ratio m/n, p is a function of k alone with a single minimum. Writing x = kn/m, so k = x·(m/n), and differentiating ln p = k·ln(1−e^(−x)) with respect to x, setting the derivative to zero gives ln(1−e^(−x)) = −x·e^(−x)/(1−e^(−x)). Substitute u = e^(−x) = 1/2: the left side is ln(1/2) = −ln2, and the right side is −(ln2)·(1/2)/(1/2) = −ln2 — both sides match exactly at x = ln2, confirming it as the critical point. So the optimum is at kn/m = ln2, i.e. k* = (m/n)·ln2.
4. Step 4 — the false-positive rate at the optimum. At x = ln2, e^(−x) = 1/2, so each bit is 1 with probability exactly 1/2, and p = (1/2)^(k*). Substituting k* = (m/n)·ln2: p = (1/2)^((m/n)·ln2) = [(1/2)^(ln2)]^(m/n) ≈ (0.6185)^(m/n) — because (1/2)^(ln2) = e^(ln2·ln(1/2)) = e^(−(ln2)^2) ≈ 0.6185.
5. Step 5 — solve for the bits-per-element you need. Take logs of p = (0.6185)^(m/n): ln p = (m/n)·ln(0.6185) = −(m/n)·(ln2)^2, so m/n = −ln(p) / (ln2)^2. That's exactly where the famous constant comes from: (ln2)^2 ≈ 0.4805 ≈ 0.48, giving the memorable form m ≈ −n·ln(p) / 0.48 (equivalently m/n ≈ −1.44·log₂p, since log₂p = ln p / ln2).

Worked and verified: 1,000,000 keys at a 1% target

Plug p = 0.01 into Step 5: ln(0.01) = −4.6052, (ln2)^2 ≈ 0.4805, so m/n = 4.6052 / 0.4805 ≈ 9.585 bits/element — the "≈9.6 bits" figure quoted elsewhere in this guide, now derived rather than looked up. Step 3 gives k* = 9.585 × ln2 ≈ 6.644 — not a whole number, since k must be a count of actual hash calls. For n = 1,000,000 keys: m = 9,585,000 bits ≈ 1.20 MB. The table below plugs whole-number candidates for k back into Step 2's exact formula to see which one actually gets closest to the 1% target:

k	p(k) from Step 2's formula
5	1.109%
6	1.014%
7 (nearest integer to k* ≈ 6.64)	1.004% — closest to the 1% target
8	1.053%
9	1.152%
10	1.300%

That is the verification, not just the assertion: k=7 lands at p≈1.004%, matching the 1% target to three significant figures and beating both integer neighbors — proof that k* should be rounded to the nearest whole number, not always truncated or always ceiled. Running the same five steps at p=10% gives m/n≈4.79 bits (≈4.8) and k*≈3.32→3; at p=0.1% they give m/n≈14.38 bits (≈14.4) and k*≈9.97→10 — matching the sizing table quoted elsewhere in this guide, now independently recomputed here rather than taken on faith.

Reading the curve

The chart sweeps k from 2 to 14 at the fixed ratio m/n = 9.585 (the size already fixed for a 1% target) and evaluates Step 2's exact formula at each integer k. Two effects pull against each other as k grows. Each extra hash function makes a query stricter — one more bit has to happen to be 1, which on its own pushes p down — but it also makes each insert set one more bit, so the array fills up faster and any single bit is more likely to already be 1, which pushes p up. At k=2, only about 18.8% of bits end up set, but just 2 of them have to align, giving p≈3.5%. At k=7, roughly 51.8% of bits are set — over half the array — yet needing all 7 of them simultaneously still lands p at ≈1.0%, because the exponent effect wins. Push k too far, to 14, and the array saturates toward 76.8% set faster than the extra AND-conditions can compensate, and p climbs back up to ≈2.5%. The minimum sits exactly where these two effects balance, which Step 3 pins down algebraically at kn/m = ln2.

Concurrency, thread-safety & staleness

The sizing math above assumes a static n. Real filters live inside services with many threads and a changing authoritative set, which raises three questions the pure math never answers: is it safe to read a filter while another thread inserts into it, why do storage engines never mutate a filter after it's built, and what happens to accuracy when the data the filter describes changes underneath it.

Why inserts are lock-free for readers — and where that breaks

Insert only ever flips bits from 0 to 1; it never clears one. That monotonicity is what makes a Bloom filter's read side effectively lock-free: once a bit is set to 1 and that write is visible to a reader, no later insert — for the same item, a different item, or ten thousand concurrent items — can ever flip it back to 0. A reader racing an unrelated insert can only ever see a bit array that is a superset of (or equal to) an earlier state, never fewer 1s than before. That preserves the "no false negatives" guarantee even under concurrent reads and inserts — with one real exception and one real implementation trap.

Exception — the item currently being inserted. A single insert sets k bits one hash at a time; it is not atomic across all k. If thread A is midway through insert(x) — say 3 of x's 7 bits are set — and thread B concurrently queries x, B may see only those 3 bits as 1 and correctly-by-the-algorithm report "definitely absent" for an item whose insert is technically still in flight. That is a genuine transient false negative, but only for the exact item being inserted at that exact moment, and only until the insert finishes; it is not a violation of the one-sided guarantee for anything that has already completed and become visible.

Trap — non-atomic bit words. Bit arrays are almost always packed into machine words (a long[], a BitSet), so setting one bit is really a read-modify-write on a whole word: words[i] |= (1L << offset). If two inserts hash into the same word at the same time on two threads without synchronization, both can read the old word value, OR in their own bit, and write back — whichever write lands second silently overwrites the first thread's bit. That is a genuine lost-update bug, not a documented property of Bloom filters, and it produces a real, permanent false negative for the item whose bit got lost. The fix is ordinary concurrent-programming hygiene: an atomic bitset (e.g. AtomicLongArray.getAndBitwiseOr in Java 9+, or a CAS retry loop), or a striped lock over the words — never a raw array shared unsynchronized across insert threads.

There is also a plain memory-visibility requirement underneath all of this: a reader is only guaranteed to see a completed insert's bits if there is a proper happens-before edge between the write and the read (a volatile reference, a lock, an atomic publish). Without one, a compiler or CPU is free to reorder or delay the writes, and a reader can see a stale, partially-updated array for reasons that have nothing to do with the algorithm and everything to do with the memory model.

Why LSM engines build once and freeze

This is exactly why Cassandra, RocksDB, and similar engines never mutate an SSTable's Bloom filter after it's built. An SSTable is immutable the moment it's flushed to disk, so its filter is built once, single-threaded, while the file is being written — no reader exists yet, so none of the races above are even possible. Once construction finishes, the filter is published as an immutable object (a final field, or a reference handed off through a safely-published channel), and from that point on it is read-only for the rest of its life: every subsequent access, from however many query threads, is a pure read of bits that will never change again. There is no locking cost at query time because there is nothing left to synchronize — the entire class of insert/read and insert/insert races is designed out by construction, not defended against at runtime.

Staleness: what happens when the authoritative set changes

A plain Bloom filter has no delete operation, which creates a specific failure mode once the real data it describes starts shrinking: if a key that was inserted is later deleted from the real store, the filter's bits for that key are never cleared — they can't be, without risking a false negative for some other key sharing one of those bits. The filter's view of the world only ever grows more "present," never less. Practically, that means the observed false-positive rate silently drifts upward over the filter's lifetime as more of the original keys are deleted, even though n may look unchanged or even shrink. A filter correctly sized on day one can be measurably worse a month later purely from churn, with no error or crash to signal it.

There are two standard fixes, and they map to how urgently deletes must be reflected. Rebuild the filter from the current authoritative key set on some cadence — this is what LSM compaction does for free, since compaction already rewrites the whole SSTable from a merge of its inputs, so it just builds a brand-new filter over the merged, live key set as a side effect, and the stale filter is discarded along with the stale file; staleness never needs to be fixed as its own operation. Or, if deletes must be reflected immediately and you can't wait for a rebuild, move to a variant that supports real deletion: a counting Bloom filter (decrement a small counter instead of clearing a bit) or a Cuckoo filter (remove a stored fingerprint outright).

Adversarial FPR: when the hash is public and unkeyed

Every derivation above assumes the k hash functions distribute inputs roughly uniformly and independently over the m positions — true for benign input, but an assumption an adversary can break when two conditions hold: the hash functions are public (a fixed, well-known function like a standard MurmurHash or FNV with no secret parameter) and the attacker controls, or can influence, some of the actual keys the filter ingests or is queried against.

Because the hash functions are deterministic and known, an attacker can compute offline, for any candidate string, exactly which k bit positions it will set or check — nothing about it is probabilistic from the attacker's side. That lets them construct a small set of colliding keys: inputs engineered so their combined bit-sets cover a large fraction of the m-bit array using far fewer distinct keys than the n the filter was sized for. A handful of such crafted inserts can saturate the regions of the array that matter, so that subsequent queries — including queries for keys the attacker never needs to control — land on bits that are already 1 far more often than the sized-for false-positive rate predicts. The observed FPR is pushed toward 1, and every one of those queries falls through to the filter's fallback: the expensive disk read, database lookup, or origin request the filter exists specifically to avoid. The attacker spends a handful of cheap, precomputed keys; the defender's backing store now eats close to 100% of traffic at full cost instead of the ~1% (or whatever p was chosen) it was provisioned for — a denial-of-service amplification through the filter, not around it.

This is the same family of vulnerability as the classic algorithmic-complexity attacks on hash tables (Crosby & Wallach, 2003), where an attacker who knows a hash table's hash function crafts keys that all collide into one bucket, degrading O(1) lookups to O(n) — generalized here to a probabilistic filter, where the crafted collisions degrade the filter-out rate from ~p to ~1 instead of degrading per-operation complexity. The blast radius has the same shape: a small, cheap, precomputable input causes a large, expensive downstream cost.

The fix mirrors the hash-table case exactly: replace the public, unkeyed hash with a keyed hash — one seeded with a secret, randomly-chosen key at filter-creation time. SipHash (Aumasson & Bernstein, 2012) is the standard choice; it's the same primitive language runtimes like Python and Ruby adopted specifically to stop hash-flooding attacks on their dict/hash implementations. With a secret seed, the attacker no longer knows which bit positions any candidate string maps to, so they can't precompute a colliding set offline — they would need a live oracle (repeated queries with visible timing or behavioral feedback) to search for collisions instead, which is far more expensive, rate-limitable, and detectable than a one-time offline computation. Keying the hash costs essentially nothing at runtime and should be the default whenever a filter ingests or is queried with input that isn't fully trusted — which, for anything reachable from outside a trust boundary, is most of the time.

Judgment layer: Bloom filter vs. the named alternatives

Vs. Cuckoo filter: pick Cuckoo when you need real deletion and are chasing a false-positive rate under roughly 3% with tight, cache-line-bound lookup latency; stay with a plain Bloom filter when you never delete, need an insert that can never fail (a Cuckoo filter's bucket eviction can exceed its retry bound under high load and reject the insert outright), and want filters that merge trivially across shards with a bitwise OR, which Cuckoo filters generally can't do. The cost of choosing Cuckoo: more implementation complexity (kick chains, an occasional victim slot) and an insert path that isn't unconditionally accepted.

Vs. a plain hash set: pick a hash set when the working set fits comfortably in memory and you need exact answers, enumeration, or the values themselves, not just membership; stay with Bloom when the set is too large to store exactly and an occasional false positive is cheap to absorb with a fallback check. The cost of the hash set: it stores full keys, typically 10–30× (more for long keys like URLs) the memory of an equivalently-sized Bloom filter, because Bloom pays a fixed bits-per-element cost that is completely independent of key size.

Vs. Quotient filter: a quotient filter stores a compact fingerprint of each key (split into a quotient and a remainder) directly inside one flat, sorted array using a handful of metadata bits per slot, instead of scattering k independent bit-writes across memory. That single-array, sorted layout is what buys it real deletion, cheap merging of two filters, and graceful in-place resizing as the item count grows — three capabilities a plain Bloom filter has none of, and that even a Cuckoo filter only partially matches (Cuckoo can delete, but as above it doesn't merge or resize cleanly either). Pick a Quotient filter when the filter itself needs to be merged, resized, or persisted and reloaded from external/flash storage — its original design target, where in-place resizing without a full rewrite was the whole point. The cost: a more involved insert path (shifting runs of neighboring slots to keep the array sorted) and, at a matched false-positive rate, a footprint that is usually a bit larger than a well-tuned Cuckoo filter. Stay with plain Bloom when none of merge, resize, or delete are needed — it remains the simplest, lowest-overhead option of the three.

Pitfalls this page adds

• "Just round k up (or down) to be safe." Neither is universally correct — round k* to the nearest integer. In the worked example, k*≈6.64 rounds to 7, and 7 genuinely beats 6 (1.004% vs 1.014%); the decimal fraction of k*, not a fixed rule like "always ceil," decides which neighbor is closer to the theoretical minimum.
• "A shared bit array is safe for concurrent inserts because it's just flipping bits to 1." Only true if the underlying word-level write is atomic. A plain, unsynchronized long[] shared across insert threads can silently lose a bit when two inserts land in the same word at the same time — a real, permanent false negative that has nothing to do with the algorithm's documented one-sided guarantee.
• "A delete-heavy plain filter is fine until we notice it's wrong." The degradation is gradual and silent — the FPR creeps up as stale 1s accumulate, with no error or crash, until a monitoring dashboard shows unexplained disk I/O growth. Budget for a rebuild cadence, don't wait to be surprised.
• "Our hash function is fine, it's just for internal load-shedding." If any part of the key space is influenced by external input — usernames, URLs, request IDs — an unkeyed public hash lets an attacker precompute colliding keys and force the fallback path on nearly every request. Treat the hash seed as a secret, the same way you'd treat a session-signing key.
• "The filter is thread-safe because reads never block." True for completed inserts under proper publication, but a query racing the specific item currently mid-insert can see a transient false negative — rare in practice, but worth knowing before building logic that assumes zero false negatives under every interleaving, not just the steady state.

Key takeaways

• The whole sizing story reduces to one probability: P(bit=0 after kn shots) ≈ e^(−kn/m). Minimising the resulting false-positive rate over k lands exactly at kn/m = ln2, giving k* = (m/n)·ln2 and m/n = −ln(p)/(ln2)^2 ≈ −ln(p)/0.48 — verified here at 9.585 bits/element and k*≈6.64 (round to 7) for a 1% target.
• Bits-only-ever-set-to-1 makes reads lock-free against completed inserts, but two real caveats bite in production: non-atomic word updates can lose a bit across concurrent inserts, and the item currently mid-insert can show a transient false negative to a racing reader. LSM engines sidestep both by building each filter once, single-threaded, then freezing it read-only forever.
• A plain filter can't delete, so its false-positive rate silently drifts upward as the real set churns; the fix is a scheduled rebuild (free, as a side effect of LSM compaction) or a Counting/Cuckoo variant if deletes must be reflected immediately.
• An unkeyed, public hash turns the filter into an attack surface: an attacker who can influence inserted or queried keys can precompute collisions that push the observed FPR toward 1, forcing every request onto the expensive fallback path. Seed the hash (SipHash) whenever the input isn't fully trusted.

---

Sources: B. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, 1970 (the sizing derivation traced above). M. Mitzenmacher & E. Upfal, Probability and Computing (the (1−1/m)^m → e^(−1) limit and the k* optimisation). S. A. Crosby & D. S. Wallach, "Denial of Service via Algorithmic Complexity Attacks," USENIX Security, 2003 (the adversarial-collision framing). J.-P. Aumasson & D. J. Bernstein, "SipHash: a Fast Short-Input PRF," 2012 (the keyed-hash mitigation). B. Fan, D. Andersen, M. Kaminsky, M. Mitzenmacher, "Cuckoo Filter: Practically Better Than Bloom," CoNEXT, 2014. M. A. Bender et al., "Don't Thrash: How to Cache Your Hash in Flash," VLDB, 2012 (the Quotient filter). Re-authored/Deepened for this guide.

I just read a lesson on **Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive)** (System Design) and want to truly understand it. Explain Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Bloom Filters — Sizing Derivation, Concurrency & Adversarial FPR (Deep Dive)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.