Username Availability with Bloom Filters

Explain how you'd check username availability for a service with billions of users without hitting the database on every keystroke.

Mid-Level questions

System Designintermediate

// interview question

Explain how you'd check username availability for a service with billions of users without hitting the database on every keystroke.

Sample answer

Use a Bloom filter as the first layer. A Bloom filter is a space-efficient probabilistic data structure that can tell you with certainty that a username is available (not in the set) or with high probability that it is taken. You load all existing usernames into the filter at startup. When a user types a username, you check the Bloom filter first. If the filter says 'not present,' the username is definitely available and you skip the database entirely. If the filter says 'possibly present,' you then query the database to confirm. For billions of usernames, a Bloom filter with a 1% false positive rate needs roughly 1.2 GB of memory, which fits comfortably on a single server. This eliminates the vast majority of database lookups.

Why this matters

This question tests whether candidates can identify the right data structure for a probabilistic membership check at scale. Bloom filters appear in many production systems: Chrome uses one to check malicious URLs, databases use them to skip unnecessary disk reads, and CDNs use them for cache filtering. The interviewer wants to see that you understand the false-positive tradeoff, can reason about memory usage, and know when an approximate answer is good enough to avoid an expensive exact lookup.

Code examples

Simple Bloom filter implementation

python

import hashlib
import math

class BloomFilter:
    def __init__(self, expected_items, false_positive_rate=0.01):
        # Calculate optimal size and hash count
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.hash_count = self._optimal_hashes(self.size, expected_items)
        self.bit_array = bytearray(self.size // 8 + 1)
        print(f"Filter size: {self.size / 8 / 1024 / 1024:.1f} MB")
        print(f"Hash functions: {self.hash_count}")

    def _optimal_size(self, n, p):
        return int(-n * math.log(p) / (math.log(2) ** 2))

    def _optimal_hashes(self, m, n):
        return int((m / n) * math.log(2))

    def _get_hashes(self, item):
        hashes = []
        for i in range(self.hash_count):
            h = hashlib.sha256(f"{item}:{i}".encode()).hexdigest()
            hashes.append(int(h, 16) % self.size)
        return hashes

    def add(self, item):
        for pos in self._get_hashes(item):
            self.bit_array[pos // 8] |= (1 << (pos % 8))

    def might_contain(self, item):
        return all(
            self.bit_array[pos // 8] & (1 << (pos % 8))
            for pos in self._get_hashes(item)
        )

# For 1 billion usernames at 1% false positive rate
bf = BloomFilter(expected_items=1_000_000_000, false_positive_rate=0.01)
# Output: Filter size: ~1144.5 MB, Hash functions: 7

bf.add("alice")
bf.add("bob")

print(bf.might_contain("alice"))   # True (definitely added)
print(bf.might_contain("charlie")) # False (definitely NOT added)
print(bf.might_contain("bob"))     # True (definitely added)

Username availability API with Bloom filter layer

python

from fastapi import FastAPI
import redis

app = FastAPI()
r = redis.Redis()

# Redis has built-in Bloom filter support via RedisBloom module
# BF.RESERVE usernames 0.01 1000000000
# BF.ADD usernames "alice"

@app.get("/check-username/{username}")
async def check_username(username: str):
    username = username.lower().strip()

    # Layer 1: format validation (instant, no I/O)
    if len(username) < 3 or len(username) > 30:
        return {"available": False, "reason": "invalid_length"}

    # Layer 2: Bloom filter check (sub-millisecond, in-memory)
    possibly_taken = r.execute_command("BF.EXISTS", "usernames", username)
    if not possibly_taken:
        # Bloom filter says NO -> definitely available
        return {"available": True}

    # Layer 3: database confirmation (only for Bloom positives)
    # This path is hit for ~1% false positives + actual taken names
    taken = await db.check_username_exists(username)
    return {"available": not taken}

Common mistakes to avoid

Saying you would query the database on every keystroke for real-time feedback
Confusing false positives and false negatives: Bloom filters never produce false negatives, only false positives
Not knowing how to estimate the memory required for a given number of items and false positive rate
Forgetting that Bloom filters do not support deletion without switching to a counting variant
Proposing a simple HashSet, which would require far more memory for billions of entries

Likely follow-ups

What happens when a new user registers? How do you keep the Bloom filter in sync?
Can you remove an element from a Bloom filter? If not, what alternatives exist?
How would you handle the filter across multiple application servers?
What is a counting Bloom filter, and when would you use one instead?
How does a cuckoo filter compare to a Bloom filter for this use case?

Answer out loud first, then check yourself against the model answer.

Practice all Mid-Level questions More System Design questions

#system-design#bloom-filters#data-structures#scalability#performance

Also worth your time on this topic

Quiz

Back-of-the-Envelope Estimation Quiz

The napkin-math skill that makes or breaks a system design interview: turning users into QPS, data into storage, traffic into bandwidth, and knowing the latency numbers every engineer should have memorised.

16-22 minutes

Interview

Instant Credit Card Validation

How does a credit card form validate numbers instantly, before even contacting the bank?

junior

Article

How Does It Work So Fast? The Engineering Behind Instant UI Responses

Credit card validation, username checks, autocomplete, URL shorteners - they all feel instant. Here is what is actually happening under the hood in each case.

Username Availability with Bloom Filters

More System Design interview questions

Also worth your time on this topic

Back-of-the-Envelope Estimation Quiz

Instant Credit Card Validation

How Does It Work So Fast? The Engineering Behind Instant UI Responses