How Gmail Knows Your Username Is Taken Before You Finish Typing

Last week I was signing up for a throwaway Gmail account (don’t ask why) and I noticed something I’d taken for granted a thousand times before. I typed three letters and it already knew the name was taken. Not after I hit enter. Not after a loading spinner. While I was still typing.

I’d built signup forms before. I knew the naive approach. But I’d never actually thought about how Google does this for, you know, a few billion accounts. So I dug in. And the answer is cooler than I expected.

What I Would Have Built (And Why It Would Explode)

When I built my first signup form, the logic was dead simple:

SELECT * FROM users WHERE username = 'anindra';

No row? Name’s free. Row exists? Taken. Ship it.

And it worked great, for the maybe 5,000 users my side project ever saw. The query came back in 15ms. Nobody ever complained.

Then I started thinking about what happens if you’re Google. You’ve got billions of accounts. Every single person on Earth is hammering this endpoint while typing, backspacing, typing again. Each keystroke might fire a check. You’re looking at hundreds of thousands of these queries per second, all hitting a table with billions of rows.

That SELECT query goes from taking 15ms to taking… well, nobody knows, because your database catches fire first.

The three things that kill you:

1. You can’t scan billions of rows that fast. Even with a good index: the sheer volume is a problem.
2. You’re not waiting for the user to finish typing. Gmail checks partial input in real time: which means way more requests than just one per signup attempt.
3. Every keystroke is a potential request. The throughput requirement is insane.

OK so raw database lookups are out. What do you do?

Start With the Right Question

The thing that clicked for me when reading about this is that the problem isn’t really “search through all usernames.” It’s “look up one specific name in a collection we’ve already organized.”

Those sound similar but they’re fundamentally different problems. The first is search. The second is lookup. And computer science has a very good tool for lookup: the hash table.

You’ve probably used one without thinking about it. A hash table is basically a wall of numbered pigeonholes. You feed in a key, a function tells you which hole to look in, and you check if something’s there. No scanning, no comparing, just straight to the answer.

The word “anindra” might map to slot 42. You go to slot 42. It’s either empty or it isn’t. Done.

The thing that makes this relevant to our problem is that a hash table with a billion entries still answers in roughly the same time as one with a hundred entries. The lookup time doesn’t grow with the data size. That’s the property we need.

But Google Doesn’t Actually Use a Hash Table

Here’s where it gets interesting. A regular hash table would work, but storing every single username in memory across multiple servers gets expensive fast. Google’s real solution is a variation called a Bloom filter, and honestly, it’s kind of a hack, but a brilliant one.

A Bloom filter doesn’t store the actual usernames. It stores evidence that a username exists. The way it works is almost absurdly simple:

You start with a big array of bits, all set to zero. When a username gets registered, you run it through several hash functions, and each function picks a position in the array and flips that bit to one.

To check if a name exists, you run it through the same hash functions and look at those positions. If any of them are zero, the name was never registered. Period. Not “probably not”, definitely not. You can tell the user the name is free with 100% confidence.

If all the positions are one, though… the name might be taken. Or those bits might have been flipped by a combination of other, unrelated names that happened to hash to the same positions. This is a false positive.

And that’s the whole deal with Bloom filters: they can tell you “definitely no” or “maybe yes,” and that’s it.

I remember learning about these in a data structures class and thinking “when would I ever use this?” Turns out, every time you check if a Gmail address is available.

Why False Positives Are Actually Fine

My first reaction when I learned about the false positive issue was: isn’t that bad? You’re going to tell someone their name is taken when it isn’t.

But think about it from the product side. What’s the worse outcome?

• False positive: User sees “name might be taken,” system checks the real database, finds out the name is actually free, and lets them have it. Maybe adds 50ms to the response. User doesn’t notice.
• False negative (the opposite error): System says “name is free,” two people end up with the same email address. That’s a catastrophic bug.

Bloom filters never make the second error. They only ever err on the side of caution. For username checking, that’s exactly what you want. The occasional extra database lookup is a tiny price to pay for never accidentally duplicating an address.

So the flow looks like:

                     Name definitely free (bits are 0)  ->  done, take it
User types a name -->
                     Maybe taken (bits are 1)           ->  ask the real database
                                                            to be sure

The Bloom filter eats almost all the traffic. The database only gets hit for the ambiguous cases, which are rare.

How Google Actually Wires This Up

Google’s internal system for this is reportedly called Baby Name, which is kind of funny given the scale we’re talking about.

From what I’ve been able to piece together, the architecture is roughly:

Each front-end server keeps a copy of the Bloom filter in its own RAM. Since the filter is just an array of bits, not actual usernames, it’s tiny. We’re talking megabytes, not gigabytes. Each server can answer the vast majority of checks locally, without talking to anything else.

When the filter says “maybe taken,” the server reaches out to the actual accounts database. That database holds the real usernames and is the final authority.

The interesting part is how new registrations get into the filter. You might think: just update the Bloom filter the moment someone signs up. But that would mean every new account triggers writes to every copy of the filter on every server. That’s a lot of coordination.

Instead, there’s a message queue in the middle. New usernames get pushed into a queue, and a background process batches them into Bloom filter updates. So there’s a small delay, maybe a few seconds, between when an account is created and when the filter reflects it. For the user, this doesn’t matter. Nobody is signing up for the same username twice within a five-second window.

The filters themselves get periodically rebuilt from scratch. You take the full list of current usernames, hash them all into a fresh bit array, and swap it in. It’s cheap to do, and it keeps the filters from getting bloated over time.

All the server copies get synced through update messages so they stay roughly consistent. It’s not perfectly real-time, but it doesn’t need to be. The Bloom filter is a fast first check, not the source of truth.

Do You Actually Need This?

Probably not. I’ll be honest, I got excited about Bloom filters after learning about this and then had to remind myself that my 10,000-user app does not need one.

If you’re at the scale where a simple SELECT with an index on the username column is taking more than a few milliseconds, you have other problems to fix first.

If you’re in the millions of users range, caching popular username checks and batching your database writes will probably buy you enough headroom.

Bloom filters start making sense when you’re at tens of millions of users or more and every millisecond of latency matters on a high-throughput endpoint. That’s a very specific set of circumstances, and most of us will never hit it.

That said, it’s worth understanding how they work, because the pattern, trading a small amount of inaccuracy for a massive speed gain, shows up everywhere in systems design. Once you see it, you start noticing it in bloom filters (pun intended), caching layers, CDN routing, and a bunch of other places.

What I Took Away From This

The thing I find most satisfying about this system isn’t the Bloom filter itself. It’s the design philosophy behind it. Google’s engineers looked at a problem that seems like it requires searching through billions of records and said: “What if we just… didn’t?”

Instead of making the search faster, they eliminated the search entirely. They precomputed a compact representation of the answer space and made the common case, “is this name free?”, into a lookup that takes nanoseconds. The expensive database query only happens for the rare edge case.

That pattern of “do less work, not faster work” is something I keep coming back to in my own projects. The fastest code is the code that never runs.

Anyway, next time you’re signing up for something and see that little green checkmark appear instantly, know that it’s not some magic database. It’s a bitmap and a few hash functions, doing a whole lot of very little very fast.

Mess around with it: Open Gmail in an incognito tab and start typing a username. Watch the suggestions pop up before you finish. Every single one of those suggestions was checked against billions of accounts in the time it took you to press the next key. Now you know how.