Como o Instagram checa disponibilidade de usernames em milissegundos

A versão simples e o que a quebra

O artigo, de Naseebullah Ahmadi, engenheiro de software sênior, explica como construir um sistema de checagem de disponibilidade de usernames com o comportamento instantâneo observado no Instagram - deixando claro que o Instagram não publica como seu sistema funciona, e que se trata de uma proposta de arquitetura, não uma descrição do código real.

A versão ingênua - um endpoint que faz um SELECT em uma tabela com índice único - funciona bem por muito tempo: uma busca B-tree em um índice único leva poucos milissegundos mesmo com bilhões de linhas. O que a quebra não é a consulta em si, mas o formato do tráfego: cada tecla digitada na tela de cadastro gera uma checagem, e poucos milhões de cadastros diários produzem muito mais requisições do que o cadastro em si, todas caindo no banco que também precisa atender logins e escritas de perfil.

Camada um: não perguntar

A requisição mais barata é a que nunca é enviada. Antes de falar com o servidor, o cliente valida o formato localmente (o navegador já conhece as regras, como espaços ou limite de 31 caracteres), aplica debounce de 250 ms - de modo que digitar um nome completo em velocidade normal gera uma ou duas requisições, não dezessete - e cancela requisições em andamento quando o usuário digita de novo, evitando que uma resposta lenta de um nome parcial sobrescreva a resposta rápida do nome final. Isso corta o tráfego em uma ordem de grandeza antes de qualquer trabalho no servidor.

Camada dois: o Bloom filter

As requisições que chegam podem ser respondidas, em sua maioria, por um Bloom filter: um array de bits com k funções de hash. Para adicionar um nome, ele é hashado k vezes e os bits correspondentes são marcados. A consulta usa os mesmos hashes: se qualquer bit consultado é 0, o nome nunca foi adicionado - "definitivamente disponível". Se todos são 1, o nome provavelmente existe - e "provavelmente", porque outros nomes podem ter marcado os mesmos bits, gerando falsos positivos.

Essa assimetria é o truque central: o "não" é certo e o "sim" é incerto, então apenas os "talvez ocupado" precisam de consulta real. Com um bilhão de nomes e taxa de falso positivo de 1%, o filtro exige cerca de 9,6 bits por nome - aproximadamente 1,2 GB com 7 hashes -, cabe na memória de um servidor comum e responde em microssegundos. Reduzir a taxa a 0,1% custa cerca de 0,6 GB a mais por bilhão de nomes.

O filtro tem limitações: não permite exclusão (limpar bits pode apagar marcas de outros nomes, então nomes liberados permanecem "talvez" até uma reconstrução periódica ou uso de uma variante com contadores), e cada servidor mantém sua própria cópia - um nome registrado segundos antes pode ainda ler como disponível.

Camada três e a garantia final

Os "talvez" do filtro vão para uma consulta indexada contra uma réplica de leitura, ou um cache dos nomes ocupados no Redis para os nomes populares (john, alex, travel), sempre ocupados e constantemente checados. Réplicas e caches têm atraso: ambos os erros são possíveis, inclusive dizer "disponível" sobre um nome ocupado.

Nenhum desses problemas importa, porque a checagem é apenas uma dica. Duas pessoas podem ver o mesmo sinal verde no mesmo segundo e apertar cadastro. O único mecanismo que resolve a corrida é a restrição de unicidade no banco (aqui PostgreSQL), no momento da escrita: o primeiro INSERT vence, o segundo recebe um erro 409 com mensagem clara. É a mesma regra de duas escritas na mesma linha - a checagem anterior é consultiva, e a restrição no insert é a única garantia. Por isso os caches podem estar desatualizados: eles determinam apenas a velocidade da resposta, nunca se um duplicado entra.

O artigo acrescenta detalhes de robustez: a restrição única deve incidir sobre a forma normalizada (minúsculas) do nome, não sobre o que foi digitado; um alfabeto pequeno (letras a-z, dígitos e poucos separadores) elimina caracteres visualmente idênticos, como o cirílico "а", que permitiriam impersonação; nomes reservados (admin, support, marcas) precisam estar na tabela e no filtro, senão o filter os chama de "definitivamente disponíveis"; e sugestões de alternativas quando um nome é ocupado podem passar por dezenas de candidatos no filtro sem nenhuma consulta ao banco.

Conclusão

A resposta instantânea é uma pilha de camadas, cada uma mais barata que a de trás: validação e debounce no cliente, Bloom filter em memória, cache/réplica para os "talvez", e a restrição única com a palavra final. Quando as camadas discordam, o pior caso é uma mensagem educada de "esse nome acabou de ser ocupado", não dois usuários com o mesmo handle.