Design de sistema de web crawler: fronteira de URLs, cortesia e deduplicação

Um crawler parece simples: baixe uma página, extraia os links, baixe esses, repita. Escrito como um loop, funciona para mil páginas. Com um bilhão de páginas, ele desmorona de jeitos instrutivos: martela sites pequenos com centenas de requisições paralelas, baixa a mesma página sob cinquenta URLs, se perde em um calendário infinito e passa a maior parte do tempo esperando o DNS.

Este post projeta um crawler que escala e continua educado: números de capacidade, a fronteira de URLs com filas de prioridade e por host, o robots.txt como padronizado pela RFC 9309, deduplicação de URLs e de conteúdo, armadilhas para crawlers e os componentes em volta, com um diagrama do loop inteiro.

Requisitos e números

O objetivo: rastrear cerca de um bilhão de páginas por mês para um índice de busca ou de análise, atualizar páginas importantes com mais frequência e nunca sobrecarregar um site.

A última linha é a que mais importa. A descoberta supera de longe o download, então o crawler está sempre escolhendo o que não baixar. Priorização é um recurso central, não uma otimização.

O loop de crawl

1. Pegue a próxima URL da fronteira.
2. Confira o robots.txt do host dela, a partir do cache.
3. Resolva o nome do host, a partir de um cache DNS local.
4. Baixe a página respeitando o atraso de cortesia do host.
5. Armazene a resposta bruta.
6. Faça o parsing, extraia os links e normalize-os.
7. Descarte os links já vistos; adicione o resto à fronteira com uma prioridade.
8. Calcule a impressão digital do conteúdo e pule os quase duplicados no processamento posterior.

Cada passo depois do primeiro é um ponto em que um crawler ingênuo desperdiça esforço ou causa dano.

A fronteira de URLs

A fronteira é o coração de um crawler: uma fila que precisa responder a duas perguntas diferentes ao mesmo tempo. Qual URL importa mais? E qual host podemos contatar agora?

A resposta clássica é o design do Mercator, descrito no capítulo sobre a fronteira de URLs do livro Introduction to Information Retrieval:

• As filas da frente cuidam da prioridade. Um priorizador coloca cada URL nova em uma de F filas com base em sinais como a frequência com que a página muda, a popularidade dos links ou a importância do site.
• As filas de trás cuidam da cortesia. Cada fila de trás guarda URLs de exatamente um host. Um heap registra, por host, o momento mais cedo em que ele pode ser contatado de novo.
• Uma thread de fetcher pega o host do topo do heap, baixa uma URL da fila de trás desse host e devolve o host ao heap com um novo momento mais cedo. Quando uma fila de trás esvazia, ela é reabastecida a partir das filas da frente, favorecendo as prioridades mais altas.

Os projetistas do Mercator recomendavam cerca de três vezes mais filas de trás do que threads de fetcher, para que as threads raramente esperem por um host que precisa ser poupado.

Em escala, particione a fronteira por host: aplique hash ao nome do host para escolher um shard da fronteira, de modo que todas as URLs de um host fiquem em um só lugar e a cortesia possa ser aplicada localmente, sem coordenação.

Cortesia e robots.txt

Um crawler educado envia uma requisição por vez para cada host e espera entre as requisições. Uma heurística comum do mesmo capítulo: esperar cerca de dez vezes o tempo que o último download daquele host levou, para que servidores lentos ganhem automaticamente mais folga. Recue ainda mais em respostas 429 e 503 e respeite qualquer cabeçalho Retry-After.

O robots.txt virou padrão em 2022 com a RFC 9309. As regras que um crawler precisa acertar:

A assimetria entre 4xx e 5xx surpreende: um arquivo ausente significa “pode ir”, mas um erro de servidor significa “fique fora”, porque o crawler não tem como saber o que as regras diriam. Crawl-delay não faz parte da RFC 9309, e os crawlers divergem sobre respeitá-lo ou não. Identifique o seu crawler com um user agent descritivo que inclua uma URL com dados de contato.

Deduplicando URLs

A mesma página se esconde atrás de muitas URLs: HTTP://Example.com:80/a/./b?utm_source=x#top e http://example.com/a/b são uma página só. Normalize antes de verificar se uma URL já foi vista:

• Passe o esquema e o host para minúsculas, remova portas padrão, resolva os segmentos . e .. e normalize a codificação percentual, seguindo a seção 6 da RFC 3986.
• Remova o fragmento, que nunca chega ao servidor.
• Remova com cuidado parâmetros de rastreamento conhecidos, como utm_*; outros parâmetros podem mudar o conteúdo.
• Respeite as indicações rel="canonical" depois do download.

Depois, verifique um conjunto de URLs vistas. Com bilhões de URLs, um filtro de Bloom é a escolha usual. Dimensionado para um bilhão de URLs com 1% de falsos positivos, ele precisa de cerca de 9,6 bits por URL, algo como 1,2 GB no total, com sete funções de hash. Um falso positivo significa pular uma URL que você na verdade não viu, um custo aceitável a 1% para a maioria dos crawls; mantenha um armazenamento exato para URLs que você não pode perder, como as entradas de sitemaps.

Deduplicando conteúdo

Espelhos, versões para impressão e parâmetros de sessão produzem páginas idênticas, ou quase, sob URLs diferentes. Duplicatas exatas são fáceis: aplique hash ao conteúdo normalizado e compare. Quase duplicatas precisam de uma impressão digital que muda pouco quando a página muda pouco. O simhash é a técnica padrão: uma impressão digital de 64 bits em que documentos parecidos diferem em poucos bits. Pesquisadores do Google relataram em 2007 que, para um repositório de oito bilhões de páginas, impressões digitais simhash de 64 bits com um limiar de três bits diferentes eram uma configuração prática para detectar quase duplicatas.

