Autocomplete

01 · CONTEXTO

Uma sugestão a cada tecla

Autocomplete de busca devolve sugestões enquanto a pessoa digita, o que significa uma consulta a cada tecla. Um guia de entrevista de system design sobre o tema afirma que o sistema precisa devolver as sugestões em menos de cem milissegundos por tecla, para centenas de milhões de usuários. Quem projeta o sistema parte, portanto, de um orçamento de latência apertado e de um volume de leitura muito maior que o de escrita. Para entender o que cabe nesse orçamento, vale separar o caminho de leitura, que atende a pessoa digitando, do caminho de atualização, que decide o que será sugerido.

1. Cada tecla gera uma consulta com o prefixo digitado, que chega ao serviço de sugestões pelo balanceador.

2. O serviço não calcula nada: ele consulta uma estrutura em memória que já guarda as sugestões prontas.

02 · TRIE E TOP-K

Respostas prontas em cada nó

A estrutura central é um trie, em que cada caminho a partir da raiz representa um prefixo. A ideia que o guia destaca é guardar em cada nó as melhores sugestões para aquele prefixo, calculadas e armazenadas de antemão. Com isso, achar o nó do prefixo e devolver a lista já pronta custa uma única busca proporcional ao tamanho do prefixo, em vez de percorrer toda a subárvore abaixo dele. É um exemplo de sistemas de busca em que o trabalho caro é deslocado da leitura para a construção.

1. O serviço envia o prefixo ao servidor de trie responsável por ele.

2. O servidor localiza o nó do prefixo e devolve a lista de sugestões que ele já guarda, sem percorrer a subárvore.

03 · COLETA E ATUALIZAÇÃO

O pipeline que alimenta o trie

As sugestões vêm do que as pessoas realmente buscam. No desenho descrito pelo guia, toda busca é registrada em um log distribuído, e um job de streaming agrega as contagens de cada consulta em janelas de uma hora. Também a cada hora, um job construtor relê a tabela de frequências e reconstrói os nós afetados do trie. A nova versão entra no ar por uma troca blue-green, em que todo o tráfego passa de uma só vez para o trie novo, sem indisponibilidade. Esse é um uso típico de pipelines de dados, em que o caminho de escrita é assíncrono e totalmente separado do caminho de leitura. A cadência de uma hora é a do guia.

1. Cada busca atendida é registrada em um log distribuído, fora do caminho de resposta ao usuário.

2. Um agregador consome o log e acumula a contagem de cada consulta na tabela de frequências.

3. Periodicamente, o construtor relê as frequências e monta o trie com as sugestões prontas em cada nó.

4. A nova versão substitui a anterior nos servidores de trie de uma só vez, sem tirá-los do ar.

04 · FRESCOR

Consultas que explodem entre reconstruções

Uma reconstrução periódica deixa uma brecha: uma consulta que dispara de repente, como um evento do momento, só entraria nas sugestões na próxima rodada. O guia propõe um componente à parte que acompanha os picos recentes e os injeta nas sugestões sem reconstruir o trie inteiro. O custo dessa solução é uma segunda fonte de resultados, que precisa ser combinada com a do trie na hora da resposta.

1. Um detector acompanha as buscas recentes e guarda em um armazenamento rápido as consultas que estão disparando.

2. O serviço consulta o trie e os picos e combina os dois resultados antes de responder.

05 · ESCALA

Particionar o trie e poupar requisições

Quando o trie não cabe em um único servidor, ele precisa ser dividido. O guia sugere particionar pelos primeiros caracteres do prefixo, de modo que cada fatia fique com uma faixa de prefixos. No cliente, o guia recomenda um debounce: só enviar a consulta quando a pessoa pausa a digitação por um intervalo curto, o que reduz as requisições ao servidor. Ambas são formas de escalar horizontalmente o sistema: uma divide os dados entre servidores, a outra diminui a carga que chega a eles.