CS Fundamentals Trainer · Guias

Projetando um web crawler

A fila de URLs (frontier) com polidez por host (código em quatro linguagens), normalização de URLs, um filtro de Bloom medido, robots.txt, detecção de quase duplicatas, spider traps testadas em um site local e frescor.

39 min de leitura

Um web crawler é um programa que parte de algumas páginas conhecidas, as baixa, encontra os links dentro delas e segue esses links para baixar mais, de novo e de novo. Os mecanismos de busca usam crawlers para coletar a web; também os usam rastreadores de preços, arquivos, verificadores de links e os pipelines de dados por trás do aprendizado de máquina. "Projete um web crawler" é uma pergunta favorita de system design porque o laço básico cabe em dez linhas e tudo em volta é difícil: a web é enorme, hostil, duplicada e cheia de armadilhas, e os sites que você visita pertencem a pessoas que não concordaram em ser visitadas em velocidade máxima. Este guia constrói o projeto em camadas e testa cada peça: um filtro de Bloom medido, a normalização de URLs, as regras do robots.txt, a detecção de quase duplicatas, um escalonador de polidez por host (em quatro linguagens) e um pequeno crawl contra um site local com uma spider trap.

1. O que estamos construindo

Requisitos funcionais

Requisitos não funcionais

Números de guardanapo

Suponha 1 bilhão de páginas por mês, uma página HTML média de 100 KB (uma suposição; meça a sua) e 10 links por página.

GrandezaCálculoResultado
Taxa de busca1 000 000 000 ÷ (30 × 86 400 s)cerca de 386 páginas por segundo
Largura de banda386 × 100 KBcerca de 38,6 MB/s, aproximadamente 310 Mbit/s
Armazenamento bruto por mês1 B × 100 KBcerca de 100 TB (cerca de 25 TB se comprimido 4:1, uma razão suposta)
URLs descobertas1 B de páginas × 10 linkscerca de 10 bilhões de URLs a conferir contra "já visto"
Consultas de DNSno máximo uma por busca, então até 386 ÷ s; se um crawl busca cerca de 50 páginas por host e divide uma consulta entre elas, 386 ÷ 50cerca de 386 por segundo sem cache, cerca de 8 por segundo com uma consulta por host (as 50 páginas por host são uma suposição)

A taxa de busca é modesta: algumas dezenas de máquinas. As partes difíceis são a verificação de URLs já vistas sobre bilhões de entradas, a polidez entre milhões de hosts e tudo o que a web faz para confundir você.

2. A arquitetura

Diagram: The crawler pipeline

Cada caixa é um serviço ou etapa separados, ligados por filas, o que faz o sistema escalar e se estender (um novo tipo de conteúdo é um novo parser; uma nova verificação é um novo filtro). O resto deste guia percorre as etapas que sustentam o projeto: o frontier, a normalização e o conjunto de vistos, a polidez e o robots, a busca, a detecção de duplicatas, as armadilhas e o frescor.

3. O frontier de URLs

O frontier é a lista de tarefas de URLs, e tem dois trabalhos que puxam em direções opostas.

Prioridade: rastrear primeiro as páginas importantes e de mudança rápida. A página inicial de um jornal importa mais que a 40 000ª página do arquivo de um fórum. A prioridade vem de sinais como a importância baseada em links (pontuações do tipo PageRank), com que frequência a página mudou no passado e a profundidade a partir de uma semente.

Polidez: acessar qualquer host devagar. Buscar um bilhão de páginas é fácil; buscá-las sem derrubar um site pequeno é a verdadeira restrição. Uma regra comum é no máximo uma requisição por vez a um host, com um atraso entre as requisições (muitas vezes um segundo ou mais, mais se o robots.txt pedir).

O projeto clássico, do crawler Mercator, separa as duas coisas com duas camadas de filas [1]. A segunda camada tem muito menos filas do que há hosts: cada fila de trás guarda URLs de um host por vez, e o número de filas de trás é escolhido como um múltiplo do número de threads de busca, de modo que uma thread quase sempre encontre um host pronto (o multiplicador é um botão de ajuste: dimensione-o medindo com que frequência as threads ficam ociosas). Quando uma fila de trás esvazia, é reabastecida com o próximo host das filas da frente.

Diagram: Two layers of queues in the frontier: priority first, then politeness

A metade de trás é a parte interessante: uma fila FIFO por host e um heap ordenado pelo primeiro momento em que cada host pode ser contatado de novo. Um fetcher pergunta "qual host está pronto?"; pega a próxima URL desse host; quando a busca termina, o host volta ao heap com agora + atraso. Um host com um servidor lento ou um Crawl-delay longo simplesmente aparece com menos frequência, e um milhão de hosts dividem os fetchers de forma justa.

