The instant tick is a stack of layers, each cheaper than the one behind it. The client debounces keystrokes and rejects invalid names without asking. A Bloom filter answers "definitely not taken" from memory in microseconds. Anything it can't rule out goes to an index lookup. And none of it is the real answer: the unique constraint on the insert is, because two people can see the same green tick.

You type nas into a signup form. Red cross. nas.codes, red.

nas.builds.things, green tick, and it appeared before you'd really

stopped typing. Somewhere there's a list of a billion or so names, and

your guess was checked against all of it in the time it took to lift a

finger.

doesn't publish how its check works, so this isn't a description of their code. It's how you'd build one that behaves like it, using the pieces systems at that scale reach for, and why each one is there.

A table of users, a unique index on the username, and an endpoint that asks:

Honestly, this is fine for a long time. A B-tree lookup on a unique index is a handful of page reads, a millisecond or two, even with a billion rows. If your product has a few thousand signups a day, stop here.

What breaks it is the traffic shape. Every keystroke of every person

on the signup screen is a request: n, na, nas, nas., and so

on. A few million signups a day, each typing a dozen or so characters

across a few attempts, and the check sees far more traffic than signup

itself. Every one of those requests lands on the database that also

has to serve logins and profile writes.

So the job is to answer most of those requests without the database, and to answer the rest cheaply.

The cheapest request is the one never sent. The client does three things before it asks the server anything:

It validates locally: a name with a space or a 31st character is

invalid, and the browser already knows the rules. It debounces:

only a pause of 250ms sends a request, so typing nas.builds.things

at normal speed sends one or two, not seventeen. And it cancels

the in-flight request when the user types again, so a slow answer for

nas.build can't land after the fast answer for nas.builds and

paint the wrong tick.

That cuts the traffic by an order of magnitude before any server work.

The requests that do arrive mostly have one of two answers. A reasonable-looking name that someone's already got, or a new one nobody has. The second kind can be answered without touching storage, by a .

A Bloom filter is a big array of bits, all zero to start, and hash functions. To add a name, hash it ways and set those bits. Here's a tiny one, 16 bits and 3 hashes, after two signups (the hash positions are made up for the example):

To check a name, hash it the same ways and look at those bits. If

any of them is 0, the name was never added: definitely available.

Someone types zoe, which hashes to 1, 7 and 13:

If all of them are 1, the name was probably added. Probably,

because other names can set those bits between them. sam hashes to

2, 4 and 13, and nobody ever registered it:

So its "no" is certain and its "yes" is a maybe. That asymmetry is the whole trick: a certain "available" can go straight back to the user, and only the maybes need a real lookup.

The chance that a name nobody has still reads as "maybe" (a false positive) depends on how full the bits are:

(1) False positive rate for n names in m bits with k hashes.

Pick the target first and the rest falls out. The best number of bits per name and the best number of hashes are:

(2) Sizing a Bloom filter for a target false positive rate.

Plug in a billion names and a 1% false positive rate: bits per name, so billion bits, about 1.2 GB, with hashes. That fits in the memory of one ordinary server, and a check is seven hashes and seven memory reads: microseconds. Drop the rate to 0.1% and it's 14.4 bits per name, about 1.8 GB, with 10 hashes. Every tenfold cut in false positives costs about 4.8 more bits per name, roughly 0.6 GB per billion names.

Every "maybe" that turns out to be free costs one index lookup. At 1%, that's one wasted lookup per hundred genuinely free names, which is nothing. The filter's value is the other 99.

A plain Bloom filter can't delete. Clearing a name's bits might clear bits another name shares. So when an account is deleted and its name is released, the name stays "maybe" forever: correct (the index lookup says free) but slower. Rebuild the filter from the table periodically, or use a counting variant that keeps a small counter per slot instead of a bit.

It's also a copy. Every server holds its own, and a name registered a second ago might not have reached every copy yet. That server will cheerfully say "definitely available" about a taken name. Which is fine, for a reason we'll get to.

The filter's maybes go to a real lookup: the same indexed SELECT as

the naive version, but against a read replica, or a cache of taken

names in in front of it. Popular names

(john, alex, travel) get checked constantly and are always

taken, so a cache keeps that hot set off the database entirely.

Replicas lag, caches go stale. A name registered a moment ago might still read as free. (Lag can also cut the other way, showing a freshly released name as taken for a few seconds, but that only costs someone a moment.) The error that matters is "available" about something that isn't, and every layer so far can make it.

Two people can type nas.builds.things in the same second, both get a

green tick, and both press Sign up. The availability check can't

prevent that; it ran before either of them committed to anything. The

only thing that can is the database (here

), at the moment of the write:

The first insert wins; the second gets no row back and a clear message. This is the same rule as any : the check before the write is advisory, and the constraint at the write is the only guarantee. It's also why the filter and the caches are allowed to be stale. They only ever decide how fast the answer is, never whether a duplicate gets in.

That warning is the tip of a bigger question. Is nas_codes the same

as nas.codes? Is nas in Latin letters the same as nаs with a

Cyrillic а, which renders identically? Allowing the second one lets

someone impersonate an account with a name no one can tell apart by

eye.

The cheap, robust answer is a small alphabet. Letters a to z,

digits, and a couple of separators, validated on the client and again

on the server. That rules out lookalike characters entirely, and makes

"lowercase it" the only folding rule you need. Past that, most

platforms keep a list of reserved names (admin, support, their own

brand) and hold released names for a while before anyone else can

claim them. Both belong in the table the check consults, and in the

Bloom filter too: a reserved name the filter has never seen is one it

will call "definitely available".

When a name is taken, a good form offers alternatives:

nas.builds.things2, nasbuilds, builds.by.nas. Generate twenty

candidates and run them through the Bloom filter in the same request.

Every candidate the filter rules out is almost certainly free (only a

copy that's seconds stale could be wrong, and the insert still has the

last word), found without a single database query. The filter was

built to answer "is this taken?" once; answering it twenty times costs

the same microseconds.

The green tick you see is every row above the last one agreeing, quickly. The account you get is the bottom row. They usually match, and the design makes sure that when they don't, the worst case is a polite "that username was just taken", not two people with the same name.