A bloom filter can’t tell you a username is taken.

It can only tell you, with certainty, that it isn’t. I built one in Go to find out whether that is enough to protect a database.

Type a name to see which three switches it hashes to. Try “carol”, then “zara”.

Added: none yet
Switches on: 0 of 32
Chance a new name looks taken: 0%

32 bits · 3 hashes per name

On Off Hash target

The question

I kept seeing the same example: sites use bloom filters to check whether a username is free. I had always assumed they just ask the database. So I built both, in a language I was new to, and measured the difference.

The filter above works the same way as the real one, just smaller. It is a row of switches. Adding a name turns on the switches its hash points to. Checking a name looks at those switches.

Any switch off means definitely free. Had the name been added, every one of its switches would be on.
All switches on means maybe. Other names share switches, so only the database can say for sure.
Names can’t be removed. Turning a shared switch off would make another name look free.

Keep adding names above and watch the chance of a false “maybe” climb. That is why a real filter is sized up front: 100,000 names at a 1% error rate needs about 958,000 switches and 7 hashes per name, around 117 KB.

What I built

A Go server with a live-check page, backed by Postgres and seeded with 100,000 users. One setting switches between three checkers: Postgres only, my own filter in the server’s memory, or a shared RedisBloom filter.

Normalize the name
Ask the filter
No Answer “available” without touching Postgres Maybe Ask Postgres, which has the final say

Every availability check takes this path.

Signup never checks first

It inserts and lets Postgres’s unique constraint pick the winner. Fifty simultaneous signups for one name produced one success and 49 “taken” responses.

Filter first, then database

If the insert fails, the name is just an extra false positive. The reverse order would briefly call a taken name free.

Checks fail open, signups fail closed

With Redis stopped, checks fell back to Postgres and stayed correct. Signups were refused rather than stored where the filter couldn’t see them.

Rebuild aside, then swap

The shared filter is rebuilt under a temporary key and renamed into place in one step, so no server ever reads a half-built filter.

The filter itself is about 60 lines of Go: bits packed into bytes, FNV-1a with double hashing, and a read/write lock so thousands of checks can run at once. Its tests prove there are no false negatives and measure the false-positive rate at 1.14%.

Results

The traffic was 90% free names and 10% taken ones, from 50 virtual users over 30 seconds. Taken names always need the database, so about 10% is the floor. The remaining 1% or so are false positives.

k6 load test, everything on one laptop
Checker	Requests per second	Median	95th percentile	False positives
Postgres only	36,953	1.05 ms	1.66 ms	n/a
Memory filter	46,856	0.08 ms	5.05 ms	1.17%
RedisBloom	40,895	0.98 ms	2.51 ms	0.50%

The surprise

Postgres alone answered 37,000 checks a second. At this size, the filter wasn’t needed.

One hundred thousand rows fit in memory, and a unique index finds any name in a few steps. On one machine, a trip to Redis cost about as much as a trip to Postgres. In the browser, the filter shaved half a millisecond off a five-millisecond request, which nobody can feel.

What it did change was how much work reached the database: about nine in ten questions never arrived. That matters when the database is the expensive, shared part of the system: tables too large for memory, a database across the network, millions of people typing. It is also why the heaviest users of bloom filters are storage engines like Cassandra and RocksDB, which ask one before reading a file from disk.

So the example I kept seeing is true, but for a different reason than I expected. A bloom filter protects the database. It doesn’t make the page faster.

Limits and next steps

The load generator shared a laptop with the server, Postgres, and Redis, so the numbers compare the checkers rather than predict production. Each run also let the faster checker receive more traffic. A fixed-rate test would compare latency more fairly.