RightSignal · Friday, October 16

Concept of the day1 / 3

Bloom filters

The concept

How a site can say a username is free without searching every account

A Bloom filter is a tiny memory aid that answers one question: have I seen this before? It can answer definitely no or probably yes, and it is fast because it never stores the items themselves.

Picture a long row of light switches, all off. Each name you add flips on a few switches chosen by a fixed recipe that scrambles the name.

Concept of the day2 / 3

Bloom filters

Real-life use case

A database skips opening a file because the answer is surely not in it

Databases keep a Bloom filter for each file on disk. Before reading a slow disk file to look for a record, they ask the filter first. If it says no, the disk read is skipped.

The same trick can let a sign-up page rule out many usernames instantly, and only check the full account list when the filter says maybe.

Concept of the day3 / 3

Bloom filters

How it helps

If even one of a name's switches is off, it was never added

To check a name, run the same recipe and look at its switches. If any one is off, that name was never added, guaranteed.

If all are on, the name was probably added, but other names might have flipped those same switches by chance. So a yes gets a quick double-check in the real list. A bigger row of switches makes those false alarms rarer.

Your RightSignal

Topics in News

How a site can say a username is free without searching every account

A database skips opening a file because the answer is surely not in it

If even one of a name's switches is off, it was never added

Got it?