Web crawler distribuído

01 · CONTEXTO E ESCOPO

O que um web crawler precisa fazer

Um web crawler, também chamado de robô ou spider, é o programa que descobre conteúdo novo ou atualizado na web. Ele parte de poucas páginas, segue os links que encontra nelas e coleta o que for aparecendo. O uso mais comum é alimentar um mecanismo de busca.

O algoritmo básico cabe em três passos: dado um conjunto de URLs, baixar as páginas; extrair as URLs dessas páginas; e acrescentar as novas à lista de páginas a baixar, repetindo o ciclo. Apesar da simplicidade, projetar um crawler de grande escala é uma tarefa extremamente complexa, e este caso trata de por que.

Quatro propriedades guiam o desenho. Escalabilidade: a web é enorme, então o rastreio precisa ser paralelo. Robustez: a web é cheia de armadilhas, como HTML malformado, servidores que não respondem, quedas e links maliciosos. Polidez: o crawler não deve fazer pedidos demais a um mesmo site em pouco tempo. Extensibilidade: aceitar um novo tipo de conteúdo deve exigir poucas mudanças.

02 · ESTIMATIVA DE ESCALA

Contas de guardanapo

O livro da ByteByteGo assume um bilhão de páginas baixadas por mês, o que dá cerca de 400 páginas por segundo, com pico de 800, o dobro da média. Com páginas de 500 KB em média, são 500 TB por mês e, guardando cinco anos de conteúdo, 30 PB.

O System Design Primer parte de premissas diferentes: 4 bilhões de links rastreados por mês, com renovação média de cerca de uma vez por semana e mais frequente nos sites populares. Isso dá 1.600 escritas por segundo, e o Primer soma ainda 40.000 buscas por segundo, porque inclui o lado da consulta.

As duas fontes divergem no volume, e isso é esperado: estimativa é hipótese. O que importa é mostrar as premissas e chegar à ordem de grandeza: com tantos dados, um servidor só não resolve e o trabalho precisa ser distribuído.

03 · DESENHO DE ALTO NÍVEL

Frontier, downloader e parser

O desenho tem poucas peças. A fila de URLs a baixar, o URL Frontier, guarda o que falta rastrear; o livro a descreve como uma fila FIFO. O downloader de HTML busca as páginas e consulta um resolvedor de DNS para obter o IP de cada URL. Depois, um parser valida a página; ele é um componente à parte porque, dentro do servidor de rastreio, deixaria o rastreio mais lento.

1. As URLs semente entram na fila de URLs a baixar e o downloader retira uma delas.

2. O downloader busca a página no servidor de origem.

3. A página baixada segue para o parser, que confere se o HTML está bem formado.

4. Páginas válidas são gravadas no armazenamento de conteúdo.

5. O parser extrai os links da página e devolve os novos à fila, fechando o ciclo.

Este desenho funciona, mas deixa três perguntas em aberto: em que ordem rastrear, como não sobrecarregar um mesmo site e como não repetir trabalho. As próximas seções respondem a cada uma.

04 · A FILA DE URLS

Ordem, polidez e frescor

A ordem natural é a busca em largura (BFS), implementada com uma fila FIFO. A busca em profundidade costuma ser má escolha, porque a profundidade pode ser enorme.

A fila simples tem dois problemas. Primeiro, a maioria dos links de uma página aponta para o mesmo servidor, e baixar em paralelo inunda esse servidor de pedidos, o que é considerado impolidez. Segundo, ela ignora a prioridade da URL, e nem toda página tem a mesma qualidade e importância.

Para a polidez, a ideia é baixar uma página por vez de cada host, com um atraso entre os downloads. Uma tabela mapeia cada host a uma fila, e cada downloader só consome a sua. Para a prioridade, um priorizador mede a utilidade da URL, por exemplo por PageRank, e as filas de maior prioridade são escolhidas com maior probabilidade.

O resultado são dois módulos: as filas da frente cuidam da priorização e as filas do fundo cuidam da polidez.

1. O extrator entrega os links novos ao priorizador, que mede a importância de cada URL.

2. Cada URL entra numa das filas da frente, conforme a prioridade.

3. O seletor sorteia uma fila da frente, com viés para as de maior prioridade.

4. A URL escolhida passa pelo roteador, que a envia à fila do fundo do seu host.

