How Does Instagram Instantly Know If Your Username Is Available?

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)

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)

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.

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 $m$ bits, all zero to start, and $k$ hash functions. To add a name, hash it $k$ ways and set those $k$ bits. 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

To check a name, hash it the same $k$ 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

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

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

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:

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

Plug in a billion names and a 1% false positive rate: $m/n \approx 9.6$ bits per name, so $m \approx 9.6$ billion bits, about 1.2 GB, with $k = 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 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.

---