Aqui está esse escalonador. Executei-o com três hosts de três páginas cada e um atraso de um segundo: fez 9 buscas em 2,0 segundos virtuais (nos instantes 0, 1 e 2), e nenhum host foi contatado duas vezes em menos de um segundo. As versões em Python, Go e JavaScript rodaram todas e deram o mesmo resultado (escolha uma linguagem nas abas; sua escolha é lembrada):

import heapq
from collections import deque
from urllib.parse import urlsplit

class Frontier:
    """One FIFO queue per host, plus a heap that says which host may be contacted next."""
    def __init__(self, delay=1.0):
        self.delay = delay
        self.queues = {}      # host -> deque of urls
        self.heap = []        # (earliest time we may contact it, host) for hosts that have work and are idle
        self.active = set()   # hosts that are in the heap or being fetched right now

    def add(self, url, now):
        host = urlsplit(url).netloc
        self.queues.setdefault(host, deque()).append(url)
        if host not in self.active:
            self.active.add(host)
            heapq.heappush(self.heap, (now, host))

    def next(self, now):
        """Returns (url, None) when a host is ready, else (None, seconds_to_wait), or (None, None) if empty."""
        if not self.heap:
            return None, None
        ready_at, host = self.heap[0]
        if ready_at > now:
            return None, ready_at - now
        heapq.heappop(self.heap)
        return self.queues[host].popleft(), None      # the host stays "active" while its page is fetched

    def done(self, url, now, delay=None):
        host = urlsplit(url).netloc
        if self.queues[host]:
            heapq.heappush(self.heap, (now + (self.delay if delay is None else delay), host))
        else:
            self.active.discard(host)
            del self.queues[host]
type slot struct {
	readyAt float64
	host    string
}
type slotHeap []slot

