Bloom filter

You are building a sign-up form and do not want to allow leaked passwords: 123456, qwerty, dragon and ten thousand more like them. You can keep the whole list and search it, but in Python a set of these strings takes almost a megabyte. Or you can keep 12.5 kilobytes of bits and answer just as fast—at the price of a rare error whose rate you know in advance. Below is the real list of the ten thousand most common passwords, turned into a filter right in your browser. Try your own.

Every orange dot is a bit that some leaked password has lit. Type dragon: all its bits are on, and it really is on the list. Type something long of your own—most likely at least one bit will be off, and the filter will say “surely not”. And sometimes—about once in a hundred checks—all the bits will happen to be lit by other passwords. That is a false positive.

The idea

Take an array of m bits and k hash functions. To add an item, light the k bits its hashes point to. To check an item, look at the same k bits: if any is off, the item is surely absent; if all are on, it may be present.

“No” is always right: had the item been added, it would have lit those bits itself, and bits in the filter only turn on and never off. “Maybe” can be wrong: other items may have lit the bits. The filter's error is one-sided, and all its uses rest on that. If the filter says “no”, you can skip the slow database, the disk or the network. If it says “maybe”, you go and check for real.

The filter does not store the item itself, only the traces of its hashes. That is why it is small: 10,000 passwords of 6.3 characters on average are 73 kilobytes of text, while a filter with an error of about 1% needs 10 bits per password, 12.5 kilobytes in all.

Where false positives come from

Look at a tiny filter: 64 bits, 3 hashes, five words inside. The code in the section below prints the three positions of every word it checks:

dragon     maybe [30, 1, 36]
sunshine   no    [32, 39, 46]
Qwerty     maybe [25, 52, 15]
letmein    maybe [15, 52, 25]
bits set: 14 of 64

Qwerty with a capital letter was never added—qwerty was. But its three bits 25, 52 and 15 are exactly those of letmein, in another order. The filter cannot tell one from the other and honestly answers “maybe”. In a big filter it is almost impossible for all k bits to coincide with the bits of one other word; far more often the bits of the checked word were lit by several different words, one or two bits each. The more ones in the array, the higher the chance that all k are ones by accident.

How many errors

Say n items were added and the hashes spread bits evenly. A bit stays off after one insertion with probability 1 − 1/m for each of the k hashes, and after all insertions with probability

A false positive means all k bits of a new item are on:

The formula shows a trade-off. More hashes make each check stricter, but they also fill the array with ones faster. The minimum over k is reached at

and then exactly half the bits are on. With this k we get how many bits per item the chosen error p needs:

Note that the size of the filter does not depend on the length of the items. A six-character password and a hundred-page document cost the same: k bits. Below are the formula and a measurement on the same ten thousand passwords, with the best k for each size:

Every 4.8 bits per item make the error ten times rarer. A good rule of thumb: “one per cent is about ten bits per item, and each further zero after the decimal point is five more”.

Code

Where do k independent hash functions come from? You do not need them: in 2006 Adam Kirsch and Michael Mitzenmacher showed that two are enough. The positions h₁ + i·h₂ for i = 0, 1, …, k − 1 give the same asymptotic error as k real hashes. We take one 64-bit FNV-1a hash and cut it into two halves. The lowest bit of h₂ is forced to one so that the step is never zero.

Now the real list. The program builds the filter with different numbers of bits per password, checks a hundred thousand strings probe-0, probe-1, …—none of them on the list—and counts how many the filter took for leaked. Python and Go print the same thing to the last digit: they share the hash.

What it costs

An insert and a lookup each take k position computations and array accesses, that is O(k), whatever the number of items. Computing the hash takes a pass over the item, O(length). Memory is m bits, about 1.44·log₂(1/p) per item.

For comparison: a hash table also answers in O(1), but it stores the items themselves. On our passwords that is 997,570 bytes in Python against 12,501 for a filter with an error of about 1%: 80 times less. That is the price of “maybe” instead of “yes”.

There is a smaller catch too: the k bits lie in different places of the array, and a big filter that does not fit in the processor's cache pays a cache miss for every bit. Blocked filters put all k bits of an item into one cache line—slightly worse on error, noticeably faster in practice.

What the filter cannot do

• Delete. A bit cannot be turned off: other items may have lit it too. If deletion is needed, small counters are kept instead of bits (a counting Bloom filter), or a cuckoo filter is used, which stores short fingerprints and can delete.
• Grow. A filter is sized for n items. Put twice as many in and the error grows not twofold but much more: a filter built for 10 bits and 7 hashes that ends up with 5 bits per item errs about 14% of the time instead of 1%. That is why growing sets are split across several filters.
• List its contents. The bits cannot be turned back into what is inside. That can be an advantage: the password list cannot be pulled out of the filter, although any string can be checked against it.

Where it runs

The most widespread use is databases built on LSM trees, such as RocksDB and Cassandra. Data lies on disk in immutable files, and looking up a key would mean opening them all. Each file has a small Bloom filter in memory, and a file that surely lacks the key is not even read. One bit that is off saves a disk read.

Caches in content delivery networks work in a similar way. Many pages are requested exactly once, and caching them only pushes out useful ones. So a page is cached from its second request, and the first requests are remembered by a Bloom filter—cheaply, if with a small error.

History

Burton Bloom described the structure in 1970 in the paper “Space/Time Trade-offs in Hash Coding with Allowable Errors”. His example was hyphenation: a hyphenation program handled most words with simple rules, and only a small share of exceptions needed a dictionary on disk. A filter in memory said whether a word might be an exception, and almost all words were done without touching the disk. The very scheme that databases use half a century later: a cheap “surely not” before an expensive check.

Problems

In the first problem you size a filter with the formulas of this article. In the second you build one and tell false positives from real ones.