Bloom Filters: What a Username Check Can Actually Tell You

A signup page checks a username and quickly says it might already exist. How can we avoid some expensive lookups without storing every name in a large in-memory set?

A Bloom filter gives us a compact preliminary check. Its answers are deliberately uneven: it can rule something out of the represented set, but a positive result still needs confirmation.

Let's build a tiny filter for usernames, then connect it to a signup flow that must never create duplicates.

Store positions instead of the original names

A basic Bloom filter starts with an array of zero bits. Hashing an inserted name gives us several positions, and we set those positions to one.

To query a name, calculate the same positions. If any required bit is zero, the name was not inserted into this intact filter. If all are one, it might have been inserted.

Why only "might"? Different names can set overlapping bits. Their combined positions may make a third name appear present even though we never added it.

This is a membership test for the represented set, not a list we can read back. We can't reconstruct the stored usernames from the bits.

Try a deliberately small filter

This Python example uses 32 bit positions and derives three positions from a SHA-256 digest. It is a teaching construction, not a production sizing or hashing recommendation.

from hashlib import sha256

bits = 0

def positions(name):
    return [byte % 32 for byte in sha256(name.encode()).digest()[:3]]

def add(name):
    global bits
    for position in positions(name):
        bits |= 1 << position

def might_contain(name):
    return all(bits & (1 << position) for position in positions(name))

add("chai_notes")
add("code_dosa")
assert might_contain("chai_notes")
assert might_contain("code_dosa")

The integer holds the toy bit pattern; Python's object overhead isn't a production memory measurement. The important behaviour is shared positions: adding a name sets bits without preserving which name set each one.

Because the filter is tiny, we can find uninserted names whose positions are already set. With this exact construction, notes_402 maps to positions 22, 4 and 5, all set by the two inserted names:

assert might_contain("notes_402")  # We never inserted this name.

That match is a false positive, not evidence that our insert code secretly added another account. Try generating more candidate names and compare positive results with the names we actually inserted.

A positive result should send us to the real lookup

For a username check, the flow can be:

1. Normalize the candidate under the account system's actual rules.
2. Query a correctly maintained filter for that same normalized set.
3. If the filter says "might exist," check the authoritative store.
4. Return the availability result under the signup contract.

Don't mark every positive result as taken. That would reject some genuinely free usernames because false positives are part of the data structure's design.

The Redis Bloom-filter guide describes its membership and sizing trade-offs. A Bloom filter may reduce costly negative lookups, but it doesn't prove how any particular email provider implements its signup page or how quickly that provider responds.

A negative answer only describes the set we represented

The mathematical no-false-negative property assumes the filter includes the relevant inserted items, uses consistent hashing and remains intact.

If a new account is saved but hasn't reached this filter yet, the filter may say absent while the database already contains it. That is a stale representation, not the basic Bloom algorithm breaking its promise about inserted items.

Does "not in this filter" mean "not in the database right now"?

Only when the maintenance and freshness arrangement justifies that conclusion. If the filter is unavailable, rebuilding or known to be behind, use a supported fallback rather than treating an incomplete copy as certainty.

The database still decides who gets the name

Two signup requests can both check a free username before either creates the account. Neither an exact availability lookup nor a Bloom result reserves it.

The creation path needs an authoritative uniqueness rule, such as a database unique constraint under the chosen normalization. Handle a conflict as an expected race and return useful feedback.

The filter helps avoid work in suitable reads. It doesn't replace the final rule that prevents duplicate accounts. That distinction keeps a performance optimisation from quietly becoming the account system's judge.

Growth and deletion need a plan

As more names set more bits, false positives become more likely. Size the filter for the expected population and target error rate, then monitor whether it is still saving useful lookups. An almost-full filter answers "maybe" so often that its benefit shrinks.

A basic Bloom filter doesn't support simply clearing a deleted name's bits: another name may rely on those same positions. Rebuild or use a suitable deletion-capable structure when the workload needs it. Keep generation and rollout of new filters compatible with live account changes.

Measure the lookups you actually avoid

Start with the authoritative lookup cost and the mix of existing versus absent candidates. Adding hashing, memory access and maintenance is worthwhile only if it saves enough expensive work under the real traffic.

The filter's useful answer is a narrow one: this candidate is absent from the represented set, or it deserves a closer look. Pair that answer with freshness and authoritative uniqueness, and we can make signup checks cheaper without asking a probabilistic structure to decide who owns a name.