Bloom Filters

When you try to sign up on platforms like Instagram, Facebook, Google, or LinkedIn, you must have noticed a common feature:

As soon as you type a username, within a fraction of a second the interface shows:

✓ Username available

or

✗ Username already taken

And it happens almost instantly.

Have you ever wondered how this works internally?

Because if you think about it, these platforms may have hundreds of millions or even billions of users. Checking username availability should technically require searching through a massive database.

Yet the response is almost immediate.

The First Intuition: Query the Database

The most straigtforward implementation might look like this:

Whenever a user types a username, the frontend sends a request to the backend.

The backend runs a query like:

SELECT * FROM users WHERE username = "thejat" LIMIT 1;