How Does Instagram Instantly Know If Your Username Is Available?
In one line
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.
Instagram 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.
Start with the version that looks fine
A table of users, a unique index on the username, and an endpoint that asks:
@itsnas — TypeScript
Hide line numbersCopy code
// GET /usernames/:name/available
async function isAvailable(req: Request) {
const [taken] = await db`
SELECT 1 FROM users WHERE username = ${req.params.name}
`
return json(200, { available: !taken })
}main
Nas (@itsnas)
Correct, and fast for one request
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.
Layer one: don't ask
The cheapest request is the one never sent. The client does three things before it asks the server anything:
@itsnas — TypeScript
Hide line numbersCopy code
const VALID = /^[a-z0-9._]{3,30}$/
function onUsernameInput(raw: string) {
pending?.abort()
clearTimeout(timer)
const name = raw.trim().toLowerCase()
if (!VALID.test(name)) return showInvalid(name)
timer = setTimeout(() => {
pending = new AbortController()
checkAvailability(name, pending.signal)
}, 250)
}main
Nas (@itsnas)
Most keystrokes never become a request
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 cancelsthe 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.
Layer two: a Bloom filter
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 Bloom filter.
A Bloom filter is a big array of mmm bits, all zero to start, and kkkhash functions. To add a name, hash it kkk ways and set those kkkbits. Here's a tiny one, 16 bits and 3 hashes, after two signups (the hash positions are made up for the example):
1. Index 0: 00 2. Index 1: 01 3. Index 2: 1 (nas)2 4. Index 3: 03 5. Index 4: 1 (alex)4 6. Index 5: 05 7. Index 6: 06 8. Index 7: 1 (nas, alex)7 9. Index 8: 08 10. Index 9: 09 11. Index 10: 010 12. Index 11: 1 (nas)11 13. Index 12: 012 14. Index 13: 1 (alex)13 15. Index 14: 014 16. Index 15: 015
Adding nas sets bits 2, 7 and 11; adding alex sets 4, 7 and 13. Bit 7 was already set, so the two names now share it.
To check a name, hash it the same kkk 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:
1. Index 0: 00 2. Index 1: 0 (zoe)1 3. Index 2: 12 4. Index 3: 03 5. Index 4: 14 6. Index 5: 05 7. Index 6: 06 8. Index 7: 1 (zoe)7 9. Index 8: 08 10. Index 9: 09 11. Index 10: 010 12. Index 11: 111 13. Index 12: 012 14. Index 13: 1 (zoe)13 15. Index 14: 014 16. Index 15: 015
zoe lands on bit 1, which is still 0. No name that was ever added could have left it unset, so zoe is definitely free.
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:
1. Index 0: 00 2. Index 1: 01 3. Index 2: 1 (sam)2 4. Index 3: 03 5. Index 4: 1 (sam)4 6. Index 5: 05 7. Index 6: 06 8. Index 7: 17 9. Index 8: 08 10. Index 9: 09 11. Index 10: 010 12. Index 11: 111 13. Index 12: 012 14. Index 13: 1 (sam)13 15. Index 14: 014 16. Index 15: 015
Every bit sam checks is 1, set by nas (2) and alex (4, 13). The filter says 'maybe taken' about a name nobody has: a false positive.
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.
Client
Bloom filter
Available
Index lookup
Sign up
users (unique)
1. Client to Bloom filter: debounced check 2. Bloom filter to Available: any bit is 0 3. Bloom filter to Index lookup: all bits are 1 4. Index lookup to Available: not found 5. Sign up to users (unique): INSERT, unique
Most requests are answered from memory. Only the filter's 'maybe' reaches storage, and only the insert decides.
How big does it need to be?
The chance that a name nobody has still reads as "maybe" (a false positive) depends on how full the bits are:
Copy formulap≈(1−e−kn/m)kp \\approx \\left(1 - e^{-kn/m}\\right)^kp≈(1−e−kn/m)k
(1) False positive rate for n names in m bits with k hashes.
Pick the target ppp first and the rest falls out. The best number of bits per name and the best number of hashes are:
Copy formulamn=−lnp(ln2)2k=mnln2\\frac{m}{n} = \\frac{-\\ln p}{(\\ln 2)^2} \\qquad k = \\frac{m}{n} \\ln 2nm\=(ln2)2−lnpk\=nmln2
(2) Sizing a Bloom filter for a target false positive rate.
Plug in a billion names and a 1% false positive rate: m/n≈9.6m/n \\approx 9.6m/n≈9.6 bits per name, so m≈9.6m \\approx 9.6m≈9.6 billion bits, about 1.2 GB, with k=7k = 7k\=7 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.
What it can't do
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.
Layer three: the maybes
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 #redis 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.
The check is a hint; the insert is the answer
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 #postgres), at the moment of the write:
@itsnas — TypeScript
Hide line numbersCopy code
async function signUp(req: Request) {
const username = req.body.username.trim().toLowerCase()
const [user] = await db`
INSERT INTO users (username, email)
VALUES (${username}, ${req.body.email})
ON CONFLICT (username) DO NOTHING
RETURNING id
`
if (!user)
return json(409, { error: 'That username was just taken' })
bloom.add(username)
return json(201, user)
}main
Nas (@itsnas)
The unique index settles the race, not the earlier check
The first insert wins; the second gets no row back and a clear message. This is the same rule as any two writes to one row: 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.
What counts as "the same name"
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".
Suggestions for free
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.
Putting it together
| Layer | Answers | Cost | Can be wrong? | | ------------------- | ------------------------------ | ------------ | --------------------------- | | Client validation | Invalid names | Nothing | No | | Debounce and cancel | Keystrokes that aren't a pause | Nothing | No | | Bloom filter | Definitely available | Microseconds | Stale copy says "available" | | Cache or replica | Taken, or free after a "maybe" | About a ms | Lag says "available" | | Unique constraint | Who actually gets the name | One insert | No |
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.
---
Pairs with
Hashing and the Birthday ParadoxTwo Writes, One Row: Who Wins?Back-of-the-Envelope Estimation