A Bloom filter's space cost is about log₂(1/p)/ln 2 bits for every key it holds, and that figure does not depend on n at all: one per cent costs about 9.585 bits a key whether the set has a thousand members or a billion. Put one on every level of a log-structured tree and a read amplification of 5 becomes 1.04, for 1.20 GB of memory over a billion keys.
Core ideas
One formula, one property of it that surprises everybody, and one design fact without which the whole use would be unsound.
At the number of hash functions that minimises the error, a filter needs about log₂(1/p)/ln 2 bits for each key it holds. Double the keys and the filter doubles; the bits per key do not move. So the sizing question is never “how large is my dataset” but “what false-positive rate am I buying”, and one per cent costs a little under ten bits a key.
If any of the k positions a key hashes to is clear, that key was never inserted: a clear bit is a certain negative. The filter can say possibly about a key that is absent; it can never say no about a key that is present. A structure that could say no wrongly would be useless for skipping a disk read, because the read it skipped might be the one holding the answer.
A lookup still reads the level that holds the key. On the other L − 1 levels it is sent to disk only by a false positive, which happens with probability p on each. At L = 5 and p = 1/100 that is 1 + 4/100 = 1.04 probes — the read amplification an LSM paid for its sequential writes, bought back for about a gigabyte of memory.
The material
The sizing formula, the constant people get wrong, and what a filter on every level does to a lookup.
A Bloom filter for a set of n keys is an array of m bits together with k hash functions. Inserting a key sets the k bits it hashes to. A query reports possibly present if all k of its bits are set, and certainly absent if any one of them is clear.
The second answer is exact. The false-positive rate p is the probability that a key which was never inserted nevertheless finds all k of its bits set by other keys.
At the k that minimises the rate, the space needed is about m/n = log₂(1/p)/ln 2 bits a key and the hash count is about k = log₂(1/p). This lesson states those two and uses them to size filters. The derivation, the exact form (1 − (1 − 1/m)^(kn))^k under the idealisation that the hashes are independent, the optimal k = (m/n)·ln 2, and the rule that a Bloom filter supports no deletion all belong to “Bloom Filters” on the Algorithms path, which owns them and proves them.
The independence from n is the part worth pausing on, because it is the reason a filter is a practical thing to build. A billion keys at one per cent is 1.20 GB; two billion keys at one per cent is 2.40 GB, and both are 9.5851 bits a key. Nothing about the filter gets relatively worse as the set grows, which is unusual enough that people assume it must be false.
The figure usually quoted for one per cent is 9.57 bits a key, and it comes from writing the constant as 1.44. The constant is 1/ln 2 = 1.442695…, and at p = 1/100 the two produce 9.5851 and 9.5672 — a gap of 0.0179 bits a key, which is about 2.2 MB over a billion keys. That is small, and it is the wrong kind of small to leave unexplained on a page whose subject is exact counting. The lab prints both columns side by side and says which constant produced which, so the difference is visible rather than argued about.
Both columns are approximations, and so is everything derived from them. The bits-per-key figure is a logarithm and the false-positive estimate is an exponential; neither returns a fraction, and the lab labels every figure that inherits the rounding. Where an exact answer still exists it shows one: at m = 64, n = 8, k = 5 the exact rate is 0.02230073 and the approximation gives 0.02167922, so the approximation is optimistic by about three per cent of itself at that size. It gets better as m grows, which is why it is safe at the sizes anyone actually builds.
A lookup that misses has to try every level, which “Write Amplification in LSM Trees” priced at RA ≈ L. Put a filter on each level and the lookup consults memory first: on the level that holds the key it goes to disk as before, and on each of the other L − 1 levels it goes to disk only on a false positive. So the expected probes are 1 + (L − 1)p, which at L = 5 and p = 1/100 is 26/25 = 1.0400 — and that figure is exact, because p is a target you chose and L is a count.
Choosing p is choosing how many of the L − 1 useless probes you are willing to keep. One in ten leaves 1.40 probes at 4.79 bits a key; one in a hundred leaves 1.04 at 9.59; one in a thousand leaves 1.004 at 14.38. The cost is linear in the digits of 1/p and the benefit falls off a cliff after the first few, which is why most engines sit at one per cent and stop.
And a filter is only worth anything to a workload that asks for keys that are not there. A lookup that hits still reads the level holding its key, and the filter saved it nothing. What 1.20 GB bought over a billion keys was four probes out of five on misses, so the value of the filter is proportional to the miss rate — which is a property of the workload and has to be measured, not assumed.
Interactive
9.585 bits at 1%, not the 9.57 a textbook quotes — and both are rounded
Method
Five lines, and the last of them is the one that keeps the page honest.
The false-positive rate is the decision; the key count only scales the answer. Ask what fraction of useless disk reads you are willing to keep, and convert that into a target — one in a hundred, one in a thousand.
One per cent is 9.5851, one in a thousand is 14.3776. Each extra factor of ten in 1/p costs the same 4.79 bits a key, because the formula is a logarithm — so the cost is linear in the number of nines.
m = n × bits a key, then divide by eight. A billion keys at one per cent is 9 585 058 378 bits, which is 1.20 GB of memory that has to be resident or the filter has bought nothing.
1 + (L − 1)p. This is the number the filter was for, and it is exact: p is the target and L is a count, so no rounding enters it.
The bits a key, the filter size, the memory and the hash count all come from the approximation to the false-positive rate. The read amplification does not. Reporting them without that distinction is how a page ends up asserting 9.57 as though it were exact.
The sizing, the constant that is usually got wrong, and the probes the filter removes.
The 1.0400 is exact and nothing else on the page is. p is the target you chose and L is a count of levels, so 1 + (L − 1)p is arithmetic on two exact inputs. The bits a key, the filter size, the memory and the hash count all descend from the approximation to the false-positive rate, and the lab marks each of them.
A gigabyte and a fifth of memory to remove four probes out of five from every miss in a billion-key store is the trade this page exists to price. Whether it is worth paying is a question about how many of your lookups are misses: a workload that only ever asks for keys that exist gets nothing from a filter at all.
For a faded rehearsal, keep n = 10⁹ and the five levels and move the target to one in a thousand. The supplied first move is that log₂(1000) = 9.9658. Compute the bits a key and the memory, state the read amplification, and then say what the extra 600 MB actually bought relative to one per cent. Check all three in the lab before opening the quiz.
You should be able to turn a target false-positive rate into bits a key and total memory for a stated key count, compute the read amplification a filter per level leaves, and say which of those figures are rounded and which are exact.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.