5. Cada fila do fundo guarda URLs de um único host.

6. Um downloader por fila baixa uma página de cada vez e pode esperar entre downloads.

As páginas mudam o tempo todo, então o crawler precisa rastrear de novo as já baixadas para manter os dados frescos. Refazer tudo é caro. Duas estratégias: rastrear antes e com mais frequência as páginas importantes, e usar o tempo médio até a atualização de cada página, como sugere o Primer, para decidir a frequência.

O frontier pode chegar a centenas de milhões de URLs. Tudo em memória não é durável nem escalável, e tudo em disco é lento. A solução híbrida do livro guarda a maioria no disco e mantém buffers em memória para enfileirar e retirar URLs.

05 · NÃO REPETIR TRABALHO

Conteúdo repetido e URLs repetidas

Parte da web é conteúdo duplicado: uma pesquisa citada pelo livro indica que 29% das páginas se repetem. Comparar dois HTMLs caractere a caractere é lento, então o componente Conteúdo já visto compara os hashes das páginas. Se o conteúdo já está no armazenamento, a página é descartada; se não, segue para a extração de links.

Os links extraídos passam pelo filtro de URLs, que exclui certos tipos de conteúdo, extensões de arquivo e links com erro. Em seguida, o componente URLs já vistas registra o que foi visitado ou já está no frontier, para não enfileirar a mesma URL duas vezes, o que aumentaria a carga nos servidores e poderia causar laços infinitos. Só URLs nunca processadas entram no frontier. Filtro de Bloom e tabela hash são técnicas comuns para implementar esse componente.

O filtro de Bloom é uma estrutura de dados probabilística e econômica em espaço, que testa se um elemento pertence a um conjunto. Ele admite falsos positivos, mas não falsos negativos: responde "possivelmente presente" ou "definitivamente ausente". Aplicado a URLs já vistas, isso quer dizer que o filtro pode apontar por engano uma URL nova como já vista, mas nunca esquece uma URL que de fato foi registrada.

1. O downloader entrega a página ao parser.

2. Depois de validada, a página vai ao Conteúdo já visto, que compara o hash dela com os já guardados.

3. Se o hash é novo, o conteúdo é gravado no armazenamento.

4. Com conteúdo novo, o extrator de links lê o HTML; se o conteúdo já existia, a página é descartada aqui.

5. Os links extraídos passam pelo filtro de URLs e depois pelo componente URLs já vistas.

6. Só URLs nunca vistas entram no frontier, e o ciclo recomeça.

O Primer segue outro caminho: uma tabela de links rastreados guarda a assinatura de cada página, e, se já existe página de assinatura parecida, o crawler reduz a prioridade do link, o que evita ciclos. O próprio Primer admite que detectar conteúdo duplicado é mais complexo do que detectar URLs duplicadas.

06 · DESEMPENHO E ROBUSTEZ

Robots.txt, DNS, falhas e armadilhas

Antes de rastrear um site, o crawler deve ler o robots.txt, o Protocolo de Exclusão de Robôs, e seguir suas regras. Para não baixar o arquivo toda hora, guarda o resultado em cache. O Primer acrescenta que o arquivo dá aos webmasters controle sobre a frequência de rastreio.

O resolvedor de DNS costuma ser um gargalo, porque muitas interfaces de DNS são síncronas: a resposta leva de 10 ms a 200 ms e, enquanto uma thread espera, as outras ficam bloqueadas. A saída é manter um cache próprio de nome para IP, atualizado periodicamente.

Outras otimizações: distribuir o rastreio em vários servidores, cada um responsável por um subconjunto das URLs; pôr os servidores perto dos sites, o que acelera o download; e definir um tempo máximo de espera, abandonando hosts que não respondem.

Para a robustez, o livro sugere consistent hashing para distribuir a carga entre os downloaders, salvar o estado e os dados do rastreio para retomar após uma falha, e tratar exceções sem derrubar o sistema.

Uma spider trap é uma página que prende o crawler num laço infinito. Limitar o tamanho máximo das URLs evita parte delas, mas não existe solução universal para detectá-las. Sites com armadilhas costumam ter um número anormalmente grande de páginas descobertas, e uma pessoa pode verificá-los e excluir o site ou aplicar filtros de URL próprios.