Design de sistema de typeahead: como funciona o autocompletar de busca em escala

Digite “how to” em uma caixa de busca e as sugestões aparecem antes de você terminar a próxima palavra. Esse recurso responde a uma requisição em quase toda tecla, para todo usuário, e precisa parecer instantâneo: pesquisas sobre tempos de resposta que remontam a décadas colocam o limite de “o sistema reage instantaneamente” em cerca de 0,1 segundo. Nada no autocompletar é difícil isoladamente. O desafio é fazer coisas simples dentro de um orçamento de latência apertado, com uma taxa de requisições muito alta, mantendo as sugestões atualizadas e livres de tudo o que você nunca quer mostrar.

Este post projeta um serviço de typeahead: requisitos e capacidade, o índice de prefixos top-k, serving e sharding, o pipeline de construção offline, consultas em alta, cache, personalização e filtragem, com um diagrama das duas metades.

Requisitos

Funcionais:

• Retornar as 5 a 10 melhores conclusões para um prefixo, ordenadas principalmente por popularidade.
• Refletir novas tendências em minutos, não em dias.
• Nunca mostrar sugestões que violem as suas políticas.

Não funcionais:

• Cerca de 100 ms de ponta a ponta, o que deixa para o backend um orçamento de dezenas de milissegundos depois do tempo de rede.
• Alta disponibilidade: se as sugestões falharem, a busca continua funcionando, então degrade com elegância.
• Barato: isso roda a cada tecla.

Capacidade

Suponha 50 milhões de usuários diários que buscam 10 vezes por dia cada um, com cerca de 6 requisições de sugestão por busca depois que o cliente para de mandar uma por caractere:

Duas observações moldam o design. Prefixos curtos são extremamente repetitivos: todo mundo que digita “w” faz a mesma pergunta. E a resposta para um prefixo muda devagar, então pode ser calculada com antecedência.

O cliente faz metade do trabalho

• Debounce. Espere de 100 a 200 ms depois da última tecla antes de enviar uma requisição, para que quem digita rápido não dispare uma requisição por caractere.
• Cancele requisições obsoletas. Quando um novo prefixo sai, aborte o anterior e ignore respostas atrasadas de um prefixo mais antigo.
• Faça cache local. Se “how t” retornou dez resultados que começam todos com “how to”, o cliente pode filtrá-los para “how to” sem nenhuma requisição.
• Falhe em silêncio. Se a chamada de sugestões falhar ou demorar, não mostre nada; a busca precisa continuar funcionando.

O índice de prefixos top-k

A estrutura clássica é uma trie, em que cada nó é um prefixo e os filhos o estendem em um caractere. Percorrer a trie e vasculhar a subárvore inteira atrás das consultas mais populares na hora da requisição é lento demais para prefixos populares. Em vez disso, calcule a resposta antes: guarde em cada nó de prefixo as k melhores conclusões, já ordenadas. Uma busca vira uma única leitura.

Muitas implementações dispensam totalmente a trie baseada em ponteiros e guardam um mapa plano do prefixo para a sua lista top-k, limitado a um comprimento máximo de prefixo, já que prefixos muito longos são raros e podem cair em um caminho mais lento. Construir um a partir de contagens agregadas é curto:

import heapq
from collections import defaultdict

def build_prefix_index(query_counts, k=10, max_prefix=12):
    index = defaultdict(list)  # prefix -> min-heap of (count, query)
    for query, count in query_counts.items():
        for n in range(1, min(len(query), max_prefix) + 1):
            heap = index[query[:n]]
            if len(heap) < k:
                heapq.heappush(heap, (count, query))
            elif count > heap[0][0]:
                heapq.heapreplace(heap, (count, query))
    return {p: [q for _, q in sorted(h, reverse=True)] for p, h in index.items()}

O resultado é somente leitura e é carregado em memória em cada nó de serving. Se você já roda Elasticsearch, o completion suggester dele oferece a mesma ideia como recurso: a documentação descreve estruturas de dados que permitem buscas rápidas, mas são caras de construir e ficam em memória, que é exatamente o trade-off deste design.

Serving e sharding

O serviço de sugestões normaliza o prefixo (minúsculas, remoção de espaços, normalização Unicode), lê a lista top-k do índice, mescla os resultados em alta e pessoais, filtra e responde. Tudo o que ele lê está em memória.

Quando o índice não cabe mais em uma máquina, divida-o em shards. Dividir pela primeira letra parece natural, mas fica muito desigual: muito mais consultas começam com “s” do que com “x”. Em vez disso, aplique hash ao prefixo, ou divida por faixas de tráfego medido, e replique cada shard para que a falha de um nó só reduza a capacidade. Como o índice é reconstruído offline, as réplicas nunca precisam concordar sobre gravações; cada uma carrega o mesmo snapshot.

O pipeline de construção offline

1. Coletar. Os front-ends de busca registram cada consulta concluída em um stream como o Kafka.
2. Agregar. Um job batch conta as consultas em uma janela, por exemplo os últimos 30 dias, dando mais peso aos dias recentes, e descarta consultas raras abaixo de um limiar para proteger a privacidade e remover ruído.
3. Filtrar. Aplique listas de bloqueio e classificadores de políticas antes que qualquer coisa vire sugestão.
4. Construir. Calcule o índice de prefixos como acima e grave-o como um snapshot versionado no armazenamento de objetos.
5. Implantar. Os nós de serving carregam o novo snapshot ao lado do antigo, trocam de forma atômica e mantêm a versão anterior para um rollback rápido.

