Data structures · 9 min

Bloom filter

Answer “have I seen this before?” for a hundred million names in about 10 bits each. It never wrongly says no.

You run the sign-up page for a site with 100 million users. Every time someone types a username, the page should say straight away whether it is taken.

Asking the database on every keystroke is slow and expensive. So you want an answer in memory. How small can “who already has a name” get?

The obvious way: keep every name

Put all 100 million usernames in a set in memory. A username is around 10 characters, and each stored string carries a few bytes of bookkeeping, so call it 16 bytes a name. That is 1.6 GB, before the set’s own overhead, on every server that runs the sign-up page.

It gives perfect answers, but it is the wrong size. Notice something, though: most people typing a name are typing a free one. What you really need is a fast, cheap “no, that one is free”. A rare “maybe taken, let me check” is fine, because the database can settle it.

A Bloom filter is built for exactly that trade. It forgets the names themselves and keeps only a row of on/off switches.

The trick: a row of switches

Start with a row of, say, 32 bits, all 0. To add the name “haruto”:

1. Hash “haruto” to get a big number.
2. Divide it by 32 and keep the remainder. That is a number from 0 to 31: a bit position.
3. Do this 3 times, each time with a different tag on the end (“haruto#1”, “haruto#2”, “haruto#3”), so you get 3 positions.
4. Turn those 3 bits on.

To ask “is haruto taken?”, do the same 3 hashes and look at the same 3 bits. That is the whole data structure: one row of bits and a recipe for picking positions.

Why “no” is certain and “yes” is only “probably”

If “haruto” had been added, its 3 bits would have been turned on, and bits are never turned off. So if any one of them is 0, “haruto” was never added. That “no” is always right: a Bloom filter has no false negatives.

A “yes” is weaker. Different names share bits. After enough adds, a name that was never added can find all 3 of its bits already on, each switched on by some other name. The filter says “probably yes” and is wrong. That is a false positive.

So the size of the row is what sets the error rate. The useful question is: how many bits per name do I need?

How many bits per name?

First, how many hashes? It pulls two ways. More hashes means a fake name has to match more bits by luck, which helps. But every name also turns on more bits, so the row fills faster, which hurts. The best point is where about half the bits end up on. The demo works this out for you: once you’ve added names, it shows “Best for … names” next to the Hashes buttons.

With the best number of hashes, the size depends only on the error rate you can live with, not on how long the names are:

Back to the sign-up page. At 1% the filter is 120 MB instead of 1.6 GB. For a free name, 99 times in 100 it says “definitely not” and the page answers instantly; only 1 in 100 free names goes to the database. For a taken name it always says “probably yes”, and the database confirms.

The filter can’t grow in place, because every position depends on the row’s length. If you expected 100 million names and got 200 million, the same 120 MB now holds 4.8 bits a name and the rate climbs past 10%. The fix is to build a bigger filter from the database.

What it looks like in code

Everything above fits in a few lines. The only thing to notice is that add and might_contain compute the same positions; one sets them, the other reads them.

bits = [0] * m              # m bits, all off
k = 7                        # hashes per name

positions(name):
    return [hash(name + "#" + i) % m for i in 1 .. k]

add(name):
    for p in positions(name):
        bits[p] = 1

might_contain(name):
    for p in positions(name):
        if bits[p] == 0:
            return False     # definitely never added
    return True              # probably added

Where you will meet one

The pattern is always the same: a cheap “definitely not” saves an expensive lookup, and a rare wrong “maybe” only costs one wasted lookup.

• Some databases (Cassandra, RocksDB, HBase) write data into many separate files on disk, so finding one key could mean opening all of them. Each file gets its own filter, and a read only opens files whose filter says “maybe”. The LSM tree concept shows why they have so many files.
• Web crawlers remember which URLs they have already fetched. A false positive means one page is skipped, which is fine.
• CDNs, the caching servers close to users, see lots of files requested exactly once. Caching those wastes space, so Akamai caches a file only on its second request, and a Bloom filter remembers the first.