Armadilhas para crawlers

Alguns sites geram espaços infinitos de URLs, muitas vezes sem querer: calendários com um link de “próximo mês” para sempre, IDs de sessão em toda URL, busca facetada com todas as combinações de filtros e links relativos que vão aumentando um caminho. Defesas:

• Limite o tamanho das URLs e a profundidade dos caminhos.
• Limite as páginas por host em cada ciclo de crawl, de acordo com a importância do host.
• Detecte segmentos de caminho repetidos como /a/b/a/b/a/b.
• Reduza a prioridade de URLs cujas impressões digitais de conteúdo continuam batendo com páginas que você já tem.

Os sitemaps ajudam no sentido oposto: listam as URLs que um site quer que sejam rastreadas, até 50.000 URLs ou 50 MB sem compressão por arquivo de sitemap, com arquivos de índice de sitemaps para mais.

Em volta do loop: DNS, armazenamento e recrawl

• O DNS é um gargalo escondido. Com centenas de downloads por segundo, um resolvedor com cache compartilhado perto dos fetchers evita mandar cada consulta para cima.
• Armazenamento. Grave as respostas brutas no armazenamento de objetos em arquivos grandes por lote e envie o texto processado e os links para a indexação por um stream.
• Recrawl. As páginas mudam em ritmos diferentes. Acompanhe com que frequência cada página mudou nas visitas anteriores e agende o próximo download de acordo; requisições condicionais com If-Modified-Since ou ETag economizam banda quando nada mudou.
• Páginas cheias de JavaScript precisam de um navegador headless, bem mais caro por página. Renderize só os hosts que precisam disso.

O diagrama do web crawler

Como ler:

• A moldura é a fronteira de URLs: as filas de prioridade alimentam as filas por host, que aplicam a cortesia.
• Os fetchers pegam uma URL por host de cada vez, consultam o cache de robots.txt e o cache DNS e baixam da internet.
• As páginas brutas vão para o repositório de objetos. O parser extrai links e texto.
• Os links novos passam pelo filtro de URLs vistas antes de voltar à fronteira, fechando o loop. As impressões digitais de conteúdo sinalizam as quase duplicatas.
• As páginas processadas seguem para a indexação pelo stream à direita.
• O bloco Markdown lista os números de capacidade e as regras de cortesia.

Desenhar pipelines com loops

• Deixe o loop visível. Um crawler é um ciclo; desenhá-lo como um pipeline reto esconde a realimentação que causa os problemas de armadilhas e duplicatas.
• Mostre onde a cortesia é aplicada. Coloque as filas por host na figura, não em uma nota de rodapé.
• Marque os caches como caches. Os caches de robots.txt e DNS mudam a carga sobre o mundo externo; rotule a expiração deles.
• Coloque números nas arestas: páginas por segundo entrando, links por página saindo.

Para o método geral, veja o exemplo de diagrama de design de sistemas. O controle de taxa para cada host usa as mesmas ideias do design de sistema de rate limiter, e o processamento depois do crawl se parece com o diagrama de arquitetura de pipeline de dados.

Monte no Archboard

1. Entre com Google ou GitHub e crie um diagrama.
2. Adicione uma Moldura do pack Básico chamada URL frontier e coloque dentro dois nós Fila do pack Dados: as filas de prioridade e as filas por host.
3. Adicione um nó Instância de computação do pack Nuvem para os fetchers, um nó DNS e um nó Internet do pack Rede, e um nó Redis do pack Dados para o cache de robots.txt.
4. Adicione um Repositório de objetos do pack Dados para as páginas brutas e outro nó Instância de computação para o parser.
5. Adicione um segundo nó Redis para o filtro de URLs vistas, um Banco de dados gerenciado do pack Nuvem para as impressões digitais de conteúdo e um nó Kafka do pack Dados para as páginas a caminho da indexação.
6. Desenhe o loop com arestas rotuladas e adicione um bloco Markdown do pack Básico com os números.

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

Perguntas frequentes

O que é uma fronteira de URLs? A estrutura de dados que decide o que um crawler baixa em seguida. Ela combina filas de prioridade, que ordenam as URLs por importância, com filas por host e um agendamento que impedem o crawler de contatar qualquer host com frequência demais.

Como os crawlers se mantêm educados? Uma conexão por host de cada vez, um atraso entre requisições que cresce com o tempo de resposta do servidor, recuo diante de respostas 429 e 503 e respeito ao robots.txt.

O que acontece se o robots.txt retornar um erro? Pela RFC 9309, um status 4xx significa que o crawler pode rastrear o site, enquanto um status 5xx ou um erro de rede significa que ele deve supor que tudo está proibido até conseguir ler o arquivo.

Como os crawlers evitam baixar a mesma página duas vezes? Eles normalizam as URLs e as verificam contra um conjunto de URLs vistas, muitas vezes um filtro de Bloom, e calculam impressões digitais do conteúdo com hashes exatos e simhash para pegar a mesma página sob URLs diferentes.

De que tamanho precisa ser um filtro de Bloom para um bilhão de URLs? Cerca de 1,2 GB para uma taxa de falsos positivos de 1%, usando por volta de 9,6 bits por URL e sete funções de hash. Taxas de erro menores custam mais bits por entrada.

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