How do you size a bloom filter for a target false-positive rate, and what does tightening it cost?

## The inputs Sizing needs exactly two numbers you must get from the problem, not from the structure: how many distinct elements the filter will hold at its fullest, and how often you can tolerate a positive that turns out to be wrong. Everything else is arithmetic. With `m` bits, `n` elements and `k` hash functions, the false-positive rate is approximately `(1 - e^(-kn/m))^k`. Minimising over `k` gives two facts worth memorising: - optimal hash count: `k = (m/n) * ln 2`, about `0.69` per bit of budget per element; - required space at that optimum: `m/n = log2(1/rate) / ln 2`, about `1.44 * log2(1/rate)` bits per element. | Target rate | Bits per element | Hash count | | --- | --- | --- | | 10% | ~4.8 | ~3 | | 1% | ~9.6 | ~7 | | 0.1% | ~14.4 | ~10 | | 0.01% | ~19.2 | ~13 | ## Reading the table properly The striking line is the growth: each factor of ten in accuracy costs a flat ~4.8 bits per element. Going from 1% to 0.01% — a hundredfold improvement — barely doubles the memory. Candidates who expect a hundredfold cost for a hundredfold gain have the wrong mental model, and it leads them to accept far sloppier rates than they need to. Make it concrete with a pre-check that screens submitted passwords against a large set of known-breached credentials before an authoritative service call. At 500 million entries, 1% costs about `9.6 * 5e8` bits ≈ 600 MB; 0.01% costs about 1.2 GB. Meanwhile an exact set must store the key material itself — say a 20-byte digest per entry — plus per-entry structural overhead, which lands in the tens of gigabytes. Note also that the filter's cost is unchanged if the entries are long passphrases rather than short digests, because only hash outputs index the array. The exact set's cost is not. ## Choosing the rate from the fallback, not from taste The rate is a business number. The expected extra work per unit time is `rate * (queries that would otherwise be answered 'absent') * cost of one authoritative check` If the confirmation is a local disk read and 99% of traffic is misses, 1% is comfortably cheap. If the confirmation is a cross-region service call with a latency budget attached, or if the fallback path is what saturates first under load, you buy the extra five bits per element and take 0.1%. And if a false positive is not confirmable at all — because the positive *is* the decision — then no rate is small enough and the structure is the wrong choice regardless of budget. One subtlety worth stating: the rate applies to queries for elements that are *not* in the set. If your traffic is mostly hits, the filter is doing little work for you anyway, since its value comes entirely from the exact negatives. ## Sizing for the final n, and what happens when you do not The formula's `n` is the count at the filter's fullest, not today's count. Suppose you sized for 1% at 9.6 bits per element and then inserted twice as many elements. The bits per element halve to about 4.8 while the hash count stays at 7 — badly suboptimal for the new density — and the rate climbs from 1% to well over 10%. Nothing errors, nothing logs; the filter simply becomes an expensive way to send most queries down the fallback path, and the first symptom is usually load on the system the filter was protecting. You cannot fix this in place. Enlarging the array would require re-hashing every element into the new positions, and the filter never stored the elements. The available moves are: rebuild from the authoritative source at a larger size; keep a chain of filters, adding a new, larger one when the current fills, so a query checks each in turn at the cost of extra probes and a compounded rate; or partition the key space up front and size each partition's filter separately. Under-sizing `n` is the expensive mistake; over-sizing merely wastes memory and is safe. ## Operating one Treat the design rate as an SLO with a measurement behind it. If you can observe how often a positive fails its authoritative check, you have the observed rate directly; compare it to the design target and alarm on drift, which is the earliest signal that the element count has outgrown the sizing. Also record `n`, `m` and `k` alongside the artefact, because a filter with no recorded parameters is a filter nobody can safely resize, rebuild or reason about later. Finally, keep the hash count sane. It is tempting to raise `k` for accuracy, but past the optimum it makes the rate *worse* while adding probe cost to every query. Compute it from the budget rather than picking a round number.