Reconstruções de hora em hora ou diárias mantêm o índice principal atualizado o bastante para a maioria das consultas.

Consultas em alta

Uma notícia urgente gera uma nova consulta popular em minutos, muito antes da próxima construção batch. Adicione uma pequena camada de tempo real: um processador de streams conta as consultas em janelas deslizantes, detecta as que sobem muito mais rápido que a sua linha de base e as grava em um armazenamento rápido como o Redis, indexadas por prefixo. O serviço de sugestões as mescla com os resultados batch. Mantenha essa camada pequena e filtre-a com rigor; é ali que um ataque coordenado tentaria plantar sugestões.

Cache em todas as camadas

Prefixos curtos são os mais quentes e os que mais se beneficiam de cache, porque são idênticos para todo mundo. Resultados personalizados não podem ficar em cache na CDN, um dos motivos para manter a personalização leve.

Personalização, erros de digitação e filtragem

• Histórico pessoal. Misturar as consultas recentes do próprio usuário com as sugestões globais ajuda muito e é barato se essas consultas ficarem no dispositivo ou em um pequeno armazenamento por usuário.
• Erros de digitação. A correspondência aproximada a uma edição do prefixo salva “pyhton”. Ela é mais cara, então muitos sistemas tentam primeiro os prefixos exatos e só recorrem à correspondência aproximada quando há poucos resultados.
• A filtragem é aplicada duas vezes: offline, antes de uma consulta entrar no índice, e online, contra uma lista de bloqueio rápida que pode ser atualizada em minutos sem reconstrução.

O diagrama do typeahead

Como ler:

• A moldura online é o caminho de cada tecla: navegador, cache da CDN, gateway de API e serviço de sugestões.
• O serviço de sugestões lê dois shards de prefixos em memória e o armazenamento de tendências no Redis, e mescla e filtra os resultados.
• A moldura offline é o caminho de construção: logs de consultas do Kafka, o job de agregação e snapshots versionados do índice no armazenamento de objetos.
• A aresta tracejada do armazenamento de objetos para os shards é o carregamento do snapshot, o único elo entre as duas metades.
• O bloco Markdown mostra o orçamento de latência e os números de capacidade.

Desenhar sistemas com muita leitura com clareza

• Separe online e offline. As duas metades têm orçamentos de latência, modos de falha e responsáveis diferentes, e o diagrama deve mostrar isso num relance.
• Mostre cada camada de cache, com a sua expiração. Em um sistema com muita leitura, os caches são a maior parte da arquitetura.
• Desenhe o único elo entre as metades: aqui, um snapshot versionado. Ele explica como as atualizações chegam aos usuários e como o rollback funciona.
• Anote o orçamento de latência no caminho online.

Para a abordagem geral, veja o exemplo de diagrama de design de sistemas. O diagrama de estratégias de cache trata as camadas de cache com mais profundidade, e a agregação de logs segue os padrões do diagrama de arquitetura de pipeline de dados.

Monte no Archboard

1. Entre com Google ou GitHub e crie um diagrama.
2. Adicione dois nós Moldura do pack Básico: Online, per keystroke, e Offline, hourly build.
3. Na moldura online, adicione um nó Dispositivo do pack Rede para o navegador, uma CDN e um Gateway de API do pack Nuvem, um nó Instância de computação para o serviço de sugestões, dois nós Redis do pack Dados para os shards de prefixos e mais um nó Redis para as consultas em alta.
4. Na moldura offline, adicione um nó Kafka do pack Dados para os logs de consultas, um nó Instância de computação do pack Nuvem para o job de agregação e um Repositório de objetos do pack Dados para os snapshots do índice.
5. Desenhe o caminho das requisições da esquerda para a direita, o caminho de construção abaixo dele e uma aresta tracejada dos snapshots para os shards.
6. Adicione um bloco Markdown do pack Básico com o orçamento de latência e a capacidade.

O exemplo usa 13 nós de diagrama e fica dentro do plano Free.

Perguntas frequentes

Que estrutura de dados é usada no autocompletar? Uma trie, ou um mapa plano do prefixo para os resultados, com as k melhores conclusões pré-calculadas em cada prefixo. O pré-cálculo transforma cada busca em uma única leitura em memória.

Quão rápido o autocompletar precisa ser? Cerca de 100 ms entre a tecla e as sugestões parecem instantâneos. Depois do tempo de rede, sobram dezenas de milissegundos para o backend, e é por isso que o índice fica em memória.

Como as sugestões se mantêm atualizadas? Um pipeline batch reconstrói o índice a partir dos logs de consultas a cada hora ou a cada dia, e uma camada de tempo real acrescenta em minutos as consultas que sobem rápido.

As requisições de autocompletar devem sair a cada tecla? Não. Aplique um debounce de 100 a 200 ms no cliente, cancele requisições desatualizadas e reutilize resultados em cache para prefixos mais longos. Isso reduz bastante o volume de requisições.

Como manter sugestões ofensivas de fora? Filtre offline antes de as consultas entrarem no índice, aplique limiares mínimos de popularidade e confira os resultados online contra uma lista de bloqueio que você consiga atualizar rápido.

Comece grátis — um assento, sem cartão de crédito.