Bloom filter simulator

The grid is the filter: m bits, each 0 or 1. Type a word and press Add: the word is hashed k times, each hash picks a bit, and those bits are set to 1. Press Test to check a word: if any of its bits is 0 the word was certainly never added; if all are 1 it may have been. The simulator also keeps the real list of added words, so it can tell you whether each answer was right.

Try these:

• Press Add 10 words a few times, then Test 1,000 unseen words. Each test adds a dot to the chart; compare the dots with the predicted curve. In a filter this small, the result depends noticeably on which words happened to be added, so the dots scatter around the curve.
• With about 20 words in 64 bits, compare k = 1, 3 and 7 (each change starts a fresh filter). Too few hash functions and each test checks too little; too many and the array fills up quickly.
• Fill the filter, then use Remove by clearing its bits on one word. The panel lists the other words that now test as absent. This is why a plain Bloom filter cannot delete.

The simulator computes two 32-bit hashes of each word and combines them by double hashing, so the k positions of a word are always different bits. The measured rate uses the words probe-0, probe-1 and so on, skipping any that were added.

A Bloom filter is a data structure for testing whether an item is a member of a set. It does not store the items, only an array of bits that they have marked, so it takes far less space than a list or a hash table of the items themselves. In exchange it can be wrong in one direction: it sometimes says an item is present when it is not (a false positive), but it never says an item is absent when it was added.

That trade suits a common pattern: a cheap check placed in front of an expensive one. If the filter says "definitely not", the expensive lookup, such as a disk read or a network request, can be skipped. If it says "possibly", the expensive lookup is done as usual. A false positive costs one wasted lookup; it never produces a wrong final answer.

The filter is named after Burton H. Bloom, who described it in 1970.

An empty Bloom filter is an array of m bits, all 0, together with k hash functions, each of which maps an item to one of the m positions.

• Adding an item: compute its k positions and set each of those bits to 1.
• Testing an item: compute the same k positions. If any of those bits is 0, the item was never added. If all are 1, the item may have been added.

There are no false negatives because bits only ever change from 0 to 1. An added item's bits were all set when it was added and nothing sets them back. A false positive happens when every one of an item's k bits was set by other items. The more of the array is set, the more likely that becomes, which is why the error rate grows as items are added.

Both operations take k steps, whatever the number of items. They touch k bits that may be far apart in memory, which matters for speed on large filters (see blocked Bloom filters).

Assume the hash functions pick positions independently and uniformly. After n items have been added with k hashes each, the chance that a given bit is still 0 is (1 − 1/m)^kn, which is close to e^−kn/m. An item that was not added is a false positive if all k of its bits are 1, so the false-positive rate is approximately

p ≈ (1 − e^−kn/m)^k

The rate depends on the number of bits per item, m/n, and on k. For a given m/n, the k that gives the lowest rate is about (m/n) × ln 2, at which point about half the bits are set. More hash functions than that fill the array faster than they help; fewer check too few bits.

The formula is an approximation. The exact rate is slightly higher, especially for small filters, but the difference is negligible at practical sizes. Given a particular filter, a more direct estimate is the fraction of bits set raised to the power k, which the simulator also shows.

To build a filter, choose the number of items you expect, n, and the false-positive rate you can accept, p. Using the best k, the filter needs

m = −n × ln p / (ln 2)² bits, and k = (m/n) × ln 2 hash functions

The number of bits per item depends only on p, not on the size of the items, which is why a Bloom filter of URLs or long keys is no larger than one of integers. Each halving of the error rate costs about 1.44 more bits per item.

A Bloom filter does not need k unrelated hash functions. Adam Kirsch and Michael Mitzenmacher showed in 2006 that two hash values h₁ and h₂ are enough: the i-th position can be computed as h₁ + i × h₂ (mod m), with no measurable loss in accuracy. Most implementations do this, often taking both values from one 64-bit or 128-bit hash.

The hash should be fast and spread its output evenly. Cryptographic hashes are not needed; non-cryptographic hashes such as MurmurHash and xxHash are common. If an attacker can choose the items and knows the hash function, they can pick items that set the same bits or that produce false positives on purpose, so filters exposed to untrusted input should use a keyed hash with a secret seed.

No deletion

Several items can share a bit, so an item cannot be removed by clearing its bits: doing so can make other items test as absent, breaking the one guarantee the filter offers. The simulator's remove button shows this. Filters that need deletion use a counting Bloom filter or a cuckoo filter, or are rebuilt from the source data from time to time.

Fixed capacity

The size must be chosen in advance. A plain filter cannot be resized without the original items, because the bits do not record which items set them. Scalable Bloom filters work around this by adding new, larger filters as the old ones fill.

No listing or counting

A Bloom filter can only answer membership questions. It cannot list its items, and it records nothing about how many times an item was added. For counting distinct items, HyperLogLog is the usual choice; for estimating how often items occur, a count-min sketch.

Memory access

Each test reads k bits at scattered positions. In a large filter each read is likely to miss the CPU cache, so a test can cost k cache misses. Blocked Bloom filters confine an item's bits to one cache line to avoid this, at a small cost in accuracy.

• Databases built on LSM trees. LevelDB, RocksDB, Cassandra and HBase store data in many sorted files and keep a Bloom filter for each one. A lookup tests each file's filter and reads only the files that might hold the key. LevelDB's documentation suggests about 10 bits per key, which it says cuts unnecessary disk reads by a factor of about 100. Cassandra's default target is a 1% false-positive rate for most tables. See the LSM tree simulator.
• Content delivery. Akamai found that, in one of its server clusters, nearly three quarters of the objects requested were requested only once. It uses a Bloom filter to remember what has been requested and caches an object only on its second request, which keeps one-time objects out of the cache.
• Web caches. The counting Bloom filter was invented for Summary Cache, a scheme in which web proxies share compact summaries of what they hold; the Squid proxy's cache digests use the same idea.
• Databases more generally. PostgreSQL ships a bloom index type as an extension, and some systems use Bloom filters to speed up distributed joins by sending a filter of join keys instead of the keys.
• Bitcoin. BIP 37 (2012) let lightweight wallets send a Bloom filter of their addresses to full nodes, which returned only matching transactions. It turned out to reveal more about the wallet's addresses than intended, and later designs (BIP 157 and 158) replaced it.
• Browsers. Early versions of Google Chrome kept a Bloom filter of known malicious URL prefixes for Safe Browsing, checking a server only when the filter matched. It was later replaced with a different compact structure.

Burton H. Bloom described the structure in "Space/Time Trade-offs in Hash Coding with Allowable Errors", published in Communications of the ACM in July 1970. His example was a hyphenation program: most English words can be hyphenated by simple rules, and only a minority need a dictionary entry stored on disk. A small filter of the exceptions kept in memory meant the disk was read only for words that were probably exceptions.

Bloom filters became widely used in networking in the late 1990s and 2000s, a period summarised by Andrei Broder and Michael Mitzenmacher in their survey "Network Applications of Bloom Filters". The many variants listed above came from the same period of renewed interest, and newer static filters such as xor and ribbon filters continue to appear.