Bloom Filters: The Data Structure That's Allowed to Lie

You know that moment when you're signing up for something, you type your username, and before you even finish, it goes "sorry, that's taken"?

I never really thought about it until one day it hit me. Instagram has like two billion users. Every time someone types a letter, it's checking whether that name exists. For millions of people. At the same time. How is that not melting a server somewhere?

Turns out there's a pretty sneaky trick a lot of systems use for this kind of thing. It's called a Bloom filter, and the funny part is that it's allowed to lie to you. Just not in the way you'd think.

(Quick side note: it's named after Burton Bloom, the guy who came up with it back in 1970. Nothing to do with flowers. I checked.)

First, the dumb ways

If you asked me to build a username checker in an interview, my first answer would be: just keep all the usernames in a list and loop through it.

Which works great. Until you have 500 million users and you're looping through all of them every time someone hits a key. Yeah, no.

Okay, fine, use a hash set then. Lookups are instant. Problem solved?

Kind of. But a hash set has to actually store every single username. 500 million strings, plus all the extra stuff a hash set keeps around, is easily tens of gigabytes of RAM, and you'd want that on every server doing the check. That's a lot of memory just to answer a yes/no question.

And that's the thing that bugged me. We don't actually care what the usernames are. We just want to know if we've seen one before. Feels like we should be able to do that without hoarding all the data.

A row of light switches

Here's how a Bloom filter works, and honestly it's simpler than it sounds.

Imagine a row of 10 light switches, all off. That's it. That's your storage.

Now you also have 3 little machines (hash functions, if you want the fancy name). You feed a word into each one, and each spits out a number between 0 and 9. Each machine scrambles the word in its own way, so one word gets three different numbers. And it's consistent: same word in, same numbers out, every time.

Let's add nightowl. The three machines say 1, 4 and 7. So I flip those switches on.

Now let's add coffee. The machines say 3, 4 and 8. Switch 4 is already on, whatever, it just stays on:

Now someone tries to sign up as pancake. We run it through the machines and get 1, 5 and 7. We check those switches. 1 is on, 7 is on, but 5 is off.

And that's all we need. If "pancake" had ever been added, switch 5 would be on. It's not. So pancake is free, 100%, no doubt about it.

Notice we never actually saved a single username anywhere. Just some switches.

Obviously a real Bloom filter isn't 10 switches. It's millions of them. Same idea though, and 10 is a lot easier to draw.

Okay so where's the lying part

Last one. Someone tries tacos. The machines say 1, 3 and 8.

All three are on. So the filter goes "yep, tacos is taken."

Except... nobody ever added tacos. Switch 1 got turned on by nightowl. Switches 3 and 8 got turned on by coffee. Two completely unrelated names just happened to cover every switch tacos needed. The filter got fooled.

That's called a false positive, and it's the whole deal with Bloom filters. The switches don't remember who turned them on. So sometimes they say yes when the real answer is no.

But here's what makes it actually useful. It can never go the other way. If you added something, its switches are on, and nothing ever turns them off. So the filter can't forget you.

Which means:

• When it says no, trust it. It's always right.
• When it says yes, it means "probably, go double check."

And for the username thing, that's perfect. Most names people type are free, so the filter shuts those down instantly without touching the database. Only the "maybe taken" ones go for a real lookup. You just skipped most of the work.

So when tacos comes back as "maybe taken", the database takes a look, sees it's actually free, and lets you have it. The lie cost us one extra lookup. Nothing more.

So how often does it lie?

Depends on how you set it up. More switches means fewer accidental overlaps. Too few switches and eventually everything's on and the filter just says yes to everything, which is useless.

This is also why we use three machines and not just one. With one machine, a single unlucky overlap fools the filter. With three, a fake name has to get unlucky three times in a row, which is way less likely. But you can't go crazy with it either, because every extra machine flips more switches per name and the row fills up faster. There's a sweet spot, and a formula that finds it for you.

I'll spare you the actual formula though. The rule of thumb that actually matters:

About 10 switches per name gets you a 1% false positive rate.

Want it 10x more accurate? Add roughly 5 more switches per name.

So back to our 500 million usernames. Each switch is just a single bit, so at 1% that's around 600 MB. Compare that to the tens of gigabytes a hash set needed. Same question answered, a fraction of the memory, and only about 1 in 100 free names ends up making a pointless trip to the database.

That's the trade. You give up being perfect, you get something way smaller and faster.

This stuff is everywhere

Once I learned about this I started seeing it all over the place:

• Databases like Cassandra and RocksDB keep one of these per file on disk. Before they bother reading a file to find your data, they ask the filter. If it says no, they skip the file. Disk reads are slow, so this saves a ton.
• Chrome used one back in the day for Safe Browsing. It kept a tiny filter of dangerous URLs on your machine and only pinged Google when a site came back as a "maybe."
• Feeds that don't want to show you the same post twice. If the filter wrongly thinks you've seen something, you just miss one post. Nobody's dying over that.

Stuff it can't do

It's not magic though.

You can't delete anything. Say you want to remove nightowl, so you turn off switches 1, 4 and 7. Congrats, you just broke coffee too, because it was using switch 4. (There's a version called a counting Bloom filter that fixes this by keeping a small counter instead of an on/off switch.)

You also can't list what's inside. You can only ask "is this in there?" You'll never get the names back out.

And you kind of have to know your size upfront. If you plan for a million items and shove in ten million, almost every switch ends up on and it starts saying yes to everything.

The code is tiny

I won't dump a whole implementation on you, but the core of it is genuinely just this:

// hashes(word) runs the word through the 3 machines
// and gives back the switch positions, like [1, 4, 7]

add(word) {
  for (const i of this.hashes(word)) this.switches[i] = 1;
}

mightHave(word) {
  return this.hashes(word).every(i => this.switches[i] === 1);
}

Add = flip some switches on. Check = are they all on? That's the entire data structure. Everything else is just picking good hash functions and deciding how many switches you need.

If you want to play with it, try writing one yourself, throw in 100k random words, then check 100k different ones and count how many it wrongly says yes to. Watching the false positive rate land almost exactly where the rule of thumb says it will is weirdly satisfying.

So yeah

What I love about Bloom filters is the mindset more than the code. Most of the time we're obsessed with making things 100% correct. This thing goes "nah, I'll be wrong sometimes, but only in a way that doesn't hurt, and I'll be ridiculously cheap in return." And somehow that's good enough to power real databases.

Also, if you read my pigeonhole principle post, this is basically pigeonhole in the wild. You're cramming millions of names into a few switches, so collisions aren't a bug, they're guaranteed. A Bloom filter just lets you pick how often they bite you.

So next time an app tells you your username's taken before you've even finished typing, there's a decent chance a bunch of light switches answered first.