Busca de posts e da web (Twitter/FB search, Google)

01 · CONTEXTO

Buscar posts sem motor pronto

O exercício é a busca de posts de uma rede social: os usuários criam e curtem posts, buscam posts por palavra-chave e escolhem ver os resultados por recência ou por número de curtidas. O enunciado assume uma regra de entrevista: nada de motor de busca pronto nem de índice de texto completo pré-construído, porque o objetivo é testar organização de dados, indexação e escala.

O escopo deixa de fora busca aproximada de termos, regras de privacidade e personalização. Tirar a personalização é a decisão que mais ajuda: duas pessoas que buscam o mesmo termo com os mesmos parâmetros veem o mesmo resultado, e isso torna o cache muito mais eficaz.

Os requisitos não funcionais são o centro do problema. A consulta mediana deve responder em menos de 500 ms, um post novo deve ficar pesquisável em menos de um minuto, todo post precisa ser encontrável, inclusive os antigos ou impopulares, e o sistema deve ser altamente disponível. A folga para posts antigos sugere desde já dados quentes na memória e dados frios em armazenamento mais barato.

02 · ESCALA

Quem manda é a escrita

A fonte parte de premissas simples: um bilhão de usuários, cada um criando um post por dia, curtindo dez e fazendo uma busca. Arredondando o dia para cem mil segundos, isso dá cerca de 10 mil posts criados por segundo, 100 mil curtidas por segundo e 10 mil buscas por segundo. Com dez anos de posts e cerca de 1 kB de metadados por post, o volume bruto chega à casa de 3,6 PB.

A lição está na comparação: é um erro comum fixar-se na busca e supor que a leitura pesa mais. Aqui as curtidas superam em muito a criação de posts, e o sistema é mais pesado em escrita do que em leitura. O tamanho do volume também avisa que será preciso limitar o que entra no índice.

03 · ÍNDICE

Da varredura ao índice invertido

A solução ingênua guarda os posts num banco relacional e busca o texto com um LIKE sobre todos eles. Devolve a resposta certa, mas é lentíssima, porque o banco precisa olhar cada post na hora da consulta. Dividir o banco em partes (particionamento) ou replicá-lo melhora só um pouco, e a busca continua lenta demais.

1. O usuário pede os posts que contêm uma palavra; o pedido passa pelo gateway.

2. O serviço de busca manda ao banco uma consulta que procura o texto da palavra dentro de cada post.

3. Sem índice, o banco precisa olhar cada post na hora da consulta; dividir o banco em partes reduz o trabalho de cada nó, mas a varredura continua cara demais.

O caminho certo é o índice invertido: um dicionário que mapeia cada palavra para os posts que a contêm. Na criação do post, a ingestão quebra o texto em palavras (tokenização) e acrescenta o ID do post à lista de cada uma. A fonte guarda essas listas em memória, com um armazenamento durável como alternativa para a questão de durabilidade.

1. Um post novo chega ao serviço de posts, que grava o conteúdo no banco de posts.

2. O serviço de posts avisa a ingestão, que quebra o texto em palavras (tokenização).

3. Para cada palavra do post, a ingestão acrescenta o ID do post à lista dela no índice invertido.

4. Na leitura, o usuário busca uma palavra e o pedido chega ao serviço de busca.

5. O serviço de busca pega no índice a lista de IDs da palavra e devolve os posts, sem varrer o banco.

Há custos. Um post pode ter de dez a mil palavras-chave, então cada post vira muitas escritas, e as listas de IDs de palavras comuns ficam enormes.

04 · ORDENAÇÃO

Recência ou curtidas

Ordenar no momento da consulta é a opção ruim: pega-se a lista de IDs da palavra, consulta-se a data ou a contagem de cada post e ordena-se na memória. Para uma palavra muito comum, com dezenas de milhões de resultados, a resposta do índice chegaria a centenas de megabytes, e ordenar milhões de itens na hora acrescenta latência sem necessidade.

A alternativa é manter dois índices por palavra: um ordenado por criação e outro por curtidas. O primeiro pode ser uma lista em que só se acrescenta no fim e se lê do fim; o segundo, um conjunto ordenado por pontuação. A troca é clara: o armazenamento dobra, e cada curtida passa a exigir a atualização de várias pontuações.

05 · LEITURA

Cache, CDN e frases

Para absorver o tráfego de leitura, o cache é a ferramenta óbvia, porque dois requisitos ajudam: não há personalização e o post pode demorar até um minuto para aparecer. Um cache de resultados ao lado do serviço de busca, com tempo de vida menor que esse prazo, nunca serve resultado que ignore um post que já deveria constar.

Na borda, uma CDN pode guardar as respostas de /search se a resposta trouxer cabeçalhos de cache-control. Um acerto na CDN responde em dezenas de milissegundos, contra centenas de milissegundos pelo caminho completo.

Para buscas com várias palavras, a opção mais simples é pegar as listas de cada palavra, fazer a interseção e depois conferir no conteúdo se a frase realmente aparece. Com listas de milhões de IDs, transferir e intersectar dentro do prazo é proibitivo. A alternativa é indexar pares de palavras vizinhas (bigramas) e ir direto à entrada da frase, ao custo de um índice muito maior: de cerca de 10 milhões de chaves para mais de 100 milhões.

06 · ESCRITA

Absorver posts, curtidas e petabytes

Cada post gera muitas escritas no índice, e uma rajada pode sobrecarregar a ingestão. A resposta é colocar uma fila ou stream na frente: ela reparte a criação de posts entre várias instâncias de ingestão, particiona a carga e amortece rajadas. Além disso, os índices podem ser fragmentados pela palavra-chave, espalhando as escritas por muitas instâncias.

As curtidas são o maior problema. Um agregador pode somar as curtidas de cada post numa janela de tempo e publicar uma única atualização: cerca de 500 escritas de um post viral viram uma só. Mas a maioria dos posts não é viral, então o ganho geral é pequeno.

O ganho maior vem de atualizar o índice de curtidas só em marcos, como potências de dois ou de dez: mil curtidas passam a custar cerca de dez escritas. O preço é um índice desatualizado, mas com ordem aproximadamente correta. Para devolver N posts, busca-se o dobro no índice e consulta-se o serviço de curtidas para reordenar pela contagem atual.

1. Uma busca repetida pode ser respondida na borda, pela CDN, com cabeçalhos de cache definidos pela resposta.

2. Se a borda não tem a resposta, o serviço de busca tenta o cache de resultados, cujo tempo de vida é menor que o prazo para um post aparecer.

3. No cache vazio, a busca lê o fragmento do índice dessa palavra; palavras raras vêm do armazenamento frio, com pequena penalidade de latência.

4. Posts novos entram por uma fila, que reparte a carga entre instâncias de ingestão e as deixa atualizar os índices no seu ritmo.

5. Curtidas passam por um agregador que soma as de cada post numa janela e publica uma só atualização na fila.

6. A ordenação por curtidas usa o índice só como aproximação: o serviço de busca pede a contagem atual dos candidatos ao serviço de curtidas e reordena.

Falta o armazenamento. Limitar cada índice a mil ou dez mil itens reduz o espaço em ordens de grandeza, e as palavras raramente buscadas podem migrar da memória para armazenamento frio de blobs; se a palavra não está na memória, a consulta ao blob tem só uma pequena penalidade de latência.