A key value store puts a bloom filter on each table file with 10 bits per key and 7 hash functions. Compute the false positive rate, the expected wasted disk reads for a missing key on a 5 level store holding 8 files per level, and the memory cost for 1 billion keys.

A key value store puts a bloom filter on each table file with 10 bits per key and 7 hash functions. Compute the false positive rate, the expected wasted disk reads for a missing key on a 5 level store holding 8 files per level, and the memory cost for 1 billion keys.

Approach: Apply the standard false positive expression for m bits per key and k hashes, then multiply by the number of filters a negative lookup has to consult.

0.0082. The false positive rate for m/n bits per key and k hashes is (1 - e^{-kn/m})^k, so with m/n = 10 and k = 7 it is (1 - e^{-0.7})^7 = 0.5034^7 = 0.0082, which is near the optimum because the best k for 10 bits per key is about 0.693 * 10 = 7. A negative lookup consults 5 * 8 = 40 filters, each returning a false positive independently with probability 0.0082, so the expected wasted disk reads are 40 * 0.0082 = 0.33 per lookup instead of the 40 reads the store would perform with no filters at all. The memory budget is 10 bits times 1 billion keys, which is 10 gigabits or about 1.25 GB held resident, competing with the block cache for RAM. Two properties matter operationally: a bloom filter never returns a false negative, so a miss is authoritative and the file can be skipped with certainty, and the rate applies per file, so a store with many small files pays more total false positives than one with few large ones, which is a further argument for keeping compaction current.

Follow-up: How would a ribbon or cuckoo filter change the memory required for the same false positive rate?

Key concepts: bloom filter false positive rate, bits per key, negative lookup, memory budget.