Bloom filters, visually

We have a suppression list: email addresses that have bounced, unsubscribed or complained, which we must never send to again. It’s about 30 million addresses, and every outgoing email gets checked against it. For a long time that check was a database lookup, an indexed one, fast enough. Then we started sending more mail in bursts, and that one indexed lookup became the busiest query on the database by a long way, and the annoying thing was that the answer was almost always “no, not on the list”.

That’s the exact situation a Bloom filter is for. It’s a data structure that can tell you an item is definitely not in a set, or that it probably is, using a small fixed amount of memory no matter how big the items are. For us, “definitely not” means send without touching the database, and “probably” means go and check. We now hit the database for about 1% of sends, plus the ones that really are on the list, instead of all of them, and the filter fits in under 40 MB of RAM.

It was invented by Burton Bloom in 1970, in a paper with the very 1970 title “Space/Time Trade-offs in Hash Coding with Allowable Errors”. His example was a hyphenation program: most words follow simple rules, the rest need a lookup in a dictionary on slow disk, and you’d like to skip the disk for the common case. Same problem, forty-six years earlier.

How it works

You have an array of m bits, all zero, and k different hash functions, each of which maps an item to a position in the array.

To add an item, hash it with all k functions and set those k bits to 1.

To check an item, hash it with the same k functions and look at those k bits. If any of them is 0, the item was never added, because adding it would have set that bit. If they’re all 1, the item was probably added, or else other items happened to set all of those bits between them.

Here’s a tiny one: 16 bits, 3 hash functions, two items added. (The positions are made up, a real hash would scatter them less neatly.)

“cow” is a false positive: we never added it, but cat and dog between them happened to set all three of its bits. That’s the trade. There are no false negatives, ever, as long as you use the same hash functions for adding and checking, but there is some rate of false positives, and the whole design of a Bloom filter is choosing m and k so that rate is one you can live with.

Notice also that you can’t remove anything. Clearing bit 7 to delete “cat” would also delete half of “dog”. There are variants that support deletion, counting Bloom filters replace each bit with a small counter, but the plain version only grows. For our suppression list that’s fine, because once an address is on it, it stays on it.

The math

This is the part I like, and it’s short.

Say the hash functions are good, so each one picks a position uniformly at random. After adding one item with one hash function, the chance that a given bit is still 0 is 1 − 1/m. After adding n items with k hash functions each, that’s kn independent tries, so the chance a given bit is still 0 is

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

using the usual (1 − 1/x)^x ≈ 1/e. A false positive means all k bits of a new item happen to be 1, so

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

Strictly, the k bits being set aren’t quite independent events, so this is an approximation, but it’s a very good one for any realistically sized filter.

Now there’s a tension in k. More hash functions means more bits to check, so a false positive needs more coincidences. But more hash functions also means each item sets more bits, so the array fills up faster. Take the derivative and you find the best k is

k = (m/n) · ln 2

and at that k exactly half the bits in the array are set, which is a nice result: the optimally loaded filter is the one with maximum entropy. Plug it back in and the false positive rate becomes (1/2)^k, or about 0.6185^m/n. So the false positive rate falls exponentially with the number of bits you spend per item.

Here’s what that looks like with 10 bits per item, for different k:

The curve is flat around the minimum, so you don’t need to get k exactly right. Going from one hash function to three makes a huge difference, and going from seven to eight makes almost none.

Sizing one

In practice you start from the other end: you know n, the number of items, and p, the false positive rate you can tolerate, and you want m and k. Rearranging:

m = −n · ln p / (ln 2)², and k = (m/n) · ln 2

That works out to about 1.44 · log₂(1/p) bits per item. A 1% rate needs about 9.6 bits per item and 7 hash functions. 0.1% needs about 14.4 bits per item and 10 hash functions. Every extra factor of ten in accuracy costs you about 4.8 more bits per item.

For a million items at 1%, that’s 9,585,059 bits, about 1.2 MB, whatever the items are. A million email addresses in a hash set would take tens of megabytes once you count the strings and the overhead. Our 30 million addresses at 1% is about 36 MB.

In code

You don’t need k truly independent hash functions. Kirsch and Mitzenmacher showed in 2006 that you can take two hashes h1 and h2 and use h1 + i·h2 for i = 0 to k−1, with no real loss in the false positive rate. So one MD5 (fine here, we need good mixing, not cryptographic strength) gives you as many as you want:

import hashlib, math

class BloomFilter:
    def __init__(self, n, p):
        self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
        self.k = round(self.m / n * math.log(2))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        d = hashlib.md5(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos // 8] |= 1 << (pos % 8)

    def __contains__(self, item):
        return all(self.bits[pos // 8] & (1 << (pos % 8))
                   for pos in self._positions(item))

I tested this with a million items at p = 0.01. It picked m = 9,585,059 and k = 7, used 1.2 MB, had no false negatives (it can’t), and when I checked 200,000 strings that weren’t in it, 0.996% came back as false positives. The math works. (Our real one is in C#, because the mail pipeline is .NET, but it’s the same thirty lines.)

If you’ve read my hash table post, the trade-off is the mirror image of that one. A hash table stores the keys so that it can be exactly right, and pays for it in memory. A Bloom filter throws the keys away, keeps only a few bits of evidence about each one, and pays in being wrong sometimes, in one direction only.

Where they show up

Once you know what they look like, you see them all over the place. Google’s Bigtable paper in 2006 described keeping a Bloom filter per file so that lookups for rows that don’t exist don’t have to touch the disk, and Cassandra and HBase both do the same. Bitcoin’s lightweight wallets send a Bloom filter of their addresses to full nodes, so the node can send back only the relevant transactions, although it turns out that leaks more about which addresses are yours than anyone intended. Chrome used one for Safe Browsing for a while, to check URLs against the malware list locally before asking Google.

If you need deletion, look at counting Bloom filters, or at cuckoo filters, a 2014 design that supports deletion and uses less space than a Bloom filter when you need a low false positive rate. I haven’t used one in production yet, but it’s next on my list to try.