func (h slotHeap) Len() int           { return len(h) }
func (h slotHeap) Less(i, j int) bool { return h[i].readyAt < h[j].readyAt }
func (h slotHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *slotHeap) Push(x any)        { *h = append(*h, x.(slot)) }
func (h *slotHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// Frontier keeps one FIFO queue per host and a heap saying which host may be contacted next.
type Frontier struct {
	Delay  float64
	queues map[string][]string
	heap   slotHeap
	active map[string]bool // in the heap, or being fetched right now
}

func NewFrontier(delay float64) *Frontier {
	return &Frontier{Delay: delay, queues: map[string][]string{}, active: map[string]bool{}}
}

func hostOf(raw string) string { u, _ := url.Parse(raw); return u.Host }

func (f *Frontier) Add(raw string, now float64) {
	h := hostOf(raw)
	f.queues[h] = append(f.queues[h], raw)
	if !f.active[h] {
		f.active[h] = true
		heap.Push(&f.heap, slot{now, h})
	}
}

// Next returns a URL when a host is ready; otherwise how long to wait (wait < 0 means empty).
func (f *Frontier) Next(now float64) (raw string, wait float64) {
	if len(f.heap) == 0 {
		return "", -1
	}
	if top := f.heap[0]; top.readyAt > now {
		return "", top.readyAt - now
	}
	s := heap.Pop(&f.heap).(slot)
	raw, f.queues[s.host] = f.queues[s.host][0], f.queues[s.host][1:]
	return raw, 0
}

// Done is called when the fetch of raw has finished.
func (f *Frontier) Done(raw string, now float64) {
	h := hostOf(raw)
	if len(f.queues[h]) > 0 {
		heap.Push(&f.heap, slot{now + f.Delay, h})
		return
	}
	delete(f.active, h)
	delete(f.queues, h)
}
class Frontier {
  constructor(delay = 1.0) {
    this.delay = delay;
    this.queues = new Map(); // host -> array of urls
    this.ready = [];         // [readyAt, host], kept sorted; hosts that have work and are idle
    this.active = new Set(); // in `ready`, or being fetched right now
  }
  #push(readyAt, host) {
    let i = this.ready.findIndex(([t]) => t > readyAt);
    if (i < 0) i = this.ready.length;
    this.ready.splice(i, 0, [readyAt, host]);
  }
  add(url, now) {
    const host = new URL(url).host;
    if (!this.queues.has(host)) this.queues.set(host, []);
    this.queues.get(host).push(url);
    if (!this.active.has(host)) { this.active.add(host); this.#push(now, host); }
  }
  /** { url } when a host is ready, { wait } seconds otherwise, {} when empty. */
  next(now) {
    if (this.ready.length === 0) return {};
    const [readyAt, host] = this.ready[0];
    if (readyAt > now) return { wait: readyAt - now };
    this.ready.shift();
    return { url: this.queues.get(host).shift() };
  }
  done(url, now, delay = this.delay) {
    const host = new URL(url).host;
    if (this.queues.get(host).length > 0) this.#push(now + delay, host);
    else { this.active.delete(host); this.queues.delete(host); }
  }
}
public class Frontier
{
    private readonly double _delay;
    private readonly Dictionary<string, Queue<string>> _queues = new();
    private readonly PriorityQueue<string, double> _ready = new();   // host, earliest time we may contact it
    private readonly HashSet<string> _active = new();                // in _ready, or being fetched right now

    public Frontier(double delay = 1.0) => _delay = delay;

    public void Add(string url, double now)
    {
        var host = new Uri(url).Authority;
        if (!_queues.TryGetValue(host, out var q)) _queues[host] = q = new Queue<string>();
        q.Enqueue(url);
        if (_active.Add(host)) _ready.Enqueue(host, now);
    }

    /// <summary>A url when a host is ready; otherwise how long to wait; both null when empty.</summary>
    public (string? Url, double? Wait) Next(double now)
    {
        if (!_ready.TryPeek(out var host, out var readyAt)) return (null, null);
        if (readyAt > now) return (null, readyAt - now);
        _ready.Dequeue();
        return (_queues[host].Dequeue(), null);
    }

    public void Done(string url, double now, double? delay = null)
    {
        var host = new Uri(url).Authority;
        if (_queues[host].Count > 0) _ready.Enqueue(host, now + (delay ?? _delay));
        else { _active.Remove(host); _queues.Remove(host); }
    }
}

Em escala real o frontier não cabe em memória: as filas por host vivem em disco, com um pequeno buffer em memória na frente de cada uma. O frontier também é particionado por host (um hash do nome do host escolhe a máquina do crawler), de modo que todas as URLs de um host vivem em uma máquina e só essa máquina impõe o atraso de polidez. Use consistent hashing, para que adicionar uma máquina mova poucos hosts (veja o guia de consistent hashing).

4. Normalização de URLs e o conjunto de vistos

A mesma página tem muitas grafias. Se o crawler as trata como páginas diferentes, desperdiça trabalho e pode entrar em laço para sempre. Antes de conferir "já vi isto?", normalize a URL. Escrevi um normalizador e o executei nesta lista (relativa a https://example.com/dir/index.html). Minha primeira versão decodificava todo escape e depois recodificava o caminho, o que transformava a%2Fb em a/b, uma URL diferente, e descartava os colchetes de hosts IPv6; um revisor pegou os dois, a versão abaixo os corrige, e o apêndice contém a tabela de testes (14 casos, todos passam):

EntradaNormalizada
HTTP://Example.COM:80/a/./b/../c?b=2&a=1&utm_source=x#tophttp://example.com/a/c?a=1&b=2
http://example.com/a/c?a=1&b=2http://example.com/a/c?a=1&b=2 (idêntica à linha acima)
https://example.com:443//a//c/https://example.com/a/c/
https://example.com/caféhttps://example.com/caf%C3%A9
https://example.com/caf%C3%A9https://example.com/caf%C3%A9 (idêntica à linha acima)
https://example.com/a%2Fbhttps://example.com/a%2Fb (%2F não é /: mantido)
https://example.com/%7Euser/%41https://example.com/~user/A (apenas caracteres não reservados são decodificados)
http://[::1]:8080/xhttp://[::1]:8080/x (o IPv6 mantém os colchetes)
/relative/page?id=1https://example.com/relative/page?id=1
mailto:a@b.c, javascript:void(0)descartadas (não são http nem https)

As regras que ele aplica: converter o esquema e o host para minúsculas; descartar a porta padrão; resolver . e ..; decodificar apenas os escapes de caracteres não reservados (%7E vira ~), pôr em maiúsculas o hex do resto e manter os reservados como %2F como estão, e codificar caracteres não ASCII crus; ordenar os parâmetros da query; descartar o fragmento (#top nunca é enviado ao servidor); resolver links relativos contra o endereço da própria página (ou seu <base href>, se tiver um); manter apenas http e https.

from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode, quote, urljoin
import re

TRACKING = {"utm_source", "utm_medium", "utm_campaign", "utm_term", "utm_content", "fbclid", "gclid", "ref"}
UNRESERVED = frozenset("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-._~")

def fix_escapes(text, safe):
    """RFC 3986 safe normalisation: decode only unreserved characters, upper-case the hex of every
    other escape (so %2F stays %2F: it is not the same as /), and encode raw non-ASCII text."""
    text = re.sub(r"%(?![0-9A-Fa-f]{2})", "%25", text)                  # a lone % is data, not an escape
    def fix(m):
        ch = chr(int(m.group(1), 16))
        return ch if ch in UNRESERVED else "%" + m.group(1).upper()
    return quote(re.sub(r"%([0-9A-Fa-f]{2})", fix, text), safe=safe + "%")

def normalize(url, base=None):
    if base:
        url = urljoin(base, url)
    s = urlsplit(url.strip())
    scheme = s.scheme.lower()
    if scheme not in ("http", "https"):
        return None
    host = (s.hostname or "").lower().rstrip(".")
    if not host:
        return None
    if ":" in host:                                                     # an IPv6 address needs its brackets back
        host = f"[{host}]"
    default = 80 if scheme == "http" else 443
    netloc = host if s.port in (None, default) else f"{host}:{s.port}"
    path = fix_escapes(s.path or "/", "/:@!$&'()*+,;=-._~")
    out = []
    for seg in path.split("/"):                                         # resolve . and ..
        if seg == ".":
            continue
        if seg == "..":
            if len(out) > 1:
                out.pop()
            continue
        out.append(seg)
    path = re.sub(r"/{2,}", "/", "/".join(out) or "/")
    query = sorted((k, v) for k, v in parse_qsl(s.query, keep_blank_values=True) if k.lower() not in TRACKING)
    return urlunsplit((scheme, netloc, path, urlencode(query), ""))

Duas dessas regras são heurísticas, não padrões: descartar parâmetros de rastreamento e colapsar // em / estão certos para a maioria dos sites e errados para alguns (alguns sites realmente dão significado a ?ref= ou tratam // de modo diferente). A RFC 3986 define as normalizações seguras (maiúsculas e minúsculas, percent-encoding, segmentos de ponto) [2]; qualquer coisa além disso é uma troca que você escolhe por crawl, e o custo de ser agressivo demais é perder páginas. Um refinamento comum é aprender, por site, quais parâmetros nunca mudam o conteúdo (busque duas vezes, com e sem, e compare os hashes de conteúdo).

O conjunto de vistos em escala

Depois de normalizar, pergunte "já enfileirei esta URL antes?". Com 10 bilhões de URLs candidatas, um conjunto hash de hashes de 8 bytes precisa de cerca de 80 GB; um filtro de Bloom responde "definitivamente não visto" ou "provavelmente visto" em uma fração do espaço. Seus erros são unilaterais: nunca diz "não visto" para uma URL que foi adicionada, mas às vezes diz "visto" para uma que não foi (um falso positivo), o que aqui significa pular uma página que você poderia ter rastreado. Para um crawl, essa é uma perda aceitável quando a taxa é pequena. Medi com um filtro contendo 1 milhão de URLs e testando 200 000 URLs que nunca foram adicionadas:

Bits por URLMemória para 1 M de URLsFunções de hashFalsos positivos medidosFórmula
40,5 MB314,70%14,69%
81,0 MB62,14%2,16%
101,2 MB70,80%0,82%
162,0 MB110,046%0,046%

As taxas medidas coincidem com a fórmula de livro-texto, (1 - e^(-kn/m))^k para n itens, m bits e k funções de hash, e também conferi que toda URL adicionada é reportada como presente (sem falsos negativos). O custo de um falso positivo é uma página perdida, então escolha o tamanho pela taxa de perdas que você aceita: para 10 bilhões de URLs, 8 bits cada são cerca de 10 GB para 2% de perdas, 16 bits cada cerca de 20 GB para 0,05%. Divida o filtro pela partição de hosts para que cada crawler guarde só a sua parte. Os filtros de Bloom não podem apagar e se enchem com o tempo, então um crawl de longa duração os reconstrói ou os rotaciona.

import hashlib

class Bloom:
    def __init__(self, m, k):
        self.m, self.k, self.bits = m, k, bytearray((m + 7) // 8)

    def _positions(self, item):
        h = hashlib.blake2b(item.encode(), digest_size=16).digest()
        a = int.from_bytes(h[:8], "big")
        b = int.from_bytes(h[8:], "big") | 1
        return [(a + i * b) % self.m for i in range(self.k)]      # double hashing: k positions from 2 hashes

    def add(self, item):
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def __contains__(self, item):
        return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._positions(item))

Se uma página perdida não é aceitável (por exemplo, um arquivo jurídico), use uma estrutura exata: um armazenamento chave-valor indexado pelo hash da URL, com sharding por host. Custa mais espaço e mais consultas, e é a resposta segura.

5. Polidez e robots.txt

O Robots Exclusion Protocol é um arquivo de texto simples em /robots.txt com regras para crawlers, agora um padrão da IETF (RFC 9309) [3]. As regras que importam:

Testei o parser padrão do Python em um arquivo com um Disallow: /private/, um Allow: /private/public.html, Crawl-delay: 2 e um grupo que bane o badbot por completo:

AgenteCaminhoPermitido?
mybot/private/xnão
mybot/private/public.htmlsim
mybot/index.htmlsim
badbot/index.htmlnão

O parser também reportou o atraso de 2 para o mybot.

Boas maneiras além do robots.txt:

6. Buscando

O fetcher é onde a bagunça da web chega. Regras defensivas:

8. Detecção de duplicatas

Há dois tipos diferentes, e o crawler precisa dos dois.

A mesma URL, muitas grafias: tratado pela normalização e pelo conjunto de vistos (seção 4).

URLs diferentes, o mesmo conteúdo ou quase o mesmo: espelhos, versões para impressão, ids de sessão em URLs, páginas com uma caixa rotativa de "artigos relacionados", páginas de texto padrão. Pulá-las poupa armazenamento e espaço de índice.

Medi em um parágrafo curto (84 palavras) com shingles de 3 palavras e uma impressão de 64 bits:

Comparado com o originalDistância de Hamming (de 64 bits)
Uma cópia exata0
O mesmo texto mais um rodapé padrão ("Publicado em…, Compartilhe esta página, Artigos relacionados…")10
O mesmo texto com duas palavras trocadas9
Um artigo diferente24

Cuidado com a lição aqui. O limiar apertado usado para o crawl em escala web no artigo (uma distância de 3 para páginas longas) não teria pego o rodapé nem a edição de duas palavras no meu texto curto; as distâncias crescem conforme o documento fica mais curto, porque cada mudança move uma parcela maior dos votos. Escolha o limiar por comprimento de documento a partir de exemplos rotulados, remova o texto padrão (menus, rodapés, anúncios) antes de calcular a impressão e use um limiar mais frouxo apenas onde um falso acerto é barato. Para buscar impressões rapidamente, divida os 64 bits em blocos e indexe cada bloco, de modo que duas impressões dentro de uma pequena distância precisem concordar em pelo menos um bloco (a ideia do artigo).

import hashlib, re

def simhash(text, k=3, bits=64):
    words = re.findall(r"\w+", text.lower())
    shingles = [" ".join(words[i:i + k]) for i in range(max(1, len(words) - k + 1))]
    votes = [0] * bits
    for s in shingles:
        h = int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")
        for i in range(bits):
            votes[i] += 1 if (h >> i) & 1 else -1
    return sum(1 << i for i in range(bits) if votes[i] > 0)

def distance(a, b):
    return bin(a ^ b).count("1")

9. Spider traps

Uma spider trap é uma parte de um site que gera um suprimento interminável de URLs novas: um calendário com um link "próximo mês" que continua para sempre, um id de sessão em cada link, combinações de filtros (?color=red&size=m&sort=price…) que se multiplicam, um link relativo que se acrescenta a si mesmo (/a/b/a/b/a/b/…). Algumas são acidentes; algumas são deliberadas. Um crawler ingênuo nunca termina.

Construí um site de teste local (código no apêndice) com 40 páginas reais dispostas em árvore, uma URL alias (/about?utm_source=home), um redirecionamento, um robots.txt que proíbe /private/ e uma armadilha de calendário. Depois executei o mini-crawler (4 threads de trabalho, um atraso de 50 ms por host, robots conferido, redirecionamentos enviados de volta pelo frontier) de três formas:

ExecuçãoPáginas buscadasPáginas reais distintasPáginas da armadilha de calendárioRequisições a /private/Como terminou
1. Sem defesas20040 de 401580parou só pela minha parada forçada em 200
2. Limite de profundidade de 64840 de 4060o frontier esvaziou sozinho, em 3,8 s
3. Orçamento de 50 URLs por host4740 de 4050o frontier esvaziou sozinho, em 2,6 s

O crawl sem defesas achou as 40 páginas reais e depois gastou 158 das suas 200 buscas no calendário; ainda estava achando meses novos do calendário quando a minha parada forçada o encerrou, e teria continuado para sempre. As duas defesas acharam as 40 páginas reais e pararam sozinhas. Outros resultados das mesmas execuções: o robots.txt foi respeitado (nenhuma requisição a /private/), o alias /about?utm_source=home colapsou em /about pela normalização (sem conteúdo duplicado), o redirecionamento foi seguido pelo frontier e o crawler fez 19 requisições por segundo ao único host, que é o que um atraso de 50 ms permite. O menor intervalo entre duas requisições foi de 49 a 50 ms nas execuções 2 e 3, mas só 15 a 27 ms na execução 1 (15 ms na primeira vez, 25 a 27 ms em duas repetições com o normalizador corrigido; os outros números não mudaram); uma causa provável é que o site de teste e o crawler compartilham um processo Python e o seu escalonador, de modo que as chegadas podem se agrupar mesmo que o atraso seja aplicado quando cada URL é retirada. Em produção, imponha o atraso no servidor que fala com o host e meça os intervalos reais.

As defesas, da mais simples à mais elaborada:

  1. Uma profundidade máxima a partir da semente (o número de links seguidos).
  2. Um orçamento por host (máximo de páginas ou URLs por site, por crawl). Também limita o dano de qualquer site.
  3. Um comprimento máximo de URL e um número máximo de segmentos de caminho ou parâmetros de query.
  4. Detecção de padrões: muitas URLs que diferem só em um segmento numérico ou de data (/cal/2026/10, /cal/2026/11, …) parecem uma armadilha; limite cada padrão, ou diminua a prioridade conforme a contagem cresce.
  5. Detecção baseada em conteúdo: uma URL nova cujo hash de conteúdo ou simhash coincide com páginas já vistas naquele site é sinal de aliases ou de um laço.
  6. Decaimento de prioridade: páginas achadas só por cadeias muito longas recebem prioridade baixa e podem nunca ser alcançadas.
  7. Uma intervenção humana: uma lista de bloqueio de hosts e padrões que os operadores podem atualizar sem um deploy.

10. Frescor: rastrear de novo

A web muda. Um crawler que visita cada página uma vez acaba com uma cópia obsoleta. A política de re-crawl decide o que buscar de novo, e quando:

11. Escalando e falhando com segurança

12. Monitoramento e testes

13. Erros comuns

14. Perguntas que os entrevistadores gostam de acrescentar

"Como você evita rastrear a mesma página duas vezes?"

Normalize a URL e depois confira-a contra um conjunto de vistos (um filtro de Bloom ou um armazenamento chave-valor com sharding); e no nível do conteúdo, faça hash para duplicatas exatas e use simhash para quase duplicatas. Diga a troca do filtro de Bloom: falsos positivos significam páginas puladas.

"Como você garante que não sobrecarrega um site?"

Uma fila por host, uma requisição por vez por host, um atraso entre as requisições (e o Crawl-delay do site se você escolher respeitá-lo), um heap de "próximo momento permitido" por host, recuo em 429/503 e particionamento por host para que uma máquina seja dona de cada host.

"O que é uma spider trap e como você se defende dela?"

Um espaço de URLs interminável (calendários, ids de sessão, combinações de filtros). Defenda-se com limites de profundidade, um orçamento por host, limites de comprimento e de padrões de URL, verificações baseadas em conteúdo e decaimento de prioridade.

"Como você rastrearia sites pesados em JavaScript?"

Um pool de navegadores headless para as páginas que precisam, usado seletivamente por causa do custo; ou achar a API JSON ou o sitemap do site. Guarde em cache os resultados renderizados e renderize de novo apenas quando mudar.

"Como você mantém o índice fresco?"

Estime as taxas de mudança a partir das visitas passadas, revisite com mais frequência as páginas que mudam e as importantes, use requisições condicionais para tornar barato o "inalterado" e use sitemaps e feeds como dicas.

"Como você o escalaria para 100 vezes o tamanho?"

Particione o frontier e o conjunto de vistos por host, adicione máquinas, use I/O assíncrono, mantenha o conteúdo em armazenamento de objetos e vigie o limite de polidez por host: é o teto real para sites grandes, e é por isso que sites muito grandes são rastreados com acordos e feeds, não apenas com mais máquinas.

"Como você rastreia este site que exige login ou que bloqueia bots?"

Você não deve, a menos que o dono tenha concordado. A autenticação e o bloqueio de bots são o site dizendo não. A resposta ética e legal é pedir acesso ou uma API.

15. Coisas a mencionar em uma entrevista

Resumo rápido

  1. Um crawler é um laço: pegue uma URL do frontier, busque, faça o parse, filtre e adicione URLs novas, com muito cuidado em cada passo.
  2. O frontier equilibra prioridade (o que importa primeiro) e polidez (uma requisição por vez por host, com um atraso); o projeto clássico é uma fila por host mais um heap de próximos momentos permitidos.
  3. Normalize as URLs e depois use um filtro de Bloom para o conjunto de vistos: 8 bits por URL deram uma taxa de falsos positivos de 2,1% no meu teste, e um falso positivo significa uma página pulada.
  4. Leia o robots.txt (RFC 9309) antes de qualquer página, guarde-o em cache, trate um erro do servidor como "proibido" e identifique o seu crawler.
  5. Trate os redirecionamentos pelo frontier e use timeouts, limites de tamanho, backoff e requisições condicionais.
  6. Detecte duplicatas por hash exato e por simhash, cujo limiar depende do comprimento do documento.
  7. Defenda-se de armadilhas com limites de profundidade, orçamentos por host e limites de URL: no meu teste, o crawl sem defesas gastou 158 das suas 200 buscas em um calendário.
  8. Particione por host para escalar, faça checkpoints do frontier, guarde o conteúdo em armazenamento de objetos e rastreie de novo pela taxa de mudança.

Apêndice: o código dos experimentos

Tudo o que foi medido acima pode ser executado de novo. Salve os três arquivos em uma pasta (o normalize.py é a listagem da seção 4, seguida da sua tabela de testes if __name__ == "__main__":), depois execute python3 normalize.py para os testes do normalizador e python3 crawl.py para as três execuções com armadilha. Apenas biblioteca padrão do Python 3. Os tempos dependem da sua máquina; as contagens de páginas devem coincidir.

testsite.py: o site local (40 páginas reais em árvore, um alias, um redirecionamento, um robots.txt que proíbe /private/, uma armadilha de calendário):

# A local test site: a real tree of pages, alias URLs, a redirect, a robots.txt, and a calendar spider trap.
import http.server, socketserver, threading, time, re
from urllib.parse import urlsplit, parse_qs
HITS=[]; LOCK=threading.Lock()
N_DOCS=40
def page(title,links,body=""):
    a="".join(f'<li><a href="{l}">{l}</a></li>' for l in links)
    return f"<html><head><title>{title}</title></head><body><h1>{title}</h1><p>{body}</p><ul>{a}</ul></body></html>".encode()
class H(http.server.BaseHTTPRequestHandler):
    def log_message(self,*a): pass
    def do_GET(self):
        u=urlsplit(self.path); p=u.path
        with LOCK: HITS.append((time.time(),self.path))
        if p=="/robots.txt":
            return self.send(200,b"User-agent: *\nDisallow: /private/\nCrawl-delay: 0.05\n","text/plain")
        if p=="/old": 
            self.send_response(301); self.send_header("Location","/docs/0"); self.end_headers(); return
        if p=="/": return self.send(200,page("Home",["/docs/0","/cal/2026/1","/private/secret","/old","/about?utm_source=home","/about"]))
        if p=="/about": return self.send(200,page("About",["/","/docs/1"],"About this site."))
        m=re.fullmatch(r"/docs/(\d+)",p)
        if m:
            i=int(m.group(1))
            if i>=N_DOCS: return self.send(404,b"nope")
            kids=[f"/docs/{2*i+1}",f"/docs/{2*i+2}"]
            return self.send(200,page(f"Doc {i}",kids+["/"],f"Unique text number {i} about topic {i*7919%97}. "*5))
        m=re.fullmatch(r"/cal/(\d+)/(\d+)",p)      # the trap: every month links to the next, forever
        if m:
            y,mo=int(m.group(1)),int(m.group(2)); ny,nm=(y+1,1) if mo==12 else (y,mo+1)
            return self.send(200,page(f"Calendar {y}-{mo}",[f"/cal/{ny}/{nm}","/"],"No events."))
        if p.startswith("/private/"): return self.send(200,page("Secret",[]))
        self.send(404,b"nope")
    def send(self,code,body,ctype="text/html"):
        self.send_response(code); self.send_header("Content-Type",ctype); self.send_header("Content-Length",str(len(body))); self.end_headers(); self.wfile.write(body)
class S(socketserver.ThreadingMixIn,http.server.HTTPServer): daemon_threads=True
def start(port=8765):
    s=S(("127.0.0.1",port),H); threading.Thread(target=s.serve_forever,daemon=True).start(); return s

crawl.py: o mini-crawler (4 threads, atraso por host, robots conferido, redirecionamentos enviados de volta pelo frontier) e as três execuções:

import urllib.error, threading, time, heapq, hashlib, re, urllib.request, urllib.robotparser, collections
from urllib.parse import urlsplit
from html.parser import HTMLParser
import testsite as S, normalize as norm
class NoRedirect(urllib.request.HTTPRedirectHandler):
    def redirect_request(self,*a,**k): return None          # hand 3xx back to us: the target goes through the frontier like any URL
OPENER=urllib.request.build_opener(NoRedirect)

class Links(HTMLParser):
    def __init__(s): super().__init__(); s.out=[]
    def handle_starttag(s,t,a):
        if t=="a": s.out+= [v for k,v in a if k=="href" and v]
def crawl(seed, workers=4, max_depth=None, host_budget=None, delay=0.05, respect_robots=True, hard_stop=300):
    frontier=[(0,0,seed)]; seen={norm.normalize(seed)}; lock=threading.Lock(); tick=[0]
    next_ok=collections.defaultdict(float); per_host=collections.Counter()
    robots={}; hashes=set(); stats=collections.Counter(); fetched=[]
    done=threading.Event()
    def allowed(url):
        h=urlsplit(url).netloc
        if h not in robots:
            r=urllib.robotparser.RobotFileParser(); 
            try: r.parse(urllib.request.urlopen(f"http://{h}/robots.txt",timeout=5).read().decode().splitlines())
            except Exception: r.parse([])
            robots[h]=r
        return robots[h].can_fetch("mybot",url)
    def worker():
        while not done.is_set():
            with lock:
                if stats["fetched"]>=hard_stop: done.set(); return
                item=None
                if frontier:
                    item=heapq.heappop(frontier)
                    h=urlsplit(item[2]).netloc
                    wait=next_ok[h]-time.time()
                    if wait>0: heapq.heappush(frontier,item); item=None       # politeness: not yet
                    else: next_ok[h]=time.time()+delay; stats["busy"]+=1      # counted as busy from the moment it is taken
            if item is None:
                time.sleep(0.005)
                with lock:
                    if not frontier and stats["busy"]==0: done.set()
                continue
            depth,_,url=item
            if respect_robots and not allowed(url):
                with lock: stats["blocked by robots"]+=1; stats["busy"]-=1
                continue
            try:
                r=OPENER.open(url,timeout=5); body=r.read(); final=r.geturl()
            except urllib.error.HTTPError as e:
                loc=e.headers.get("Location") if e.code in (301,302,307,308) else None
                with lock:
                    stats["redirects" if loc else "errors"]+=1; stats["busy"]-=1
                    n=norm.normalize(loc,url) if loc else None
                    if n and n not in seen: seen.add(n); tick[0]+=1; heapq.heappush(frontier,(depth,tick[0],n))
                continue
            except Exception:
                with lock: stats["errors"]+=1; stats["busy"]-=1
                continue
            digest=hashlib.sha1(re.sub(rb"\s+",b" ",body)).hexdigest()
            p=Links(); p.feed(body.decode("utf8","ignore"))
            with lock:
                stats["busy"]-=1; stats["fetched"]+=1; fetched.append(url)
                if digest in hashes: stats["duplicate content"]+=1
                else: hashes.add(digest)
                if max_depth is not None and depth>=max_depth: continue
                for l in p.out:
                    n=norm.normalize(l,final)
                    if not n or n in seen: continue
                    seen.add(n); h=urlsplit(n).netloc
                    if host_budget and per_host[h]>=host_budget: stats["over host budget"]+=1; continue
                    per_host[h]+=1; tick[0]+=1; heapq.heappush(frontier,(depth+1,tick[0],n))
    ts=[threading.Thread(target=worker) for _ in range(workers)]
    t0=time.time(); [t.start() for t in ts]; [t.join() for t in ts]
    return stats, fetched, time.time()-t0
if __name__=="__main__":
    srv=S.start()
    for name,kw in [("1. naive: no depth cap, no budget",dict(hard_stop=200)),
                    ("2. depth cap 6 only",dict(max_depth=6)),
                    ("3. budget of 50 URLs per host only",dict(host_budget=50))]:
        S.HITS.clear()
        st,f,dt=crawl("http://127.0.0.1:8765/",**kw)
        cal=sum(1 for u in f if "/cal/" in u); docs=len({u for u in f if "/docs/" in u})
        priv=sum(1 for t,p in S.HITS if p.startswith("/private/"))
        times=sorted(t for t,p in S.HITS if p!="/robots.txt"); gaps=[b-a for a,b in zip(times,times[1:])]
        print(name); print("  fetched %d | distinct docs %d of 40 | calendar-trap pages %d | /private/ requests %d | redirects followed via frontier %d | duplicate content %d | %s"%(
              st["fetched"],docs,cal,priv,st["redirects"],st["duplicate content"],"stopped by the hard stop" if st["fetched"]>=200 else "frontier emptied by itself"))
        print("  %.1f s, %.0f requests/s to the one host, smallest gap between requests %.0f ms (delay asked for: 50 ms)"%(dt,len(times)/dt,1000*min(gaps)))

O teste do filtro de Bloom é a classe Bloom da seção 4, preenchida com 1 000 000 de URLs e testada com 200 000 outras que nunca foram adicionadas; o teste do simhash usa a listagem da seção 8.

Fontes

  1. Allan Heydon e Marc Najork, Mercator: A Scalable, Extensible Web Crawler, World Wide Web, 1999. O frontier com filas de prioridade e filas por host, a verificação de URLs vistas e o projeto modular.
  2. IETF, RFC 3986: Uniform Resource Identifier (URI): Generic Syntax, seção 6 (normalização e comparação).
  3. IETF, RFC 9309: Robots Exclusion Protocol. As regras, o cache e o que fazer quando o robots.txt não pode ser buscado.
  4. Google Search Central, A note on unsupported rules in robots.txt (2019). O post de 2019 nomeia crawl-delay, nofollow e noindex como regras não suportadas no robots.txt.
  5. IETF, RFC 9111: HTTP Caching e RFC 9110: HTTP Semantics (requisições condicionais, ETag, If-Modified-Since, Retry-After).
  6. Moses Charikar, Similarity estimation techniques from rounding algorithms, STOC 2002. A ideia por trás do simhash.
  7. Gurmeet Singh Manku, Arvind Jain e Anish Das Sarma, Detecting near-duplicates for web crawling, WWW 2007. Simhash e distância de Hamming em bilhões de páginas.
  8. Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 1970. O filtro de Bloom.
  9. Sergey Brin e Lawrence Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, 1998. Uma descrição inicial de um grande crawler e da importância baseada em links.
  10. Sitemaps.org, The Sitemaps protocol. Listar URLs e lastmod para crawlers.

Pratique este tema: System Design System Design › Case studies

Mais guias