Start typing a username on a sign-up form and, before you've even reached the last letter, a little message shows up underneath telling you it's taken. Change a letter or add a number and it flips to available, as if the site had been waiting for you.
I got curious about how that works on a site with millions of accounts, maybe billions. I'd seen it listed as a common system design interview question, so before reading anything I tried to answer it on my own, and my first idea went in the wrong direction. Figuring out what the form is really asking took me from the database index that does most of the work to a data structure I'm only now getting my head around.
Where I started: ruling names out letter by letter
My first idea was to narrow the list as I typed. "m" rules out almost nothing, "ma" a bit more, "map" more still, and by the last letter only the exact name is left to check. It looked efficient, because each keystroke would build on the work of the one before.
That is the answer to a different question. Narrowing by prefix is how autocomplete works: show me everything that starts with these letters. The sign-up form asks something much smaller. Does this exact string exist, yes or no?
The intermediate answers don't help with that. Almost every short prefix matches a huge number of taken names, so knowing that "ma" has matches tells me nothing about "maple". The only result the user cares about is the one for the complete string, and as it turns out, the form shouldn't even ask about the partial ones.
Finding one name among billions
The lookup itself turned out to be the easy part. Put a unique index on the username column and the database keeps the names sorted in a B-tree. Each node of the tree is a page on disk, and depending on the page size and the length of the keys, it holds a few hundred of them, each pointing to another page one level down. To find a name, the database reads the root, picks the branch where the name would sort, and repeats until it lands on the name or on the spot where it would be.
Because every page fans out to hundreds more, the tree is very wide and very short. With 300 keys per node, four levels already cover 300⁴, about 8 billion entries. With 200 per node you need a fifth. For a table of two billion users, that means four or five hops from the root to the answer.
In practice it's cheaper still. Every lookup reads the top levels, so they stay in memory, and a single check costs at most a couple of page reads that aren't already cached. That's fast enough to run every time the user pauses.
One detail matters later: the index should be on a normalized form of the name, something like lower(username), so that "Maple" and "maple" collide instead of becoming two accounts.
The same index also settles what happens when two people submit the same free name at the same moment. Both INSERT statements reach the database, the index lets exactly one of them through, and the other fails with a duplicate-key error that the application can turn into "sorry, that name was just taken". It also means the green "available" under the field is only a hint, because the answer that counts is the one the INSERT gets.
The instant part happens in the browser
The "before you finish typing" part is mostly frontend work. If the form sent a request on every keystroke, typing "maple" would fire five requests, four of them about names nobody wants. So the form waits for a short pause, cancels whatever request is still in flight, and ignores any answer that arrives late.
const input = document.querySelector('#username');
const status = document.querySelector('#username-status');
let timer, controller, latest = 0;
input.addEventListener('input', () => {
clearTimeout(timer);
timer = setTimeout(check, 300);
});
async function check() {
controller?.abort();
controller = new AbortController();
const id = ++latest;
try {
const url = `/api/usernames/${encodeURIComponent(input.value)}/available`;
const res = await fetch(url, { signal: controller.signal });
const { available } = await res.json();
if (id === latest) status.textContent = available ? 'Available' : 'Taken';
} catch (e) {
if (e.name !== 'AbortError') status.textContent = '';
}
}
Two details are easy to miss. Aborting a fetch only tells the browser to stop waiting, and the server may still run the query. And the latest counter is there because an old response can slip through if it had already arrived when the abort happened. Without it, the label could briefly show the verdict on "map" while the user is looking at "maple".
The Bloom filter, which I'm learning right now
This is the part I'm still studying, and the one that struck me most.
A Bloom filter is an array of bits, all zero at the start, plus a few hash functions. To add a name, you hash it with each function and switch on the bits at those positions. To check a name, you hash it the same way and look: if any of those bits is off, the name was never added.
A toy version makes it concrete. Take 10 bits and two hash functions, and suppose (the values are made up) that they send "sunny" to bits 2 and 7, and "rocket" to bits 4 and 9. After adding both names, bits 2, 4, 7 and 9 are on.
Now check "pixel", which hashes to 3 and 7. Bit 3 is off, so "pixel" is definitely free. Then check "comet", which hashes to 2 and 9. Both bits are on, so the filter says it might be taken, even though nobody registered it. Bit 2 came from "sunny" and bit 9 from "rocket". That's a false positive.
A zero means the name was never added, guaranteed. A one only means somebody set that bit, and it may have been somebody else. So a Bloom filter can be wrong when it says "maybe", but it's never wrong when it says "no": there are no false negatives.
Its size depends on the error rate you accept. The optimal number of bits per name is -ln(p) / (ln 2)², which for a 1% false-positive rate comes to about 9.6 bits, with 7 hash functions. For two billion names that's around 19 billion bits, roughly 2.4 GB. A 10-character name stored as plain ASCII takes 80 bits on its own, so the filter is about an eighth of the bare list of names, and its size doesn't grow with their length.
I wouldn't write one myself, since there are solid implementations for most languages. What I wanted to understand was what it actually speeds up. A Bloom filter is fast at saying no. When it says maybe, the form still has to ask the database, because the maybe could be a false positive. So the filter only saves work on names that are free.
And think about who's typing. Someone picking a username tries the obvious names first, like their own name or a word they like, and those are exactly the names most likely to be taken already. For them the filter says maybe, the database gets queried anyway, and I've added a 2.4 GB structure that has to stay in sync with the table. It can't even forget a name when an account is deleted, because switching a bit off could erase a bit that another name relies on.
Where it does fit is the opposite case: suggesting alternatives when a name is taken. Generated candidates are mostly free, so the usual answer is no, and that's exactly where a Bloom filter could earn its memory.
One thing I haven't settled
"admin" written with a Cyrillic а (U+0430) is a different string from "admin" with a Latin a (U+0061). The index sees two different names while a person sees the same one, so whoever registers the lookalike can pass for the original.
Unicode Technical Standard #39 describes a "skeleton" for exactly this: it maps each character to a prototype of the characters it can be mistaken for, so two names that look alike end up with the same skeleton, and a unique index on the skeleton would catch them. The blunt alternative is to accept only lowercase a to z, digits and a couple of symbols, and most of the problem never shows up.
I don't know yet which one I'd pick. The skeleton leaves room for people whose names aren't written in Latin letters, while the short whitelist is much harder to get wrong.
Why it's still worth knowing
Most of us will never write a B-tree or a Bloom filter for production. The database already has the first, and a library has the second. What's worth having is a sense of what each one costs: a B-tree gives an exact answer in a handful of page reads, while a Bloom filter gives a cheap no and a maybe that still needs checking, for about 10 bits a name. That's enough to choose between them for the right reasons, and to notice when the clever option doesn't help.
Have you ever put a Bloom filter in front of a database and seen it actually pay off? I'd like to hear where it did.
Top comments (0)