Bloom Filter Visualizer

In 1970 Burton Bloom looked at a problem that sounds dull and turned out to be everywhere: test a stream of messages, one at a time, for membership in a large set. His paper weighed three costs against each other. One was the size of the hash area, one was the time needed to reject a message that was not in the set, and the third was an error frequency he was willing to allow. That third cost was the new idea.

Bloom argued that letting a small share of test messages be wrongly declared members would allow a much smaller hash area without slowing the rejections. A slower, exact test could catch the few mistakes afterwards. That is the bargain: memory saved now, a little extra work later, and never a missed member.

The structure that carries his name has outlived the machines it was built for.

What the filter keeps, and what it forgets

A Bloom filter is an array of m bits, all zero at the start, and k hash functions that each map an item to one position in the array. Adding an item sets its k bits to 1. Testing an item reads the same k bits. If any of them is 0, the item was never added, because adding it would have set that bit. If all of them are 1, the item may be present, or other items may simply have set those bits on its behalf.

That asymmetry is the whole design. A no is a proof. A yes is a likelihood. Bits only ever change from 0 to 1, so nothing that happens later can turn a correct no into a wrong one, and nothing short of keeping the items themselves can make a yes certain. The filter never stores the items at all, and that is where the saving comes from.

The probable part has a cost that grows with use. The more items go in, the more bits are 1, and the easier it becomes for a stranger to find all of its k bits already lit. A filter does not fail when it fills. It degrades quietly until, with every bit set, it answers yes to everything.

Where the formula comes from

The usual estimate starts with a single bit. If each hash picks a position uniformly, a given bit escapes one hash with chance 1 - 1/m, and it escapes all kn results for n items with chance (1 - 1/m)^kn, which is close to e^(-kn/m) when m is large. A non-member is reported present when all k of its positions are among the set bits, so the false-positive chance is about (1 - e^(-kn/m))^k.

That expression rests on a convenient fiction. It treats the k tested bits as independent of one another, which they are not quite, and the exact value, written with Stirling numbers of the second kind, comes out slightly higher. The NIST Dictionary of Algorithms and Data Structures points to work showing that the actual false-positive rate is strictly larger than Bloom’s formula, and also to the conclusion that for large m and small k the difference is negligible.

Minimising the approximate rate over k gives k = (m/n) ln 2. At that k about half the bits end up set and the rate falls to one half raised to the power k. Turned around, the bits needed per item for a target rate are minus the natural logarithm of the rate divided by the square of ln 2. For 1 percent that is about 9.6 bits per key, whatever the keys are, and each further factor of ten costs only about 4.8 more bits.

The same two rules turn up wherever filters are built for real. BIP 37, the Bitcoin proposal for filtering what a peer sends, gives the filter size in bytes from the item count and the target probability, and the number of hash functions from that size. It caps a filter at 36,000 bytes, which it describes as room for 20,000 items below 0.1 percent. RocksDB’s documentation shows a filter of about 10 bits per key working well for many workloads, and its table of diminishing returns lists 9.9 bits per key for 1 percent in its own implementation, a shade above the textbook figure.

Choosing m and k, with real numbers

Suppose 20 words must be tested at a 1 percent target. Twenty times 9.585 is 191.7, so 192 bits; the page rounds up to the next prime, 193, for a reason that comes up below. The best k is 193 divided by 20, times 0.693, or 6.69, so k = 7. The approximation then predicts 0.97 percent and the exact expression 1.02 percent, and on average 51.7 percent of the bits should be set.

Built from the twenty sample words on the page, the filter lit 108 of its 193 bits, a fill of 0.56 rather than 0.517. One filter is one sample, and this one came out a little crowded. The made-up word stydel was never added, yet all seven of its positions are 1. Forty seeded filters of twenty random words, each asked about 2,000 words it never held, averaged 1.11 percent with a 95 percent interval of 0.99 to 1.22 percent: the exact value sits inside the interval and the approximation just below it.

Rounding k matters less than it seems. Near the optimum the curve is flat, so 6 or 8 would cost little; at the same size the tool measured 1.13 percent for k = 6 and 1.31 percent for k = 8. Misjudging n is far worse. The same 193 bits holding forty words instead of twenty answered yes to about one stranger in six.

Real filters seldom run k separate hash functions. Kirsch and Mitzenmacher showed that two are enough: positions of the form h1(x) + i h2(x) give a Bloom filter without any loss in the asymptotic false-positive probability. The step h2 must never be zero, or every index lands on the same bit, and it must share no factor with m, or the positions start repeating early. A prime m makes every nonzero step safe, which is why the page rounds up to one.

The word asymptotic is doing real work there. With 101 bits, ten keys and k = 7, positions drawn independently matched the exact value of about 0.85 percent, while the two-hash scheme measured about 1.2 percent, whether its base hashes came from FNV or from a random generator. At 2,003 bits the gap had nearly closed. A filter small enough to draw is small enough to show what the shortcut costs.

The base hashes here are FNV-1a, which RFC 9923 describes as a fast, non-cryptographic hash with good dispersion, and which its authors have placed in the public domain. That is fine for counting false positives. It is no defence against someone who picks words to collide on purpose.

What removal costs

A plain filter cannot delete safely. Clearing one of an item’s bits could erase another item that shares it, turning a correct yes into a false no, and the one guarantee that made the filter useful would be gone.

Counting filters, introduced by Fan, Cao, Almeida and Broder, swap each bit for a small counter. Adding increments, deleting decrements, and a test asks whether every counter is above zero. Their summary cache protocol kept each proxy’s view of the others in representations as small as 8 bits per entry. Counters are usually 3 or 4 bits wide, so a counting filter takes three to four times the space of a plain one, and a counter that overflows has to stay at its maximum from then on.

The cost that matters most is subtler. A counting filter will happily remove a word it never held, provided all of that word’s counters are above zero, which is exactly what a false positive looks like. Doing so lowers counters that real members depend on. With the twenty sample words and 4-bit counters, removing the never-added word lurounux drives five counters down to zero, and five real members, elder among them, then answer no. A false positive, mishandled, becomes a false negative.

Where filters earn their place

The pattern in real systems is always the same: a cheap test in memory in front of an expensive one on disk or across a network. Apache Cassandra keeps a filter for each SSTable so a read can skip files that definitely lack a partition, and its tables default to a false-positive chance of 0.01, or 0.1 under leveled compaction. PostgreSQL’s bloom index stores lossy signatures, 80 bits long by default, and every match must be rechecked against the row itself.

Broder and Mitzenmacher’s survey notes that databases have used Bloom filters since the 1970s and that networking took them up much later. BIP 37 even treated the false-positive rate as a privacy dial. A client with bandwidth to spare could ask for a noisier filter, so that a peer could not tell which transactions were really its own.

What a filter cannot do is as plain as what it can. It cannot list its members, count them exactly, or forget one without counters and some trust that the item was there. Its error rate belongs to the hashes and the fill, not to any single query, and one unlucky filter can run well above the average.

Combining filters has the same split between exact and approximate. The union of two filters with the same size and hashes, a bitwise OR, is exactly the filter of the combined set; the intersection, a bitwise AND, can keep bits that no shared item set, so it may say yes more often than a filter built from the shared items alone. Bloom’s trade still holds. Know which answer you can trust, and size for the load you will really carry.