⚡

System Design: Fast Username Lookups

System Architecture Deep Dive
✍️ Curated by Rajat Kumar | LinkedIn • GitHub

How Gmail Checks Billions of Usernames in Milliseconds

When you type a username into a sign-up form, the system queries billions of existing accounts. Standard database lookups fail at this scale due to heavy disk I/O and latency. Explore how high-scale systems combine Bloom Filters and Two-Step Architecture to return instant results with minimal RAM.

⚡
Bloom Filter Check
< 0.1 ms (In-Memory)
💾
Memory Overhead
~1.2 Bytes / Username
🛡️
False Negatives
Strictly 0%

1. Interactive Bloom Filter Playground

This interactive module demonstrates how a Bloom Filter works under the hood. A Bloom Filter uses multiple hash functions ($k=3$) to map strings into a bit array. Test adding existing usernames to the filter, then check new usernames to see true negatives, true positives, and probabilistic false positives in action!

Sets bits at 3 computed hash locations to 1.

Evaluates bit positions in real-time as you type.

In-Memory Bit Array (32 Bits Simulation) Active Bits: 0 / 32
Ready

Enter a username above to start lookups

The Bloom Filter will check memory indices without querying disk storage.

Hash indices: h1(-), h2(-), h3(-)
Quick Test Preset Scenarios:

2. The Two-Step System Architecture Flow

To eliminate false positives while keeping response times in microseconds, production systems use a dual-path architecture. The Fast Path (Bloom Filter in RAM) instantly filters out available usernames. The Slow Path (Database lookup) is only invoked when the filter signals a potential collision.

STEP 1 ⌨️

Frontend Request

User types a username in UI. Debounced input fires an API request to the API Gateway / Microservice edge layer.

Latency: ~1-5 ms (Network)
STEP 2: FAST PATH 🧠

In-Memory Bloom Filter

Evaluates bit indices in global RAM. If ANY bit is 0, username is guaranteed 100% available.

Returns Available instantly ~0.01 ms
STEP 3: SLOW PATH 🗄️

Database Verification

Only triggered if Bloom Filter returns "Probably Taken". Queries SQL/NoSQL store to confirm or dismiss false positives.

Filter bypass rate: ~1% ~15-50 ms

Simulate System Request Path:

// Select a test case above to trace the execution request lifecycle...

3. Scale, Memory Capacity & Math Calculator

Why not just use Redis RAM caching for all usernames? Below is a comparative memory consumption breakdown across data sizes, along with an interactive mathematical calculator to compute exact bit requirements ($m$) and optimal hash functions ($k$) for your scale.

Bloom Filter Sizing Calculator

100,000,000 (100M)
1% (0.01)
Required Bit Array ($m$)
114.1 MB
9.6 bits per user
Optimal Hash Count ($k$)
7 Hash Functions
$k = (m/n) \times \ln(2)$
Comparison: Storing 100M raw usernames (~20 bytes each) in Redis key-value cache requires ~2.5 GB RAM (plus hash map overhead). The Bloom filter requires only ~114 MB!

RAM Requirement Comparison by Scale (MB)

4. Interview Strategy & System Comparison

Use this summary matrix and interview talking points to structure your response cleanly when asked this system design question in technical interviews.

Approach Latency RAM Footprint Scalability Trade-offs & Notes
Direct SQL Query Slow (~30-100 ms) Minimal (Disk reliant) Poor Requires disk I/O. Concurrent sign-ups will overwhelm database connection pool.
In-Memory Redis Cache Fast (~2-5 ms) High (~25 GB / 1B) Moderate Fast RAM lookups, but storing billions of raw text string keys is financially expensive.
Bloom Filter + DB (Standard) Blazing (< 0.1 ms) Tiny (~1.2 GB / 1B) Excellent Probabilistic structure. No false negatives. Filters out 99% of requests before DB.
Cuckoo Filter Alternative Blazing (< 0.1 ms) Low (~1.4 GB / 1B) Excellent Supports deletions of items (unlike standard Bloom Filters) with better cache locality.
🌍

Edge & CDN Distribution

Mention to the interviewer that Bloom Filters are small enough to be replicated to Edge locations (Cloudflare Workers, Fastly, or local regional caches). Users checking availability hit a local edge node in their country, reducing round-trip latency.

🔄

Handling Account Deletions

Standard Bloom filters cannot delete items (unsetting a bit might break another username's hash). Discuss Counting Bloom Filters (which use counters instead of single bits) or Cuckoo Filters if account deletion/username freeing is required.