Sizing & Tuning Bloom Filters

Sizing & Tuning Bloom Filters

A Bloom filter is only useful if it's sized correctly. Make it too small and every lookup turns into a false positive, forcing you to hit disk anyway — the filter becomes dead weight. Make it too large and you waste memory that could hold more of the actual index. This lesson is about the math that lets you dial in exactly the trade-off you want.

The two knobs

A Bloom filter has three quantities that are all related:

• n — the number of elements you expect to insert (e.g. the number of keys in an SSTable).
• m — the number of bits in the underlying bit array.
• k — the number of independent hash functions used per element.

You don't pick m and k directly. Instead you pick a target false-positive rate p (say, 1%) and derive m and k from n and p. This is the standard operating mode for every real system that uses Bloom filters — LevelDB, RocksDB, Cassandra, and Postgres's pg_bloom all expose "bits per key" or "false positive rate" as the tunable, not raw bit counts.

The formulas

Given n items and a desired false-positive rate p:

m = ceil( -n * ln(p) / (ln(2))^2 )
k = round( (m / n) * ln(2) )

Intuitively: smaller p needs more bits per element (m/n grows as p shrinks), and k is the number of hash functions that minimizes the false-positive rate for a given m/n — using more bits per element without adding more hash functions leaves the filter under-mixed; too many hash functions saturates the array with 1-bits faster than necessary.

A useful mental anchor: at the optimal k, roughly half the bits in the array end up set to 1 once you plug in the true optimum. That's why m/n (bits-per-element, often called bpe) is the number production systems actually report — RocksDB's default of 10 bits per key corresponds to roughly a 1% false-positive rate.

Worked example

For n = 1000, p = 0.01:

m = ceil(-1000 * ln(0.01) / ln(2)^2) = 9586
k = round((9586 / 1000) * ln(2)) = round(6.64) = 7
bpe = 9586 / 1000 = 9.59

So you'd allocate a 9586-bit array and hash each key with 7 independent hash functions.

Practical considerations

• Rounding matters for correctness, not just cosmetics. m must be an integer bit count — round up (ceil), since under-allocating bits pushes your real false-positive rate above the target. k is rounded to the nearest integer because you can't run a fractional number of hash functions.
• k growing without bound is a smell. For very small p (e.g. 1e-9), k can become large (dozens of hash functions), which slows down every insert and lookup. Real systems often cap k (e.g. RocksDB caps around 30) and accept a slightly worse false-positive rate rather than pay the CPU cost.
• This is a per-SSTable decision. Each SSTable knows its own key count n at flush/compaction time, so m and k are computed fresh per file — there's no global filter size.

What you're building

Your exercise takes (n, p) pairs from stdin and prints the derived m, k, and bpe, exactly matching the formulas above. Getting the rounding and formatting right here is exactly the logic your LSM tree will use later when it decides how many bits to allocate for each SSTable's Bloom filter at flush time.